Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

I can't see a way to do this if the arrays are unsorted. A linear-time common-elements algorithm does not come to mind on unsorted array

- Anonymous January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Since the integer is not larger than 2^32, simply use a bit map of size 2^32 can help, the total size is only 2^29 byte, which is 500Mb. Certainly modern computer can do that.

- lixing January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u please elaborate a bit.... in array we can store the occurencences as given in above post.. but in one bmap hw wud u implement tat..... i can understand tat we can do it if we use 2 bmaps..

- andy_kumar January 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I love this bitmap idea

- chenlanbo1988 February 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hashing integer will not work if the memory is limited. May be bitvector would be acceptable.

- Rayden January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We'd need a count unless we know there are no duplicates.

- eugene.yarovoi January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That actually needs clarification. For instance if input arrays are {1,1,1} and {1,1,2} is the output suppose to be 1,1 or just 1?

- Anonymous January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous:Output is supposed to be just 1.

- doomguy January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

duplicates is not a matter here, because we just need to find shared element, we can just ignore duplicates in first array

- tony June 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

by tweaking the external merge sort

First sort both the arrays using external merge sort....
Now you have 2 arrays which are sorted....

Now repeat extenal merge sort on both the arrys but
Now while merging this two arrays using external sorting...
if the front elemnets of both the arrays are same then include them in a separate array...(i.e tweak the merge step)...

- y so serious? January 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

merge sort is not O(N).

- srt January 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do not jump onto solution. Asking more *clarifying questions* on 'type' of data will drive solution easy, which is what interviewer expects too.

- saga January 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

HashSet<Integer> a = new HashSet<Integer>();
a.add(4);
a.add(2);
a.add(5);
a.add(6);
a.add(1);
a.add(3);
a.add(7);
a.add(9);

HashSet<Integer> b = new HashSet<Integer>();
b.add(4);
b.add(2);
b.add(6);

a.retainAll(b);
System.out.println(a);

In this way, you can make this one O(1).

- swoosh9144 January 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cool this is the best way..!!

- cp January 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good thinking but retainAll is not O(1)
retainAll is an inbuilt JAVA algorithm which takes higher time complexity.
(nobrainer .co .cc)

- Anony February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

There is no restriction placed by the interviewer on the secondary storage. So we can use it I suppose.

1. Read the integers in file1 one by one and make files with that name.
2. Open the second file and read the integers one by one. For every integer you read check the existence of the file.
3. If the file exists then print the integer as common.

It O(n+m) solution i.e. O(n).

- rishi.b.agrawal February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very inventive thinking Rishi. Truly refreshing. :)

- Pavan Dittakavi May 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's a truly horrifying solution, in every way worthy of the Daily WTF. So you're saying that you would create as many files as there are integers? If the integers don't fit in memory, isn't it because there are probably, say, > 1B of them? So you're going to create over 1B files on your system?

Worse perhaps is the person who thinks this solution represents refreshing thinking. An Einstein quote comes to mind here: "Creativity is no substitute for knowing what you're doing."

- Anonymous May 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A bit map of integer size containing all ints require only 2^32 space = 4 GB of RAM.

First step: Prepare this bit map and store it on disk.

Suppose the total memory available to program is 2 GB.

Second step : So take the first 1 GB of bitmap from first array and another GB of bitmap from second array. Compare them and store it in a third file in bitmap format. Do same thing for the rest of the array.

Third Step: Convert bit map back to integer array.

- nidhi February 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

bit array, size = 2^32 bits,
total mem size of the array is
2^32 / 8 bytes = 0.5 G = 500M
not 4G

- asuran April 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A bit map of integer size containing all ints require only 2^32 space = 4 GB of RAM.

First step: Prepare this bit map and store it on disk.

Suppose the total memory available to program is 2 GB.

Second step : So take the first 1 GB of bitmap from first array and another GB of bitmap from second array. Compare them and store it in a third file in bitmap format. Do same thing for the rest of the array.

Third Step: Convert bit map back to integer array.

- nidhi February 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Convert first array into a Binary tree...for each element in the second array , find if tat is present in b tree.. if so, then its common element ,else continue wit next element..

search in tree : log n
for m elements in second array... so m logn

- Sathish_master February 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Second step : So take the first 1 GB of bitmap from first array and another GB of bitmap from second array. Compare them and store it in a third file in bitmap format. Do same thing for the rest of the array.

Third Step: Convert bit map back to integer array.

- nidhi February 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As we have integers we can have +ve and -ve numbers

We can build a bitmap actually 2 bitmaps one for +ve and one for -ve
We simple mod a -ve number to get the position in a bitmap.
Build bit map for both the arrays and then "AND" them together.

Which ever bit is set to one is the common number.
Any repeating integer in single array can be rejected. This can be looked at a more compress hashmap.

