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:
Aug 9, 2009
The question was the following. I'm rephrasing the question to make it clear for everyone to understand: - You are going on a one-way flight trip that includes billions of layovers. - You have 1 ticket for each part of your trip (i.e: if your trip is from city A to city C with a layover in city B, then you will have 1 flight ticket from city A to city B, and 1 flight ticket from city B to city C. - Each layover is unique. You are not stopping twice in the same city. - You forgot the original departure city. - You forgot the final destination city. - All the tickets you have are randomly sorted. Question are: - Design an algorithm to reconstruct your trip with minimum complexity. - How would you improve your algorithm. Example: - randomly sorted: New York->London San Francisco-> Hong Kong Paris->New York London->San Francisco - sorted: Paris->New York New York->London London->San Francisco San Francisco-> Hong Kong
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (8)
Nov 7, 2009
Represented it as a direct graph, the number of nodes are N+1, the number of edges are N,
topological sorted, Time = O(N)
topological sorted, Time = O(N)
Helpful Answer?
Yes |
No
Inappropriate?
Nov 21, 2009
Represented as a directed graph.
Start from node without any entering edge O(n) and follow the path O(n).
Start from node without any entering edge O(n) and follow the path O(n).
Helpful Answer?
Yes |
No
Inappropriate?
Nov 27, 2009
Hmm, I implemented this graph using a Hashtable :
Note that this solution will only work for unique layovers...
The starting cities are the keys, and the ending cities are the values
Note that this solution will only work for unique layovers...
The starting cities are the keys, and the ending cities are the values
Helpful Answer?
Yes |
No
Inappropriate?
Nov 27, 2009
I forgot to finish my answer:
loop through all the entries {
add the start->end pairs in there (checking to see if the start doesn't already exist) and an empty entry for the end city (again, only if it doesn't already exist). In the case that you add a start->end entry, the start becomes your global start.
}
Then just follow the white rabbit from the global start at the end to get your list :)
If I've screwed up somewhere please let me know, thanks!
loop through all the entries {
add the start->end pairs in there (checking to see if the start doesn't already exist) and an empty entry for the end city (again, only if it doesn't already exist). In the case that you add a start->end entry, the start becomes your global start.
}
Then just follow the white rabbit from the global start at the end to get your list :)
If I've screwed up somewhere please let me know, thanks!
Helpful Answer?
Yes |
No
Inappropriate?
Feb 4, 2010
I think its simpler than that. Just count all of the cities on the tickets. The original departure and final location city will appear once (assuming unique layovers, an odd number of times with non-uniqueness) this is O(n).
Then, follow the path, which I think is O(n^2) because you have to check the remaining remaining tickets each time.
Then, follow the path, which I think is O(n^2) because you have to check the remaining remaining tickets each time.
Helpful Answer?
Yes |
No
Inappropriate?
Feb 17, 2010
none of these will work for billions of layovers. you can not load billions of layovers into memory.
Helpful Answer?
Yes |
No
Inappropriate?
Dec 4, 2011
Benquan Yu, yes but to reconstruct the whole path we'll always need O(N) memory, either RAM memory or disk space.
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 neakor:
1. Select a ticket from the pool of tickets that is different from all the previously selected starting tickets.
2. Keep a count on how many tickets you have used.
3. Keep walking on the ticket path until you exhaust all possible paths without going back. Increment count every time a ticket is used.
4. If the final count equals the total number of tickets you have, you've got the path sorted.
5. Otherwise, repeat from step 1.
Can be improved via parallelization where you can shoot off multiple threads each having its own starting ticket in parallel. Whenever a thread completes the sorting based on step 4, stop all other threads.