Amazon.com Interview Questions | Glassdoor

# Amazon.com Interview Questions

7,513

interview questions at Amazon.com shared by candidates

## Amazon.com Interview Questions

Sort: RelevancePopular Date

Apr 28, 2009

Mar 1, 2012

### Software Engineer at Amazon was asked...

Mar 29, 2011
 Write an algorithm to determine whether a given number is of the form (2^n)+1, where n is an integer.17 AnswersSubtract one and then keep dividing by two until you either get to 1 (true) or the number is not evenly divisible (false).return (n == 1) || ((n-1)&(n-2) == 0);bool if_power(int n) { n--; return n&(n-1) ? false : true ; }Show More Responsesif(n%2==1) return TRUE else return FALSEboolean isapower(int pow, int num); int main(){ int num = 2; int pow = 2; if(isapower(pow, num-1)) { printf("%d is power of %d + 1", num, pow); } else { printf("%d is not power of %d + 1", num, pow); } return 0; } boolean isapower(int pow, int num) { while((num > pow) && (num % pow == 0)) { num /= pow; }; return num == pow; }if(n & (n-1))==(n-1) return true else return falseThe simplest answer would be: (number & 1) == 1. The last bit should be 1.Sorry. That answer is for checking odd or even. Not power of 2 + 1.The interview candidate's answer does not account for (2^0) + 1. It would return false for that. Another option. Assuming Int x contains the value: boolean correctForm(int x) { x--; String binString = Integer.toBinaryString(x); if (binString.charAt(0) == '0') { return false; } for (int i = 1; i < binString.length(); i++) { if (binString.charAt(i) != '0') { return false; } } return true; }(number - 2) in binary must be all 1s because 2^n-1 isits binary form must match regexp \$0*10*1^public class isPowerOf2 { public boolean isPower(int number){ if(number <=0){ return false; } number = number -1; if((number & -number) == number) return true; else return false; }boolean isPower(int num){ num--; Boolean foundOne = false; for(int i = 1; i < sizeof(int); i++){ if((1<

Feb 27, 2010

### Software Design Engineer at Amazon was asked...

Mar 19, 2009
 Given a string find the first non-repeated character.10 AnswersHint: use a hash tablepublic static char getFirstNonRepeatedChar(String s) { List charList = null; char nonRepeatedChar ='?'; if (s != null) { s = s.trim(); charList = new ArrayList(); for (int i=0; i 1): continue else: return x return "No nonrepeating character found"for (int index = 0; index < str.Length; index++) { if (str.LastIndexOf(str[index]) == str.IndexOf(str[index])) { return str[index].ToString(); } }I will have one variable x to store the first non repeating character, variable y as a backup And a set of characters already encountered. I will start from position n to position 0 where n is the lenght of the string. If char(n) is not present in the set, then check if x=char(n), if yes, x = y. If no, y=x and x=char(n). The idea is to keep updating the newest character that has not been repeated and also keeping the second newest character as a backup. In the end return x.

### Software Engineer at Amazon was asked...

Jul 12, 2012
 given an array of numbers to remove the duplicates11 AnswersI'm not sure. Maybe use merge sort and throw away duplicate values.Sort the array in place. Then iterate and you can easily find duplicates by comparing the current and previous values. Sort is n log n; iterate is n. Total is n log n.That is the answer that I gave. The interviewer than asked "how do you delete the duplicates from the array." I couldn't figure out that part.Show More ResponsesThe simplest way is to use a set (no duplicate keys, and, if values are used as keys, no duplicate values). This way you simply need to iterate over the entire array and add each key/value into the set (it ignores adding it if it's a duplicate).Matt, Can't use more memory.1) Sort this array by using quicksort, so the time will be O(nlogn), 2) Start p1 pointer at beginning, and p2 at last and start move p1++ 3) if found p1 == previous p1, sway p2 and previous p1, and move p2--, the idea is trying to move all duplication to the end of arrary, 4) keep doing 3) till p1 = p2, 5) so we have a clear array without dup, then use quicksort again from index 0 - p1if you want to remove duplicate element in the array, try this algo: num = 0; for (i =0; i < arr.length()-1; i++) { if (arr[i] < arr[i+1]) { arr[num++] = arr[1]; } } arr[num] = arr[n-1];http://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-arrayin C# 3.5+ , you can use LINQ query //given array arr arr.Distinct().ToArray(); removes duplicatesConvert array to a set. If thats not an option, consider, counting sort if range known else merge sort as mentioned by some one earlierHow about using HashTable or Dictionary to store the array values as keys. We can use ContainsKey method to skip over duplicates. Once the array elements are copied into the dictionary, we can convert the dictionary keys into an array to get a non-duplicated version of the original array This is constant space, but linear time. However this method will not keep the original order of the elements.

### Software Development Engineer at Amazon was asked...

Jun 24, 2010
 List all anagrams in a file. Assumptions: case-insensitive, a-z characters only, one word per line. For example, if the file contains dog, cat, ddd, goo, act, god -- output dog, god, act, cat10 AnswersThankfully I was taking a theory course and one trick used in the course was "encoding" programs as a large natural number using product of primes. 1. Adapt the encoding as follows -- generate the first 26 primes and assign a prime to each letter 2a. For each word, take the product of each letter's prime. So #(act) = 2*5*prime(t) 2b. As you can see, #(cat) = 5*2*prime(t) = #(act) 3. Insert a handwavey argument about inserting the number/word pairing into a HashMap>Sort the words. Anagrams appear next to each other in the sorted list.Sorry, sort the letters in each word, then sort the words. Anagrams appear next to each other in the list. For example the sorted list for the input would be: act act ddd dgo dgo gooShow More ResponsesThanks for sharing Bill For this set of input, the expected output should contain only [cat, act, god, dog]. I'm curious to see what "next steps" your algorithm will perform to provide this expected outputYou keep track of the mapping from the sorted word to the actual word in a pair, for example: [act, cat] [act, act] [ddd, ddd] [dgo, god] [dgo, dog] [goo, goo] Then you go through this list and count if you have a duplicate entry or not. If you do, like for act, you print out those duplicate entries: cat, act.Bill, your algorithm is O(n*log(n)) while the candidates would be O(n) - provided he uses a decent hash functiondonutello, bills algo is not n log n it is n*log(k) where as candidates algo is n * k again (multiplications for each word) where k = length of the longest word on top of that calculating primes is expensive anyway I would go with bills answerBills algo is nlogk + nlgn. After sorting the k letters for n times you also have to sort the n words.#Get inputs a = [] f = open('input.txt','r') for line in f: line = line.strip() a.append(line) #Sort letters in a word def sort_letter(s): r = [] for i in s: r.append(i) t = sorted(r) v = ''.join(t) return v #Find anagrams d = {} for v in a: sv = sort_letter(v) if sv in d: d[sv].append(v) else: d[sv] = [v] #Print results for k,v in d.items(): if len(v) > 1: for s in v: print sthink of each line as a set of characters, not a word, then create set of sets of characters which you fill from the input. then print the set (order does not matter as its not specified)

Feb 15, 2012