# Senior Engineer Interview Questions

Senior engineer interview questions shared by candidates

## Top Interview Questions

### Senior Software Engineer at Apple was asked...

In a stream of integers from 1 to n, only one number will be repeated. How can you tell what that number is? 10 AnswersThis felt like a brain teaser question to me, and since I hadn't heard it before it took me a little while to come up with a solution that involved using a factorial function. You know n. S = n*(n+1)/2 is the sum of 1st n numbers. P = sum of the n+1 numbers you are provided with. Finding P given an array of n+1 integers can be done in O(n). P - S is the repeated integer. Heres an explanation, http://www.techinterview.org/post/526329049/sum-it-up Show More Responses int sum = 0; int xorSum = 0; for(int i =0 ; i < n; i++) { sum += input[i]; xorSum ^= input[i] } return (sum - xorSum)/2; Mat, try 1,2,2,3: 1+2+2+3= 8 1^2^2^3= 2 (8-2)/2=3?2 A hash table would resolve the question with O(n) Add to HashSet. It will return true if it exists. If you're writing it in ruby def find_repeat(numbers) numbers.length.times{|n| return numbers[n] if numbers[n] != n } end lmao, ok everyone getting a little craycray, why not just simply this.... int prev << stream; while (stream) { int curr << stream; if curr == prev return else prev = curr; } (sum_of_numbers - (n*(n-1)/2)) |

### Senior Software Engineer at Google was asked...

what's wrong with the following code : <template type T > T accumulate ( vector<T> in) { T total = in[0]; for (int i =0; i < in.length() ; i++) { total = total + in[i]; } return T } 7 Answers1. The big bug in[0] is accumulated twice. 2. empty vector ... The solution or 1 and 2 : total = T(); 3. input vector need to be const & 4. Better return the value as a &T in the argument list rather than as the ret value T can also be a string for example ! or some class that is expensive to copy. I.e. void accumulate(const vector & , T &total) 5. For string this function sucks and better a template specialization for string is preferred. 6 (? ) total += in[j] . Much more effective if T is not primitive type . On the other hand should ask if += is defined for the required T . 7. Not a big thing but passing in const_forward_iterators is nicer (This one I thought only afterward ) 8. I think the most important thing, after doing 1-7 the function will be exactly as the accumulate from algorithm.h ( as I said I missed few knock outs in this interview) .size not .length return T? Show More Responses Right - should be "return total;", though I'd agree with most of the comments made by the Interview Candidate. Can elements of a Vector be accessed array style...? I thought it was a Iterable Collection. In addition to what is suggested by the candidate: - If you are going to hand-write iteration, do it with const_iterators instead of an index into the vector - Prefer ++i instead of i++. The post-increment operator is defined in terms of the pre-increment operator and is less efficient since a copy of the original value needs to be made and returned Re: #6. If += is not defined, define it! operator+ should be defined in terms of operator+=. I'd just like to point out that you signed a non-disclosure when you interviewed (as everybody does), so it's pretty unethical of you to post actual interview questions here. You're explicitly asked not to post or talk about the actual questions. |

### Senior Software Engineer at Google was asked...

Create a stack of numbers where the maximum number is always known. 7 AnswersCreate a separate stack for the maximums. maintain a sorted stack, the insert would look like insert(int p,stack s){ stack large; int top = s.peek(); while(top>s){ large.push(s.pop()); top = s.peek(); } s.push(p); while(!large.empty()){ s.push(large.pop()); } } sorry, typo while(top>p) Show More Responses I was asked of this question as well. I not sure how to implment a second stack in a way that the max number is always on top. I was asked of this question as well. I not sure how to implment a second stack in a way that the max number is always on top. To Job Seeker: The basic idea is that when a new number is being pushed onto the stack, you need to see if that number is greater than or equal to the current top of the maximums-stack. If it is, you push the number onto maximums-stack as well. Also, when pop is called, you look to see if the number being popped is equal to the number on the top of the maximums-stack. If it it, pop that stack as well. just saw this, i think u can just map your number into an object, that has both the maximum number, and the last number that you've pushed in just peek the stack before you push, compare the peek'd value 'vs' your new pushed number, then replace or update the max number as you see fit? if you're only allowed to push numbers into your stack, just push your number in the stack more than once (at-least three times) indicating that every value that you put in is a sequence of 2 numbers, and so, push another one (the 3rd, which will always be your maximum number) so on every 3 pushes, you've stored the maximum value, then everytime you push something in, just peek the last 3 values in the stack, knowing that the 2nd and 3rd value was probably the number you pushed in, and the first 1 was the max value it's funny |

### Senior Software Engineer at Google was asked...

Implement a base 3 adder which takes two strings as input and returns a string 6 Answers// sum : null terminated pre-allocated large enough string char *addBase3(const char *a, const char *b, char *sum) { char oldsum[20] = ""; // stacking characters would be much better than this const int alen = strlen(a); const int blen = strlen(b); int retainer = 0; int apos, aval; int bpos, bval; int partsum; int pos; for(pos = 1; pos = 3) { retainer = 1; partsum = 3 - partsum; } else { retainer = 0; } strcpy(oldsum, sum); sprintf(sum, "%d%s", partsum, oldsum); } if (retainer) { strcpy(oldsum, sum); sprintf(sum, "%d%s", retainer, oldsum); } return sum; } if allowed, converting base 3 to base 2, then adding and converting back is better // sum : null terminated pre-allocated large enough string char *addBase3(const char *a, const char *b, char *sum) { char oldsum[20] = ""; // stacking characters would be much better than this const int alen = strlen(a); const int blen = strlen(b); int retainer = 0; int apos, aval; int bpos, bval; int partsum; int pos; for(pos = 1; pos = 3) { retainer = 1; partsum = 3 - partsum; } else { retainer = 0; } strcpy(oldsum, sum); sprintf(sum, "%d%s", partsum, oldsum); } if (retainer) { strcpy(oldsum, sum); sprintf(sum, "%d%s", retainer, oldsum); } return sum; } Show More Responses public class Test1 { public static void main(String[] args) { System.out.println(new Test1().add("21", "22")); //prints 120 } int toInt(String str) throws NumberFormatException { int result = 0; for (int index = 0; index 2) { throw new NumberFormatException(); } result = result * 3 + i; } return result; } String toStr(int i) throws NumberFormatException { StringBuffer sb = new StringBuffer(); while (i > 0) { sb.insert(0, i % 3); i /= 3; } return sb.length() == 0 ? "0" : sb.toString(); } String add(String str1, String str2) throws NumberFormatException { return toStr(toInt(str1) + toInt(str2)); } } base3DigitAdd(char lhs, char rhs, char &extra, char &carry,char &sum) { int s = (lhs - '0') + (rhs - '0') + (extra - '0'); carry = (s/3) + '0'; sum = (s%3) + '0'; } base3Add(const string &lhs, const string &rhs, string &result) { string::const_iterator il = lhs.end(); string::const_iterator ir = rhs.end(); result.clear(); char carry = '0'; char digit = '0'; while((il != lhs.begin()) || (ir != rhs.begin()) { char l = (il != lhs.begin) ? (*(il - 1)) : '0'; char r = (ir != rhs.begin) ? (*(ir - 1)) : '0'; base3DigitAdd(l, r, carry, carry, digit); result.push_front(digit); if (il != lhs.begin()) { --il; } if (ir != rhs.begin()) { --ir; } } if (carry != '0') { result.push_front(carry); } } string base3Add(const string & in1, const string & in2) { int i1 = atoi(in1.c_str()); int i2 = atoi(in2.c_str()); int carry = 0; char buff[2]; string result; while(i1 != 0 || i2 != 0 || carry != 0) { int i1p = i1 % 10; int i2p = i2 % 10; int total = i1p + i2p + carry; itoa(total % 3, buff, 10); result.push_back(buff[0]); carry = total / 3; i1 /= 10; i2 /= 10; } reverse(result.begin(), result.end()); return result; } |

### Senior Software Engineer at Google was asked...

Given a series of words written using a scrambled alphabet, figure out what order the letters of the alphabet are in. 7 AnswersUse a graph! More than three words would be helpful. Do what with a graph? How would you build it? How would you search it? Given a ciphertext C, and plaintext P, the problem is to find a key K that converts the ciphertext to plaintext. Without considering the asymptotic complexity, it should be straighforward to generate the key combinations using a backtracking search algorithm. Show More Responses More specifically, you would be given a list of words in the ciphertext which are in alphabetical order. Your job is to determine the alphabetic order of the ciphertext letters. In a graph, each node would represent a letter, the directed edge would indicate ordering of the two letters it connects. Once the graph is built you can do a simple traversal of the graph to generate your alphabetical ordering. Hope that helps! I think I didn't get the question. Could someone elaborate on it a bit please? @Alexander An example of what I believe the question is presenting to the applicant is as follows. Say I knew one of the words was 'CAT'. Now, if I look at the scrambled 3 letter word, and it was ZBS, then I know that C = Z, A = B, and T = S. Essentially, potentially every letter in the alphabet (up to 26 letters in total) are not of the same value. So, if I had another example word, say 'TACS', and the given scrambled word is 'SBCY', then I now know that S = Y as well. This is not an explanation of how to approach the problem, as we're not given any sample words; This is simply my interpretation of how the question is supposed to be interpreted as @Alexander is probably not the only person who does not understand the question. Of course, I could have it wrong too, so who knows. http://www.careercup.com/question?id=19114716 |

