Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,069 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:
Sep 28, 2009
Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (4)
Nov 27, 2009
To respond to Sid's comment:
Binary search is the way to go, but you do need a slight modification, coz a simple binary search may not necessarily return the index of the first occurence, e.g. given input array
7777777777, what would a simple search return?
The trick would be to seek to the left if the index at the middle of the current partition is the element you are looking for.
The performance would depend on how many duplicates there are on average + log n
If this average is n as in the above example you are looking at O(n/2), but then if you knew that already you could simply return the first element :)
Anyone have a better idea?
Binary search is the way to go, but you do need a slight modification, coz a simple binary search may not necessarily return the index of the first occurence, e.g. given input array
7777777777, what would a simple search return?
The trick would be to seek to the left if the index at the middle of the current partition is the element you are looking for.
The performance would depend on how many duplicates there are on average + log n
If this average is n as in the above example you are looking at O(n/2), but then if you knew that already you could simply return the first element :)
Anyone have a better idea?
Helpful Answer?
Yes |
No
Inappropriate?
Apr 24, 2010
binary search for target.-1. At the last step remember where you were checking even if you don't find it. If the element is target this is the first one. Otherwise it is in the next index of the array.
Helpful Answer?
Yes |
No
Inappropriate?
Apr 24, 2010
*I left out an important part. You need to modify the binary search for the case that there's more than one instance of target-1. If you are at a node that matches your search and the right and the item at the next index also matches, move to the right child and continue searching.
Helpful Answer?
Yes |
No
Inappropriate?
Members can
answer or comment on this question
–
Join Now (It's Free) or
Sign In
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
0 of 0 people found this helpful
by Sid: