truongkhanh
BAN USER- 0of 0 votes
AnswersThis is the screening question from Dropbox. I see it appear in other topics as the question in the interview. However I did not find a complete solution so I put my discussion here (http://www.capacode.com/?p=447) for your reference.
- truongkhanh in United States
Question: Given a pattern and a string, check whether the string matches the pattern. For example: pattern "aba" and the string is "redblackred" then it matches because "a" is translated to red and "b" is translated to "black". Note that for each character in the pattern, the translation is not empty and unique.| Report Duplicate | Flag | PURGE
Dropbox Software Engineer Algorithm
Try to count the number of solutions. Wiki has the number of solutions for N <20
- truongkhanh April 09, 2015nice solution. Using 4 arrays makes the "safe" checking in O(1). If the checking is O(N), I'm sure it is not possible to solve N=15
- truongkhanh April 09, 2015Assume L is the length of the string and P is the length of the pattern. Then, we can try to split the string in P substrings and verify the translation. So the size of the problem is C(L, P) ~ L^P.
More precisely, for each character in the pattern, if it already appears earlier, checking is O(L). So we only need to care the unique characters. Assume there are k unique character in the pattern. For each new character, there is maximum L candidates for its translation. Therefore, the complexity is F(P) = L^k.
It should be F(P) = L^k
- truongkhanh March 03, 2015I think the code is correct. I only have some minor suggestions. You should not name the function as "foo". Try to make the function name meaning.
In your program, whenever you call recursive foo(), you create new String. This is not memory efficient. You should update the start index for each string.
The code is nice. However, it is not efficient when the character in the pattern already has the translation. For example, if the translation of the current character is "red", then the suffix from "index" must start with "red". Otherwise, return invalid.
- truongkhanh March 03, 2015I think using array is a good suggestion. However, if we use 2-D array as yours, it is error-prone because you need to make sure arr[i] have the same length. Instead, why don't you use array of String.
- truongkhanh March 03, 2015
n & (n – 1) == 0 //include 0
- truongkhanh February 25, 2016n & !(n & (n – 1))