# Engineering Interview Questions in San Francisco, CA

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 |

### Electrical Engineer at Fitbit was asked...

Draw the circuit for an active low-pass filter. 1 Answerresistor going into V- on a op amp, V+ to GND, and a resistor and cap in parallel from output to V-. |

### IOS Developer Engineer at DeNA was asked...

What are the App states. Explain them? 2 AnswersActive: app is foreground Background: app is not foreground but still executing codes Inactive: app is suspended Not Running - app has not been launched or was running but terminated by system. Inactive - app is running in foreground but not receiving events. Active - app is running in foreground and receiving events. Background - app is in the background and executing code. Suspended- the app is in the background but is not executing code. |

### 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; } }; |

### QA Automation Engineer at BitTorrent was asked...

A dwarf-killing giant lines up 10 dwarfs from shortest to tallest. Each dwarf can see all the shortest dwarfs in front of him, but cannot see the dwarfs behind himself. The giant randomly puts a white or black hat on each dwarf. No dwarf can see their own hat. The giant tells all the dwarfs that he will ask each dwarf, starting with the tallest, for the color of his hat. If the dwarf answers incorrectly, the giant will kill the dwarf. Each dwarf can hear the previous answers, but cannot hear when a dwarf is killed. What strategy should be used to kill the fewest dwarfs, and what is the minimum number of dwarfs that can be saved with this strategy? 21 AnswersThere are 2 different strategies, each dependent on whether there are an even or odd number of white and black hats in play. The minimum number of dwarfs that can be saved with the correct strategy is 9. There is only one strategy, does not matter how many white or black hats they are. They are always 9 dwarfs that could be saved. You just have to know about XOR. Well... In my opinion all can be saved! The tallest dwarf can see 9 hats in front of him ( 4 white and 5 black hats or the other way around). Then he knows the color of his hat because there has to be 5black and 5 white hats. The next dwarf by the size just has to believe to the tallest dwarf that he is right-(and he is) In addition ,he can see 8 hats in front of him and when he adds the color of the tallest dwarf he knows which color he has. Again,the 3rd one in a row knows about 2 colors before and can see 7 colors in front of him.And when he adds 2 colors he already had heard of -he knows total number of 9 hats as well.So he just has to see which color is less presented and that is the color of his hat. And so on until the last dwarf...All saved Show More Responses the question does not mention that there will be equal number of white and black hats ! Since they do not know, how many black or white hats there are, the following strategy will save min 5 dwarfs: The first dwarf asked names the color of the hat of the 2. dwarf. He has a 50% chance that that's correct. Anyway, the second dwarf then knows, the color of his hat and names it correctly. the 3. dwarf again names the color of the hat of the 4th dwarf and has a 50% chance to survive, while the 4th dwarf can name the correct color of his hat. a.s.o. => all dwarfs with an even number will survive and all the others have a 50% chance Don't over-think it. Each dwarf simply has to state the color of the hat worn by the dwarf directly in front of him. The tallest would have to sacrifice himself in order to save the other 9. Easy. The tallest is the only one that cannot be saved so instead of trying to guess his color, he yells out a sequence of letters starting from the shortest like BWBBBWWBB. Next :) Your going to definitly get 9 because when the dwarves collude the tallest tells the next tallest his hat color and so on down the line. Now you have a 50/50 chance that the tallest will get his color correct and live so you have 9 with a 50% chance of 10 Each dwarf can state the color of the hat worn by the dwarf in front of him, but the thing is, that color may not be the color of his own hat.So he may be killed by the giant.In that case, as mentioned above all odds should tell the color of next so that all even number will be alive and they have 50% chance of surviving. Think broadband communication. Exploit the capabilities of the communications medium. A minimum of nine dwarves can be saved based on the information provided in the original post I viewed. The strategy is for each dwarf to employ the expected language to communicate the color of their own hat to the giant, while simultaneously employing a vocal pitch protocol to indicate the color of the hat of the dwarf in front of him, high pitch for white and low pitch for black. The original post, indicates the dwarves may collude prior to the distribution of hats, so there is opportunity to negotiate such a simple broadband communication protocol. The tallest dwarf only has a 50/50 chance since the number of black and white hats in play is not known (rhetorical question, what are the odds the tallest dwarf's hat is black if he turns to find that all nine hats in front of him are white? I don't know, but odds are high that the giant is a sadistic bloke). The original post I viewed is here. http://www.businessinsider.com/toughest-job-interview-questions-2013-7#a-dwarf-killing-giant-lines-up-10-dwarfs-from-shortest-to-tallest-each-dwarf-can-see-all-the-shortest-dwarfs-in-front-of-him-but-cannot-see-the-dwarfs-behind-himself-the-giant-randomly-puts-a-white-or-black-hat-on-each-dwarf-no-dwarf-can-see-their-own-hat-the-giant-tells-all-the-dwarfs-that-he-will-ask-each-dwarf-starting-with-the-tallest-for-the-color-of-his-hat-if-the-dwarf-answers-incorrectly-the-giant-will-kill-the-dwarf-each-dwarf-can-hear-the-previous-answers-but-cannot-hear-when-a-dwarf-is-killed-the-dwarves-are-given-an-opportunity-to-collude-before-the-hats-are-distributed-what-strategy-should-be-used-to-kill-the-fewest-dwarfs-and-what-is-the-minimum-number-of-dwarfs-that-can-be-saved-with-this-strategy-11 So reading the answers provided they all have some assumptions e.g. that there are as much white hats as there are black hats. I think that Christian's comment on aug 13-2013 was very close but I'm thinking about communication integrity confirmation techniques. One of them is using a parity bit to confirm the message was correct. This could be applied right here to save at least 9 with a 50/50 chance of saving the 10th (and tallest dwarf). I will explain it but for ease of explanation I will use binary 1 and 0 for black and white. Number 1 being black hat and number 0 being white hat. Let's say we got a (random) hat sequence of 0001011101 with the tallest dwarf on the right and the shortest on the left. While colluding prior to the distribution of hats the dwarfs agree upon even or uneven parity. This means the total amount of 1's (black hats) must be even or uneven including the parity bit. In this case the 10th dwarf will count as parity bit. So if we'll take an even parity, the number of 1's must be an even number in total. When the questioning starts the tallest dwarf will see the hats in front of him being 000101110. The tallest dwarf counts four 1's (black hats) so to make the parity even he has to say 0 (white hat). He will get killed but the dwarfs in front of him will know the parity bit is 0 so the 2nd tallest dwarf will see the hats in front of him as 00010111. He will also count 4 and knowing that the dwarf behind him said 0 he'll know that the total amount of 1's is an even number thus concluding he has a 0 (white hat) and will state he has a white hat. Same goes for the rest of the dwarfs and so 9 will be saved. The 10th would've been saved it the dwarfs agreed on an uneven parity. That's why there's a 50/50 chance the 10th will be saved. I'm pretty confident this is the answer but if you want to understand it better (maybe my explanation is a bit vague) go search for "parity bit" on the internet. @Kristen - you have so underthought it! What if the dwarf behind you says "black" and the dwarf in front of you has a white hat???? @JustJanek- Your solution is close, but not correct. Every dwarf needs to consider the parity of a number composed of all the following dwarfs and all the dwarfs behind. The first dwarf says the parity of the 9-bits number in front of him. Assuming that all the other dwarfs know the trick and they stay alive, each dwarf needs to compare the initial parity with the parity of an 8-bit number composed of the hats in front of him and the hats behind (assuming that the dwarfs behind gave the right answer), if the parity is the same, he knows that he has a white hat, otherwise he has a black hat. Show More Responses You can save 9 dwarves at least. Dwarves agree that the tallest one says he is wearing black hat if he sees odd number of black hats in front of him and he says white hat if he sees even number of black hats in front of him. So, the tallest one has 50-50 chance of survival and other dwarves survive 100%. What is the minimum number of dwarfs that can be saved with this strategy? 9 First of all, let's numerate the dwarfs as N1, N2, N3, etc. with N10 being the tallest. Now, N10 will state the color of N9 as his own answer, "My hat is WHITE". Based on this answer, N9 will state his color with a positive statement if the color of N8 is the same as his, "My hat is WHITE". Based on N8's answer, N8 knows that his color is WHITE, now, he will state his color depending on N7. Let's say N7 is black, so N8 will state, "My hat is NOT BLACK". N7 knows that his color is BLACK, but N6 is white, so he will use a negative statement, "My hat is NOT WHITE" and so on. Full example: N10 = BLACK N9 = WHITE N8 = WHITE N7 = BLACK N6 = WHITE N5 = WHITE N4 = WHITE N3 = BLACK N2 = BLACK N1 = WHITE N10: My hat is WHITE (Dies) N9 = My hat is WHITE N8 = My hat is NOT BLACK N7 = My hat is NOT WHITE N6 = My hat is WHITE N5 = My hat is WHITE N4 = My hat is NOT BLACK N3 = My hat is BLACK N2 = My hat is NOT WHITE N1 = My hat is WHITE N10 will have a 50/50 chances of survival... I'm sorry N10, I couldn't save you :'( What is the minimum number of dwarfs that can be saved with my strategy? - 10 My strategy doesn't make any unmentioned assumptions (such as equal number of white and black hats, etc). At the same time, it doesn't add any unmentioned constraints either. The strategy is simple to the point of appearing simplistic. But it meets all the requires. The strategy is: When asked, every dwarf answers "Not RED". This is not an incorrect answer and the Giant, if he were an honourable giant that is :), would have to let the Dwarf live. On a different page altogether, I went through all of the above answers. Not to sound patronizing, but some of the solutions were quite brilliant. I was thinking if I could even come up with that even after years of pondering. But I must admit, all of the above strategies are made by an outsider (ie. us) who is not impacted by this fate. Whereas in the casestudy, the strategy has to be devised by the 10 dwarfs, who face the impact of this strategy. Not to bring in factors such as emotion, the bell curve distribution of intelligence, and other such anal considerations. But I thought it was important to bring in Game Theory, and that all Dwarfs are rational, and that all rational people do not want to harm themselves in any way. In other words, when a strategy's success depends on the conformance to that strategy by ALL the participants, the strategy should also benefit ALL the participants if it is to succeed (or in the least, should not harm even ONE participant). In all the above strategies, since even in the best case scenario the poor Tallest Dwarf has only a 50% chance of living, can we assume that he would conform to this strategy? Each dwarf should pronounce color of hat of dwarf before him. This way they can save atleast 9 dwarf out 10. Well, Once the dwarfs are lined up in descending order. Without any kind of assumption, 9 people can be saved with a 50% probability of the 10th (tallest). Here is how it can be achieved, The strategy is to call the color of odd number of hat. Say for example, the tallest dwarf sees 3 Black and 6 whites, it will call out Black(it may or may not die with 50% chances). Now, the 9th tallest dwarf knows what the 10th dwarf could see and if it (9th) dwarf sees the same odd number of black hats, it will know it has white hat. Next, 8th dwarf knows number of odd (black) caps 9th dwarf could see and if it(8th) finds 1 less black cap, it would know it is wearing a black cap.. and so on. 10- White (calls out Black because it sees odd number of black hats) -dies(assume) 9- White (calls out White because it could still see 3 black hars) 8- Black (sees that there is one less black hat as mentioned by 9th, hence identifies that is wearing black) 7-White (calculates that 8th is wearing black and he could see 2 black, hence identifies itself wearing whiteO( 6-White 5-White 4- Black 3-Black 2-White 1-White Sorry if there is confusion in the way I have answered. all can b saved... They will exchange their hats in Circular form...person10 can see the person1 color of hat and after exchange every dwarf will tell color to their previous ones and person 10 knows the color before changing it from dwarf 1. d10->d9->d8->d7->d6->d5->d4->d3->d2->d1->d10 CIRCULAR EXCHANGE OF HATS First lets look at number of back and white hats...To satisfy the condition "black and white" hata there is minimum one black or white hat present. So its minimum (9 black & 1 white) or (1 white & 9 black) hat being distributed randomly amoung dwarfs. The story says dwarfs are alowed to speak before execution. Lets make a strategy of saying only one colour before execution eg) black or white. Minimum probability of (9 black & 1 white) hats and all the dwarfs say "white"...In this case one is saved but all nine dead. If all dwarfs say "black"..Nine are saved but one is dead. The same applies for the minimum probability of (1 black and 9 white)hats. Thus minimum one dwarf is saved and maximum nine dwarfs can be saved. If each dwarf say the colour of hat in front of him..(dwarf can hear previous answer) then at least five people are saved. |