### Senior Software Engineer at Amazon was asked...

Given an array of integers A[1...n], compute the array B[1...n] such that B[k] is the product of all the elements of A, except A[k]. Part ii) Try to do it without division (some mobile devices don't have division). Was asked to write code for part ii. 7 AnswersHere is a psedocode for the same. public void solveAns() { Integer a[] = {1,2,3,4,5}; Integer b[5] = new Integer[5](); for ( i =0; i<5; i++) { b[i] = getProduct(a, i); } } private Integer getProduct(Integer[] a, int index) { Integer prod = 1; for ( i =0; i @Shilpa while your answer is correct, it is O(n^2). This can be done in O(n) with no auxillary space. Two passes of the array A : After first pass B[i+1] = A1 * A2 * A3 * .... Ai So in second pass, by traversing A in reverse order and multiplying we can get the desired result. @AV seems your method is still O(n^2) or a extra array is needed; like this: void product (int * a, int* b,int n) { int * c= new int [n]; for (int i=0;i Show More Responses long Totl = 1; for ( i = 0; i < length; i++ ) // Get total product { Totl *= arry1[i]; } for ( i = 0; i < j; i++ ) { if ( arry1[i] ) prdArry[i] = Totl / arry1[i]; else prdArry[i] = 0; } It can be almost done in O(n) time in two steps. #1. Determine the product of all numbers O(n) #2. Divide the product at its index & store it to b. Complexity O(n); For example, Let a[] = {1,2,3,4,5};//make sure doesn't have zero. and b[] as a new array; int product=1; for(int i=0; i Linear time guys. #include "stdafx.h" #include using namespace std; void printmultipliers(int a[], int b[], int n) { int totalProduct = 1; cout = 0) { if(j == (n -1)) { cout << b[j -1] << " "; } else if(j == 0) { cout << reverseproduct; } else { cout << b[j-1] * reverseproduct<< " "; } reverseproduct *= a[j]; j--; } } int _tmain(int argc, _TCHAR* argv[]) { int a[] = {1, 2, 3, 4}; int b[4]; printmultipliers(a, b, 4); return 0; } Another take on O(n) (or may be what AV was saying above). It takes a couple extra arrays, but better than O(n^2) int[] a = new int[] {2, 3, 4, 5, 6}; // should render final = [360, 240, 180, 144, 120] int len = a.length; int[] before = new int[len]; // will become [1, 2, 6, 24, 120] int[] after = new int[len]; // will become [360, 120, 30, 6, 1] int[] final = new int[len]; // will be [360, 240, 180, 144, 120] int front = 1; int back = 1; before[0] = 1; after[len - 1] = 1; for (int i = 1; i < len; i++) { front = front * a[i - 1]; // first pass 2, second 6, etc. before[i] = front; // end up with [1, 2, 6, 24, 120] after = after * a[len - i]; // first pass 6, second 30, etc backward[len - i - 1] = after; // filled backwards so we don't have to mess with this below. } for (i=0; i < len; i++) { final[i] = before[i] * after[i]; } return final; |

### Senior Software Engineer at Google was asked...

Intersection of two numerical arrays 6 AnswersAlgorithm and pseudo code * assuming b[] is the longer array quick sort b[] for all items from a[] binary search this item in b[] for above.. O(n log n) + O(n) * O(log n) Show More Responses I have a O(n) algorithm: 1. Iterate over all the elements of first array a[] and build a dictionary mapping the element value to the index - O(n) 2. Now iterate over all the elements of the second array b[] and for each element that is already present in the dictionary, move the element to a different array that maintains the intersection elements - O(n) 3. Hence the overall complexity is O(n) in time and O(n) for the dictionary and the array to maintain the intersection elements. given arrays of lengths n and m. A simple solution is to sort array n in O(n lg n) and for each item in array m, look for it in sorted n, O(m lg n). So total time = O((m+n)lg n), let array n be the short array. I feel there is a much quicker solution, maybe O(n+m) if we assume integers. Two possible approaches: 1. Sort both arrays and then walk over each array simultaneously until you find all the common entries. This is O(n*logn) to do the sort and then walking over the items is O(n). 2. Walk over first array and insert each item into a hash table. Then search for each item in the hash table. This is O(n) time and O(n) space. If you're doing this a lot with the same sets of data, both algorithms allow you to do the expensive step once for each array and then find the common items in linear time. |

### Senior Software Engineer at Amazon was asked...

Write a program to count the number of words in a file. 5 AnswersYou have to code a program over the phone. What I would look for in an answer here would be for the person to focus on the definition of what delimits a word. Then a state machine construct that counts the number of transitions from the "in a word" state to the "out of word" state would be the word count * 2. #!/usr/bin/perl -w my $cnt = 0; while() { my $num_blanks = s/ +/ /g; $cnt += $num_blanks + 1; } print "$cnt\n"; Show More Responses wc -l Not a program per se, but works :) #!/usr/bin/bash echo "Enter filename" read fileName for WORD in $(cat $fileName) do echo $WORD done | wc -l |

### Senior Software Engineer at Microsoft was asked...

Given a set of people, one of them is a celebrity. You have a 2D array which describes which people know each other, that is [N, M] is true if N knows M. The celebrity will not know anyone (except them self) and everyone will know the celebrity. Find an order N algorithm to find the celebrity. 6 AnswersDon't think there is an O(n), but O(n*m) yes. The key here is that the celebrity knows nobody AND everybody knows the celebrity. So for each iteration, you can rule out 1 person. [Notation: A->B -- A knows B] If A->B then A is not the celebrity .. rule out A Next check would skip B->A since we don't care if B->A etc It is not so simple. You can construct a matrix of relationships to defeat this algorithm. For example, start with A knows B. Then check if B knows C, and say answer is false. Then check B -> D, answer is false. And so on. That's O(N) operations. B looks like a good candidate. But then you check B-> A, you get true, so after all that work B is ruled out. Need to examine C now. Same thing. You end up checking perhaps half of all possible pairs, that's O(N^2). Show More Responses How about constructing a graph with edges between who know each other.. and then checking if target is reachable.. http://courses.cs.vt.edu/~cs5114/spring2010/notes.pdf Please correct me if I've made some incorrect assumptions here. It seems like the matrix is an adjacency matrix, so M is always equal to N. The solution is to follow the diagonal. If A is the celebrity then following are the patterns possible along the diagonal. If A is the first element in the matrix, i.e. i=0 and j=0 then [0,0] = 1, [0,1]=0, [1,1]=1, [1,0]=1. If A is the last element in the matrix, i.e. i=M and j=M then [M,M]=1, [M-1,M-1]=1,[M,M-1]=0,[M-1,M]=1 The third case is when A is an element somewhere other than the above cases. In this case, you're looking for the following pattern [i,j]=1,[i-1,j]=1,[I+1,j]=1,[i,j+1]=0,[i-1,j]=0. Looking at the time complexity, it is going to be a tad higher than O(N) but certainly not O(M^2). |

### Senior Software Engineer at Oracle was asked...

Considering a 2-dimension matrix that can only be traversed by 1 adjacent position at a time and never diagonally. Create an algorithm to traverse that matrix from its upper-left corner to its lower-right corner using the shorter possible path in the most efficient way. 6 AnswersThis is a very interesting problem. Although I knew immediately that I had to use recursion to effectively traverse the matrix and eventually got a working algorithm, the catch to make the algorithm much more efficient is to traverse the matrix backwards. How back traverse make the algo efficient? Why not just go all the way down then all the way right? Without diagonal moves the path length is fixed. Unless they provide a different definition for 'shortest length' Show More Responses For a thinking outside the box answer.... assuming the set is closed for indexing, go up -1 and left -1. I guess it's the traversal of a graph's depth first search (DFS) using Adjascent matrix... it is similar to two way BFS. Start from top left and bottom right and then keep moving until they meet. |

**11**–

**20**of

**10,877**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Software Developer
- Software Development Engineer
- Staff Software Engineer
- Director
- Principal Software Engineer
- Senior Software Developer
- Product Manager
- Software Engineer III
- Senior Software Development Engineer
- Data Scientist
- Intern
- Project Manager
- Vice President
- Manager
- Software Development Engineer II
- Engineering Manager
- Engineer
- Java Developer