# Computer scientist Interview Questions

# 253

Computer Scientist interview questions shared by candidates### What thing about yourself other than experience and grades would make you a better candidate than the other people?

4 Answers↳

The two answers above suck. Don't say them if you get an interview.

↳

This looks so good: bit.ly/faang100

↳

i believe in work not in words

### 1. 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. 101-1=> 101 => it's a 5 which is not divisible by 3.

4 Answers↳

Keep dividing while storing stream e.g - 10101-1 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 Less

↳

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. Less

↳

Question 2 is damn easy and can be done in o(1) space complexity:- This is basically a conversion of base-2 to decimal base-10 . 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 + Less

### Partition an array such that all non-zero values are at the beginning.

4 Answers↳

By i++ and j++, I think you mean —

↳

This is an interesting read: bit.ly/faang100

↳

int j = numbers1.length-1; for(int i=0;i!=j;i++){ while(numbers1[j] == 0) { j--; } if(i==j)break; if(numbers1[i] == 0){ numbers1[i] = numbers1[j]; numbers1[j] = 0; j--; } } return numbers1; Less

### Desgin a search system for a document search.

3 Answers↳

Use Trie data structure or any graph based representation.

↳

take a map with string and vector in cpp, and store positions of a particular element in vector, the best part vector will be sorted. Less

↳

take a map with string and vector in cpp, and store positions of a particular element in vector, the best part vector will be sorted. Less

### First face to face round went OK. The interviewer asked about a matrix with dynamic programming algorithm and psuedo code for it. Also asked about explaining basics of technologies mentioned in the resume. I think I did justice with explaining what I knew, and from his expressions, I could not understand whether he was satisfied or not interested to listen :). No cross questions, not asking for details, just kept writing the feedback on his computer after asking. Second face to face round had two questions. One was algorithm for a tree traversal problem and proper code for it along with corner cases. Second question was a low level design problem.

2 Answers↳

I discussed the approach and wrote code for it. There was one mistake in the code which I corrected and provided proper code and he was satisfied with it. The low level design question - which was not explained well (or may be I could not understand) - and I gave a reflection based answer (which seemed to be the only way to solve what I understood). Later on after some clarifications, I came up with 2 more approaches, but probably he was not satisfied with it and insisted on making it better, without explaining problems in design I proposed. I think he had something in mind, and he wanted me to read his mind and come up with the same solution, which I could not. After the interview I googled for it and I feel my solution was quite close (like 80% close) to a highly rated stackoverflow answer. After this round I was told to leave :). Less

↳

Can you please share what was the low level design question that he asked you ?

### How would you find a needle in a haystack (or for example a specific 20 byte string in files that are recursively archived/zipped to three levels) and let's say you can't find how to do this by researching the net?

1 Answers↳

There is no correct answer and the interviewer is just trying to assert his mental superiority. Less

### On the CMM scale of 1 to 5 what is the level you prefer to work at?

1 Answers↳

The correct answer is a negative number.

### Programming Question: Maximum Product Sub array of size k (Better time complexity solution expected) Interview questions: Sort an infinite array, String rotated by k times, OOPs concepts(Polymorphism,Encapsulation), Next smallest palindrome greater than given no.

1 Answers↳

is it a typo ? should oit be Search an Infinite array ?