## Amazon Interview Question for Software Engineer / Developers

• 0

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

Basic bit manipulation problem:
Just XOR all the elements in the given array, output will be the no which appeared in array an odd number of times.

for(i=1;i<array.length;i++)

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

XOR won't work for [2,4,6,6] = 6
In good software engineering practices you should validate your arguments and in this case the cost of validation is the same as using the map solution

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

Sure it wouldn't work. 'cause only one integer must appear an even number of times. In your case, [2, 4, 6, 6], two integers (2 and 4) appear only 1 time. This example works fine - [2, 4, 2, 6, 6]. The answer is 4.

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

XOR is a solution if you can validate the input in O(n) time and O(1) space... I don't think that's possible

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

This XOR will work if and only if ONE number appears in array ODD no of times, and all other appear EVEN no of times. And this is what said in the question. So this XOR soln assumes that ONLY one number appears ODD times.

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

We can use a hashmap where key is the number and value is a bit.

1. Start traversing the array and pushing into the hashmap
2. If no key found with the number being traversed push into hashmap with value 0
3. If a key is found for the number being traversed just alter the state of the value (i.e., 0 if 1 and 1 if 0)
4. Parse the hashmap once to find:
a.) 0, if we are looking for one number which is repeated even number of times.
b.) 1, if we are looking for one number which is repeated odd number of times.

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

Use hashtable
during the 1st scan of the array, check wat is returned from
object o=hashtable.get(arr[i])
if o is null then hashtable.put(arr[i], odd)
if o==odd, then hashtable.put(arr[i], even)
if o==even, then hashtable.put(arr[i],odd)

finally scan the array and return arr[i] for whichever the hashtable.get(arr[i]) returns even.

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

class Program
{
static void Main(string[] args)
{

int[] a = {3,6,3,5,7,5,7};
HashSet<int> h = new HashSet<int>();
for (int i = 0; i < a.Length; i++)
{
if (!h.Contains(a[i]))
{
}
else
{
h.Remove(a[i]);
}
}

foreach (int i in h)
{
Console.WriteLine(i);
}

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

IS there any way to find the reverse.i.e. All but one appears odd no of times.And we have to find the element which appears even no of times?

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

Why cant we write a simple code like this...
#include <stdio.h>
#include <conio.h>
#define N 10
int main()
{
int a[N]={1,2,3,1,2,4,9,3,6,6},temp,cnt;
for(int i=0;i<N;i++)
{
temp=a[i];cnt=0;
for(int j=0;j<N;j++)
{
if(a[j]==temp)
cnt++;
}
if(cnt%2!=0)
printf("%d\n",a[i]);
}
getch();
return 0;
}

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

Why cant we write a simple code like this...
#include <stdio.h>
#include <conio.h>
#define N 10
int main()
{
int a[N]={1,2,3,1,2,4,9,3,6,6},temp,cnt;
for(int i=0;i<N;i++)
{
temp=a[i];cnt=0;
for(int j=0;j<N;j++)
{
if(a[j]==temp)
cnt++;
}
if(cnt%2!=0)
printf("%d\n",a[i]);
}
getch();
return 0;
}

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

of course we can. The issue is how much time you cost for your alg. n^2 is bad answer maybe.

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

Hash table: Time: O(n), space: O(n)
Sort and count: Time: O(nlogn), space: O(1)

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

XOR all of them: Time: O(n), Space: O(1)

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

This is the best solution.

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

hashtable:

key-> value of array
value-> array indexes

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.

### 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.

### 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.