Software Engineer Interview Sunnyvale, CA

NetAppAnswer## 1. Given a binary tree, find the path from leaf node to

leaf node such that the values of nodes in between are the maximum. The interviewer was interested more the maximum sum than the path itself. 2. Write/describe algorithm to re-sort a rotated sorted array with O(1) complexity. 3. Given an array of integers design an algorithm to return the sum of all integers in a given range with O(1) complexity. So, sum(i1, i2) returns sum of all integers i1 - i2. No for() loops. Now, how would you do it if the array were 2 dimensional? 4. Merge 2 link lists. So, if the linked lists are L1 and L2, the resultant list will be L1->next = L2, L2->next = L1(original)->next; ... They may not have the same number of elements.

1 Answer

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

1. The interviewer did not specify the goal precisely at the beginning, so I wound up returning maximum sub-tree instead.

2. Used binary search to detect index of min number and then shift it. This doesn't do it in O(1) though. What I did seemed to be acceptable though.

3. Pre-compute sum and save sums in second array, so the look up reads the sum directly. 2XO(1). Couldn't do the second part.

4. Couldn't do it in time.