Software Engineering Intern Interview Questions in San Jose, CA | Glassdoor

# Software Engineering Intern Interview Questions in San Jose, CA

154

Software engineering intern interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

### Software Engineering Intern at Google was asked...

Oct 14, 2011
 how would you find the shortest path between two nodes in a social network? 7 Answersdo breadth first search from both ends at the same time. Keep a set of all nodes that each has reached. When the sets have any element in common, there is a path.Does the above method have any advantage over the method in which we do bfs from one node of the nodes and stop when the other node is reached?BFS from both sides is massively faster than just doing BFS from one. Suppose each person has k friends and that the two nodes are d apart. BFS from one node is O(k^d). BFS from both nodes is O(k^(d/2)) -- the exponent is half as big. To put some example numbers on it, if each person has 100 friends and they are 10 apart, then BFS from one node takes 10^20 operations, whereas BFS from both nodes is 2*100^5= 200 billion operations. BFS from one node is intractable. BFS from both nodes is slow, but tractable.Show More ResponsesHow about using Dijkstra's shortest path algorithm? Isn't that more efficient than a bfs?If you only care about the distance between two nodes and every edge length is 1 (both of which are true in this problem), then Dijkstra's shortest path algorithm basically is breadth first search (and BFS from both sides is faster than a simple BFS). If that doesn't make sense, then explain how http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode is different from a breadth first search in this case and I will clarify.Aren't you ignoring the time taken for checking for a common element in the two sets (which will be O(k^d))?Checking for set inclusion is constant time (assuming a reasonable hashset). Thus, it is O(1) to know whether or not a node that I add to one side's fringe is already in the other side's fringe. Does that make sense?

### Software Engineer Intern at Facebook was asked...

