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.

- Teja February 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Mr Teja,
Can you please write code and explain

- Mansoor Shaikh Vice President Barclays February 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- TY February 04, 2010 | Flag
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.

- Anonymous February 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice approach...

- Anonymous November 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice approach...

- Anonymous November 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it is the best solution!

- sergey.a.kabanov January 13, 2012 | Flag
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)

- Anonymous February 05, 2010 | Flag Reply
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

- gautam kumar February 05, 2010 | Flag Reply
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

- indra February 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can think on soritng and hashing also

- gautam kumar February 09, 2010 | Flag Reply
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

- Raj February 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Amit December 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

ya. good .. nice approach

- sathiyan k April 25, 2010 | Flag Reply
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)

- Anonymous April 25, 2010 | Flag Reply
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)
Reply to Comment

- sathiyanannauniversity April 25, 2010 | Flag Reply
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);
}
}

- sathiyanannauniversity April 25, 2010 | Flag Reply
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);
}
}

- sathiyanannauniversity April 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry i forgot to put break statement within if block

- sathiyanannauniversity April 25, 2010 | Flag Reply
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();
}

- aks June 27, 2010 | Flag Reply
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;

- vick May 13, 2011 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More