Question

GoldMan Sachs | Recent Interview Experiences | Coderpad | SDE | Set-29

Answer 1

I was asked this question in recent De Shaw interview for entry level software developer.

 

You are given k number of groups having unequal ranges :-
g1 - 0 - 10
g2 - 11 -15
g3 - 16-22
g4 - 23-34

 

and a sequence of numbers. You have to find the length of minimum window containing element from every group. I had to do this without using map.

 

for eg. 9, 5, 3, 12, 17, 25, 27
Ans - 4

 

Another Question that was asked :

 

You are given a binary tree. You have to find an AP series in tree such that no two nodes are consecutive and distance between 2 node (i.e. no. of nodes between the 2 nodes) should be from 1-3 (there can be one node, two node or three node) between consecutive terms of AP series. I had to find the length of longest AP series.

 

• You cannot revisit the node once you traverse the node. For eg 1 -> 2-> 5 -> 4 -> 3. 1, 3, 5 is not a valid sequence for the above binary tree.

 

I was not able to solve the question.

Answer 2

First question : https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/
Second question : complicated approach
Every node will get an triple nested {arr1[][], arr2[][], arr3[][]} from left and right
arr1 = list( val, diff, len) ,i.e. array of 3 data points (value of node, AP diff, AP len)
Node will try to compute max length for the 3 cases
res = max(res, left->list1[diff] + right->list1[-diff] + 1) if current node can extend an diff

Node will return max of either right +1, or left +1 for every diff it can extend for the 3 categories
return {{left->val, INT_MIN, 0}, {right->val, INT_MIN, 0} max values from arr1, max values from arr2}