## Amazon Interview Question for Principal Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
6
of 6 vote

You can do this using only one HashSet. Add new element to HashSet if its not already in the HashSet - else, remove it from the HashSet. This will make sure by the end of the iteration - the HashSet will only have the odd* occurring elements. Accessing elements in a HashSet is O(1) complexity. The overall time-complexity is O(n) for the linear traversal of the array elements.

Comment hidden because of low score. Click to expand.
0

To add on - HashSet uses HashMap internally to store its entries.

Comment hidden because of low score. Click to expand.
0

I second your idea. But you cannot access the elements in HashSet in O(1). Only the contains method return the element in O(1). You will have to iterate over the set.

Comment hidden because of low score. Click to expand.
0
of 0 vote

(1)use two HashSets instead of one HashMap, one for those numbers occurred odd times so far, let's call it oddSet, while the other for those occurred even times being evenSet.
(2)iterate to next number, if it has been in oddSet, we remove it from oddSet and add it to evenSet, otherwise we add it into oddSet and remove it from evenSet.
(3)finally, those numbers that occurred odd times are all in oddSet.

Comment hidden because of low score. Click to expand.
0
of 2 vote

XOR works when there is exactly one number that occurs odd number of times and also there should not be any 0 in the array.

``````int getOddFreqNumber(int[] array) {
int oddFreqNumber = 0;
for (int i=0; i<array.length; i++)
oddFreqNumber = oddFreqNumber ^ array[i];

return oddFreqNumber;
}``````

Comment hidden because of low score. Click to expand.
0

This is only possible for only 1 odd times number in the array, is it?

Comment hidden because of low score. Click to expand.
0

we can have a counter for zeroes . It it's odd , we know zeroe's have occured an odd number of times

Comment hidden because of low score. Click to expand.
0
of 0 vote

why not doing it like sql? You can use group by the same number with count. Then return the number that has odd count? of course, if this is an interview, they probably won't let you use the easy and best way to do it unless you interview for microsoft.

Lambdas in C#
str.GroupBy(n => n).Select(s => new {num = s.Key, count = s.Count()}).Where(g => (g.count %2) != 0);

you can use Quaere in Java.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int getOddOccurrence(int ar[], int ar_size)
{
int i;
int res = 0;
for (i=0; i < ar_size; i++)
res = res ^ ar[i];

return res;
}

/* Diver function to test above function */
int main()
{
int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
int n = sizeof(ar)/sizeof(ar[0]);
printf("%d", getOddOccurrence(ar, n));
return 0;
}

But it works only for +ve integers

Comment hidden because of low score. Click to expand.
0
of 0 vote

//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
{
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
{
}

int i;
//Iterate each element in the array
for(i=0;i<number.length;i++){

{
}
else
{
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
{
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
{
}

int i;
//Iterate each element in the array
for(i=0;i<number.length;i++){

{
}
else
{
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ //Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) { return oddNumbersSet; } int i; //Iterate each element in the array for(i=0;i<number.length;i++){ if(oddNumbersSet.contains(number[i])) { oddNumbersSet.remove(number[i]); } else { oddNumbersSet.add(number[i]); } } return oddNumbersSet; } }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Find oddnumber in array public Set<Integer> getListOfOddNumbers(int[] number) {{{ Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length); if(number.length<0 || number==null) {{{ return oddNumbersSet; }}} int i; //Iterate each element in the array for(i=0;i<number.length;i++){{{ if(oddNumbersSet.contains(number[i])) {{{ oddNumbersSet.remove(number[i]); }}} else {{{ oddNumbersSet.add(number[i]); }}} }}} return oddNumbersSet; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)

Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)

int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)

else

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)

Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)

int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)

else

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)

Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)

int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)

else

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)

Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)

int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)

else

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)

Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)

int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)

else

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)

Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)

int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)

else

Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the array and then apply XOR

Comment hidden because of low score. Click to expand.
0
of 0 vote

A hash function associated with a linked list can be the best solution. Hash function uses number as a key and address of node in linked list as value. Hash function initialize its entries as NULL. If a number is not present in hash map ,add it to linked list and store its address in hash map.otherwise remove it from linked list.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another approach:

Step 1. Heapify the numbers - O(log n)

Step 2. Read through each element: O(n)
- Since the items are already sorted, repeat items keep coming out one after the other.
- Count these. When number changes, determine if the previous number recurred odd/even number of times (counter's value) and print accordingly.

Overall time complexity: O(log n) + O (n) = ~O(n)
Additional Space : 0 if we can reuse the input array.

Comment hidden because of low score. Click to expand.
-1
of 3 vote

when you have a new number, just to search if it's already in the hashmap,
1) if it's in the hash map, delete it.
2) otherwise, add it to the hash map
At the end, all the numbers in the hash map should have odd occurrences.

Comment hidden because of low score. Click to expand.
0

I think O(n) lookup here means iterating through map to print odd frequency digits, which we have to somehow to get rid of. Your method doesnt get rid of that step.

Comment hidden because of low score. Click to expand.
0

What?

If you have a case where all the numbers are occuring odd times, then you still need to "print/access" them in a final loop. This will be ~ N/3 = O(n) "second thing" as you say.

How would you get rid of "another second O(n) thing?"

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Use radix sort, complexity is O(n). Then scan the list again.

Comment hidden because of low score. Click to expand.
0

What if individual digits are big?

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Your algo's time compplexity in nlogn

Comment hidden because of low score. Click to expand.
0

can you explain how it's nlogn.. you 're just going to Xor all the nos ?

Comment hidden because of low score. Click to expand.
0

First of all XOR all nums will give result only when there is only one digit that is repeated odd number of times. Clearly here there are multiple digits that are repeated odd number of times. So your first algo will fail. Your second method says sorting which takes nlogn.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.