## Amazon Interview Question Software Engineer / Developers

• 0

Given an array of positive integers, print out all the numbers which are repeated an even
number of times? Can you do this without using additional storage?

Country: United States

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

It can be done without extra storage given the data has some bounds. Generally, if you have n elements and you are guaranteed that the elements are between 0 to n-1, we can use the value of the element itself as an "index" within the array and change the data to mark the item as read. For example, if a[i] =3, you can go to third index and multiply the value by -1 (a[3] * -1). But this requires the data to be bounded

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

I think the same. Since in the statement is said "array of positive integers" probably they do not mean to just sort in nlogn.

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

No need to the element to be in any range!

See my comment below for the approach!

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

@words&lyrics: your approach makes some assumptions that are probably not acceptable

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

@eugene: I agree, but I specified them. And I guess interviewer was looking for this approach as well as
otherwise it seems is not possible to come up with a solution for this!

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

@words&lyrics: You didn't specify the assumptions correctly. Your approach assumes that all elements are between [min, min + arr.length - 1]. How is that justified?

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

Please look at the solution again! Either I don't understand you or you missed something. Can you explain how I have assumed that?? I didn't intended

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

To my understanding, the sign of element at each position is used to indicate the repeating pattern. So negative means a number appears for odd number of times, and positive means appearing for even number of times. But what if a number never shows up? in that case, the sign is positive, how to catch this case?

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

sort

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

yes it can be done in n.ln(n) time by using sorting. first sort the array and then you have to traverse the array once to count the number of appearances.

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

Correct.
Before giving the answer, should ask interviewer if its ok to sort the array. 2 cents! :)

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

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

O(n) time O(1) Space

1. Find max and min
2. Traverse the array and for each a[i] change sign of a[[a[i]- min]]

Each time a element is found sign of location corresponding to that
(mapped to a[i]-min) changes sign. So same sign after this traversal means
even number of occurrences, different sign means odd no. of occurrences

3.Finally traverse the array from i =0 to i = max-min
and look for -ve element at location 'j'.
4. Return j+min

This algorithm will work only if all elements are of same sign initially

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

This assumes that all elements are between [min, min + arr.length]. This is blatantly false for most inputs.

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

I didn't understand what you mean! My only assumption was that they are of same sign. Can you
be more clear??

Please look again j can be between min and max-min
so j+min is between min to max, where min and max are minimum and maximum in the array

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

"Each time a element is found sign of location corresponding to that (mapped to a[i]-min) changes sign"

Why is a[i]-min necessarily in bounds? It's not, unless all a[i] are in the range [min, min + arr.length - 1]

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

Sorry I mean j can be b/w 0 and max-min
so j+min is between 0 and max

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

"2. Traverse the array and for each a[i] change sign of a[[a[i]- min]]"

Again, same assumption.

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

I got this!
Thanks for pointing

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

What is correct solution for this problem?

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

I think the solution for specific ranges and the sorting solution pretty much cover it.

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

Eugene: I guess its not possible to do this without extra space??

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

If you want no extra space and can't destroy the input, you'll have to use the naive quadratic time algorithm.

The two approaches discussed don't use extra space but do destroy the input.

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

#include <math.h>
void main()
{
int a[] = {3,3,5,5,5,7,7,8,8,8,9,9,3};

for(int i = 0; i<13; i++)
{

if(a[abs(a[i])] > 0)
{
a[abs(a[i])] = -a[abs(a[i])];
}
else
{
a[abs(a[i])] = -a[abs(a[i])];
}
}

for(int i =0; i<13; i++)
{
if(a[abs(a[i])] > 0)
{
printf("\n even time %d ", abs(a[i]));
}
/* else
{
printf("\n odd time %d ", abs(a[i]));
}*/
}
}

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

The program crashes for this input......

int a[] = {221,9,3,3,5,5,5,7,7,8,8,8,3};

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

What if I will change the array to int a[] = {13,3,5,5,5,7,7,8,8,8,9,9,3}
made the first element of array greater than the length of the array

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

Assuming the array can be sorted using standard C/C++ library functions here is the code to count the even number of occurring elements in the given array. It is better to ask the interviewer that the array can be sorted as suggested by some one in this thread.

``````void CountEvenOccurences(int *array,int length)
{
int prev_key = array[0];
int num_count = 1;
for (int i = 1; i < length; i++) {
int curr_key = array[i];
if (curr_key == prev_key) {
++num_count;
continue;
}
if ( (num_count %2) == 0 ) {
printf("Element %d occurs %d times.\n",prev_key,num_count);
}
prev_key = curr_key;
num_count = 1;
}
}``````

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

here complexity is O(n^2)

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

``````public class EvenlyRepeated {

/**
* @param args
*/
public static void main(String[] args) {

System.out.println("Even repetation xor is " + (3 ^ 3 ^ 3 ^ 3));
System.out.println("Odd repetation xor is " +  (2 ^ 2 ^ 2));

int[] values = { 1, 2, 3, 4, 1, 2, 3, 1, 2, 1 };
for (int i = 0; i < values.length; i++) {
int result = values[i];
for (int j = 0; j < values.length; j++) {
if (i != j && values[i] == values [j]) {
result = result ^ values[j];
}
}
if (0 == result) {
System.out.println(values[i]);
}
}
}

}``````

This works but prints repeated numbers every time it appears in array. This can be fixed by sorting array and then breaking loop on next number.

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

This is O(n^2) solution. Also you dont need xor here...for two numbers simple equality check will do..

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

complexity is O(n^2)...
xor is not required at all...

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

``````//O(n log n) solution
public static void printOutEvenRepeats(int[] A) {
Arrays.sort(A); //O(n log n)
int currentNum = A[0];
int numSeen = 0;
for (int i = 0; i < A.length; i++) {    // O(n) in worst case
//			We see the same number
if (A[i]==currentNum) {
numSeen++;
if (i==A.length-1) {
if (numSeen != 0 && numSeen % 2 == 0)
System.out.println("We saw  " + currentNum + " an even number of times.");
}
}
//			The value at this array index is a different number.  Reset numSeen and the currentNum
else {
if (numSeen != 0 && numSeen % 2 == 0)
System.out.println("We saw " + currentNum + " an even number of times.");
numSeen = 1;
currentNum = A[i];
}
}``````

}

Name:

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

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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