## Amazon Interview Question for Software Engineer / Developers

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

Do an XOR operation on all the numbers.. final output is the number which appears odd number of times.

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

Mr Teja,
Can you please write code and explain

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

XOR of a number with itself will give you a 0. 0 XOR'd with any number will give you the same number. Thus an even count of a particular number will give you a 0 while an odd count will give you the number itself.

If you XOR all values one after the other, the even count values will cancel each other out and only the odd count value will remain at the end.

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

xor all the elements.. the result will be the element which appear odd no. of times.

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

nice approach...

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

nice approach...

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

I think it is the best solution!

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

1. Sort the array
2. read through the sorted array and find the integer that appears odd number of times
Complexity = O(n log n) + O(n)

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

take one more array of size equal to domain of the integers present in the given array

initialise this array with zero(count)
trevel to the original array increase the corresponding count value in new array..and finally travel this new array to know the output i.e. count value should be odd

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

Apply xor operation on given array elements and result is the required element

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

we can think on soritng and hashing also

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

soln1.) O(2n)=O(n)
1.)Push the count of elements in the HASHMAP - O(n)
2.)loop through the elements in the hashmap and check for %2==0 if not then thts the integer O(n)

soln2.) Solution requires O(n), does not require u to loop thru the hashmap entries
1.)Push/increments the count element in the hashmap
2.)Decrement the count as you see the element again when tranversing
and keep a check if the count is 0 if yes, delete the hashmap entry
3.)The last element remaining in the hashmap is the element required

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

Simpler..
1. Traverse over the Array
2. For each element .. check if element is present in hashset.. if present remove the entry else add the element to hashset
3. Whatever element tht remains in the hashset.. is the answer

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

ya. good .. nice approach

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

we can solve the problem with the help of hashmap or hashtable aswell.
1 read through the area and keep the elements and its count in hashmap
2 the value is already available . increase the count value .
3 if it is not available . put entry in hashmap element with the count value 1
finally iterate through hashmap and check for entry for which odd number of count value.

so time complexity-o(n)
space complexity-o(n)

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

we can solve the problem with the help of hashmap or hashtable aswell.
1 read through the area and keep the elements and its count in hashmap
2 the value is already available . increase the count value .
3 if it is not available . put entry in hashmap element with the count value 1
finally iterate through hashmap and check for entry for which odd number of count value.

so time complexity-o(n)
space complexity-o(n)

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

Java Pseudocode
int[] arrContent={1,3,7,3,9,7,1};
// Papulate hash map content
HashMap<int,int> oddMap=new<int,int> HashMap();
for(int i=0;i<arrContent.length;i++) {
if(!oddMap.containKey(arrContent[i])) {
oddMap.put(arrContent[i],1);
}
else {
int count=oddMap.get(arrContent[i]);
oddMap.put(arrContent[i],++count);
}
}

// iterate through hashmap and find the value

Set set=oddMap.keySet();
Iterator it=set.iterator();
while(it.hasnext()) {
int element=it.next();
int countVal=oddMap.get(element)
if(countVal%2==1) {
System.out.println(" Element with the odd number of count"+element);
}
}

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

Java Pseudocode
int[] arrContent={1,3,7,3,9,7,1};
// Papulate hash map content
HashMap<int,int> oddMap=new<int,int> HashMap();
for(int i=0;i<arrContent.length;i++) {
if(!oddMap.containKey(arrContent[i])) {
oddMap.put(arrContent[i],1);
}
else {
int count=oddMap.get(arrContent[i]);
oddMap.put(arrContent[i],++count);
}
}

// iterate through hashmap and find the value

Set set=oddMap.keySet();
Iterator it=set.iterator();
while(it.hasnext()) {
int element=it.next();
int countVal=oddMap.get(element)
if(countVal%2==1) {
System.out.println(" Element with the odd number of count"+element);
}
}

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

sorry i forgot to put break statement within if block

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

#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int n;
int a[100],count[100]={0};
cout<<"enter no of elements";
cin>>n;
cout<<"enter the elements";
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
count[a[i]]++;
for(int i=0;i<n;i++)
{
if((count[a[i]]%2)!=0)
{cout<<"element repeating odd tyms is "<<a[i];break;}
}
getch();
}

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

``````|x|y|xor|
|0|0| 0 |
|0|1| 1 |
|1|0| 1 |
|1|1| 0 |

x^0=x
x^1=!x
x^x=0

from the above truth table and equations we can see that any number x which is xor'd with itself an even number of times will result in zero.  However, if it is xor'd with itself an odd number of times then the result will be itself.

for example:
int numbers[] = { 1,2,1 };
int result = 0;

result ^= numbers[0] = 1;
result ^= numbers[1] = 3;
result ^= numbers[2] = 2;``````

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.