# Software Engineering Interview Questions

Software engineering interview questions shared by candidates

## Top Interview Questions

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

### Software Engineer at Dell Technologies was asked...

Suppose you are writing a test script to test a function running in a process over night. How do you make sure that if the process is halted, your test function will be able to detect that. 1 AnswerAnswer: run your test function in an independent process. |

### Software Engineer at Snap was asked...

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: 1.Only one letter can be changed at a time 2.Each intermediate word must exist in the word list 3 AnswersUsing BFS, Loop through 'a' to 'z' to replace each char of the neighbors word then check if it matches wordList.If so, add it into queue.count the level and return the level when you find a word which equals to the endWord. here is my solution code: public int ladderLength(String beginWord, String endWord, Set wordList) { Queue q = new LinkedList(); int level = 1; q.offer(beginWord); int cnt = q.size(); while(!q.isEmpty()){ String tmp = q.poll(); cnt--; char[] cArr = tmp.toCharArray(); for(int i = 0; i < cArr.length; i++){ for(char c = 'a'; c <= 'z'; c++){ cArr[i] = c; String str = new String(cArr); if(str.equals(endWord)){ return level + 1; } if(wordList.contains(str)){ wordList.remove(str); q.offer(str); } } cArr[i] = tmp.charAt(i); } if(cnt == 0){ cnt = q.size(); level++; } } return 0; } Assumes "beginWord" and "endWord" are the same length "wordLen". Finds all possible combinations of words that are 1,2,...,wordLen away for both beginWord and endWord and calls them "comb1" and "comb2" respectively (ex: if begin word is "now", Combo1 is made of 3 lists each consisting of words that are 1,2, and 3 changes respectively away from now like [[not, new, tow, cow, etc....], [nut, nap, bot, cot, etc... ], [lab, dad, rid, cat, etc... ] ]). Goes through both the combo sets and finds the intersection with the smallest number of transformations then returns the number of transformations. main method -> runs tests getTransLen -> compares array of arrays comb1 and comb2 to find smallest intersection getTransformations -> returns an array of arrays of words in dict that are 1,2,...,wordLen different from the word given (ex: for "now", [ [not, new, tow, cow, etc....], [nut, nap, bot, cot, etc... ], [lab, dad, rid, cat, etc... ] ]) words.txt downloaded from: https://raw.githubusercontent.com/dwyl/english-words/master/words.txt ========================================== import java.util.*; import java.lang.*; import java.io.*; public class SnapchatQ1 { public static void main(String args[]) { ArrayList dictList = new ArrayList(); try { BufferedReader br = new BufferedReader( new InputStreamReader( new FileInputStream("words.txt"))); try { String line; while ((line = br.readLine()) != null) { dictList.add(line); } } finally { br.close(); } } catch (Exception e) { } Set dictSet = new HashSet(dictList); int answer1 = getTransLen("not", "new", dictSet); System.out.println("Answer 1 - Expected: 3 Received " + answer1); int answer2 = getTransLen("cold", "tell", dictSet); System.out.println("Answer 2 - Expected: 4 Received " + answer2); int answer3 = getTransLen("smile", "speak", dictSet); System.out.println("Answer 3 - Expected: 5 Received " + answer3); } public static int getTransLen(String beginWord, String endWord, Set wordList) { ArrayList comb1 = getTransformations(beginWord, wordList); ArrayList comb2 = getTransformations(endWord, wordList); int smallNum = -1; for (int i = comb2.size() - 1; i >= 0; i--) { for (int j = 0; j ) comb2.get(i)) { if (((ArrayList)comb1.get(j)).contains(currWord)) { int newNum = i + j + 1; if (newNum wordList) { int wordLen = word.length(); ArrayList toReturn = new ArrayList(); for (int i = 0; i ()); } for (String compWord : wordList) { if (compWord.length() == wordLen) { int diffNum = 0; for (int i = 0; i ) toReturn.get(diffNum)).add(compWord); } } return toReturn; } } ========================================== This is same as this leetcode question https://leetcode.com/problems/word-ladder/ Here's a working solution. #include #include #include #include class Solution { public: int ladderLength(string beginWord, string endWord, vector& wordList) { std::set wordSet; for(auto& word: wordList) wordSet.insert(word); if (wordSet.find(endWord) == wordSet.end()) return 0; std::queue> bfsQueue; bfsQueue.push(pair(beginWord, 1)); while(!bfsQueue.empty()) { auto curWordPair = bfsQueue.front(); bfsQueue.pop(); string curWord = curWordPair.first; string candidateWord(curWord); for(int i = 0; i (candidateWord, curWordPair.second + 1)); wordSet.erase(candidateWord); } } candidateWord[i] = replaceChar; } } return 0; } }; |

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

Write a method to decide if the given binary tree is a binary search tree or not. 4 Answersfor binary search tree, inorder traversal should result in sorted array in the increasing order. Further, know that the difference between the two is that a binary search tree cannot contain duplicate entries. recur down the tree - check if element is already in hashtable - - if it is, return false - - if it isnt, insert element into the hashtable - - - recur to children I'm sorry but Anon's answer is not correct, at least according to "Introduction to Algorithms, 3d Edition" by Cormen. The binary search tree property says that there CAN be duplicates: "Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key = x.key." In other words, the value of a child node may be equal to the value of a parent node, which would yield the result that "Interview Candidate" posted on Mar 14 2012. Performing an inorder tree walk would yield sorted nodes. Show More Responses public static isValidBST(TreeNode root, MIN_INTEGER, MAX_INTEGER) { if (root == null) // children of leaf nodes { return true; } return root.data >= INTERGER_MIN && root.data <= INTEGER_MAX && isValidBST(root.left, INTEGER_MIN, root.data) && isValidBST(root.right, root.data, INTEGER_MAX) } |

**1**–

**10**of

**52,910**Interview Questions

## See Interview Questions for Similar Jobs

- Senior Software Engineer
- Software Developer
- Software Development Engineer
- Intern
- Software Engineer Intern
- Data Scientist
- Analyst
- Engineer
- Product Manager
- Business Analyst
- Consultant
- Associate Software Engineer
- Staff Software Engineer
- Java Developer
- Director
- Project Manager
- Senior Software Developer
- Software Engineering Intern
- Software Engineer III