# Senior Engineer Interview Questions

Senior engineer interview questions shared by candidates

## Top Interview Questions

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

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 Responses In 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 series If 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...

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) space Create 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 Responses def 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...

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 Responses Merge 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 Network Engineer at CSC was asked...

What are the 6 TCP flags? 2 AnswersGOOGLE EM URG, RST, PSH, CWR, SYN, FIN, ACK, ECN |

### Senior RF Engineer at Nexius was asked...

What will be the greatest contribution that you can ever make as an individual to your team 1 Answercoalescing my individual knowhow with overall experience that my team has makes for a well-rounded team that knows esprit de corps and can work towards success all the times |

What has been your active role in the team process you're currently working with? 1 AnswerExplained details of daily involvement, software used, level of completion of initial input received, and final deliverable. |

What sort of anomalies would you look for to identify a compromised system? 1 AnswerI used a whiteboard to draw out a basic network architecture including security technologies like IPS/IDS, Firewalls, AV, etc, and described the type of traffic and logs I could use to identify a compromised system. |

### Linux Kernel Engineering at Google was asked...

You have 25 horses, what is the minimum number of races you can find the top 3. In one race you can race 5 horses, and you don't have a timer. 29 AnswersI don't know, but Google it, you'll find the answer. Once you know it, it's obvious. 12 Probably 8. First answer: at least 5 (you have to look at every horse). Second answer: 11. You can race five horses, replace 4th and 5th place horse by two horses from pool of horses that haven't raced, and continue doing this until all horses have raced. Since there are 25 horses, you need 1 race for the first five horses and 10 to go through the remaining 20. Third answer: 8. Round 1 (5 heats) : Race horses in heats of five. Eliminate all 4th and 5th place horses. (15 horses left) Round 2 (1 heat): Race winning horses from every heat. Eliminate 2nd and third place horses that lost to horses in round 2 that came third or worse. (7 horses left). Round 3 (1 heat): Pick any five horses. Race them. Eliminate bottom two and replace with remaining two horses. (5 horses left) Round 4 (1 heat): Eliminate bottom two. Note: after round 2 it may be possible to use some interesting decision tree mechanism to determine the three fastest horses using fewer horses per heat but you still need two heats to do that. This problem assumes horses don't get tired, no ties are possible and a horse's speed is deterministic race after race after race. Good assumptions for brain teasers, but not for real life. Show More Responses Actually, should be 7. Forgot that after round 2 you can eliminate one more horse leaving you with 6 horses, one of which (the winner of the second round), is the fastest horse of them all. One more race with the five horses not No.1 and you pick the top two. 6. First round consists of 5 races of 5 horses. Pull aside the winner of each race in the first round for the final heat and eliminate the bottom 2. 8. Run 5 races of 5 horses. (5) Put all the 3rd place horses in a race, winner is 3rd fastest. (6) Put all the 2nd place horses in a race, winner is 2nd fastest. (7) Put all the first place horses in a race, winner is fastest. (8) The third place horse was beaten by one of the 2nd place horses. So third stays in third. Same for the second place horse. chzwiz, r u sure u r not high? B, what happened in round 2? why 8 horses suddenly get eliminated by 1 race? again, do u know what you are smoking? oh, forget J,..... just speachless 7. chzwiz, your answer is incorrect. One of the first or second place horses could be 2nd fastest and/or 3rd fastest. I drew a grid to visualize the problem. First, run five races to establish 5 groups of internally ranked horses, and you can of course immediately eliminate 4 & 5 of each race. 1 2 3 x x 1 2 3 x x 1 2 3 x x 1 2 3 x x Then race 1st place horses, eliminate 4 & 5, and those they beat earlier. You can also eliminate the horses #3 beat, and the 3rd place horse from #2's first race. 1 ? ? X X 2 ? X X X 3 X X X X X X X X X X X X X X You know #1 is fastest. Race the remaining horses (2, 3 and ?'s), and the top two are 2nd and 3rd. After reading the above answers, this is the same as B's revised answer, but I found it easier to explain/visualize with the grid. @brad ... but isnt dat v dont have timer to know d ranking ... or my assumption is wrong?? I thought v know only 1 result of every race .. i.e. top 1 Spawn, it's true that you don't know timings, but you do know RANKINGS. I don't see errors in logic with each answer above. They may claim to discover the answer with fewer races, but they have too many assumptions or errors to be correct. To do this optimally and without any potential error, you must eliminate as many correctly placed horses as possible and eliminate the maximum number of non-win/place/show horses each round. Round 1: (Races 1-5) You must start with 5 heats @ 5 horses apiece. The non-Win/Place/Show horses of each round have been eliminated, leaving 15 horses. Round 2: (Race 6) You then race the top finishing horses against one another, leaving you with your overall fastest horse. We now have the Win horse, leaving only Place and Show as unknowns. This also eliminates the bottom two horses, leaving 2 horses from this race. There are also only two more unknown horses. Race 7) You may race the Place horses against one another. Only two survive this race, since we know that each of these horses can place 2nd at best. This leaves 2 horses from this race. (Race 8) You may also race the show horses of each round. Since they each have been beaten by two other horses in Round 1, only the 1st place horse of this round survives as the potentially 3rd best horse. This will leave 1 horse in this race to battle for the 2 remaining spots. Round 2 leaves 2 Horses (Race 6) + 2 Horses (Race 7) + 1 Horse (Race 8) = 5 Horses, for 2 unknown spots. Round 3: (Race 9) We can now have the final 5 horses race for the remaining two spots leaving us with the undisputed 2nd and 3rd places. Here is a more complex scenario below in which the top 2 horses come from the same original race and the later races are full of lame horses. Many of the solutions above do not address those problems. Each # is a horse, named by it's inherent ranking. X signifies 'eliminated horse' Race1 R2 R3 R4 R5 1-->R6 3-->R6 11-->R6 16-->R6 21-->R6 2-->R7 7-->R7 12-->R7 17-->R7 22-->R7 4-->R8 8-->R8 13-->R8 18-->R8 23-->R8 5X 9X 14X 19X 24X 6X 10X 15X 20X 25X Round 2: Race 6 (Winners) Race 7 (Places) Race 8 1 -->1st Place 2-->Race 9 4-->Race 9 3 -->Race 9 7-->Race 9 8X 11-->Race 9 12X 13X 16X 17X 18X 21X 22X 23X Round 3: Race 9 2P 3S 4X 7X 11X First Place = 1 Horse -- Race 6 Winner Second Place = 2 Horse -- Race 9 Winner Third Place = 3 Horse -- Race 9 2nd place To fix the formatting issues that appeared as spaces are eliminated above-- Race1________R2___________R3___________R4___________R5____ _1-->R6_______3-->R6_______11-->R6_______16-->R6_______21-->R6 _2-->R7_______7-->R7_______12-->R7_______17-->R7_______22-->R7 _4-->R8_______8-->R8_______13-->R8_______18-->R8_______23-->R8 _5X__________9X___________14X__________19X___________24X _6X__________10X__________15X__________20X___________25X Round 2: Race 6 (Winners)__________Race 7 (Places)__________ Race 8 1 -->1st Place_____________2-->Race 9______________4-->Race 9 3 -->Race 9_______________7-->Race 9 _____________ 8X 11-->Race 9______________12X____________________13X 16X_____________________17X____________________18X 21X_____________________22X____________________23X Round 3: Race 9 2P 3S 4X 7X 11X Less ascetically pleasing than the original, but it will suffice. Show More Responses This problem can be reduced to (viewed as) multiway mergesort: 1) split the horses into groups of five as if we had five files to sort 2) do a multiway mergesort but instead of sorting all horses, stop as soon as you get the top 3 We need one race per group to sort them (5 races total). And 3 more races to get the top 3. We will need 8 races. The interviewer might have been looking whether an applicant was able to spot this relation to algorithms or not. But if this was a brain teaser instead, maybe the answer is less than 8. The answer is definitely 7, here is a fantastic explanation: http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/ Randomly race the horses 5 times and keep a winner's bracket. The 6th race will determine the fastest horse. This is trivial. The 2nd and 3rd fastest could be in the winner's bracket or they could be the 2nd or even 3rd fastest in one of the losing brackets. Then we have to race 2nd and 3rd place from the winners bracket as well as from each original bracket, which had 5. This means we have 12 horses to try. Randomly keep 2 horses out and race 5v5. Keep the top two horses from both. We have 6 horses now. Race 3v3 and keep the top two, leaving 4 horses. Then race these. I count 11? Brute force divide and conquer solution = 18 races. Just be aware of the brute force solution in case there's restriction where we can't use the memory to save the first 3 places. Those who want a system that averages that fastest solving time, the answer will be 7 races.. Those gamblers who want an algorithm that gives the fastest possible solving time (all though sometimes it WILL take longer) the answer is 6. Race 1-5: First 5 races of five.. We randomly seed with no overlaps.. we use this to eliminate the bottom two from each race. I am going to use a two digit number labeling system where the first digit is which race in heat one they competed in and the second digit is which place they obtained in that heat.. These are the horses we have left: 11 12 13 21 22 23 31 32 33 41 42 43 51 52 53 Race 6: We have the winners from each heat compete, and for ease of explanation lets say that they ranked 11, 21, 31, 41, 51.. Now we know that 41, 51 and all the horses slower than them (their heats) are out.. also, we know that any horse slower than 31 is out (ie. 32 & 33), and we know that any horse that is at least two horses slower than 21 is out (ie 23). This leaves 11, 12, 13, 21, 22, 31.. 6 horses. Possible rankings: 11 12 13 21 22 23 31 32 33 Race 7 Rank 1 is already known.. and we just need to know how to organize 12, 13, 21, 22, and 31.. And look at that!! that's 5 horses! We race those 5 and the top two receive the overall rank of 2nd and 3rd. 5 races in round one, 1 race in round 2, 1 race in round 3.. it took us 7 races.. Option two: 6 Races Now, an alternate answer.. when we read "What is the minimum number of races to find the top 3 horses" we can interpret that maybe they don't care about this method working every time.. instead they want to hit up the Vegas Casinos and test their luck, and maybe save some track time.. If i was a gambling man.. i would race the first group of those that i thought looked the strongest.. I would eliminate 2 in that race (we are now down to 23 horses).. and then race the 3rd fastest multiple times and hope that he gets first in the remaining races, thus eliminating 4 horses each time. This is going to be painful for the horse that placed 3rd in heat one. Race 1: Eliminate 2, 23 horses remaining Race 2.. Eliminate 4, 19 horses remaining Race 3.. 15 horses Race 4.. Eliminate 4, 11 horses Race 5.. Eliminate 4, 7 horses Race 6.. Eliminate 4, 3 horses.. The original top 3 from Race 1. So using method 2, we completed this race in 6 races instead of 7! I messed up the possible ranks after race 6.. That should have read.. 11 12 13 11 12 21 11 21 22 11 21 31 Please forgive me. Brad's explanation is the perfect one. All other explanations are junk and impossible to read and follow. Round1: (5 groups) remaining horse 15 Round: (1 groups). Topper from each heat Round: (1 gounds). Forget about the 4th and 5th Heat horses (becoz their toppers are at last place) go to the 3rd position 6 races as the 25 horses are divided into 5 groups each grouping 5 horses in each group , then the winner from each group would be 5 then there should be last n final race to find the first , second and third placed horse . in this way we can find our top 3 horses :) It should be 11. In each race you can only eliminate 4th and 5th place simply because there's a chance that the top 3 in that single heat are the 3 fastest of all the horses. So each race you can select 5 random horses each race or keep the top three in the following race, the outcome is the same. Show More Responses I get 8 races to guarantee you get the top three. 5 races of 5 to get the fastest horse from each group. 1 race to determine the fastest overall. The second fastest horse can be in the group (x) that produced the fastest, 1 race with the remaining 4 fastest from the other groups and the second fastest from group x. That race will produce the second fastest overall guaranteed. 1 more race with the 3 or 4 from the original winners and the replacement from the group that produced the second place horse. That makes 8 races. I dont get it.. It shoudl be five races right? U will know how long each horse takes to cover same distance. Pick the three that took shortest. Y need more rounds? If u down vote my answer, u have the obligation to explain why 😜 Answer is 6. You will have 5 races and 5 winners. Next race with 5 winners is the 6th race and you get top 3. You're welcome. It would be 7, mainly because since there only 5 racers each round, then it would be tournament style. As you can tell, tournament style never determines the rankings in the short term. (Imagine if a new tennis player played against Roger Federer and he loses. He's not bad, he's just really unlucky haha) So in order to determine the answer, you would have to use massive logic and reasoning. First step is obvious: you get 5 sets of horses to race through 5 races. So the number is already at 5. We get the top horse in each one and note them. However, one problem is that you have to consider if fastest horses could lie all in the first, second, third, fourth, or fifth group. But we can't determine that yet, so let's race one more time with the winners of each race. Second step: Race with each winner from their groups. That makes 6 total races so far. Ok, now we can get somewhere with this. So now, its a question of which horses we can eliminate to determine the next race. Who can we eliminate though? Well, we can get rid of: - All the horses in the group with the last race that were 4th and 5th place. This makes sense since if the winner of their groups only made 4th and 5th place in the tournament style race, then they are definitely not the fastest horses. 15 horses remaining. - Well, we can also get rid of the last two horses of each group since we are only looking for the top 3. 9 horses remaining. - We also can get rid of the first place winner since we already know he is definitely the best. 8 horses remaining. - Since we already determined who the fastest horse is, now we have to determine who the second and third fastest horse can be. In that case, the second place horse from the last round can get rid of the third horse of that group, since he definitely has no shot of being the first or second fastest horse of this new race. Also, in the third group, we can get rid of the second and third horse in the group due to the same reasoning above. 5 horses remaining. Oh wow! We now have 5 horses left! This means we can just have a clean race and find the second and third fastest horse. So overall, the answer is 7 races! 7 In my opinion, you need 26 RACES to make sure that you get the top 3 without a timer. You need to know that without a timer if we plan only 5 races with 5 horses on each one, the last horse on the first group could end the race in 1 minute while the first horse on the second group (the winner) could end it in 2 minutes, which mean that the last horse of the first group is much faster than the first horse of the second group..and this is why we need to make a total of 26 RACES to determine the top 3 as follow: 5 RACES with 5 horses each .> We get the 5 winners from each race .> We race the 5 winners > We get the top 4 > We race the top 4 with one of the remaining 20 horses > we get the top 4 > we race the top 4 with one of the remaining 19 horses > we get the top 4 > we race the top 4 with one of the remaining 18 horses...etc until the last race then we select the top 3 winners from the last race. 5 RACES + 1 RACE + 20 RACES = 26 RACES |

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

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. 24 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 Responses Am 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 Responses <strong>Brutefoce Method : </strong> 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. <strong>Other Solution : </strong> 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 commentary nt a[N] = {1, 2, 3, 4}; int products_below[N]; int products_above[N]; int p=1; int p1=1; for (int i=0;i def 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 Responses p = 1 g = 1 for x in nums: g = g* x + p p = p + x return g |

How many credit cards does Amex issue in a year in US? 11 AnswersI knew it was an estimation problem, but I am not really good at doing fast math, so stumbled at a few places involving percentages. There is no exact answer, but the focus is in how you arrive at the answer. Cong8ss!! Even I gave the interview last month with same questions but didn't hear back anything from them....Did they call you or send you note to update this??Please advise.Thanks Thanks. I was contacted by the Sr.Director about 10 days after the interview and made the offer. Show More Responses Cool then I still have a chance :) Do you remember what type of questions they asked in online coding screen sharing ? I have an interview on next tuesday and i am nervous about typing code in a text editor . Can you give me some sample questions they asked ? These were fairly straight forward ones- FizzBuzz, Fibonacci for coding problems, couple of bitwise operations with XOR, regex for US phone number, abt 50% theory questions like interface vs abstract classes and uses of generics and SOLID principles. One question were I messed up a bit was 'Write the api for System.out.println()'. I didn't fully understand the question, then the interviewer clarified. Essentially, he wanted me to write the classes and methods (ignoring the actual logic code) that would allow the user to write System.out.println(). I used inner class to implement it. Good luck. Thank you , i cleared the first round . Can you give me more details on onsite interview ? How should i prepare ? What type of questions they are asking in the onsite rounds ? Technical stuff will be similar to initial screen, lots of theory, fibonacci/factorial code, debug a simple code block etc. Prepare for behavioral questions and estimation problems. There is a chapter in the book "How Would You Move Mount Fuji" by William Poundstone about problems like that. Good luck. I attended the Interview in Phoenix , HR contacted me today and said that the Cognitive interview did not go well as planned . So they are not going to proceeding with me , They asked me the same question "How may cards does AMEX approve each year " . I was prepared for this and i think i answered well for this question , but not sure what went wrong . I am curious to know good answer, what answer did you provide for the credit cards question ? Sorry to hear that. These things are sometimes very unpredictable. I don't remember the exact numbers I did that day, but It is an estimation problem. I started with US population- 300 million...cards will not be issued for ppl under 15 and old people, lets say 20%, so remaining 2.4 M. Similarly, subtract X% for people with bad credit, y% for people who bought card within last year, since they are unlikely to get another..and so on. Essentially, i started with max limit and subtracted an estimated % for the filters I thought were applicable. I remember in the end, the interviewers were not even looking at the final number I came up. So they probably just wanted to see how I approached the problem. 1 million. |

**1**–

**10**of

**10,164**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