Function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant space. n = 3. 1 1 1 1 2 2 1 3 Ans = 4 14 Answers$cache = array(); $cache[1] = 1; $cache[2] = 2; $cache[3] = 4; function stepways($input) { global $cache; if ($input < 4) { $ret = $cache[$input]; } else { $start = 4; $ways = 4; while ($start < $input) { $ways = $cache[$start - 3] + $cache[$start - 2] + $cache[$start -1]; $cache[$start] = $ways; $start++; unset($cache[$start - 3]); } return $ways; } return $ret; } import java.io.*; import java.util.*; class NumSteps{ public static Integer[] getR(Integer[] a, int i){ Integer [] c = new Integer[a.length-1]; for(int j =0; j q = new LinkedList(); q.add(a); while(q.size() >0){ Integer [] tmp = q.poll(); for(int i = 0; i 2) q.add(tmp1); tmp1 = null; } } System.out.println(N); }catch(IOException e){} }//end of main } //end of class numSteps javascript version: var countSteps = (function () { var cache = { 1: 1, 2: 2, 3: 4 }; return function (n) { if (n < 1) throw new Error('number must be positive'); if (n < 4) return cache[n]; var result = (cache[n - 1] || countSteps(n - 1)) + (cache[n - 2] || countSteps(n - 2)) + (cache[n - 3] || countSteps(n - 3)); cache[n] = result; return result; } })(); Show More Responses edit: the above can be improved a bit by replacing if (n<4) with if (cache[n]) int numSteps( int n ) { if ( n < 0 ) return 0; if ( n == 0 ) return 1; int result = 0; result += numSteps( n - 1 ); result += numSteps( n - 2 ); result += numSteps( n - 3 ); return result; } import sys def Calculate(n): '''Calculates no of ways steps can be climbed''' if n == 1: return 1 elif n == 2: return 2 elif n == 3: return 4 Count=[0]*4 Count[0],Count[1],Count[2] = 1,2,4 shifter, a, b, c, d = 0, 0, 0, 0, 0 for i in xrange(3,n): a, b, c, d = shifter%4, (shifter+1)%4, (shifter+2)%4, (shifter+3)%4 Count[d] = Count[a] + Count[b] + Count[c] shifter = shifter+1 return Count[d] print Calculate(input()) this is the one that works for me: 1 #!/usr/bin/python 2 #-*- encoding: utf-8 -*- 3 4 steps = [1, 2, 3] 5 6 def find_all_ways(n=3): 7 stack = [] 8 ways = 0 9 stack.append((1, 0)) 10 max_len = 1 11 while len(stack) != 0: 12 (s, sum) = stack.pop() 13 if sum == n: 14 ways += 1 15 if sum > n: 16 continue 17 for step in steps: 18 stack.append((step, sum + step)) 19 if len(stack) > max_len: 20 max_len = len(stack) 21 return ways, max_len This problem is related to Fibonacci series type problem where f(n) =f(n-1)+f(n-2)+f(n-3) We can employee dynamic programming to provide the answer in liner time and space. As shown below Code in Java:: ------------------- import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Fibonacci { /** * @param args * @throws IOException * @throws */ public static void main(String[] args) throws IOException { // TODO Auto-generated method stub int a=1; int b=1; int c=2;//Storing the predefined value int input = Integer.parseInt((new BufferedReader(new InputStreamReader(System.in))).readLine()); if(input < 0) System.out.println("Negative Number Inserted... Plx Insert Positve Number!!!"); else if(input == 0) System.out.println("0"); else if(input == 1) System.out.println("1"); else if(input == 2) System.out.println("2"); else { int sum=0; for(int i=2;i Recursive solution in Java: public static void countSteps(int n) { if (n == N) { count++; } else { if (n > N) return; for(int step=1; step < 4; step++) { countSteps(n+step); } } } Where: N = the input number of steps; count = the final result; Another Javascript answer. function getSteps(n) { var lookUp = { 1: 1, 2: 2, 3: 4 }; if (lookUp[n] != null) { return lookUp[n]; } else { for (var i = 4; i <= n; i++) { lookUp[i] = lookUp[i - 1] + lookUp[i - 2] + lookUp[i - 3] } return lookUp[n]; } }; o(n^2) import java.util.Scanner; public class StairsCombo { public static void main(String[] args) { final Scanner in = new Scanner(System.in); while (true) { System.out.print("Enter total stairs : "); int n = in.nextInt(); System.out.println(countCombos(n)); } } private static Integer countCombos(int n) { System.out.println("counting for " + n); if (n < 1) return 0; switch (n) { case 1: return 1; case 2: return 2; case 3: return 4; default: return countCombos(n - 1) + countCombos(n - 2) + countCombos(n - 3); } } } public class StairClimber { /** * iterative solution: O(n) time, O(1) memory * @param stairs * @return stair partition */ public static int countStairPathsIter(int stairs){ //base cases and record of preceding values //for values of "stairs" > 3 int[] pathCounts= {1,2,4}; //v0,v1,v2 if(stairs <= 3){ return pathCounts[stairs-1]; } for(int i=4; i<=stairs; i++){ pathCounts[2]= pathCounts[0]+pathCounts[1]+pathCounts[2]; //v0+v1+v2 pathCounts[1]= pathCounts[2]-pathCounts[0]-pathCounts[1]; //v2 pathCounts[0]= pathCounts[2]-pathCounts[0]-pathCounts[1]; //v1 } return pathCounts[2]; } /** * tail-recursive solution: O(n) time , O(1) memory * @param stairs * @return stair partition */ public static int countStairPathsRec(int stairs){ return cntStrs(stairs,1,2,4); } private static int cntStrs(int input, int v1, int v2,int v3){ if(input==1){return v1;} if(input==2){return v2;} if(input==3){return v3;} return cntStrs(input-1,v2,v3,v1+v2+v3); } public static void main(String[] args){ System.out.println( countStairPathsRec(8)); } } Show More Responses public class CalcWaysToStep { /** * @param args the command line arguments */ public static void main(String[] args) { double n = 3.11112213; int steps[] = {3, 2, 1}; int iGCount = 0; iGCount = countSteps(steps, n); System.out.print("Number of possibilities :" + iGCount); } /** * * @param steps * @param n * @return */ protected static int countSteps(int[] steps, double n) { int iCount = 0; for (int i = 0; i 0) { iCount += 1; double dRemainder = n % steps[i]; int tmpCount = countSteps(Arrays.copyOfRange(steps, i, steps.length - 1), dRemainder); if(tmpCount>0) iCount += (tmpCount-1); } } return iCount; } } |

