A friend of mine was interview for a position in Google, he got this hard question asked:
"You have a list of numbers which some of them are negative and some of them are positive, find out the largest sum of sequential subset of numbers from this list."
For example:
-5, 20, -4, 10, -18
The solution is the subset [20, -4, 10] which its sum is 26
The solution for this question is not summary the positive numbers or sort the list because the subset needs to be sequential.
A possible not efficient answer would be to to calculate the summary of all the possible subsets in the list but the complexity of this solution is O(N^2)
However the interviewer wanted a solution of O(N) !!!
Let see you solve this problem in few minutes...
In the next post I would publish the solution
Sunday, December 16, 2007
Google Interview Questions Part 1
Subscribe to:
Post Comments (Atom)
Links
11 comments:
Run through the list but with two additional varaibles: Sum and int array where Sum is used to compare and hold max sum and int array is our solution :)
You can found the complete solution on this post:
google interview questions part 2
That's the tipical kind of problem you forget how to solve when you work for years using high level frameworks (in any language); in my career I have never seen a case where a problem of this complexity had to be solved.
I think I'll have to change the way I work or I'll become even dumber in the years to come!
that is just retarded, i heard about google dumb interviews, but this one is the best.
P.S. if they were smart they would ask about advance math. I just wonder what stupid biology questions they have, where is the liver? make it harder damn it, ask about small bones.
Any subset is a substring of the original string (thinking of a subarray as a substring)...
To find any substring, first find the start of the subtring and then the end.
When trying to find the start: When you hit a negative number, discard the substring.
Then find the ending (you need to reach the end of the string to know where it should end).
This problem is pretty hard, I think, but it can be done in O(n) because whenever the total of the substring you are calculating is > 1, then it "pays" to add to other strings. The problem is how to divide the search...
I think the question is okay. From my experience, the smartest programmers will focus some of the interview time on asking such questions, typically around 15% of the time, while dumbest programmers will focus nearly 100%of their questions on them.
The solution is to buy the book "Programming Pearls" by Jon Bentley and read the answer there; it contains a comprehensive and interesting treatment of this problem.
This problem is explained well in "Programming Pearls" by John Bentley. He gives 4 different solutions to it with asymptotic complexity of O(n3), O(n2), O(nlogn) and O(n).
You can view the O(n) solution in Python at http://www.harvestmanontheweb.com/programs/google/sumlist.py
You can view the solution here
Some more interviews
Interview At Google
Google Top Interview Questions ( around 30 With Solutions)
Google Interview for Freshers
Some more google interviews
Interview At Google
Google Top Interview Questions ( around 30 With Solutions)
Google Interview for Freshers
Post a Comment