Google Interview Question
Software Engineer / DevelopersCountry: Russia
Interview Type: Phone Interview
Don't really understand the question. What is the definition of a substring here?
In "Grass is green". "green" is obviously a substring, but is "rag" a valid one?("r", "a", "g" appear in that order but are not consecutive).
So the question is asking to find a substring that isn't in the file? Substring of what? Just any smallest permutation of 8 bit chars that doesn't appear in the file?
Assuming each byte is a character of the string (so basically 256 characters possible).
- _anonymous September 22, 2012Create a suffix tree and find the node closest to the root which does not have 256 children.