Technical Interview Questions

Software Engineer, Google Fiber at Google was asked...

Sep. 12, 2012

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)]."

9 Answers

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

Show more responses

google_interview = ( [(1, 5), (10, 15), (20, 25) ], (12,27) ) just_insert = ( [(1, 5), (10, 15), (20, 25), (80,89)], (17, 18) ) join_case = ( [(1, 5), (10, 15), (20, 25), (80,89)], (12, 22) ) empty_case = ( [], (1,10) ) def merge(orig,anew): """ If the input items are sorted, and interval is a 2-tuple, create a new list of intervals, such that we join together any overlapping intervals into a single tuple describing the combined range of the two or three tuples that could collide when we merge another interval into a list""" newlist = [] if len(orig)==0: return [anew] n = 0 # get items that are before the join while norig[n][0]: middleitem[0] = orig[n][0] if n=orig[n+1][0] and middleitem[1] middleitem[1]: # print "break",orig[n] break if orig[n][1] > middleitem[1]: # print "extend" middleitem[1] = orig[n][1] # print "skip",orig[n] n = n + 1 # now append remaining items newlist = newlist + [tuple(middleitem)] newlist += orig[n:] return newlist def test(tup): print 'merge( '+repr(tup[0])+', '+ repr(tup[1])+ ' )' print ' -> ', merge(tup[0], tup[1] ) print ' ' print "Test begin" test( google_interview ) test( just_insert ) test( join_case ) test( empty_case ) print "Test end"

n*lgn sorted by lower bound and gogogo scan once.

JAVA CODE: import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; /** * Created by admin on 3/2/16. */ class Interval { int start; int end; Interval() {start = 0;end =0;} Interval(int s, int e) { start = s; end = e; } } public class Solution { public List insert(List intervals, Interval newInterval) { ArrayList result = new ArrayList(); intervals.add(newInterval); return merge(intervals); } public List merge(List intervals) { ArrayList result = new ArrayList(); if (intervals == null || intervals.size() == 0) { return result; } Collections.sort(intervals, new Comparator() { public int compare(Interval a, Interval b) { return a.start - b.start; } }); for (int i=0;i= intervals.get(i+1).start) { current.end = Math.max(current.end, intervals.get(i+1).end); i++; } result.add(current); } return result; } } Time Complexity: nlgn + n = O(nlgn)

int[] mergeDisjointIntervals(int[] intervals, int[] range){ ArrayList result = new ArrayList(); for(int i=0;irange[0]&&high is inside return 0; } else if(lowrange[0]&&high overlaps tail return -1; } else if(low>range[0]&&lowrange[1]){ // 1 -> overlaps head return 1; } else{ // 2 -> does not overlap return 2; } }

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Supply Chain Analyst at Apotex was asked...

May 21, 2015

What is your 30, 60, 90-day plan if you receive the offer?

7 Answers

Senior Software Engineer at Amazon was asked...

Aug. 16, 2012

Write a function that divides one number by another, without using the division operator, and make it better than O(n).

7 Answers

Manufacturing Development(III) at Coca-Cola Canada Bottling was asked...

Jul. 31, 2019

Why did you apply to work at Coca-Cola?

5 Answers

Software Developer at Arista Networks was asked...

Sep. 13, 2015

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.

4 Answers

char *str1 = "string1". This is called a string literal and is stored usually in a read-only section of the program. It cannot be modified. The pointer str1 can only be used to read-only access the string literal, but cannot modify the contents of it. It is just like defining that pointer as "const char * str1".

I remember the other terms that were asked: wireshark, traceroute, tcpdump, netstat. Also, what was the answer to implementing malloc in another memory space?

I don't know why I wasn't more prepared for the malloc question since I read it here before the interview. In any case, I just took it a step at a time starting from the most naive (i.e. leaky) implementation and improving it through some guidance from the interviewer. What we finally settled on was describing chunks of memory with the following data structure: struct chunk { void *start; size_t size; }; There are two binary search tress containing this structure at each node: one for free memory and one for allocated memory. The keys of the free tree are size, the keys of the allocated tree are start. At the start of the program, the allocated tree is empty, and the free tree contains one node describing the entire available memory. When malloc is called it searches through the free tree to find the first chunk larger than the requested amount. If that chunk is larger than the requested amount, split it into the requested amount and the remainder. Put the requested chunk in the allocated tree and return the pointer to it's start member. Put the remainder back into appropriate place in the free tree. When free is called, search through the allocated tree to find the appropriate chunk and place it back in the free tree. The main limitation of this is that it causes fragmentation. Firstly, you end up with a bunch of small remainder chunks floating around. Secondly, over time, the size of chunks in the free tree gets smaller and smaller until eventually there is no chunk large enough for a particular request. Some of these chunks will obviously be contiguous, but since the free tree is keyed on the size, not the location, it will be expensive to "clean it up" by finding contiguous chunks.

Show more responses

IT Business Analyst at eHealth Ontario was asked...

Jun. 19, 2015

15 minute technical written test around various computing technologies. How would you prioritize your work load? How do you keep up with technology? Why do you think we should hire you?

4 Answers

QA Analyst at KUBRA was asked...

Feb. 1, 2014

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.

4 Answers