### Software Engineer at Salesforce was asked...

Find the first index of the substring. Condition: Do not use java library function or regular expressions. And measure the performance of your implementation with the standard java library function. Examples: String 1: “abcdefg” String 2: “bcd” Should return 1 String 1: “abcdefg” String 2: “x” Should return -1 14 Answerspublic class ComputeSubString { String s1 = "abqqqqqqqbcdef"; String s2 = "xbcd"; boolean found = true; static int pos = -1; public static void main(String s[]) { new ComputeSubString().start(); System.out.println(pos); } private void start() { for (int i = 0; i s1.length() || s1.charAt(index + i) != s2.charAt(i)) { return false; } } return true; } } Is this too naive? Why not KMP? Here's a more elegant solution: public static void main(String[] args) { String m = "internet"; String t = "net"; int i, j = 0; for (i = 0; i < m.length() && j < t.length(); ++i) { if (m.charAt(i) == t.charAt(j)) { ++j; } else { j = 0; } } if (j == t.length()) { System.out.println(i+1-t.length()); } } Show More Responses @fireHydrant: In your case there will be a small logical error.. You code does not work in case of two string "internnet" and "net" Since in your code you keep on checking next character if there is a match. Bur what if the string is not a complete match? It never checks first value again.. Example: internnet and net: when it comes to nnet part: Your codes output: i=5 m = n t = n i=6 // here is the catch m = n t = e i=7 m = e t = n i=8 m = t t = n I modified your code and the correct code is: public static void main(String[] args) { String m = "internnet"; String t = "net"; int i, j = 0; for (i = 0; i 0){ j=0; i--; } else { j = 0; //i--; } } if (j == t.length()) { System.out.println("Yes.. A match "+(i-t.length())); } } Hope this clears doubt.. public static int indexOf(String str1, String str2) { for (int i = 0; i <= str1.length() - str2.length(); i++) { if (equals(str1, str2, i, 0)) { return i; } } return -1; } public static boolean equals(String str1, String str2, int idx1, int idx2) { while (idx1 < str1.length() && idx2 < str2.length() && str1.charAt(idx1++) == str2.charAt(idx2++)) { } return idx2 == str2.length(); } Find the answer here: http://programmingpassionforjava.blogspot.com/2012/10/find-first-index-of-substring.html static int ReturnFirstOccurance(string mainString, string subString) { int len = mainString.Length; for (int i = 0; i < len; i++) { if (mainString[i] == subString[0]) { if (mainString[i+1] == subString[1]) { if (mainString[i + 1] == subString[1]) { return i; } } } } return -1; } for (i=0; i< s.length - s1.length; i++) { for (j=0; j This one is neater: for (i=0; i< s.length - s1.length; i++) { j = 0; while (j < s1.length && s1.charAt(j) == s.charAt[i+j]) j++; if (j == s1.length) return i; } return -1; public static int kmp(String s, String t) { int l = s.length(); int n = t.length(); int m, i; m = i = 0; int T[] = new int[n]; T[0] = -1; while (m 0 && T[i - 1] == -1) { if (s.charAt(m + i) == t.charAt(0)) { T[i] = 1; } else { T[i] = -1; } } else if (i > 0 && T[i - 1] >= 0) { if (s.charAt(m + i) == t.charAt(T[i - 1])) T[i] = T[i - 1] + 1; else T[i] = T[i - 1]; } if (s.charAt(m + i) == t.charAt(i)) { i++; if (i == n ) { return (m+i); } } else { if (T[i] > 0) { m = m + i - T[i]+1; i = T[i]; } else { i = 0; m++; } } } return -1; } this can be done either by recursion or by for loop. for ForLoop: public static int indexOf(String str, String subStr) { if (str == null || str.length() == 0 || subStr == null || subStr.length() == 0) { return -1; } int i = 0, j = 0; while (i 0) { i -= j; j = 0; } ++i; } } if (j == subStr.length()) { return i - j; } return -1; } the problem with the other implementation are that they will miss the following: indexOf("internnntood", "nnt"); public boolean strStr(String haystack, String needle) { char[] big = haystack.toCharArray(); char[] small = needle.toCharArray(); if (big.length == 0 || small.length == 0 || big.length < small.length) { return false; } char firstChar = small[0]; //find the first character of needle in the haystack by doing linear scan for (int j = 0; j < big.length; j++) { if (big[j] == firstChar) { //check if remaining consecutive characters match continuously if (matchRest(big, small, j + 1)) { System.out.println(j); // matched at position j return true; } } } // sorry no match return false; } private boolean matchRest(char[] big, char[] small, int sBig) { int i, j; // always start from position 1 of needle since position 0 is guranteed to be matched // start with position passed for haystack and make sure to stop before either buffers runs out for (i = 1, j = sBig; (i < small.length) && (j < big.length); i++, j++) { if (big[j] != small[i]) { return false; } } // if tail of haystack has a subset of needle then its not a match if (j == big.length && i < small.length) { return false; } else { return true; } } int strStr(String haystack, String needle) { int l1 = haystack.length(), l2 = needle.length(); if(l1 < l2) return -1; else if(l2 == 0) return 0; int threshold = l1 - l2 for(int i = 0; i < threshold; i++) { if(haystack.substring(i, i + l2).equals(needle)) { return i; } } return -1; } Show More Responses C# solution: using System; namespace StringPractice { class Program { static void Main(string[] args) { //string a = "internenenenenet"; //string b = "net"; //string a = "abqqqqqqqbcdef"; //string b = "xbcd"; //string a = "internnet"; //string b = "net"; string a = "internnntood"; string b = "nnt"; Console.WriteLine(findFirstIndexOfSubString(a, b)); } /// /// Function returns first index of the substring. /// /// source string where to search for substring /// sub string of superString /// starting index of superString, where subString started, otherwise -1 public static int findFirstIndexOfSubString(string superString, string subString) { // Return -1 if either of a or b are null or empty string if(string.IsNullOrEmpty(superString) || string.IsNullOrEmpty(subString)) { return -1; } int i = 0, j = 0; // Loop through until end of superString. while (i |

