Sr Software Engineer Interview Questions | Glassdoor

# Sr Software Engineer Interview Questions

6,963

Sr software engineer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

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

Jul 18, 2010
 Write some pseudo code to raise a number to a power.11 Answerspretty trivial...int raise(num, power){ if(power==0) return 1; if(power==1) return num; return(raise(num, power-1)*num); }double Power(int x, int y) { double ret = 1; double power = x; while (y > 0) { if (y & 1) { ret *= power; } power *= power; y >>= 1; } return ret; }Show More ResponsesIn Ruby: def power(base, power) product = 1 power.times do product *= base end product end puts "2^10 = 1024 = #{power(2,10)}" puts "2^0 = 1 = #{power(2,0)}" puts "2^1 = 2 = #{power(2,1)}"If I were an interviewer, I would ask the Aug 29, 2010 poster why he used bitwise operators, and whether he would deploy that code in a production environment, or if he merely wanted to demonstrate, for purposes of the interview, that he understands bitwise operations.Because it uses dynamic programming and is lots more efficient than your algorithm.If the power is not integer, use ln and Taylor seriesIf I'm the interviewer, none of above answers is acceptable. What if y < 0? what if y < 0 and x == 0? I'm seeing an endless recursion that will eventually overflow the stack, and the none-recursive one just simply returns 1.There is a way to do this in a logN way rather than N. function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1); } This is from Programming pearls.. interesting way.small mistake function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1) * x; }# Solution for x ^ n with negative values of n as well. def square(x): return x * x def power(x, n): if x in (0, 1): return x if n == 0: return 1 if n < 0: x = 1.0 / x n = abs(n) # Even number if n % 2 == 0: return square(power(x, n/2)) # Odd number else: return x * power(x, n - 1) print ("0 ^ 0 = " + str(power(0, 0))) print ("0 ^ 1 = " + str(power(0, 1))) print ("10 ^ 0 = " + str(power(10, 0))) print ("2 ^ 2 = " + str(power(2, 2))) print ("2 ^ 3 = " + str(power(2, 3))) print ("3 ^ 3 = " + str(power(3, 3))) print ("2 ^ 8 = " + str(power(2, 8))) print ("2 ^ -1 = " + str(power(2, -1))) print ("2 ^ -2 = " + str(power(2, -2))) print ("2 ^ -8 = " + str(power(2, -8)))

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

Sep 6, 2010
 Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division. 8 AnswersO(size of array) time & space: First, realize that saying the element should be the product of all other numbers is like saying it is the product of all the numbers to the left, times the product of all the numbers to the right. This is the main idea. Call the original array A, with n elements. Index it with C notation, i.e. from A[0] to A[n - 1]. Create a new array B, also with n elements (can be uninitialized). Then, do this: Accumulator = 1 For i = 0 to n - 2: Accumulator *= A[i] B[i + 1] = Accumulator Accumulator = 1 For i = n - 1 down to 1: Accumulator *= A[i] B[i - 1] *= Accumulator Replace A with B It traverses A twice and executes 2n multiplicates, hence O(n) time It creates an array B with the same size as A, hence O(n) temporary space# A Python solution (requires Python 2.5 or higher): def mult(arr, num): return reduce(lambda x,y: x*y if y!=num else x, arr) arr = [mult(arr,i) for i in arr] # O(n^2) time, O(n) spaceCreate two more arrays. One array contains the products of the elements going upward. That is, B[0] = A[0], B[1] = A[0] * A[1], B[2] = B[1] * A[2], and so on. The other array contains the products of the elements going down. That is, C[n] = A[n], C[n-1] = A[n] * A[n-1], and so on. Now A[i] is simply B[i-1] * C[i+1].Show More Responsesdef without(numbers): lognums = [math.log10(n) for n in numbers] sumlogs = sum(lognums) return [math.pow(10, sumlogs-l) for l in lognums]Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e. tolal = A[0]*A[1]]*....*A[n-1] now take a loop of array and update element i with A[i] = toal/A[i] Since division is not allowed we have to simulate it. If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g. 2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input void ArrayMult(int *A, int size) { int total= 1; for(int i=0; i< size; ++i) total *= A[i]; for(int i=0; i< size; ++i) { int temp = total; int cnt = 0; while(temp) { temp -=A[i]; cnt++; } A[i] = cnt; } } Speed in O(n) and space is O(1)#include #define NUM 10 int main() { int i, j = 0; long int val = 1; long A[NUM] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Store results in this so results do not interfere with multiplications long prod[NUM]; while(j < NUM) { for(i = 0; i < NUM; i++) { if(j != i) { val *= A[i]; } } prod[j] = val; i = 0; val = 1; j++; } for(i = 0; i < NUM; i++) printf("prod[%d]=%d\n", i, prod[i]); return 0; }void fill_array ( int* array, size ) { int i; int t1,t2; t1 = array[0]; array[0] = prod(1, size, array ); for(i = 1; i < size; i++){ t2 = array[i]; array[i] = prod(i, array.size(), array)*t1; t1 *= t2; } int prod(start, end, array){ int i; int val(1); for(i = start; i < end; i++ ) val *= array[i]; return val; }Hello, Thank you for sharing your interview experience. As a small team of ex-Google employees, we have recently launched a new website, interviewjoy.com, where you can earn money by sharing your interview experiences/insights with other job candidates. (It is a marketplace for sharing job interview insights). Posting an interview consultancy service is totally free & anonymous and we are giving 50 USD sign-up bonus for the first 500 users. You are kindly invited to interviewjoy.com to check it out. Users already started making money on the website! Best Regards.. (For more information: onboarding@interviewjoy.com)

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

Mar 19, 2009
 What sort would you use if you required tight max time bounds and wanted highly regular performance.6 AnswersVector sort.Guaranteed to be O(n log n) performance. No better, no worse.That is so say, a "Balanced Tree Sort" is guaranteed to be O(n log n) always.Show More ResponsesMerge sort and heapsort are always guaranteed to be n*log(n). Quicksort is usually faster on the average but can be as bad as O(n^2), although with very low probability. Heapsort also does it sorting in-place, without needing an extra buffer, like mergesort. Lastly, heapsort is much easier to implement and understand than balancing trees mentioned by earlier posts.for something like this you generally want bubble sort or insertion sort. It's not about being fast it's about being consistent. Make it do exactly the same thing every time.Use a sorting network. There's some precomputation time, but runtime will be very consistent (the only variability is branch prediction performance)

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

Jul 13, 2009
 Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division. 26 AnswersCreate a tree, where the leaf nodes are the initial values in the array.Given array A[1..n] create array B[1..n]= {1} // all elements =1 ; for (i=1; ij) B[i] *=A[j]; } } A=B;To husb: Your answer will work, but it's O(n^2) solution. Can you do better?Show More ResponsesAm I missing something? It can't be this easy: given array[0..n] int total = 0; for(int i=0; i<=n; i++) { total += array[i]; } for(int i=0; i<=n; i++) { array[i] = total-array[i]; }Ah yes.. I was. The question is PRODUCT, not sum. That will teach me to read the question too fast ;)Create a tree, where the leaf nodes are the initial values in the array. Build the binary tree upwards with parent nodes the value of the PRODUCT of its child nodes. After the tree is built, each leaf node's value is replaced by the product of all the value of the "OTHER" child node on its path to root. The pseudo code is like this given int array[1...n] int level_size = n/2; while(level_size != 1){//build the tree int new_array[1...level_size]; for ( int i=0; i left = array[i*2]; (and also from child to parent) new_array[i] -> right = array[i*2+1] new_array[i] = new_array[i] -> right* new_array[i] -> left; (take the product) } array= new_array; level_size /=2; } for(int i=0; iparent; if( parent->left == node){//find the other node under the parent brother = parent->right; } else{ brother = parent->left; } p *= brother; node = parent; } return p; }btw, it's O(n*logn)It seems to me that for any number array[i], you're looking for PRODUCT(all array[j] where j i]) we can simply precompute these "running products" first from left-to-right, then right-to-left, storing the results in arrays. So, leftProduct[0] = array[0]; for j=1; j = 0; j-- rightProduct[j] = rightProduct[j+1]*array[j]; then to get our answer we just overwrite the original array with the desired product array[0] = rightProduct[1]; array[n-1] = leftProduct[n-2]; for j=1; j < n-1; j++ array[j] = leftProduct[j-1] * rightProduct[j+1] and clearly this solution is O(n) since we just traversed the data 3 times and did a constant amount of work for each cell.betterStill, I think you have the answer the interviewer wanted.. But... if the array is google sized, don't we have to worry about overflows?it looks to me can be done in order n time given the following relation: product[n] = product[n-1]*array[n-1]/array[n] for example we have array 2 3 4 5 6 product[0]=3*4*5*6 product[1]=2*4*5*6 array[0] = 2; array[1]=3 product[1]=product[0]*array[0]/array[1]Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e. tolal = A[0]*A[1]]*....*A[n-1] now take a loop of array and update element i with A[i] = toal/A[i] Since division is not allowed we have to simulate it. If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g. 2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input void ArrayMult(int *A, int size) { int total= 1; for(int i=0; i< size; ++i) total *= A[i]; for(int i=0; i< size; ++i) { int temp = total; int cnt = 0; while(temp) { temp -=A[i]; cnt++; } A[i] = cnt; } } Speed in O(n) and space is O(1)narya trick is good but really useful as it might take more iterations depending on values... eg. 2,3,1000000000000000 so if you have 3 numbers and if you are trying for the first one it will go for 500000000000000 iterations, hence as the overall product value wrt to the value matters a lot... try something else....narya, your solution is not O(n). You have to also account for how many times you will run through the inner loop - which will be a lot. You can do it in O(n) time and O(n) space. In one pass, populate B[i] with the product of every number before i. In the second pass, multiply this with the product of every number after i. Can't think of a way to do it without the second array. void ArrayMult(int *A, int size) { runningProduct = 1; int *B = new int[size]; for(int i = 0; i = 0; --i) { B[i] *= runningProduct; runningProduct *= A[i]; } for(int i = 0; i < size; ++i) { A[i] = B[i]; } }Show More ResponsesBrutefoce Method : The brute-force method suggests that if we take each element, multiply all elements and store the product in the array B[i], then it would take O(n^2) time. Other Solution : The other solution to this problem can be we multiply all the elements of the array "A" and store the product in a variable (say product.), and then divide the product by each element, then we will get the desired array. The C code of the solution can be : #include int main() { int n,i=0; scanf("%d",&n); int arr[n]; int brr[n]; int product = 1; for(i=0;i This solution will take O(n) time. The space complexity of this solution will be O(1). If we have particularly given that "We can't use the *DIVISION* operator, then the solution to this problem will be as follows." polygenelubricants method : Let we have 2 arrays, "A" and "B". Let the length of "A" is 4. i.e. {A[0],A[1],A[2],A[3]} Then we will make two arrays (say temp1 and temp2). One array will be storing the product the array before a particular element and temp2 will store the product of elements after a particular element. temp1 = { 1 , A[0] , A[0]*A[1] , A[0]*A[1]*A[2]} temp2 = {A[1]*A[2]*A[3] , A[2]*A[3] , A[3] , 1} And then we will correspondingly multiply temp1 and temp2 and store in B. B = {A[1]*A[2]*A[3] , A[0*A[2]*A[3] , A[0]*A[1]*A[3] , A[0]*A[1]*A[2]} The C code to this solution will be : #include int main() { int n,i=0; scanf("%d",&n); int A[n],B[n]; int temp1[n], temp2[n]; for(i=0;i=0;i--) { temp2[i] = product; product *= A[i]; } for(i=0;i The time complexity to this solution will be O(n) and the space complexity to this problem will also be O(n).var nums = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; var newnums = new int[nums.Length]; for (var i = 0; i index != i).Aggregate((a, b) => a*b); }We can fill two arrays: headProduct and tailProduct. Each headProduct[i] == product of A[0..i-1], tailProduct[i] ==[i+1..A.lenght-1]. They can be built in O(n) and the result could be gathered in O(n). Memory demand is O(n)Not commentarynt a[N] = {1, 2, 3, 4}; int products_below[N]; int products_above[N]; int p=1; int p1=1; for (int i=0;idef solve(arr,n): product_arr=[1]*n product=1 for i in xrange(n): product_arr[i]*=product product*=arr[i] product=1 for i in xrange(n-1,-1,-1): product_arr[i]*=product product*=arr[i] return product_arr{{{ If A = {a0, a1, a2, ... an} Construct two arrays called left_p left product and right_p right product: left_p = {1, a0, a0 * a1, a0 * a1 * a2, .... , a0 * a1 * a2 ... * an-1} right_p = {a1*a2*...*an, ....... an-2 * an-1 * an , an-1 * an, an , 1} prod_p[i] = left_p[i] * right_p[i]; }}}O(N) Solution!!! static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i < iArr.Length; i++) { total *= iArr[i]; } for (int i = 0; i < iArr.Length; i++) { iArr[i] = (int)(total * (1 / (double)iArr[i])); } }The answer I post above this uses division. Oops. Here is an answer without division static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } }Sorry, that last one didn't paste properly static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } }Show More Responsesp = 1 g = 1 for x in nums: g = g* x + p p = p + x return gWay easy with a simple negative exponent var arr = [2,3,4,5] var prod = arr.reduce((a,b,arr)=>a*b) arr.map((x)=>Math.pow(x,-1)*prod) console.log(arr) //[60,40,30,24]I don't know if this is correct. But i think it is. I have done it with python def multiply(numbers,n): total = 1 for x in numbers: if x != n: total *= x return total a = [10, 3, 5, 6, 2] n = 4 prod = [] for i in a: re = multiply(a,i) prod.append(re)

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

Mar 1, 2012
 Traverse nodes in a binary tree11 AnswersWhat is taught in compsci, and even what's in Knuth, isn't entirely right on modern out-of-order execution core CPUsvoid traverse(Node node){ if(node == null) return null; System.out.println(node.data); traverse(node.left); traverse(node.right); }It can't be that this candidate really serves on a language committee. I find it difficult to believe that someone who serves on a language standards committee doesn't care about the difference between an O(N^2) and an O(logN) solution, for that would be horrifying indeed. And in defense of the employee conducting the interview, if I did see a candidate that didn't care about the difference between the two, I really wouldn't care what they have on their resume. They could be a Turing award winner for all I would care. There's a valid point about spatial locality, etc, but for something like N = 10^6 (for example), I'll take even O(logN) disk reads (*gasp*), over N^2 quick register operations any day..Show More ResponsesWell, I do serve on language committees, two to be precise (though one is mostly in a feed forward role). And I do care about the difference between O(N^2) and O(log N)! I gave a complex answer to the interviewer because there is so much "it depends on the situation and circumstance". Other companies had interview processes which coped far better with the ambiguity, but from what I saw Amazon's are very "by the book" black and white. Look, I interviewed for four roles within Amazon and all four interview experiences ranged between bad and truly awful, which is why I chose neither the worst nor best experience and wrote up a review of it here as representative of *my* personal experience. Some of my experiences with other Fortune 500 companies were equally awful, and there are reviews for those on here too. However, I did also have many very good interview experiences, and I begin work with one Fortune 500 company in the Fall with whom my interview experience - over 20+ hours over twelve interviewers - couldn't have been better. Tip to interviewers: it *really* helps if you at least read the abstracts of the academic papers the interviewee has written. You could easily segment those companies which do this from those which don't, and Amazon from my four experiences with them don't or didn't.I hope you weren't offended too much by my earlier comment. Your explanation just now puts things into better context. I have to admit that upon initially reading your original review it wasn't very clear to me that you understood or cared about the difference between O(logN) and O(N^4). If the company was also unclear on that, you have to admit that one can see why they wouldn't extend an offer. Of course not everything is about big-O, but you should still be able to give answers in terms of it when needed. It's great if you know about data locality and caches, but you should still be able to show the basic analysis too. On another point, of course you should try to reuse code, but you also need to demonstrate (in an interview more than ever) that you have the skills to write new code when necessary, not by pointing them to some open source project you did, but by writing some nice, clean code for them right on the spot. A demonstration of your high skill level is more impressive than a description. It's a proof-by-demonstration sort of culture. You might ask why anyone should re-invent the wheel, but I'll leave you with this: if you can't prove to them that you *can* reinvent the wheel, why would they believe you have the creativity needed to invent a motorcycle?Wasn't offended at all - in fact, your comment is by far the best made on this thread (as you can tell from everything else being deleted by glassdoor). And besides, caustic opinions of your opinions are part of publishing an opinion, I'm well used to it. My issue with Amazon - and it's one shared by my buddies within Amazon too - is there is too much box ticking of standardized procedures in the recruitment process. That rewards rote pre-learning the answers to the live programming tasks you do over the telephone (search google, you'll find precompiled cheat sheets for Amazon and indeed many of the big tech companies). That's hardly "writing some nice, clean code for them right on the spot" as you suggest. A github repo with 40,000 lines of code stretching over a decade is much harder to fake. Amazon ought to hire on that in preference, but their recruitment process requires a standardized approach. The company I start with in the Fall used a completely unstructured process. They interview you on things that THEY don't know anything about let alone you, and topics which have absolutely nothing to do with compsci or technology, so for example one topic was on mining copper on the Mongolian steppes. I know very little about that, and neither did they. But as the elite of the elite team (within the company) said at the start of the interview, "we're not going to talk at all about anything to do with code during this interview. We'll know if you're a good hire by seeing how you think on topics both you and us know nothing about". That company offered the lowest compensation of any offers I received. But boy, what a great interview experience, so I had to accept. I hope working there is even 10% as good as they came across during the interviews. If so, I'm more than happy with lower pay. I'm no 10x programmer, maybe a 4x, so I'm not the perfect recruit. But I don't think Amazon should have failed me on stage 1 of each of the four roles I interviewed for. Hence the review.Mining copper on the Mongolian steppes, huh? That must be a very unique company.They're actually a multinational quite similar to Amazon - well known to consumers, occasionally known for moments of brilliance, otherwise fairly dull and dependable. Mining copper was one of many curve ball interview topics. Off the top of my head other topics included the technology policies of Kim Jung Il in North Korea, something about water and Tar Sands in Canada which I forget now, whether and how Russians are naturally good at science and math, how would you go about reconciling quantum physics with relativity, conflict resolution strategies between culturally disjunctive teams - and the list goes on much further (all this was many months ago now, so I'm forgetting). All this for a standard software engineering role, so I'm expected to be in a cubicle coding, not organizing world peace. Looking back on it now, it should have freaked me out much more than it did at the time. I suppose I was interviewing with so many companies at the same time it all just blurred. Anyway, we're getting off topic from Amazon's interview strategies. Amazon *are* a great company. They've soaked up the best and brightest from Microsoft particularly and it's a much less dysfunctional working environment than Microsoft where something went wrong a long time ago, but no one can agree exactly what, and even if they could agree, top management don't seriously think it's a problem. However Amazon is naturally silo-ized, where the consumer goods division is quite different to consumer services which is quite different to cloud provision and even cloud reliability provision. The problem, I think, is that Amazon's HR would prefer every engineer to be hired according to similar criteria, and that's where this box ticking standardized list of coding exercises comes from. As a comparison, Google's silo structure and hiring process is not dissimilar, though Google do run an elite expedited recruitment pathway which skips all the normal hoop jumping nonsense at the cost of fast tracking only those with the very best academic grades from the best US universities, or are famous. I have pretty terrible grades with a lot of bare scraping passes, none from Ivy League anything, and I'm not Dennis Richie or Rob Pike or Guido van Rossum famous. Still, it's interesting how companies start to struggle so hard with high skilled recruitment as they get bigger. It's not like there aren't very good HR books on the topic, yet no one in the HRs of these big famous tech multinationals seems to ever read them (or if they do, they sure don't implement them). I guess what I'm saying is that tech recruitment is hard, but it's not NP hard. Just be organized and constantly reflect on your hiring system. A very good start for Amazon would be to read these reviews on Glassdoor, and proactively enact changes so they're not failing candidates like me at stage 1 in the interview process (fail me later for lack of fit sure, but not on the initial programming exercise when I have 40k lines of open source contributions and I serve on ISO - that sort of indicates I'm not an incompetent programmer). Amazon also ought to knock some humility into some of their engineers, as a minority of them were rude and ignorant (I had one storm out during the telephone interview after giving a torrent of invective about me personally after I showed him up on a series of technical mistakes, and his colleague was clearly very embarrassed. As I said to him, "really, honestly don't worry about it, I've heard far worse said about me. But you can forget me ever working for Amazon after that"). I haven't posted a review of that interview on glassdoor because it was probably not representative of Amazon in general and the guy in question was probably just having a really bad day, though as I mentioned earlier, all four of my interviews did not go well. I just hope my review here has some effect within Amazon one day. As I said earlier, it *is* a great company.I agree with you. You have to focus on the person's ability to find answers not re-invent the wheel. If I were interviewing someone...as long as he can google a problem take me to an answer which perfectly fits the needs and then explain the solution (instead of blindly copying/pasting it) to me clearly, that would be the perfect candidate for the job. These kind of questions are only suitable for fresh out of college grads not people who have been in the industry for a long time.@NikB: Thanks for the comment. Certainly when I've been interviewing others, I'm generally fairly shocked at how awful the average candidate is - I mean, I catch an easy third who have lied on their resume and that's with five minutes of googling (depending on the lie, if they admit it in the interview, I actually give them a pass on it because I know what it's like to have poor grades from no name universities). About two thirds clearly have no integrity and will tell you whatever they think you want to hear, and I personally can't have that on my own teams (I won't veto hires for other teams on this though). About three quarters have no evidence that they seriously self-engage in continuing professional development e.g. teaching themselves new skills not directly needed for work. I would *far* prefer a poor programmer who continually self improves over a rock star programmer. I would *far* prefer a programmer who uploads even crappy non-reusable bits of personal script to github than someone who claims they have always been too busy to get round to it. It gives me extra information to evaluate that candidate. Less information = more uncertainty = much higher chance of me choosing elsewhere. A true coder codes all the time including people and social structures, and I want those on my team irrespective of skill. I agree only about half of those are willing to share their work with others, so lack of sharing does exclude a lot of worthwhile hires. But I guess we all have our personal preferences on what we think works best. Some colleagues of mine who I respect greatly think my hiring philosophy bananas!Do you mind if I ask what those 3 algorithms that you wrote are?

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

Apr 21, 2011
 In a stream of integers from 1 to n, only one number will be repeated. How can you tell what that number is?11 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-upShow More Responsesint 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?2A 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 } endlmao, 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))Add each integer to the map if it doesn’t already exist as key if it’s exists then it is a repeated number.

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

Jul 29, 2010
 what's wrong with the following code :

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

Jul 13, 2009
 Create a stack of numbers where the maximum number is always known.10 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 ResponsesI 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 funnySort the array so that the numbers are in descending order this way you know for sure the first element is the maximum number.Maintain your Stack ADT like this: class Node { T data; T max; Node next; } class Stack { Node top; push(T value) { } }Maintain your Stack ADT like this: class Node { T data; T max; Node next; } class Stack { Node top; void push(T value) { Node node = new Node(); node.value = value; if(top == null) { node.max = value; } else { node.max = value.compareTo(top.max) > 1 ? value : top.max; } node.next = top; top = node; } T pop() { if(top == null) { return null; } T val = top.val; top = top.next; return val; } T max() { return top == null ? null : top.max; } } public static void main(String[] args) { Stack stack = new Stack(); stack.push(3); stack.push(2); stack.push(5); System.out.println(stack.max()); // 5 System.out.println(stack.pop()); // 5 System.out.println(stack.max()); // 3 System.out.println(stack.pop()); // 2 System.out.println(stack.max()); // 3 System.out.println(stack.pop()); // 3 }

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

Apr 7, 2010
 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 Responsespublic 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...

Apr 27, 2013
 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 ResponsesMore 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
110 of 6,963 Interview Questions