Interview Question
Computer Scientist Interview

Adobe1. Given an empty BST consist of n nodes and and an array consist of n numbers. The n nodes in a BST have been already arranged in some fashion(i.e. the BST is not empty), and none of the nodes in BST are having any data, that means we have to pick the n numbers from the given array and have to fill in the given BST. We have to make sure that the structure of the BST doesn't change. That means all the left subtree and right subtree at any given node should not change at all. 2. We have a function which returns a value among {1, 0, 1}. When the function returns 1 that means we have to terminate. we have to keep on calling this function and till we get 1. this means we will get series of 1's and 0's which we have to treat like bit pattern and has to check whether the given number is divisible by 3 or not. for e.g. the function call returns the below output. 1011=> 101 => it's a 5 which is not divisible by 3.
Interview Answers
4 Answers
Keep dividing while storing stream e.g  101011 will be like 1 > 1 0 > 10 1 > 101(5) divided and remain 10 0 > 100 (4) divided and remain 1 1 > 11(3) divided and remain 0
Ankur Dattatrey on
I have answered the second question saying that we can keep storing the 1's and 0's in a vector and the moment we hit 1, we will reverse iterate the vector and can get the integer number out of the bit stream and can see whether %3 is zero or not. he told me to optimize the program in terms of space and time complexity. I told we can compress the bit stream in such a way so that when we have continuous 1's and 0's can be replaced by only single 1's and 0's. He was not satisfied with the answer.
Anonymous on
Question 2 is damn easy and can be done in o(1) space complexity: This is basically a conversion of base2 to decimal base10 . int finalNum = 0; keep reading the val of (1's and 0's till we hit 1), for each received input, follow the below logic. finalNum = 2 * finalNum +
Anonymous on
For Question1 : Traverse BST in inorder store into node array. Sort integer array given. Now iterate both array simultaneously & update node value with the value at same index in integer array.
mayank pesswani on