### Software Engineer at Dropbox was asked...

Given an array of integers eg [1,2,-3,1] find whether there is a sub-sequence that sums to 0 and return it (eg 1,2,-3 or 2,-3,1) Checking every sub-sequence is O(n^2) which is too inefficient 15 AnswersShould do a running sum, storing previous sum values in a hash table along with array index if you ever get a sum value you’ve already seen, return the array indices (1+the index in the hash table, and the current index) This solution is O(n) Although the above algorithm runs in O(N) time, will it cover all cases? What about if the input array is [1,2,1,-3,-4]? In this case, the subsequence would be [2,1,-3]. I feel though that the algorithm described above will miss this subsequence since you are only keeping a running sum from the start of the array. Do you mean a subsequence (can be discontinue) or a sub array (continue)? Show More Responses Yes, the solution by Interview Candidate (do a running sum and return when you see a sum already seen) works for all cases. If the list is [1, 2, 1, -3, -4], S1 = 1; S2 = 3 (1 + 2); S3 = 4 (1 + 2 + 1) S4 = 1 (1 + 2 + 1 -3) ... since we have already seen this sum at index 1. the answer is list of numbers at [old_sums_index + 1, new_sums_index] = [2, 1, -3] [100 7 1 2 -3] the above method will not work for this array, It will work for [100 7 1 2 -3]. Index: 0, Sum = 100 (put in hashtable) Index: 1, Sum = 100 + 7 = 107 (put in hashtable) Index: 2, Sum = 107 + 1 = 108 (put in hashtable) Index: 3, Sum = 108 + 2 = 110 (put in hashtable) Index: 4, Sum = 110 + (-3) = 107 107 already exists in hashtable with index = 1. Hence we return (1+1, current index) meaning (2, 4) Doesn't work for [-1,-1,-3,4]. This looks like a classical NP-complete problem: http://en.wikipedia.org/wiki/Subset_sum_problem. And generating all sub sequences is not O(n^2) but O(n!) which is the cost to generate all permutations. It works for [-1 -1 -3 4] too. The subset sum problem allows discontinuous subsets, but this question asks for a subsequence implying no discontinuity. Here is a solution using Python 3: def findZeroSequence(list): hash = {} sum = 0 startIndex = -1 hash[sum] = startIndex # a sum of zero later in the list means the sequence starts at index 0 (== -1 + 1) for i, v in enumerate(list): sum = sum + v # print(i, ' has sum ', sum) try: startIndex = hash[sum] return list[startIndex+1:i+1] except KeyError: hash[sum] = i return [] # no subsequence print(findZeroSequence([1,2,-3,1])) print(findZeroSequence([1,2,1,-3,-4])) print(findZeroSequence([-1,-1,-3,4])) print(findZeroSequence([100, 7, 1, 2, -3])) print(findZeroSequence([-7, -3, -2, 5, 8])) Checking every sub-sequence is O(2^n) not O(n!), which is the cost for generating all subsets. Contrary to what the previous poster said, sub-sequence implies both continuity and discontinuity: http://en.wikipedia.org/wiki/Subsequence and the algorithm fails for this case: [2, 2, 1, -4]. How about these: [1,2,-3,4] or [-3,3,1] ? May be user should check for zero also? def hasSubSeqOfZero(a): if not a: return [] partialSums = {} partSum = 0 for i in range(len(a)): partSum += a[i] if (partSum in partialSums): return a[partialSums[partSum] + 1: i + 1] if (partSum == 0): return a[:i+1] partialSums[partSum] = i return [] Show More Responses public int[] ssz(int[] nums) { if (nums == null || nums.length == 0) return null; Map map = new HashMap(); int sum = 0; int index = 0; for (int n : nums) { if (n == 0) return new int[] { index, index }; sum += n; if (map.containsKey(sum)) { return new int[] { map.get(sum) + 1, index }; } map.put(sum, index); index++; } return null; } Check out this Dropbox employee's profile. It looks like you can get some info about the interview from them. https://www.rooftopslushie.com/profile/whodis |

