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)
14 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
Hi, well be sensible, well-all described
This is really interesting because I've never had an interview like that before, I'd like to know how to solve it easier in order to learn the technique just in case taking a interview like that.m10m
Thanks for sharing such an interesting post with us. You have made some valuable points which are very useful for all readers
Post a Comment