Software engineer Interview Questions in Boston, MA | Glassdoor.co.in

# Software engineer Interview Questions in Boston, MA, US

3,590

software engineer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

### Software Engineer at Vistaprint was asked...

21 Jan 2010

22 Mar 2012
 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 searchShow more responsesIf 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.

11 Mar 2012
 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 upGood 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 responsesThe 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_problemDynamic programming

27 Apr 2012
 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 responsesIn 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) { coutIt is a classical programming question that derives from the first fit decreasing algorithm in discrete (decision) mathematics.

### Software Engineer at Wayfair was asked...

2 Nov 2015

19 Apr 2011
 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 responsesI 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)

13 Mar 2014

17 Oct 2011