NetApp Interview Question: 1. Given a binary tree, find ... | Glassdoor

Interview Question

Software Engineer Interview Sunnyvale, CA

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.

Interview Answer

1 Answer


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.

Interview Candidate on Jun 2, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.