Sep 21, 2011
 Generate a new array from an array of numbers. Start from the beginning. Put the number of some number first, and then that number. For example, from array 1, 1, 2, 3, 3, 1 You should get 2, 1, 1, 2, 2, 3, 1, 1 Write a program to solve this problem.7 Answersint[] Reformat(int[] original, int length) { LinkedList list = new LinkedList(); int currentCount; for(int i=0;ifunction numberArray( \$arr ){ \$a = array(); \$number = null; \$c = -1; foreach( \$arr as \$v ){ if( \$v != \$number ){ if( \$number ){ \$a[] = \$c; \$a[] = \$number; } \$number = \$v; \$c = 1; } else { ++\$c; } } if( \$c > 0 ){ \$a[] = \$c; \$a[] = \$number; } return \$a; } var_export( numberArray( array( 1,1,2,3,3,1 ) ) );\$val) { echo \$val . "\t"; } echo " \n"; } ?>Show More Responsesworking in php: sizeof(\$list)-2) || (\$list[\$i]!=\$list[\$i+1])){ \$result[]=\$count; for(\$j=0;\$jvector reformat(int arr[], int size) { vector res; int j, count = 0; for(int i = 0; i < size; ) { cout << i << endl; count = 0; for(j = i; j < size; j++) { if(arr[j] != arr[i]) break; count++; } res.push_back(count); res.push_back(arr[i]); i = j; } return res; }int i=0; int j=1; ArrayList array=new ArrayList(); while(i@Anonymous: Your inner while loop will cause an out-of-bounds exception to be thrown when your scanning hits the end of the array. Your while loop will try to access givenArr[i+j] even when j increments to the point that surpasses the length of the array. You need while((i+j) != givenArr.length ... )

### Software Engineer Intern at Facebook was asked...

Mar 6, 2011
 Write a function that finds the minimum and maximum values within an unsorted array using divide-and-conquer.6 AnswersThe best I can do in Java: int findMinimum(int[] a, int start, int end){ if (end-start == 0){ return a[end]; } if (end-start == 1){ if (a[end] = 2){ int split = (start+end)/2; int leftLeast = findMinimum(a, start, split); int rightLeast = findMinimum(a, split+1, end); if (leftLeastvoid GetMinMax(int[] array, out int minValue, out int maxValue) { if (array == null || array.Length == 0) throw new ArgumentException("array null or empty."); MinMax minmax = GetMinMax(array, 0, array.Length - 1); minValue = minmax.Min; maxValue = minmax.Max; } MinMax GetMinMax(int[] array, int begin, int end) { if (begin == end) return new MinMax { Min = array[begin], Max = array[begin] }; else if (begin + 1 == end) return new MinMax { Min = Math.Min(array[begin], array[end]), Max = Math.Max(array[begin], array[end]) }; else { int mid = begin + (end - begin) / 2; MinMax left = GetMinMax(array, begin, mid); MinMax right = GetMinMax(array, mid + 1, end); return new MinMax { Min = Math.Min(left.Min, right.Min), Max = Math.Max(left.Max, right.Max) }; } } struct MinMax { public int Min; public int Max; }#include #include void devide_conque(int*, int, int, int*, int*); int main(int argc, char** argv) { int min, max; int i = 0, array_size = (argc - 1); int* array = (int*) malloc(sizeof(int) * (argc - 1)); for (; i rmax ? lmax : rmax; } }Show More Responsespublic static int[] minMax(int[] a) { int[] mm = new int[2]; if (a.length > 0) { mm[0] = a[0]; mm[1] = a[1]; } mm = minMax(a,0,a.length-1); return mm; } public static int[] minMax(int[] a, int low, int high) { int[] temp = new int[2]; if (low+1 < high) { int mid = (low+high)/2; int[] temp1 = minMax(a,low,mid); int[] temp2 = minMax(a,mid+1,high); temp[0] = Math.min(temp1[0],temp2[0]); temp[1] = Math.max(temp1[1],temp2[1]); return temp; } else if (low <= high) { if (a[low] < a[high]) { temp[0] = a[low]; temp[1] = a[high]; } else { temp[0] = a[high]; temp[1] = a[low]; } } return temp; }def find_min_max(arr): return min_max(arr, 0, len(arr)-1, 1e308,-1e308) def min_max(arr, i, j, mn, mx): if not arr or i > j: return mn, mx elif i == j: return min(mn, arr[i]), max(mx,arr[i]) else: mid = ( i + j) / 2 left = min_max(arr, i, mid-1, min(mn, arr[mid]), min(mn, arr[mid])) right = min_max(arr, mid+1, j, min(mn, arr[mid]), max(mx,arr[mid])) return min(left[0], right[0]), max(left[1], right[1])first divide list in two, compare number from each list so we got 1list where the minimum is and second list where maximun is. Search for the min in the first list and the max in the second list. \$list[\$n-1-\$i]){ \$temp = \$list[\$i]; \$list[\$i] = \$list[\$n-1-\$i]; \$list[\$n-1-\$i] = \$temp; } } \$min = \$list[0]; for(\$i=1;\$i\$max) \$max=\$list[\$i]; } \$result = array('min'=>\$min, 'max'=>\$max); return \$result; } ?>

### Software Engineer Intern at eBay was asked...

Jan 19, 2011
 Questions related to data structures like "What data structure would you use for a browser's BACK & FORWARD ability"7 AnswersMay be Stack , any one please correct me if I am wrong.This can be implemented by using two different stacks, one for back and one for forward.Command PatternShow More ResponsesI would use doubly link listDoubly linkedListUse two stacks. Every time you visit a site, push its address in stack1. When you press back, pop from stack1 and also push in stack2. When user presses forward, pop from stack2 and also push in stack1.two stacks. When you visit a site, push its address into stack1 and clear stack2; When you press back, pop the address from stack1 and push the same address into stack2; When you press forward, pop the address from stack2 and push the same address into stack1.

### Software Engineering Summer Intern at Facebook was asked...

Mar 30, 2010
 25 racehorses, no stopwatch. 5 tracks. Figure out the top three fastest horses in the fewest number of races. 11 AnswersWe can do it in seven races, we'll call them races A-F. For notation, we'll say that the Nth horse in race X is called X.N. Races A-E: Divide the horses into 5 groups of 5 each such that each horse races only once. We can eliminate the slowest 2 horses in each of the five races because there are definitely 3 horses faster in each case. As a result, we eliminate 5x2 = 10 horses: {A.4,A.5,B.4,B.5,C.4,C.5,D.4,D.5,E.4,E.5} Race F: Race the fastest horses in each race A-E: {A.1, B.1, C.1, D.1, E.1}. To simplify notation, we'll label F.1 as horse A.1, F.2 as horse B.1, and so forth. That means the winner of this race is A.1, and it is the fastest horse of all. We don't have to race A.1 anymore. We can eliminate D.1 and E.1 = 2 horses. Because they are not in the top 3. As a result, we know that all remaining horses from D and E are eliminated. This is D.2,D.3,E.2,E.3 = 4 horses. We know that A.1,B.1, and B.2 are all faster than B.3 (and similar for C.3) so they are not in the top 3.We can eliminate B.3 and C.3 = 2 horses. Finally, we know that A.1 is faster than B.1, which is faster than C.1, and thus C.2, so we can remove C.2 = 1 horse. Race G: We have removed 19 horses from competition and are sure that A.1 is the fastest horse of them all. This leaves just 5 horses: {A.2,A.3,B.1,B.2,C.1}. We race them and select the top 2 to join A.1 as the top 3 fastest horses.just run them all on the one track :) one race, and you get your 3 fastest horses in one go........or am I missing something!6 races. Divide 25 horses into 5 groups. Each group races and the fastest is selected. The winner of each of the 5 races all race together. Pick Top 1,2 and 3. My only concern: Could the answer be this simple?Show More ResponsesB, you're mistaken. Imagine the top three fastest horses are Santa's Little Helper, Yojimbo, and I'm Number One. By random luck, in your first race, the five random horses you choose includes all three of those. I'm Number One wins and goes on to the final race; the other two do not.8 5 top horses from each race of 5 races (25 / 5) 5 top contenders race; 1 wins--that's one top horse (5-1) 4 remaining top horses race, one wins; that's 2 top horses (4-1) 3 remaining top horses contend; winner is #3 That's 3 top horses from 8 racesRace#1 Race#2 Race#3 Race#4 Race#5 A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Race#6 A1 B1 C1 D1 E1 Let's Say ranking 1st 2nd 3rd 4th 5th Eliminate D1 E1 D2 E2 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Left with B1 C1 A2 B2 C2 A3 B3 C3 Eliminate C3 as there are more than three faster horses C2, C1, B1, A1 Eliminate C2 as there are three faster horses C1, B1, A1 Eliminate B3 as there are three faster horses B2, B1, A1 Left with 5 horses for Race#7 B1 C1 A2 B2 A3 So 7 races7 races. put 25 horses in 5 group. and we will have 5 sorted list of horses in each group. put 1st place horse in each group, and we will have a sorted list X. X_1 is the 1st place horse, and X_2 is 2nd place horse's candidate, X_3 is 3rd place's candidate. 2nd place horse in X_1's group is candidate for 2nd place, 3rd place one is candidate for 3rd place. and 2nd place horse in X_2's group is a candidate for 3rd place. that's 5 horses in total, 2 from X_1's group, 2 from X_2's group, X_3. race them, and 1st place is 2nd place, 2nd place is 3rd place horse.8the answer is one race as the question doesn't specify all the horses have to run in separate races.0 Races. Ask the jockeys to rate the 10 fastest horses and take the average of the top 3. Nobody knows the horses that are fast better than the jockeys. Race results can vary from race to race but the jockeys truly know the fastest and besides because race results vary anyway you will not find the fastest horses with the least races you will find the fastest on that day. Either way your results will not be accurate without a larger dataset. The jockeys however already have a deeper dataset.Better yet find the local bookie for the track and ask for the odds on the horses. Why solve a problem that has already be solved.

### Software Engineer Intern at Twitter was asked...

Mar 31, 2012
 Implement integer division without using / or %. Questions about running time. Can you do it faster?6 AnswersOptimal running time: O(log n)Binary searchHere's an implementation that works -- any ideas on how to make it go faster? public static void divide_without_slash_or_mod(int num, int divisor) { int factor = 0; int remainder = num; System.out.println("Number = " + num + " divisor = " + divisor); while(remainder >= divisor) { remainder -= divisor; factor++; } System.out.println(" remainder = " + remainder + " factor = " + factor ); }Show More ResponsesHere's an implementation that works -- any ideas on how to make it go faster? public static void divide_without_slash_or_mod(int num, int divisor) { int factor = 0; int remainder = num; System.out.println("Number = " + num + " divisor = " + divisor); while(remainder >= divisor) { remainder -= divisor; factor++; } System.out.println(" remainder = " + remainder + " factor = " + factor ); }D(Divisor), N(Divident) low = 0, high = INT_MAX/D while(low N) high = mid - 1; else low = mid + 1; } return -1; //No divisorHere is the Java implementation of implementing division with O(log n) time complexity (actually, this solution is using divide operator). public static void divide(int dividend, int divisor) { int mid, low = 0, high = Integer.MAX_VALUE / divisor; while(low dividend) { high = mid-1; } else { low = mid +1; } } }

### Software Engineer Intern at Motorola Mobility was asked...

Mar 19, 2009
 Write a function in Java that will take a sorted array of ints, possibly with duplicates, and compact the array removing all the duplicate numbers. That is, if the contains the numbers - 1, 3, 7, 7, 8, 9, 9, 9, 10, then when the function returns, the contents should be - 1, 3, 7, 8, 9, 10. Be sure your answer is as efficient as possible. Describe the efficiency of your algorithm using big O notation.5 Answerscreate temp array; starting from the second element copy the i'th char if input[i-1] != input[i] return tempoh efficiency is O(n)you can't create a temp array because you don't know the size until after you process. you could count the number of dupes in one pass, then allocate the array, then do the compacting. or you could allocate the array equal to the size of the original and accept that some elements will be null (or -1, or whatever). or you could use some dynamic data structure like an ArrayList to build the compacted list and convert it to an array at the end (ArrayList.toArray(...)). regardless, it's still O(n) and uses 2x the memory. makes me think there's a more elegant solution though.Show More Responsesdo bitwise XOR of consecutive numbers. When the xor is 0, you know the number is duplicate. It will require single pass thru the array to identify number of duplicates in the array.you can also use 2 index, at the beginning they both = 0, then you will have a previous and a next, if previous value = next value increment next index until next value != previous value then increment previous index by 1 and assign "next value" to it and so forth until you "next index reach the end of the array and then increment all previous index assigning null or -1. O(n) without using 2x memory. Anyway, I hope it is not too confusing, its late but I hope you got the big picture.

### Software Engineering Intern at Palantir Technologies was asked...

Apr 16, 2012
 Say you have a single-column table of entries of variable size. Implement this table to also contain methods to lengthen one cell, cut a cell shorter, and to return which cell we're pointing at if given a certain distance from the beginning of the table. All methods need to be fast (assume a single-column table with many many entries).6 AnswersOne way to do this is to use the doubly linked list. Assuming lengthening and cutting short a cell happens only at the end of the table, then both operations can be done easily and quickly on a D.L.List. Not sure what the interviewer meant by distance from beginning of the table... like number of bytes from the beginning of the table and he wants the cell number?For example, if each cell has length 5, and the user clicks on 13 from the top, then you need to let the user know he has clicked on cell 3. This operation needs to be fast.The search function needs to be doable in less than linear time, and so do inserts and deletesShow More Responsesbinary indexed treeslink list of link listsAn dynamically allocated array that can be resized..

### Software Engineering Intern at Palantir Technologies was asked...

Apr 16, 2012
 Given a list of "threads", which contain 2 variables - starting and ending times - implement a function that will return all running threads at some time t. Optimize it. (faster than O(n) )7 AnswersWe need to pre process this, Given the thread timings, we can create a int array of size max(endtimings) - min(start timings) and add 1 from array[start] to array[end] for each thread. Now, given a certain time, you can just lookup in the array, which takes O(1) time.The above solution will work and will be efficient in terms of time. But the amount of storage required is going to be massive, especially since thread timings are going to be generally specified in precision of milliseconds and can potentially run for a long time. A more optimal solution in terms of space could be dividing the time between min(start) and max(end) in ranges and then store the corresponding threads for each range. Since a thread can cover a range fully or partially, we will need to store the start time and end time corresponding to each thread. The ranges can be decided based on the trade-off that is required between time and space efficiency. When size of ranges is 1, the solution will effectively turn into the one mentioned above.I believe the best solution is as follows: You iterate through each thread and make note of where it starts and where it ends. You store this information in a sort of object that holds a time, the number of the thread, and whether or not the thread started or ended. Sort this list of objects based on time. You have essentially divided your space into time ranges based on the start/stop times of threads. Now we create some array of lists that has it's size set to the number of objects we created, BUT DO NOT fill this array with the objects! The array will be used to keep track of which threads are running in each time range. Iterate through the objects you made, filling up the lists in the array as you go. Example: Thread durations: 1: |---------| 2: |---| 3: |-------| Final array: {(1),(1,2),(1),(1,3),(3),null} Now you can do O(logn) lookup in the array with a basic binary search on the time ranges. The result in the array is what threads are running at that time.Show More ResponsesGlassdoor formatted the picture so it is useless. Here is attempt 2: 1: |---------|......... 2: ... |---|............. 3: ............|-------|@Jake The solution's pre-process can be faster. You can just store all times in an array, along with whether each time is a start/end time. The you can just traverse the array. This means that you don't need to figure out, for each discrete period in time, what threads are running. that could be pretty inefficient.try using interval tree https://en.wikipedia.org/wiki/Interval_tree. You can then traverse the tree and find all timeranges that overlaps with given time t. The complexity is O(log n + m) where m is the number of results.you might also divide overlaping timeranges into non-overlaping ranges. To each non-overlaping range assignlist of ranges that used overlaps there. Sample solution is here: http://stackoverflow.com/questions/628837/how-to-divide-a-set-of-overlapping-ranges-into-non-overlapping-ranges Then you can lookup the non-overlaping range that overlaps your given time t. Return list of ranges that used to overlaps there. You can do this with binary search (log n).

### Software Engineer Intern at PayPal was asked...

Apr 25, 2012
 n= 20 for (i=0;i
110 of 154 Interview Questions