# Engineering Interview Questions

Engineering interview questions shared by candidates

## Top Interview Questions

### Engineer at Eventbrite was asked...

Given a table that has parent's id and children id, write a query that return grandparents and grandchildrens 4 AnswersRelational schema - p_name and c_name make a composite primary key relation {p_name varchar, c_name varchar} select t1.Grandchild, t2.Grandparent from (select c_name as Grandchild, p_name from relation where p_name in (select distinct(r.p_name) from relation r join relation t on r.p_name = t.c_name)) as t1 inner join (select p_name as Grandparent, c_name from relation where c_name in (select distinct(r.p_name) from relation r join relation t on r.p_name = t.c_name)) as t2 on t1.p_name=t2.c_name order by t1.Grandchild; select t1.Grandchild as Grandchild ,t2.Grandparent as Grandparent from (select distinct(r.c_name) as Grandchild,r.p_name as parent from relation r join relation t on r.p_name = t.c_name) t1 ,(select distinct(r.p_name) as Grandparent,r.c_name as parent from relation r join relation t on r.c_name = t.p_name) t2 where t1.parent=t2.parent; select a.p_name as grandparent, b.c_name as grandchild from relation a join relation b on a.p_name=b.c_name Show More Responses Correct one select a.p_name as grandparent, b.c_name as grandchild from relation a join relation b on a.c_name=b.p_name |

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

