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 Intern at Google:
Aug 13, 2011
Given an array of numbers, there is one number that has a duplicate. How would you find the number?
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (4)
Oct 1, 2011
Better than a hash table, which uses oodles of RAM, you could sort the array in NlogN time, and then all of your duplicates would be clustered together. Then you can traverse the array in N time and you can say something like
if previous index == current index
return index.
if previous index == current index
return index.
Helpful Answer?
Yes |
No
Inappropriate?
Oct 2, 2011
But in terms of looking for only ONE duplicate, and not care about RAM but runtime, the hash table is the way to go. It would be O(n) only.
Helpful Answer?
Yes |
No
Inappropriate?
Feb 6, 2012
If you are looking for a minimal ram
you can sort in nLog(n) time and in the sort, if you see two numbers that are equal, just save that number and return just that number. pure nlogn optimal
you can sort in nLog(n) time and in the sort, if you see two numbers that are equal, just save that number and return just that number. pure nlogn optimal
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 Intern Interview Questions, Google Interview
1 of 1 people found this helpful
by Interview Candidate: