Amazon Interview Question: The most difficult question w... | Glassdoor

Interview Question

Software Development Engineer II Interview Seattle, WA

The most difficult question was to find the maximum

  contiguous subsequence in a bar chart. I was able to find a solution in O(N^3) which is basically the brute force method The idea is that given a bar chart with peaks and valley's, you should find the subsequence X which gives you the maximum area underneath the chart. For the life of me I couldn't think of the answer at the time, , I had a hard time visualizing it, however it's a classical computer science problem called "the maximum sum contiguous subsequence problem."

Add Answers or Comments

To comment on this, Sign In or Sign Up.