You have a 100 coins laying flat on a table, each with a head side and a tail side. 10 of them are heads up, 90 are tails up. You can't feel, see or in any other way find out which side is up. Split the coins into two piles such that there are the same number of heads in each pile. 36 AnswersAnswer #1: Place 50 coins into two piles on its edges so that both have the same amount of heads in each pile, neither facing up or down. Answer #2: Trick question, place 50 coins in both piles and in theory they all have heads just not necessarily facing up or down. agree with 2nd ans Split into two piles, one with 90 coins and the other with 10. Flip over every coin in the pile with 10 coins. Show More Responses Just split into two piles, each with 50 coins. The question only asks 50 heads in each one, it doesn't ask for the number of heads up!!! Pick 10 coins from the pile, flip it and put it in the other pile. This will ensure that the number of heads up are equal in both the piles Pick 10 coins from the original 100 and put them in a separate pile. Then flip those 10 coins over. The two piles are now guaranteed to have the same number of heads. For a general solution of N heads and a total of M coins: 1.) Pick any N coins out of the original group and form a second pile. 2.) Flip the new pile of N coins over. Done. Example (N=2, M=6): Original group is HHTTTT (mixed randomly). Pick any two of these and flip them over. There are only three possible scenarios: 1: The two coins you picked are both tails. New groups are {HHTT} {TT} and when you flip the 2nd group you have {HHTT} and {HH}. 2.) The two coins you picked consist of one head and one tail. New groups are {HTTT} and {HT} and when you flip the 2nd group you have {HTTT} and {TH}. 3.) The two coins you picked are both heads. New groups are {TTTT} and {HH} and when you flip the 2nd group you have {TTTT} and {TT}. The question says "'You' can't feel, see or in any other way find out which side is up....' Can a team member? Cooperate with a fellow engineer, or other colleague, who can see the coins to solve the problem? Question has its answer in it... 10 coins are head up..... 90 coins are tail down..... so it means all 90 coins are head up.... Now, all you have to do is to split it into half. 50/50 Let's generalise the question to where there are n heads and any number of tails on the table. Select any n coins. This set will contain m heads, where m is between 0 and n inclusive, and n - m tails. The other n - m heads will be in the remaining coins. We now have two piles: the selection of n coins with n-m tails and the remainder with n-m heads. All we have to do is flip the selection so that the n-m tails become n-m heads, the same number as the heads in the remainder. This is a straightforward extension of the 'pick any 10 coins and flip' answer correctly given above by several people. All of you are over thinking it. Read the last bloody line, "Split the coins into two piles such that there are the same number of heads in each pile" They're not asking for the heads to be up or down, just an equal amount & every coin has a head side so dividing the pile equally achieves that. 100 coins total, 10 of them are heads up, 90 are tails up. Meaning all of them are heads up AND tails down. Split it 50/50 and you are done. It is not as easy as to just split it. And it says heads UP tails UP. Given 10 h, 90 t. Pick some random 10 coins call it P1. Rest is P2. In P1, (10-x) heads, (x) tails In P2, (x) heads, (90-x) tails Flip the coins in P1. In P1, (x) heads and (10-x) tails P1 and P2 have the same number of heads. reading these answers is such a confidence builder. Show More Responses I agree to trev, don't think anyone read the question. we already have 2 piles --> 90 coins with tails up and 10 coins with heads up, just flip over 10 of the coins from 90 coins that have tails up, we will have same number of coins with heads up in each pile. get all coins in your hands, shake them, drop them. for each coin there is a 50% probability to lay heads up, and 50% probability for tails down. now split i half question doesn't need to look faces of which side is up after splitting it in two piles. split all coins in two part of 50 50 and they all have heads ...and thats what questioner asking..! and move them to the 10-coin pile. Take 40coins from 90-coin pile, flip them over and move to the 10-coin pile. It's really depends on whether Apple is hiring Software Engineers who are collaborators, mathematicians or tricksters. It's clear that Apple does hire Engineers who listen to the question accurately. Make two groups at random for 10 and 90 coins. Example:- G1(10) G2(90) case 1:- 6H,4T 4H,86T case2:- 3H,7T 7H,83T Now flip all coins of smaller group G1(10). The result will always have same Heads in each pile. G1(10) G2(90) case 1:- 6T,4H 4H,86T case2:- 3T,7H 7H,83T We just get 5 coins head up put in each piles ==> we get the same number of head up in each pile. They just ask we "Split the coins into two piles such that there are the same number of heads in each pile" . They didn't say that we don't kow what is coin head up and they mixed together. "The question says "'You' can't feel, see or in any other way find out which side is up....' Can a team member? Cooperate with a fellow engineer, or other colleague, who can see the coins to solve the problem?" This is the best answer yet! Completely out of the box answer and yet so simple. Show More Responses Flip every other coin, 90 Tails will get split into 45 Heads and 45 Tails. Similarly 10 Heads will get converted to 5 Head and 5 Tails, so now we have 50 heads (45 + 5) and 50 tails (45 + 5). Then just split them into two equal groups. Find complete answer with description here: http://www.puzzlevilla.com/puzzles/puzzle/172 Answer Make a pile of 10 and flip them over. Then the number of heads is equal in both piles. question says both group should have equal heads, but doesnt specifiy, it should be up, hence, just grouping 50 each would solve the problem This is a screw you question, but yeah if you take out 10 coins you can have anywhere between 0-10 heads for every head you have you have one less head in the other pile and one less tail in your pile of 10 coins. So if you have 100 coins 10 heads and you take lets say 10 coins 0 heads, 10 tails. The 90 coins has 10 heads. 1 heads, 9 tails. The 90 coins has 9 heads (you stole one when selecting 10 coins). 2 heads, 8 tails. The 90 coins has 8 heads (same you stole 2 when selecting 10 coins ect). 3 heads, 7 tails. The 90 coins has 7 heads. 4 heads, 6 tails. the 90 coins has 6 heads. 5 heads, 5 tails, the 90 coins has 5 heads. 6 heads, 4 tails, the 90 coins has 4 heads. 7 heads, 3 tails, the 90 coins has 3 heads. 8 heads, 2 tails, the 90 coins has 2 heads. 9 heads, 1 tails, the 90 coins has 1 heads. 10 heads, 0 tails, the 90 coins has 0 heads. As you can see whenever you take out 10 because your not only stealing from the pile of 90's heads your also offsetting the pile of 10 coins tails by 1 equally you have an equal connection between the tails you have in the pile of 10 coins as you do heads in the pile of 90 coins that your tails in 10 coins pile always equals heads in 90 coin pile. So you just flip over each coin in the pile of 10 coins and your tails becomes heads. So if you selected 1 head and in the 10 coins pile you had 9 heads in the 90 coins pile and 9 tails in the 10 coins pile, you are guaranteed after flipping each over once to have 9 heads in the 10 coins pile as tails becomes heads and 9 heads in the 90 coin pile, and ect, ect. This stands true for any pile that you know the amount of one category and 2 options, If you know you have 25 of one things, despite how many things there are if each thing had only two options like heads or tails, you know selecting 25 of them the same amount you know of one thing that when taking out 25 or the equal number of what you know of one thing is in there that what you unsucessfully try to filter out is the inverse of what you selected successfully to take out. Pick 10 coins, flip them and form a separate pile. The no.of tails in both pile will be equal inspite of your choice being a tails up coins or a heads up coins. Coz when u pick a tails up coin u r reducing the no.of tails up in the first pile and since u flip it its gonna b a heads up coin the second pile, if u r picking up a heads up a coin u turn it into a tails up coin in the second pile so that it can cancel out one tails up coin in the existing first pile. If it means heads up then separate the coins into one pile of 90 one pile of 10 then flip the ten coins it works with all scenarios Of sides you ended up choosing also like to point out that we can't feel them so we probably can't use our hands to flip them but I assume they would allow us to use something as how else would we separate them The answer lies in the exact wording of the question "Split the coins into two piles such that there are the same number of heads in each pile. " It does not specify heads need to be face up, so you would simply split the piles in 50 each and you have the same number of coins with heads in each pile. Take ten coins (consider as one pile, Pile A and other 90 coins as another pile, Pile B). Now you have two piles. Turn all coins as in pile A, you will end up with same number of heads in both piles. Ex: Scenario 1: Consider in Pile A, there are 2 heads and 8 tails. Hence in Pile B there will 8 heads.Now when you turn all the coins in Pile A you will end with 8 heads in Pile A. Hence both Pile A and Pile B have same number of heads. Scenario 2: Consider in Pile A, there are 10 heads. Hence in Pile B there will be 0 heads.Now when you turn all the coins in Pile A, you will end with 0 heads in Pile A. Hence both Pile A and Pile B have same number of heads. Scenario 3: Consider in Pile A, there are 0 heads. Hence in Pile B there will be 10 heads.Now when you turn all the coins in Pile A, you will end with 10 heads in Pile A. Hence both Pile A and Pile B have same number of heads. Show More Responses Take 10 coins.Split into two piles of 5 each.Flip all coins in one pile.Both piles now have equal heads and tails.Take another 10 and go through the same procedure.Follow the same process for the entire original pile.You end up with two sets of 5 piles having equal no. of heads and tails.Combine all 5 piles on each side and it's done. Its very simple. step 1 take group of 10 coins from all now flip this pile and you will get your answer. how? lets see cases 100 total ( 10 H + 90T) so you get group of 10 from them so lets assume you will get 4 h+6T , and (6H + 84T) then flip this smaller one new group will be 4T+ 6H so now we 2 groups 1 new 1 old 4t+6h and 6h+85T both have same number of heads .... LITERAL ANGLE Split 50/50. Both piles have the same number of heads. Parameters do not require each pile to have the same number of heads facing upward. TEAMWORK ANGLE Ask the most efficient, skilled coin identification analyst at Apple to identify the coins so the skilled sorting robot can separate the piles equally. PATRONIZING ANGLE Take a picture of the table with your iPhone and sending to a laborer hired to come sort for you via a services app in the app store. NEXT LEVEL QUANTUM ANGLE If the coins are in no way observable, the question is impossible to answer because the coins are sitting next to Schrodinger's cat and thus are in a state of both heads and tails until observed. |

You are in a boat in a pool with a rock in your hand. You throw the rock into the pool. Does the water level rise, drop, or stay the same? 13 Answersdepends on how big the pool is and how accurately you can measure the water rise you're already in the pool with the rock, so the water displaced is the same...this other guy is stupid If the rock were neutrally buoyant the water level would remain the same. It is heavier than water which causes it to displace more than its own volume while in the boat compared to at the bottom of the lake. Therefore the water level of the lake would go down. Show More Responses At the moment the rock leaves your hand the water falls in the pool. When the rock enters the water the water level of the pool rises again to the level it had before you threw it. really? I thought the water would go up ? These answers are troubling. The only correct answer so far is Ben. The water level goes down. I'm not a mechanical engineer, but I did stay in a Holiday Inn Express last night. I hope no one else who has answered this question here (except for Homebrook) is a mechanical engineer. When you add the volume of the rock and subtract the volume of water previously displaced by the boat+rock, there is no change in the water level of the pool. Another way to answer is: The water level measured at the side of the pool remains the same. The boat becomes more buoyant and the water level measured at the side of boat falls. The weight of the boat plus you plus the rock has already displaced the height of the water. The only time the water level will change will be when the rock is mid air. M no Bbbbbbbbbbbbbbbbbbvvbvbbvbbb. B.B. BNb. Bbbb Bbvbbbbbbb Bbbbbbbbb B.B. Bbbbb V bbbb BNb B.B. BNb Bbbbbb BNb BNb Bbbb. BNb B b. Bbbbbbbb. N n. Bbbb. B B.B. N BNb bbb Nnnnn Nnnn nnn Nnnn Nn N. Nn N M Mm. I. N. M M m Mmm n nnn Mmm mmnmmmnm Mmnmmmmm Mmm my Mmmm Mmm Mmm Mmmmmmmmm m Mmmmmmmm It will raise by the same volume of the rock. First time, the water buoyant force is equal to the mass(boat + person + rock).g /subsequently, the water got displaced was also that much, the water level on the pool will be higher. second time, since rock is gonna deposit down to the bottom of the pool, it'll be like: water displacement = (boat + person).g + the volume of the rock (but it's probably much less than the water displacement it could have created when it's on the boat). There is no way that rock is displacing the same amount of water as it did previously. (1kg gold (Density: 19.30 g/cm3) and 1kg silver(Density: 10.49 g/cm3) in normal situation has different volume, so when deposited to the bottom, silver will displace more water than gold, yet both displace less water than when rock was sun-bathing on the boat) In conclusion, first time the water level was higher both on the pool wall and the mark on the boat, second time it'll be lower on both end. Depends on how big the rock is LOVE SPELL CASTER (DR. GBOJIE) THAT HELPED ME BRING BACK MY DIVORCE HUSBAND CONTACT HIM NOW FOR ANY KIND OF HELP With so much in my heart i am here to express myself on how Dr. GBOJIE saved my marriage from divorce. Myself and my husband were having some misunderstanding and it was tearing our marriage apart to the extend my husband was seeking for a divorce. So i have no option than to go to the internet to seek for solution to my problem it was there i came across Dr. GBOJIE details and about how he has helped a lot of people by restoring there relationship. I contact Dr. GBOJIE and in less than 48 hours my husband cancelled the divorce papers. Now myself and my husband live together in peace and harmony all thanks to Dr .GBOJIE for saving my marriage from breaking up. Dr. GBOJIE contact information are via email: gbojiespiritualtemple@yahoo.com , gbojiespiritualtemple@gmail.com or call his phone number or WhatsApp: +2349066410185 .or check out his website :http://gbojiespiritualtemple.website2.me |

### 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))) |

Describe and code an algorithm that returns the first duplicate character in a string? 12 AnswersSimple Python example. Not sure it's most efficient. def findDup(str): match=[] i=1 while (i first clarify if it is ASCII or UNICODE string For ASCII, create BOOL checkArray [128] = {false}; walk the string and update the index of checkArray based of the character. for (int index=0;index< strlen(str); index++) { if (checkArray[str[index]] == true) { printf (str[index]); return; } else { checkArray[str[index]] = true; } } public class FirstDupCharacter { public static void main(String[] args) { System.out.println(findDupCharacter("abcdefghiaklmno")); } private static Character findDupCharacter(final String input) { final Set set = new HashSet(); Character dup = null; for (int i = 0; i < input.length(); i++) { if (set.contains(input.charAt(i))) { dup = input.charAt(i); break; } else { set.add(input.charAt(i)); } } return dup; } } Show More Responses String samp = "Testing"; samp = samp.toLowerCase(); char chararr[] = samp.toCharArray(); int size = chararr.length; char repeat = ' '; for (int i=0;i for (int i=0;i public static in findDuplicateChar(String s) { if (s == null) return -1; char[] characters = s.toCharArray(); Map charsMap = HashMap(); for ( int index = 0; index < characters.length; index++ ) { // insert the character into the map. // returns null for a new entry // returns the index if it previously if it existed Integer initialOccurence = charsMap.put(characters[index], index); if ( initialOccurence != null) { return initialOccurance; } //there where no characters that where duplicates return -1; } } Another python solution: def findFirstNonRepeatedCharInOneIteration(str1): for i,j in enumerate(str1): if j in str1[:i] or j in str1[i+1:]: print "First non-repeated character is "+ j break str1 = "abcdefglhjkkjokylf" findFirstNonRepeatedCharInOneIteration(str1) function getFirstDuplicateCharacter(str) { const seen = new Set(); for (const char of str) { if (seen.has(char)) return char; seen.add(char); } } import java.io.*; import java.util.*; /* * code an algorithm that returns the first duplicate character in a string? */ class Solution { public static void main(String[] args) { String input = ""; int j = removeduplicate(input); if(j == input.length()){ System.out.println("String has unique characters" ); } else{ System.out.println("duplicate character is "+input.charAt(j)); } } public static int removeduplicate(String input){ Set set = new HashSet(); boolean flag = false; int i =0; for(; i import java.io.*; import java.util.*; class Solution { public static void main(String[] args) { String input = ""; int j = removeduplicate(input); if(j == input.length()){ System.out.println("String has unique characters" ); } else{ System.out.println("duplicate character is "+input.charAt(j)); } } public static int removeduplicate(String input){ Set set = new HashSet(); boolean flag = false; int i =0; for(; i public static int removeduplicate(String input){ Set set = new HashSet(); boolean flag = false; int i =0; for(; i Anyone can share Expedia Group interview questions? I'll pay $20 bounties for the interview information on Rooftop Slushie. https://wwww.rooftopslushie.com |

In a given sorted array of integers remove all the duplicates. 8 AnswersIterate the array and add each number to a set, if number is already there, it won't be added again, thus removing any duplicates. Complexity is Big-O of N The array is already sorted, no need for a set. example: 2,2,5,7,7,8,9 Just keep tracking the current and previous and the index of the last none repeated element when found a difference copy the element to the last none repeated index + one and update current and previous, no extra space and it will run in O(n) public RemoveDuplicates() { int[] ip = { 1, 2, 2, 4, 5, 5, 8, 9, 10, 11, 11, 12 }; int[] op = new int[ip.Length - 1]; int j = 0, i = 0; ; for (i = 1; i <= ip.Length - 1; i++) { if (ip[i - 1] != ip[i]) { op[j] = ip[i - 1]; j++; } } if (ip[ip.Length - 1] != ip[ip.Length - 2]) op[j] = ip[ip.Length - 1]; int xxx = 0; } Show More Responses def removeDuplicatesSecondApproach(inputArray): prev = 0 noRepeatIndex = 0 counter = 0 for curr in range(1,len(inputArray)): if (inputArray[curr] == inputArray[prev]): counter = counter + 1 prev = curr else: inputArray[noRepeatIndex+1] = inputArray[curr] noRepeatIndex = noRepeatIndex + 1 prev = curr inputArray = inputArray[:-counter] return inputArray if(inpArr[i] == inpArr[i+1]) { int repeats = 1; opArr[opPos] = inpArr[i]; int j = i + 1; while(j+1 <= inpArr.length - 1 && inpArr[i] == inpArr[j+1]) { j++; repeats++; } opArr = Arrays.copyOf(opArr, opArr.length - repeats); i = i + repeats; } else { opArr[opPos] = inpArr[i]; } opPos++; } for(int i =0; i<=opArr.length-1;i++) { System.out.println(opArr[i] + ","); } Apologies for the previous incomplete answer int[] inpArr = {1,2,2,3,4,5,5,5,8,8,8,9,13,14,15,18,20,20}; int[] opArr = new int[inpArr.length]; int opPos = 0; for(int i= 0; i<=inpArr.length - 1; i++) { if(inpArr[i] == inpArr[i+1]) { int repeats = 1; opArr[opPos] = inpArr[i]; int j = i + 1; while(j+1 <= inpArr.length - 1 && inpArr[i] == inpArr[j+1]) { j++; repeats++; } opArr = Arrays.copyOf(opArr, opArr.length - repeats); i = i + repeats; } else { opArr[opPos] = inpArr[i]; } opPos++; } for(int i =0; i<=opArr.length-1;i++) { System.out.println(opArr[i] + ","); } public static void removedup(int[] input){ int count =1; int i=0; for( ;i public static void removedup(int[] input){ int count =1; int i=0; for( ;i |

Suppose you have a matrix of numbers. How can you easily compute the sum of any rectangle (i.e. a range [row_start, row_end, col_start, col_end]) of those numbers? How would you code this? 8 AnswersIt can be done in constant time by precalculating sums of some basic rectangles (extending all the way to the border of the matrix). That precalculation times time O(n) by simple dynamic programming. Please elaborate, which "basic rectangles"? Are you recursively dividing each rectangle into 4 smaller rectangles? Precalc time for doing that is not O(n)?!? Compute the sum of the rectangles, for all i,j, bounded by (i,j), (i,m), (n,j), (n,m), where (n,m) is the size of the matrix M. Call that sum s(i,j). You can calculate s(i,j) by dynamic programming: s(i,j) = M(i,j) + s(i+1,j) + s(i,j+1) - s(i+1,j+1). And the sum of any rectangle can be computed from s(i,j). Show More Responses Awesome!! The answer is already popular in computer vision fields!! It is called integral imaging. See this page http://en.wikipedia.org/wiki/Haar-like_features It wasn't 100% clear to me, then I found the Wiki page http://en.wikipedia.org/wiki/Summed_area_table Let a[][] be the 2d array, int i=0; for( j = row_start; j <= row_end; j++) for( k = col_start; k <= col_end; k++) i+=a[j][k]; Iterate over matrix as an array storing (new sums array) in each position the cumulative sum up to that point. For each row in the desired submatrix we can compute its sum as a difference between its end and start positions. Repeat for other rows. Add up all the row sums. |

### 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) |

### Product Design Engineer at Apple was asked...

What are the different ways you can you tell if this part is steel or aluminium. 4 AnswersSimply by using a magnet, Steel has metallic properties, and the magnet will connect. Aluminium will do nothing. Many stainless steel alloys are not magnetic, so if your magnet is attracted to the material you will definitely know it is steel, but if it doesn't you will not know what the material is. Simple methods would be density (feeling the mass of the object), surface finish (color, texture). If coated that may give you the answer i.ie anodized would indicate aluminium. For more information I would go for EDX( Energy-dispersive X-ray spectroscopy) and possible a cross section to look at the grain structure. Show More Responses By far the easiest way is to test for material properties. -density -hardness -modulus of elasticity I would choose hardness. Strike each item with an equal force, which one deforms more? Thats aluminum. You could probably pull this test off with a hammer. The simplest solutions is always the best. |

**1**–

**10**of

**119,580**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Mechanical Engineer
- Intern
- Engineering
- Senior Software Engineer
- Process Engineer
- Electrical Engineer
- Project Manager
- Project Engineer
- Systems Engineer
- Senior Engineer
- Software Developer
- Design Engineer
- Manufacturing Engineer
- Manager
- Analyst
- Engineer I
- Consultant
- Business Analyst
- Director