interview questions shared by candidates
Recently I attended the interview at Google and I was asked "You are given a sorted list of disjoint intervals and an interval, e.g. [(1, 5), (10, 15), (20, 25)] and (12, 27). Your task is to merge them into a sorted list of disjoint intervals: [(1, 5), (10, 27)]."
You can use line-sweep algorithm for that.
First you need to sort the pairs according to their starts. Then we compare each two first pair together if they have intersection or not. if the end of the first pair is greater or equal to beginning of the second pair then they have intersection and it is obviously : start = min(start_first pair, start_second pair), end= max(end_first pair, end_second pair); this new pair will be compared with the next pair.. till the end. if there is not an intersection we leave it az an interval. We can use queue to hold the pairs
The interviewer started with some small talk. Talked a little bit about my research work. Then went on with technical questions. Openned terminal on his computer. First he asked about if I know anything about zombie process. Then he asked about ‘malloc’. Then he told me, how would I implement a malloc like function in a separate memory space like some PCI connected to the main memory. The question was not very clear to me. I tried to explain how I could implement that memory over the extra connected memory. I am not sure if he was very happy about it. Then he went onto his terminal. A C program was there. Just two lines char* str1 = “string1”; char str2 = “string2”; He told me to print the two strings. I did and then he told me to change the ‘t’ in both of the string to ‘T’. I told him that we cannot change the first string. He asked me why? I could not tell it clearly. I just showed him that, it generates a segmentation fault. I told it might be in some place in the memory which we cannot edit. He kept asking the question to prove my point. Then gave me hint and let me print the addresses of main, some variables which have higher value sounded like they are in the stack part. Printing the values of main showed very low address which shows that, it’s in the code segment. The char* variable was in a little more higher address which clearly shows that, it is in the data segment, which suggests that we can not edit anything on the data segment. So need to know what’s more there in the data segment? Then he showed some networking terms ip ipconfig ping some more (around 6-7) which I forgot. He told me to explain in short what these functions do. Then he asked me to write a script on python, which will read a file and add all the numbers on the third column. He showed me the file with cat command. It as a space separated text like 1 7 8 9 6 5 5 0 8 8 4 5 7 2 4 6 8 9 0 7 4 5 1 7 9 6 0 3 8 0 1 7 8 9 4 6 8 0 8 6 9 8 6 9 7 0 7 6 4 0 1 2 3 4 5 6 7 8 4 5 6 7 8 9 1 0 1 3 4 8 3 5 1 7 8 9 4 6 8 0 8 6 9 8 6 9 Then he gave me a problem on linked list. The problem was to delete all the nodes with a particular number on it. I just needed to write the main function and call that from the main file. The structure and main file was already written. I just needed to add the function prototype to the *.h file.
The guy asked me if I know what the quality means. His example of quality was super-expensive designer bags that his girlfriend impulse-buys on the internet. No, that is NOT a joke. He was visibly not interested in the whole process, I could tell. Not a single technical question, and his answers to mine were vague. My guess is he is a lousy programmer, even though he doesn't have to be one to do his job.