Software engineer Interview Questions in Boston, MA, US
software engineer interview questions shared by candidates
Top Interview Questions
Software Engineer at Vistaprint was asked...
How many bottles of shampoo are produced in the world a year? 25 AnswersNot enough, apparently. Let's start with the US market: 300X10^6 people. About 60% use shampoo (others are bald or use soap). They go through about one bottle every two months, so that is about 1.8X10^9. Human population is about 6.6 X 10^9. As far as the undeveloped nations, most people don't use shampoo. The developed world is about four times the size of the US population or approximately 1.2 X 10^9. People in the US wash their hair more than in Europe, but I will neglect this. My estimate is about 5X10^9 bottles. Enough to wash everyone's hair. Show more responses 15 * 10^9 Could you please provide more info. Does this include sample size & super size bottles? sssss ssss wwwww sssss wwwww wwww www kkjk kjskjsk ksksjksj ksksjkjsknksnk knsknkskns ,xmnkjkjxc Show more responses yeah ok inwiill be more b=vernose butvwhatvthe fucj do youwnat me tinsay? nothing to sau actually what ou ghing to do? gbh bh bh ok i will say that you re shite aactulall as you want to know more nad more yeag ur vhvgi I would assume 6 billion people in the world- 50% use shampoo others just use regular soap. Assume that we are using some std sze bottle ~15oz. With daily use of 1/2 oz/day a bottle would be used in 1 month (probably close for US and western counties). However men use less than women and developing coutries would likely not shampoo daily. Generous estimate is a bottle lasting 1.5 months. Therefore each person uses 8 bottles /year. 8 x 3 billion is 24 billion bottles view my answer at http://bit.ly/b8riKs 1. Production is always>consumption because we have more product varieties to sell 2. We never see any shop with out of stock shampoo products, forget brands in this case. 3. Even if we consider 50 per population uses shampoo, they will never run out of shampoo because not everybody uses one bottle/person. A family might use one bottle. Enough to wash everyone's hair and keep bathrooms, store shelves, and warehouses stocked. A s a sales person, I'd be more concerned with how many bottles of shampoo can be moved from one place to another in a year as this is what generates revenue. Show more responses All of them. Lets look again at the question- it is not 'how many bottles of shampoo are USED" the question clearly states "how many bottles of shampoo are PRODUCED in the world in a year". It interests me to note that this is a production question for a software engineer position which clearly leads me to determine that the answer is not meant to be a number but a program or mathmatical equation of some sort. There is not enough information listed to solve to any given number with so many variables, and it is not safe to assume that 50% of the population uses shampoo or how many people are bald. The idea is to take the information given and develop a method to calculate the numerical value if the actual values are supplied. |
Software Engineer at Tripadvisor was asked...
Given a BST with leaf nodes having a numeric value, and nodes having the sum of values of its two children. Find an algorithm to find the maximum node within a tree. 7 AnswersRecursively navigate the tree. If the left val is negative and right val is positive return right, vice versa, if they are both negative, return the one that's less. if they are both positive return current. If they are equal, return either. If a node's value is always the sum of it's children, whouldn't the root be the maximum node? Not if the tree contains negative numbers. I think the "nodes having the sum of values of its two children" is redundent information - just do a regular binary search Show more responses If it is BST, why shouldn't the max be the right most node? Ya, even I was thinking of d same.. As stated the problem is meaningless. The correct statement is "given a BINARY TREE, with values at its leaves, and interior node values implicitly defined to be the sum of the value of their children, find a subtree with the maximum value." Its the PARENT node.. not the right most node.. if the question is defined as is. Its basically saying everything its sorted from greatest at the top to least at the bottom. |
Find the largest sum of contiguous numbers in an array 6 AnswersAre you sure?! If this is the question then just add all numbers of the array lol. What about negative numbers in the array - you can't just sum it up Good point! In that case, just iterate over the array and: 1) n 0, add 3) next time you encounter n <=0, compare with the current max number and assign the new sum if larger. Show more responses The key word is "contiguous" - the solution above will nto work. Just google the solution - there are quite few options here. maximum subarray algorithm http://en.wikipedia.org/wiki/Maximum_subarray_problem Dynamic programming |
Software Engineer at Tripadvisor was asked...
Write a program that given 4 coin denominations and a dollar amount finds the best way to express that amount using the coins given. I.e. you have coins with denominations of 1c, 7c, 13c,19c and you have to express $2.12 with the least number of coins. There is always a 1c coin but the other 3 are arbitrary. 6 AnswersTurns out , this problem only has an elegant solution when the coin denominations are divisible by each other, such as the US coins (1, 5, 10, 25). Otherwise, it requires a (slightly optimized) brute force algorithm. I was told so by the interviewer after struggling with it using different approaches for about 40 minutes. If you have a coin of value 1, you can use a greedy algorithm: always select the most valued coin, until you have less money left that this value. Remove the coin, try again with less coins and the money left. Otherwise, just bruteforce and memoization, to implement a simple dynamic programming approach where you want to minimize the number of coins used, caching on the amount of money left to divide. Greedy algorithm is not right at all for general cases. This is a very classical questioin. If you fail on this question, I would say that it is probably your fault. Show more responses In all my years of giving and receiving interview questions I have never seen this one. It is definitely NOT a classical programming problem. Asking whether a candidate knows of an obscure academic puzzle does not sound like a good interview question. int main() { int currency[] = {19,13,7,1}; int money = 212; int i=0; int div=0; while (money>0) { div = money/currency[i]; money = money%currency[i]; if(div>0) { cout It is a classical programming question that derives from the first fit decreasing algorithm in discrete (decision) mathematics. |
Software Engineer at Wayfair was asked...
An array has negative and positive numbers. Separate the numbers such that negative numbers are at the beginning and positive numbers at the end without changing the order. You cannot sort it. Explain with O(1) space 8 AnswersHi, i cannot figure out a efficient way to solve this problem, could you please tell me how did you solve it? Show more responses $j && $val In Ruby, def arrange(array) array.partition { |x| x < 0 }.reduce(:+) end example, arrange([-3,-2,1,0,2,-4,-9,8,7]) gives [-3, -2, -4, -9, 1, 0, 2, 8, 7] In Python, def arrange(array): return [x for x in filter(lambda x: x = 0, array)] example, arrange([-3,-2,1,0,2,-4,-9,8,7]) gives [-3, -2, -4, -9, 1, 0, 2, 8, 7] The editor sanitized/ removed the code in the Python solution. That is not correct class Solution { static int[] arr; public static void swap(int pos){ int prev = pos - 1; while(prev >= 0){ if (arr[prev] < 0){ break; } int temp = arr[prev]; arr[prev] = arr[pos]; arr[pos] = temp; pos--; prev--; } } public static void main(String[] args) { int[] a = {1,2,-3,4,-8,12}; arr = a; for(int c = 0; c < arr.length; c++){ if(arr[c] < 0){ swap(c); } } for(int c : arr){ System.out.print(c + " "); } } } One or more comments have been removed. |
Software Engineer at Tripadvisor was asked...
Given four coins that could have any value (i.e. $.17, $.07, $.05, $.01), come up with an algorithm that figures out the fewest number of coins to get that value. 6 AnswersBuild a tree where the root node value is the amount you are trying to solve. Off of that node make a new node for for the amount with the value of each coin subtracted off. Do this recursively until until all solutions are found then do a breadth first search until you get to a leaf. for each coin x=value of coin int q=x/25 int d=(x%25)/10 int n=((x%25)%10)/5 int p=((x%25)%10)%5 return (q+d+n+p) Sorry. My description was a little ambiguous. I didn't mean using a quarter, dime, nickel, and penny. The coins themselves could have arbitrary values. For example, Coin A is worth 16 cents, Coin B is worth 9 cents, coin C is worth 4 cents, and coin D is worth 1 cent. Now using coins A, B, C, and D, find the fewest amount of coins to get to value X. Now the typical reaction is to subtract the largest coin from the total until the total is less then the value of that coin, repeat with the next smallest coin, and so on and count up the coins (like how the previous poster solved it). But that solution doesn't always work. Given the coin values described above, get the fewest coins for value X=18. This algorithm would result in 1 coin A and 2 coin Ds for a total of three coins but the correct answer is 2 coin Bs. The original solution with the tree and breadth first search is the way to get this answer. Show more responses I think use dynamic programming to solve this problem is quite easy. In Java: static int pickCoins(int valueIn, int[] coinsIn) { if (valueIn == 0) return 0; int num = 0; Set first = new HashSet(), second = new HashSet(), temp; first.add(valueIn); while (!first.isEmpty()) { num++; for (int i : first) { for (int j : coinsIn) { if (i-j == 0) return num; else if (i-j > 0) second.add(i-j); } // for-coinsIn } //for-first // swap first and second temp = second; first.clear(); second = first; first = temp; } //while return -1; } //pickCoins() public static int totalNum(int valueIn, int[] coinsIn){ Arrays.sort(coinsIn); int num = 0; for(int i = (coinsIn.length-1); i >= 0; i--){ num += valueIn/coinsIn[i]; valueIn = valueIn % coinsIn[i]; if (valueIn == 0) return num; } return -1; } From main: int[] coins = { 1, 7, 5, 11 }; int amount = 100;// $1 tatalNum(amount, coins) |
Software Engineer at Yelp was asked...
Write code to generate all possible case combinations of a given lower-cased string. (e.g. "0ab" -> ["0ab", "0aB", "0Ab", "0AB"]) 6 AnswersUsing iteration to generate the combinations of its prefixed substring and append the two possible cases of its suffix letter to the generated combinations. Could use a recursive approach ...similar to generating all subsets Ruby: def zok(str) return [] if str.empty? head,tail = str[0], str[1, str.length - 1] return [head.upcase, head.downcase] if tail.empty? zok(head).map { |h| zok(tail).map { |t| h + t } }.flatten.uniq end Show more responses import java.util.Iterator; import java.util.LinkedList; import java.util.List; /** * Assumption: the letters passed are all lowercase. If not, need additional checkings using isLowerCase()/isUpperCase() * */ public class CaseCombinations { public List convert(String s) { LinkedList list = new LinkedList(); if(s.length() == 0 || s == null) return list; if(s.length() == 1) { list.add(s); list.add(s.toUpperCase()); return list; } char c = s.charAt(0); List returnList = convert(s.substring(1)); Iterator it = returnList.iterator(); String partial; while(it.hasNext()) { partial = it.next(); list.add(c + partial); if(Character.isLetter(c)) list.add(Character.toUpperCase(c) + partial); } return list; } public static void main(String[] args) { // TODO Auto-generated method stub CaseCombinations cc = new CaseCombinations(); List list = cc.convert("0ab"); System.out.println(list); } } Ruby: def cases str str.chars.inject(['']) do |arr, char| if /[[:alpha:]]/ === char ups = arr.map{|seq| seq + char.upcase} downs = arr.map{|seq| seq + char.downcase} ups + downs else arr.map{|seq| seq + char} end end end Python: import itertools ['0' + "".join(i) for i in list(itertools.product("aA", "bB"))] |
Software Engineer at Google was asked...
write a program to translate alphanumeric phone number to numbers only 6 AnswersActual translation is easy. Store information is a hashmap (key,value) for example (abc, 2), (def,3) ...(wxyz, 9). You can get the information back very easily in O(1) time. Even when you have 20 characters in the alphanumeric string: 1(800)gofedex. It would still be very efficient O(20) etc...But extracting the information you need is somewhat complicated because you can't control what a user enters...lots of cases to consider...not in a 30 minute phone interview. Why wouldn't you map ..... ..? it reduces complexity of retrieval. You're saying you can't come up with a 10 line solution in 30 minutes but want a job at google? Once you came up with the crazy hashmap idea you had already failed the interview .... the solution to every problem is not a hashmap, especially when a simple lookup table will do. Show more responses public class PhoneConverter { public static List convertPhone (List list){ int[] values = new int[26]; int i=2; int j=0; for (char tag='a'; tag temp = new LinkedList(); for (Character c : list){ if (Character.isDigit(c)){ temp.add(Integer.parseInt(c.toString())); } else{ temp.add(values[c-'a']); } } return temp; } public static void main(String[] args){ List input = new ArrayList(); input.add('1'); input.add('8'); input.add('0'); input.add('0'); input.add('g'); input.add('o'); input.add('s'); input.add('z'); List output = convertPhone(input); for (Integer num : output){ System.out.println(num); } } } Yeah, this is a very simple problem IMO. As she suggested, you can just consider alphanumerics so you don't really have to worry about the input. Also you can convert all characters to small caps or big caps to make things easy. Then use a simple array of size 26 to map a character to its corresponding number, go through the input number and replace each character with the value in the array. {{{ void convert_numeric(char a[]) { char *p = a; char *post = a; char map[27] = {0}; strcpy(map,"22233344455566677778889999"); while(*p != '\0') { if((*p >= 'a') && (*p = 'A') && (*p = '0') && (*p <= '9')) { *post = *p; post++; } p++; } *post = '\0'; } }}} |
Software Engineer at Yelp was asked...
How to find the only different number in two unsorted arrays? 6 AnswersUsing HashTable to count the occurrence of each number Here is the C# code with HashTable class Class1 { public int Different_Number(int[] A, int[] B) { if (A.Length < B.Length) { return Hash_It(A, B); } else { return Hash_It(B, A); } } private int Hash_It(int[] A, int[] B) { Hashtable ht = new Hashtable(); for (int i = 0; i < A.Length; i++) { ht.Add(A[i], i); } for (int i = 0; i < B.Length; i++) { if (!ht.Contains(B[i])) { return B[i]; } } return null; } public static void Main() { int[] A = new int[] { 1,5,3,8}; /* Unsorted array */ int[] B = new int[] { 5,3,8,2102,1}; Class1 cls = new Class1(); Console.WriteLine(cls.Different_Number(A, B)); Console.ReadLine(); } } You can use xor Show more responses Why not just sum both arrays up the difference will be the different no. In Python: from collections import Counter def diffNum(a,b): aCount = Counter(a) for x in b: if x not in aCount: return x return None a = [1,3,4,5,2] b = [1,2,7,5,4,3] print diffNum(a,b) Given 2 lists a and b with one element that is different, sum(a) - sum(b) will give you the element |
Software Engineer at Google was asked...
Find the largest 100 numbers out of a list of a trillion unsorted numbers 5 AnswersUse a heap to hold the 100 largest numbers so far. If the new number is larger than the heap top (the smallest number in the heap) pop it out and add the new number. The worst case complexity is O(N * log(100)). Hence log(100) is a small constant (7) the complexity should be good enough. That's a great idea. Another approach could be using a select algorithm to select the N-100 biggest number in O(N) time and then partition around its value, again in O(N), to get the 100 biggest numbers (in unsorted order). Note that this is actually independent of how many of the largest numbers you need. Would it be crazy to just merge sort the numbers and then print the last 100? Show more responses @Chris - yes, because mergesort is O(n logn) where n = 1 trillion; sorting is _highly_ inefficient in this case. A heap is not a great idea because you would have to copy/move all the elements to insert one in the middle. If you use a linked list and insert records as needed you never have to do a multipass sort |
See Interview Questions for Similar Jobs
- Senior Software Engineer
- Software Developer
- Associate Software Engineer
- Java Developer
- Software Development Engineer
- Intern
- Analyst
- Business Analyst
- Consultant
- Technical Lead
- Trainee Software Engineer
- Engineer
- Software Development Engineer II
- Systems Engineer
- Fresher
- Technical Support Engineer
- QA Engineer
- Software Engineer II
- Associate
- Project Manager