NetApp Interview Question
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
Anonymous
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.