Dropbox Interview Question
Question was "Given a pattern and a string input - find if the string follows the same pattern and return 0 or 1.
Examples:
1) Pattern : "abba", input: "redblueredblue" should return 1.
2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.
I saw someone else had a similar question, but it was much much easier as the other candidate was given spaces between words to help identify individual words to pattern match.
Interview Answers
How come Pattern : "abba", input: "redblueredblue" should return 1 ? Was this a typo?
Is there any additional information about the pattern or the string? For example, the length of the pattern or if the pattern contains only "a" and "b", or it can be like "aabcdbbeefa"?
There was no additional information about the pattern or string. You are not given the length of the pattern or what letters the patterns contain.
def isPattern(mystr, pattern, matches):
if len(pattern) == 1:
print("%s %s"%(pattern, mystr))
if pattern not in matches or matches[pattern] == mystr:
matches[pattern] = mystr
return True
return False
maxMatchLen = len(mystr) - len(pattern) + 1
for i in range(1,maxMatchLen+1):
proposedMatch = mystr[:i]
if pattern[0] in matches and matches[pattern[0]] != proposedMatch:
continue
matches[pattern[0]] = proposedMatch
ret = isPattern(mystr[i:], pattern[1:], matches)
if ret == True:
return True
if pattern[0] in matches:
del matches[pattern[0]]
return False
def main():
mystr = 'redblueredblue'
pattern = 'abab'
print("%s - %s - %s"%(mystr, pattern, isPattern(mystr, pattern, {})))
main()
def isPattern(mystr, pattern, matches):
if len(pattern) == 1:
if pattern not in matches or matches[pattern] == mystr:
matches[pattern] = mystr
return True
return False
maxMatchLen = len(mystr) - len(pattern) + 1
for i in range(1,maxMatchLen+1):
proposedMatch = mystr[:i]
if pattern[0] in matches and matches[pattern[0]] != proposedMatch:
continue
matches[pattern[0]] = proposedMatch
ret = isPattern(mystr[i:], pattern[1:], matches)
if ret == True:
return True
if pattern[0] in matches:
del matches[pattern[0]]
return False
def main():
mystr = 'redblueredblue'
pattern = 'abab'
print("%s - %s - %s"%(mystr, pattern, isPattern(mystr, pattern, {})))
main()
seems the editor doesnt support formatting :(
Umm ... This is a standard hackerrank question that drop box asks everyone to attempt when you submit your resume, through their website. Don't feel cheated.
1. get length of pattern as patLen
2. get length of string as strLen
3. if (strLen%patLen)!=0 -> return false
4. subStrLen=strLen/patLen
5. make a hashmap -> Map
6. Read patternString one char a time as currentChar. If char not in hashmap, insert key value pair -> key as curentChar and value has substring from actual string (as per subStrLen in step 4)
7. if currentChar exist in map, check if value is same as subSTring (as per subStrLen in step 4) .if not return false
8. go back to step 6