- blackice February 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can store the one array integers into a hash map . Maximum number of different integers can be stored in RAM . Hash map will have only unique integer values. Duplicates are ignored.


Here is the implementation in Perl language.

#!/usr/bin/perl
use strict;
use warnings;
my @arr1,@array2; # array elements assumed to be filled 

my $hash; # hash map to store value of one array

# runtime to prepare hash map is O(n). 
foreach my $ele ($arr1){
$hash->{$ele}=true; # true here element exists key is integer number and value is true, duplicate elements will be overwritten

# size of array will fit in memory as duplicate integers are ignored   ( mx size will be 2 ^( 32) -1 or 2^(64) -1 based on operating system) which can be stored in RAM.
} 
# O(n ) to traverse second array and finding common elements in two array
foreach my $ele2($arr2){
# search in hash map is O(1), if all integers of array are same then hash map will have only one entry and still search tim is O(1) 
if( defined $hash->{$ele}){  
print "\n $ele is common in both array \n";
}
}

I hope it helps.

- Giridhar June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The basic idea behind limit the RAM size if that you have to use disk for solving the issue or a limited amount of RAM, for more clarity you will have to ask the size of RAM which is allowed.

The problem will involve sorting the disk files (if you know how to do it and get into questions related to sorting.). If the interviewer says that it will take a lot of time, you can simply place a bit vector, which will be allowed, of the files integers and then just print the common bits.

- Rishi Agrawal June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can try to hash all the elements by maintaining a count in that location. So if the count at any location becomes 2, we have got the repetition..

- Sandeep January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hashing cost O(1) for 1st array, then linear map for the second array

- Andrew Nguyen January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can use max/min heaps for both the arrays in memory, and then compare the max elements, till the entire heap is compared, if its a match, reject the element from the heap, else insert the element back to the heaps, read back from the disk till the heap size is reached(assume a HEAP_SIZE).

- Ashish January 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

plzz post optimal solution
most frequently asked question in interviews

- Anonymous January 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Having RAM swap to and from disk is still O(N). It'd be N / some constant related to memory size, times a big constant for swap time, but still, O(N). I vote for some sort of hash table that can hold all the encountered ints; at each, keep a flag of whether it's been seen in A or B or both, and swap to/from disk as necessary. Use a memory-mapped file for ease-of-use and speed.

Of course, the intended answer is probably something tricky with XOR or summing and subtraction :)

- JeffD January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I answered the same. Interviewer did not give any specific reaction. He moved to another question.

- doomguy January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem with this is that both of your files are bigger than memory, which means that unless there are a TON of duplicates in both files you'll have to write your hash table to disk, which is sorta eliminating the point.

- Jon January 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Take an array A1 of size equal to max size of integer. Now if the number is found n number of times in first array count should remain 1 A1 and if the number is found in both array then the count in A1 is increased to 2. At the end iterate through the array A2 to collect all numbers which have count as 2.

- Anonymous January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1. Create a boolean array of length = number of integers in the first file.
2. For every integer you read from file1 update it's index to true. ( Say x = file.readLine() ; array[x] |= true ) This way array is just 32 times smaller than the file. This loop = O(n)
3. Do step 2 for second file on the same array. ( y = file.readLine() ; array[y] &=true )
4. After step 3 you are left with the array that had intersection of file 1 and 2 and all those indices which have value = true are the integers that are common.

- Sunny January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Only in the first step, create array of size = number of integers of the file that has biggest size.

- Sunny January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Only in the first step, create array of size = number of integers of the file that has biggest size.

- Sunny January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can use max/min heaps for both the arrays in memory, and then compare the max elements, till the entire heap is compared, if its a match, reject the element from the heap, else insert the element back to the heaps, read back from the disk till the heap size is reached(assume a HEAP_SIZE).

- Ashish January 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

void printCommonNumbers(FILE* fp1,FILE* fp2){
	int x,y;
	fscanf(fp1,"%d",&x);
	fscanf(fp2,"%d",&y);

	while(!feof(fp1) || !feof(fp2)){
		if(x<y)
			fscanf(fp1,"%d",&x);
		else if(x>y)
			fscanf(fp2,"%d",&y);
		else{
			printf("%d ",x);
			fscanf(fp1,"%d",&x);
			fscanf(fp2,"%d",&y);
		}
	}
}

Assuming, the input files contain sorted numbers.

- TheGhost January 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What kind of moron are you? who told you that you can simply assume sorted array.

- Kaayotee January 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What kind of moron are you? who told you that you can simply assume sorted array.

- Kaayotee January 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Kaayotee :
whoa easy there boy, no need to get all foul-mouthed !
u think the approach is moronic, just scroll through !

- TheGhost January 30, 2012 | Flag


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