Interview Question

Interview(Student Candidate)

First question was to find all numbers that occurred an

  odd-number of times in an array and second question was implement a stack that could return the largest number in the stack at anytime.
Answer

Interview Answer

3 Answers

1

Find all numbers that occurred an odd-number of times in an array Create vector of pairs: boolean and integer value Iterate through array: - For each value, check if it is in the vector: - If not, add it and set its boolean value to true - If it exists, flip its boolean value All values in vector that have boolean values set to true have an odd number of occurrences in array Implement a stack that could return the largest number in the stack at anytime * Assuming stack grows positive: Store index of -1 before stack is populated As items are pushed onto stack, check: - If index is -1, set it to first index in stack (zero) - If index is greater or equal to zero, compare new value: - If not larger, increment index by one - If new value is larger, reset index to zero Index will provide offset to largest element in stack * If stack grows negatively, set to 1 instead and decrement if new value is not larger ** Could also store largest number instead of index, dependant on implementation desire

Anonymous on Jan 8, 2015
0

For the first question, you can use a hash table data type with integer as the key as well as the value. Looping over the array. For every single integer in the array, if it isn't in the hash table, put (the integer, 1) into the hash table, otherwise, remove the entry from the hash table. At the end of the loop, the key set of the hash table contains all numbers that occurred an odd-number of times in the array.

Anonymous on Jun 15, 2015
0

For the first question I found this solution http://www.davismol.net/2014/03/01/amazon-interview-find-the-only-element-that-appears-an-odd-number-of-times-within-an-array-of-integers even if in this case there is only one element that appears an odd number of times

Anonymous on Jun 30, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.