Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
May 2, 2010
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (5)
Oct 17, 2010
Not sure how the previous comment's method would find the shortest... I would scan the string once, counting the # of occurrences of each of the desired chars. Then I would start two pointers at each end of the string and march them inward element by element, decrementing the corresponding char count if the pointer pass over one of the chars in the set. As soon as one of the counts hits zero for a pointer, say the left one, I know that is the left limit of the smallest substring. Ditto for the right. Overall O(n) algorithm.
Helpful Answer?
Yes |
No
Inappropriate?
Jan 2, 2011
That doesn't quite work either. Your method finds the first string such that: its first character does not occur anywhere to its left. But this is not guaranteed to be the shortest.
Helpful Answer?
Yes |
No
Inappropriate?
2 of 2 people found this helpful
Jan 2, 2011
If you approach this the simplest way:
For all substrings, test it to see if it has all the characters. For those that pass, take the shortest. There are O(n^2) substrings, and the test takes O(n) time, so we have O(n^3).
However, we are doing some work over and over. I.e. some substrings are tested, and then retested as parts of other substrings. If we avoid this duplication, we can get down to O(n^2). I'm guessing that's the best we can do.
For all substrings, test it to see if it has all the characters. For those that pass, take the shortest. There are O(n^2) substrings, and the test takes O(n) time, so we have O(n^3).
However, we are doing some work over and over. I.e. some substrings are tested, and then retested as parts of other substrings. If we avoid this duplication, we can get down to O(n^2). I'm guessing that's the best we can do.
Helpful Answer?
Yes |
No
Inappropriate?
0 of 2 people found this helpful
Apr 20, 2011
Let the string to searched be A. Let the set we want to find be S.
Find beg, the first position in A such that A[beg] is in S. Find the smallest value named end such that A[beg], ..., A[end] has all the characters in S. The length of the substring found so far is end - beg + 1 (assuming this operation succeeded).
Increment beg until A[beg] is again in S. Increment end until we again have in the substring all characters in S (we just need to get back the character we lost when we incremented beg). We found another solution.
Keep on incrementing beg and end. Keep track of the shortest solution.
Overall it is an O(n) algorithm. An actual implementation needs to take into account what data structures to use to hold the needed data.
Find beg, the first position in A such that A[beg] is in S. Find the smallest value named end such that A[beg], ..., A[end] has all the characters in S. The length of the substring found so far is end - beg + 1 (assuming this operation succeeded).
Increment beg until A[beg] is again in S. Increment end until we again have in the substring all characters in S (we just need to get back the character we lost when we incremented beg). We found another solution.
Keep on incrementing beg and end. Keep track of the shortest solution.
Overall it is an O(n) algorithm. An actual implementation needs to take into account what data structures to use to hold the needed data.
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
0 of 0 people found this helpful
by somebody: