# Interview questions in California

Google Interviews in California

www.google.com / HQ: Mountain View, CA

2,649 Interviews in California (of 10,402)

Apple Interviews in California

www.apple.com / HQ: Cupertino, CA

1,653 Interviews in California (of 7,323)

Facebook Interviews in California

www.facebook.com / HQ: Menlo Park, CA

1,523 Interviews in California (of 5,317)

## Interview Questions in California

You have a birthday cake and have exactly 3 slices to cut it into 8 equal pieces. How do you do it? 39 AnswersCut in half, stack, cut in half, stack, cut in half. All you have to worry about is the 45 degree rotation of one of the 4 pieces after the second cut. Blade can be kept in place, like a paper cutter, as to minimize the margin for error. Slice it horizontally across the middle creating two equal halves top and bottom. Then simple two slice cross from above like normal. Cut each slice into 3 slices. Then eat one of them. Show More Responses This is really an easy one. First cut into half across the top, then cut the halves in half also across the top (you now have 4 equal pieces) then cut across the middle = 8. No, Jason and Sharon, you will only wind up with 6 slices. z, too many stacks. You need to cut in half, then make another cut - to get four pieces. NOW you stack these four pieces and make the last third cut - and you get 8 pieces. A rather easy lateral thinking question. Alina's got it. The stacking seems to be the "right" answer. But this is a stupid question. Who stacks cake? The frosting from the bottom slice would meld with the stacked slice, thus making the cake inseparable. I wouldn't get the job because I would swear at the interviewer for asking a dumb question. What good is an answer to this question if it wrecks the cake? Assuming the cake is square: slice 1: cut horizontally to create 2 equal pieces slice 2: cut vertically to create 4 equal pieces slice 3: line up all 4 pieces of cake side by side and cut horizontally to create 8 equal pieces. don't stack, it will ruin the frosting. With a knife Alina would be penalized for not being able to count past 6. But then, she could get a job at another company where they appreciate people who say someone's idea is wrong, then put forth the same idea and take credit for it. A new solution for you: who says slices have to be a straight line and not circular? I would cut a concentric circle in the middle (would have to calculate the radius compared to the whole), and then slice an X with the remaining 2 cuts. It will look like a target. If done correctly the sizes will be the same, it says nothing about having the same shape! I guess it's much easier if you think of two planes: first cut in half, then to quarters. That's the easy part. Now look at the cake from the side, and cut it across... Each quarter is cut into two and all pieces are equal. I would consider the interviewer's emphasis on "equal pieces." While my first thought was to bisect across each of the three dimensions, half of the pieces would end up with less frosting than the other half. Stacking the pieces would result in frosting transfer, which would also screw up some of the pieces. Therefore, I'd go with lining the pieces up and have a large knife on hand for each bisection. Hey, people get crazy about their cake slices. Show More Responses I would take a different approach to this. First of all the question asks for the cake to be cut into 8 equal pieces, not 8 identical or 8 of the exact same size. Equal doesn't always have to mean the same, just equivalent to. First I would find out who I am cutting the cake for, if its 4 old ladies and 4 young guys, equal pieces would not mean that they all needed to be the same. If everybody wanted the exact same amount of cake I would figure out a way to give everybody 12.5% of the entire cake volume, but if some wanted larger or smaller pieces I would come up with a way to satisfy each individuals desire. If you know how to cut an arbitrary shape in half, you have the solution. After every round, plan the cuts for each individual piece. Then align them so the proposed cuts are in one straight line. Make a cut. This way you can cut any cake into 2^n equal size pieces with n cuts. An interesting question is, if you start with one connected piece, will you always be able to end up with connected pieces. Think of cutting letter S in the middle, like this: $. You end up with two equal figures that are not connected (or, in other words, with 4 pieces). It's also easy to design a cake that can be split into 8 pieces with one straight cut. I LOVE Andrew's answer! Eat one of the freakin' pieces. That's the corporate way in America anyway. Mike is either a socialist, or works in non-profit, or government. I thought "slice them long ways" but then someone misses out on the freaking frosting, which is the best part. UNLESS, it's a layer cake. Cut 'em all in thirds and give the extra to the birthday boy/girl to take home. First I'd yell at whoever cut the cake incorrectly to start with. He's ruining the party. Then I'd squish the 3 pieces of cake together and re-cut the cake into the required 8 pieces. Boom. This is as easy as pie. Viewing the cake from the top, make 1 cut vertically down the middle of the cake and another horizontally. Viewing the cake from the side, make your third cut horizontally through the middle; QED three slices and 8 pieces of cake with a beamsplitter and prisms it could be done in 1 (with a laser) That's an oddly presented question that is understood 2 ways: - 3 cuts allowed to cut one cake in 8 pieces. Which yields cut in 4 parts, then split those in 1/2 again with the last cut, either by stacking, realigning the slices or making a round cut. - 3 pieces of cake must be re-cut to make 8 equal parts. Which is an impossibility unless one piece is 2/3 smaller than the other 2. That yields different answers like cutting in 3, and eat one to leave 8 pieces. They key to answering any of the brain teaser questions is to ask a few critical questions before even attempting to answer. I would start with: Is the original cake round or square? If square, line up all three pieces and recut to be 4 equal widths of cake. If round, was the original cake cut in 6 or 8 pieces? If 6 pieces you have 1/4 of a cake = easy to redivide into 8 equal slices. If 8 pieces, you have 1/3 of a cake and a little math needs to be applied to create 8 equal slices. First slice a strip off each of the 3 slices to create a fourth slice. then divide each in 1/2 to make 8 equal slices. Cut each slice into 8 small slices. Then give each person 3 small slices. Show More Responses There are some posting above who seem to not have a good grasp of numeric's. The answer is not that difficult. First, presume the pieces are not equal size (nothing states they are). Second, presume two pieces are of equal size and the third piece is twice that size. Third, cut vertically (the most usual manner in which to cut cake) the 2 equal pieces (we now have 5 pieces -4 the same size and one larger piece). Fourth, cut the large piece in half, then those two pieces in half again. Fifth, voila, one now has eight equal pieces of cake. Hmmm, I always assumed they meant three knife cuts by the word "slice" Kind of interesting to me that others assumed the cake was given to you in 3 parts as defined by the word "slice" I'd say that you should cut the cake horizontally using the knife as a measuring device to find the exact center of the circle, then cut vertically using the same method, then take each quarter , using the knife as a straight edge, build an alignment diagram that places each set of two quarter pieces point to point along an axis that defines their center lines, and cut all 4 quarter slices with a single cut of the knife ( defined by the word slice ). Put it all in a blender. Pour each of the resultant mixture onto a plate or into a bowl. 1. assemble 3 sliced cakes into a big cake (original shape) 2. cut it half (don't care about the indentation) , you would get 2 piece of cake 3. cut it half again, you would get 4 pieces of cake 4. cut all of them half again, that's finish. To those who think it means you start with 3 pieces ("slices") of cake, READ IT AGAIN. It says (emphasis added): “You have a birthday cake and have exactly 3 slices to cut IT into 8 equal pieces." Get it? "... to cut IT [the cake] into 8 equal pieces."... There is NO WAY it means to cut 3 slices of cake, otherwise it would say "...exactly 3 slices to cut into...". And Mike: "equal doesn't mean same, just equivalent". That's the funniest (and stupidest) thing I've heard all day. Anyway, since 2^3 = 8, you have to stack. Assuming a round cake: Cut (or "slice") 1 creates 2 semi-circles. Stack them. Cut 2 creates 4 quarter-circles. Stack then Cut 3 creates 8 1/8th circles. is the 3 slices equal in size? Great answer and explanation here: http://www.programmerinterview.com/index.php/puzzles/birthday-cake-8-pieces/ Make sure the guest of honor has Blown out candles 1st! (was not specified but hey so were many other things) If the birthday boy/girl is under the age of 10, I am not too sure you want to be messing with their cake!! Cakes come in many different sizes and shapes...ESPECIALLY Birthday Cakes!!! ACK They even come in characters and shapes you can NEVER get into equal pieces but, back to the solution! Will use 2 shapes: Round and Square! Cut 1: Parallel to cutting board and horizontal to create 2 layers of equal depth; Cuts 2 and 3: Perpendicular to cutting board once then rotate 90 degrees and repeat! Now give it to the Kid in the high chair to for quality control/assurance! Like Andrew, I would eat one piece and then cut the 2 in four equal pieces. Remember 1 whole cake, 3 slices with a knife = 8 equal pieces Place cake flat on table. Grab a knife big enough to cut the cake horizontally. 1st cut - Cut the cake horizontally leaving the cake flat on table as if the cake still in one single piece. Now you have 2 cakes instead of one. 2nd and 3rd cut - cut through the cake vertically in the form of a cross. Now you have 8 equal pieces of cake. As if you had cut 2 cakes in 4 pieces each. Show More Responses I would state that I only eat cakes in the shape of circle. then 3 equal cuts across the middle. think of it like a pizza... or a pie.... or a pizza pie. Remember these questions are made to have you think outside the box. Not all cakes are square. cut the diagonal portion then centre line of cake Cut each of the 3 slices into 8 equal parts which makes the slice count 3*8 = 24, Divide the 24 between 8 people 3 each. Cut 2 slices into 4 pieces each, cut the third one into 8 pieces. Separate 2 of the 3 slices, dividing 2 slices for 8 people is easy (each slice in 4) Then with the left piece I divide it in 8 and offer one to each person. One more: I could put all the 3 pieces together and re slice into 8 equal pieces. |

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

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

### Data Scientist Intern at LinkedIn was asked...

Find the second largest element in a Binary Search Tree 16 Answersfind the right most element. If this is a right node with no children, return its parent. if this is not, return the largest element of its left child. One addition is the situation where the tree has no right branch (root is largest). In this special case, it does not have a parent. So it's better to keep track of parent and current pointers, if different, the original method by the candidate works well, if the same (which means the root situation), find the largest of its left branch. if (root == null || (!root.hasRightChild() ) { return null;} else return findSecondGreatest(root, root.getValue()); value findSecondGreatest(Node curr, value oldValue) { if(curr.hasRightChild()) { return (findSecondGreatest( curr.getRightChild(), curr.value)); } else return oldValue; } Show More Responses Above answer is wrong. it has to be something like this. public static int findSecondLargest(Node node) { Node secondLargest = null; Node parent = null; Node child = node; if (node!=null && (node.hasLeftChild()||node.hasRightChild())) { if (node.hasRightChild()) { while (child.hasRightChild()) { parent = child; child = child.rightChild(); } secondLargest = parent; } else if (node.hasLeftChild()) { child = node.leftChild(); while (child.hasRightChild()) { child = child.rightChild(); } secondLargest = child; } } return secondLargest; } The above answer is also wrong; Node findSceondLargest(Node root) { // If tree is null or is single node only, return null (no second largest) if (root==null || (root.left==null && root.right==null)) return null; Node parent = null, child = root; // find the right most child while (child.right!=null) { parent = child; child = child.right; } // if the right most child has no left child, then it's parent is second largest if (child.left==null) return parent; // otherwise, return left child's rightmost child as second largest child = child.left; while (child.right!=null) child = child.right; return child; } Soln by "mindpower" works. Thank you. I am trying to solve a similar problem Find the 2nd nearest high(in in-order traversal) value for a given node Eg: Given nums: 12 7 14 3, construct a BST. If the given value is: 7 then we should return 14 (in the sort order: 3, 7, 12, 14) if the given value is: 3 then we should return 12 (in the sort order: 3, 7, 12, 14) Generic solution in C# for any k. Notice that this example can be easily changed to find the k-th smallest node by doing a depth-first recursion on root.Left first, and then a tail recursion on root.Right. public Node GetKthLargest(int k) { return GetKthLargest(ref k, this.Root); } Node GetKthLargest(ref int k, Node root) { if (root == null || k < 1) return null; var node = GetKthLargest(ref k, root.Right); if (node != null) return node; if (--k == 0) return root; return GetKthLargest(ref k, root.Left); } recursion is not needed. SecondLargest(Node root, Node secondLarge) { if(root.right==null) return root.left; Node secondLargest = root; while(secondLargest.right.right==null) secondLargest=secondLargest.right; return secondLargest; } int getmax(node *root) { if(root->right == NULL) { return root->d; } return getmax(root->right); } int secondmax(node *root) { if(root == NULL) { return -1; } if(root->right == NULL && root->left != NULL) { return getmax(root->left); } if(root->right != NULL) { if(root->right->right == NULL && root->right->left == NULL) { return root->d; } } return secondmax(root->right); } In-order traverse the tree. The second last element in the array in the answer. In Python: def find_second_largest_bst_element(root, parent=None): if parent is None: # BST root if root.right is None: # no right subtree if root.left is not None: # if a left subtree exists... return root.left else: # root is the only element of the BST return False else: if root.right is None: # right-most element if root.left is not None: # left subtree exists return root.left else: # leaf return parent else: # check right subtree find_second_largest_bst_element(root.right, root) find_second_largest_bst_element(root) For kth smallest, descend the left subtree first. class Node: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def findKthLargest(root, k): global count if root is None: return findKthLargest(root.right, k) count += 1 if count == k: print root.value return findKthLargest(root.left, k) count = 0 r = Node(10, Node(5, Node(2), Node(7)), Node(30, Node(22), Node(32))) findKthLargest(r, 3) // solution in java // main routine Node findSecondMax(Node root) { if(root == null || (root.left == null && root.right == null) return null; else { Node max = findMax(root); return (max.parent == null) ? findMax(max.left) : max.parent; } } //helper routine, recursive implementation.... can also be done non-recursively Node findMax(Node root) { return (root.right == null) ? root : findMax(root.right); } Show More Responses Find the largest number in the binary tree and delete it. And again find the largest number. Short and fast. Reverse in-order traversal of the BST, keeping a count of # of visited nodes. This methods works great to return the kth largest element in a BST. mindpower's solution looks right |

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

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. |

### Sales Associate at Bloomingdale's was asked...

how do you attempt to sale when there are no customers in the sore? 4 Answersby calling people and begging them to come to the store to shop,no kidding! use the time to call your clients and tell them about upcoming events in the store. Be sure to suggest that they come by to shop with you. Contacting my Clients. Sometimes when starting out you do not have clients and I recommend asking friends and family to ask around for people to come in and as well posting events online and in neighborhoods. It sounds foolish but you will notice a difference in your paycheck and when you meet your goals and pre-sales. Show More Responses Through my online website |

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? 10 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. |

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

### Software Engineer In Test at Google was asked...

Implement a binary tree and explain it's function 4 AnswersBinary Search tree is a storage data structure that allows log(n) insertion time, log(n) search, given a balanced binary search tree. The following implementation assumes an integer bst. There's a million implementations. Just look on wikipedia for search and insert algorithms. Hi Xin Li, A binary tree is not the same as binary search tree.. A binary tree is a tree in which every node has atmost two children nodes. It is a k-ary tree in which k=2. A complete binary tree is a tree in which all nodes have the same depth. The fact is ttttttt t t. T to t. To. A a aaAs Sdsassss. Show More Responses 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) |

**1**–

**10**of

**213,822**Interview Questions