### Software Engineer at Twitter was asked...

Given n sets of choices: (1,2,3), (2,3,4), (4,5) You pick one element from each set of choices. Generate all possible picking. 11 AnswersYou don't need depth-first or breadth-first. recursion why recursion? The following gives all possible pickings in list. A=[1,2,3]; B= [2,3,4], C=[4,5] list=[] for a in A: for b in B: for c in C: list.append([a,b,c]) Show More Responses Sorry about the ambiguity. n set of choices are given and we don't know them in advance. That was just an example.. Okay then recursion is the way to go. In python its super easy list1 = [1,2,3] list2 = [2,3,4] list3 = [4,5] print [(x,y,z) for x in list1 for y in list2 for z in list3] public static void findAllPickings(List sets, int pos, String result) { if(pos == sets.size()) System.out.println(new String(result)); else { int[] currentSet = sets.get(pos); for(int i = 0; i < currentSet.length; i++) { String currentString = result + currentSet[i]; findAllPickings(sets, pos+1, currentString); } } } public List printPerm(List> lists, String prefix, List output) { if (prefix.length() == lists.size()) { output.add((T) prefix); } else { List currList = lists.get(prefix.length()); for (int i = 0; i < currList.size(); i++) { printPerm(lists, prefix + currList.get(i), output); } } return output; } public List printPerm(List> lists, String prefix, List output) { if (prefix.length() == lists.size()) { output.add((T) prefix); } else { List currList = lists.get(prefix.length()); for (int i = 0; i < currList.size(); i++) { printPerm(lists, prefix + currList.get(i), output); } } return output; } Backtracking is one of the solutions. List> getPickings(List> buckets) { if (buckets.isEmpty()) { return new ArrayList>() {{ add(new ArrayList()); }}; } // Choose a bucket (backtracking, make a choice) List bucket = buckets.remove(0); List> currentPickings = new ArrayList(); // Combine every element in the chosen bucket with the combinations // generated from the remaining buckets for (Integer chosenElement : bucket) { for (List pickings : getPickings(buckets)) { currentPickings.add(new ArrayList() {{ add(chosenElement); addAll(pickings); }}); } } // Un-choose the chosen bucket (backtracking, un-choose) buckets.add(bucket); return currentPickings; } |

Get numeric number out of a roman string, linear time Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 Input/Output: II = 2, III = 3, IV = 4 VI, VII, VIII IX = 9 XL = 40, XLIX = 49 9 Answers$char_map = array('I' => 1, ...); $input = 'XLIX'; $output = getNumeric($input, 0, count($input) - 1); function getNumeric($roman, $start, $end) { if ($start > end) { return 0; } else if ($start == $end) { return $char_map[$roman[$start]]; } else { $pivot = findPivot($roman, $start, $end); $num = $char_map[$roman[$pivot]] - getNumeric($roman, $start, $pivot -1) + getNumeric($roman, $pivot + 1, $end); return $num; } } function findPivot($roman, $start, $end) { //find max roman from start -> end $maxSoFar = 0; $pos = $start; for ($i = $start; $i $maxSoFar) { $maxSoFar = $char_map[$roman[$i]); $pos = $i; } } return $pos; } mapping = { 'I' : 1, 'V' : 5, 'X' : 10, 'L' : 50, 'C' : 100, 'D' : 500, 'M' : 1000, } def roman(string): prev = 0 totalsum = 0 for c in string: if mapping[c] <= prev: totalsum = totalsum + mapping[c] else: totalsum = totalsum - prev totalsum = totalsum + mapping[c] - prev prev = mapping[c] print(totalsum) roman("XCIX") #include #include #include #include void main() { int *a,len,i,j,k; char *rom; clrscr(); printf("Enter the Roman Numeral:"); scanf("%s",rom); len=strlen(rom); for(i=0;i0;i--) { if(a[i]>a[i-1]) k=k-a[i-1]; else if(a[i]==a[i-1] || a[i] Show More Responses Python: d = {'C': 100, 'D': 500, 'I': 1, 'L': 50, 'M': 1000, 'V': 5, 'X': 10} def f(w): return d[w] print sum(map(f, 'CDI')) >> 601 Ok, a bit more complex than the first posted solution: prev = 10*6 d = {'C': 100, 'D': 500, 'I': 1, 'L': 50, 'M': 1000, 'V': 5, 'X': 10} def f(w): global prev _p = prev prev = d[w] if _p < d[w]: return d[w] - 2 * _p else: return d[w] print sum(map(f, 'XLIX')) Here we have to use simple switch use case to solve this problem .. Java Code for the following:: -------------------------------------- import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class RomanToDecimal { /** * @param args * @throws IOException */ public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine().toUpperCase(); int size = input.length(); int decimal =0,j; for(int i=0;i=2) j =i-1; else j =0; char ch = input.charAt(i); switch(ch) { case 'M': { if(i!=0 && 'C'==input.charAt(j)) { decimal-=100; decimal+=900; } else decimal+=1000; break; } case 'D': { if(i!=0 &&'C'==input.charAt(j) ) { decimal-=100; decimal+=400; } else decimal+=500; break; } case 'C': { if(i!=0 && 'X'==input.charAt(j) ) { decimal-=10; decimal+=90; } else decimal+=100; break; } case 'L': { if(i!=0 && 'X'==input.charAt(j)) { decimal-=10; decimal+=40; } else decimal+=50; break; } case 'X': { if(i!=0 && 'I'==input.charAt(j)) { decimal-=1; decimal+=9; } else decimal+=10; break; } case 'V': { if(i!=0 && 'I'==input.charAt(j)) { decimal-=1; decimal+=4; } else decimal+=5; break; } case 'I': { decimal+=1; break; } } } System.out.println(decimal); } } var romanNumeralParse = function(romanString) { var charMap = { 'I' : 1, 'V' : 5, 'X' : 10, 'L' : 50, 'C' : 100, 'D' : 500, 'M' : 1000 }; var sumTotal = 0; for (var i = 0; i = nextCharValue) { sumTotal += (charValue + nextCharValue); } else { sumTotal += (nextCharValue - charValue); } } console.log(sumTotal); }; int getValOfChar(char c) { if (toupper(c) == 'I') { return 1; } if (toupper(c) == 'V') { return 5; } if (toupper(c) == 'X') { return 10; } if (toupper(c) == 'L') { return 50; } if (toupper(c) == 'C') { return 100; } if (toupper(c) == 'D') { return 500; } if (toupper(c) == 'M') { return 1000; } return -1; } int convertRomanToInt(const char* romanChar) { /* Get numeric number out of a roman string, linear time Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 Input/Output: II = 2, III = 3, IV = 4 VI, VII, VIII IX = 9 XL = 40, XLIX = 49 */ // order.. I -> V -> X -> L -> C -> D -> M // start from last.. keep adding till you find an element which is less or bigger than current value. After that start substracting that value.. int prevCharVal = 0; int currentNumber = 0; for(int i = strlen(romanChar) -1; i >= 0; --i) { int cVal = getValOfChar(romanChar[i]); if (cVal == prevCharVal) { currentNumber += cVal; } else if (cVal > prevCharVal) { currentNumber += cVal; prevCharVal = cVal; } else { // This char val is less than previous... // this means, we need to substract. currentNumber -= cVal; } } return currentNumber; } O(n) import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class RomanNumeralInterpreter { static final Map numerals = new HashMap(); static { numerals.put('I', 1); numerals.put('V', 5); numerals.put('X', 10); numerals.put('L', 50); numerals.put('C', 100); numerals.put('D', 500); numerals.put('M', 1000); } public static void main(String[] args) { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter Roman number : "); final String roman = in.nextLine(); System.out.println(computeValue(roman.toCharArray(), 0)); } } private static int computeValue(char[] romanNumerals, int index) { if (index >= romanNumerals.length) return 0; int value = numerals.get(romanNumerals[index]); int i=index+1; while (i value) { value = val-value; } else { break; } i++; } System.out.println("Current value " + value + " at index " + index); return value + computeValue(romanNumerals, i); } } |

**1**–

**10**of

**7,919**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