## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

@estif None of those is "fast" except union, which is O(1). The others take O(N) time.

If the numbers are coming in fast, then you can do some things to mitigate that, like put in a circular buffer, and pass it off to a separate thread. It's the typical producer-consumer pattern.

Secondly, what is interesting about this problem, is that you can do your typical tradeoff of space for speed. So, if you're getting numbers off the wire, then you have fixed set of numbers you can support, namely 2^32.

So, create two 2^32 bit arrays (only 536Mb each), labeled A & B. Number comes in, it's O(1) to flag the correct bit. Accessing the correct bit is simple arithmetic.
Union is A | B on all the bits.
Intersection is A & B.
A-B is A^ (A & B)
B-A is B^ (A & B)
All these operations will be fast-as-hell bit operations, and they're all O(1), since the array sizes are fixed.

You'd need to profile this for the actual performance gains, because the approach is a bit silly.

Otherwise, you could perform your various set constructions on the fly, as numbers are coming in.

The words "real time" are imprecise. What are the requirements? Is it 10ms? 20ms? 5ms?

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

What do you mean by ^ operator?

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

@rotinom thanks for the response.
Few questions my union solution is not o (1) it is o (n).

Coming back to your solutions
We don't have any clue what the nature of the numbers could be . It could be just 11111111 and 2222222 so keeping that much space may not be ideal.

Let's say we have two arrays saving bits of the two inputs.
Even though bit operation will be faster than string comparison the fact that u have to read over the arrays will make all the solutions o (n)

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

Bit operations are fast only if you could fit an integer in a register. With a huge bit stream, it need not be fast.

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

I would attempt something like this

``````Let's assume Initially both A and B are null sets A = {} and B = {}
1) Create 3 data structures Hash Table, List_Union, List_Intersection
2) Whenever u get a new number in A or B add it to the hash table

2a) if the number already exists in hash table, add the number to List_union
2b) If number does not exist in hash table, add it to hash table and add that number to List_Intersection

3) you can maintain these 3 data structures and whenever u have to find the A-B or B-A just do AUnionB - AIntersectionB``````

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

I think you can take care of it with single hashmap.

e.g.
Given inputs A = {1,2,3,4} , B={1,2,5}
Writing to the hashMap will be something like..
H = {1: 'AB', 2: "AB", 3: "A", 4: "A", 5: "B" }

A Union B = H.keys()
A Intersection B = [key for key in H.keys() if H.get(key) == "AB"]
A - B = [key for key in H.keys() if h.get(key) == "A"]
B - A = [key for key in H.keys() if h.get(key) == "B"]

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

Following your idea:

``````import java.util.HashMap;
import java.util.Iterator;

public class NumbersStore {
static HashMap<Integer, String> tmpTable = new HashMap<Integer,String>();

private static void printByBuffer(String bufName){
String InterAcumContainer		= " ";
Iterator<Integer> keySetIterator	= tmpTable.keySet().iterator();
while(keySetIterator.hasNext()){
Integer key = keySetIterator.next();
if(tmpTable.get(key).equals(bufName)){
if(InterAcumContainer.equals(" ")){
InterAcumContainer	= ""+key;
}else{
InterAcumContainer	= InterAcumContainer+","+key;
}
}
}
System.out.println(bufName+": "+InterAcumContainer);
}

private static void printUnion(){
String unionAcumContainer		= " ";
Iterator<Integer> keySetIterator	= tmpTable.keySet().iterator();
while(keySetIterator.hasNext()){
Integer key = keySetIterator.next();
if(unionAcumContainer.equals(" ")){
unionAcumContainer	= ""+key;
}else{
unionAcumContainer	= unionAcumContainer+","+key;
}
}
System.out.println("Union: "+unionAcumContainer);
}

private static void addValue(int keyIndex, String bufName){
if(tmpTable.containsKey(keyIndex)){
String tmpBufName	= tmpTable.get(keyIndex);
if(!tmpBufName.equals(bufName)){
tmpTable.put(keyIndex, "AB");
}
}else{
tmpTable.put(keyIndex, bufName);
}
}

public static void main(String[] args){

//add some values
addValue(1, "A");
addValue(1, "B");
addValue(2, "A");
addValue(3, "B");
addValue(4, "B");
addValue(5, "A");

printUnion();
printByBuffer("AB");
printByBuffer("A");
printByBuffer("B");
}
}``````

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

In the above proposed approach..if the number is already exists in the hash table we need to add it to intersection set..else we have to add it to union set..correct me If I'm wrong.

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

Assuming numbers are only added
Define a struct with an 2 bit value field and a next pointer, prev pointer
now make a hash_table of int, the above struct node
let 2 bit field be such that
if == 01 number is in B
if == 10 number is in A
if == 11 number is in A and B
Maintain three lists
1. that goes through nodes with bit value = 11 (intersection list)
2. that goes through nodes with bit value = 01 (B-A)
3. that goes through nodes with bit value = 10 (A-B)
4. for Union return all elements that are in hash

operations
adding number, if not present already add to either lis 2 or list 3 based on whether it is in set A or set B
if present remove the current from either 2 or 3 and move to head of 1.

All operations are O(1)

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

There seems no need for list structure, bit vector is sufficient.
I think it is better to use two different bit vectors for A and B,
for better localization of data.
e.g A for Thread 1 and B for Thread2

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

Three sets
Set A :- holds the numbers that are only exist in A.
Set B:- Holds the numbers that only exist in B.
Set C :- Hold the numbers that exist in A AND B.

A intersection B = C --> O(1)
A - B = A --> O(1)
B - A = B --> O(1)
A U B = A U B U C --> O(n)

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

I'd like to solve this problem like the following.

Thread A: will manage two data structures for set A
- hash_map with key = number and value = true if A intersection B
- hash_set for A - B
similarly
Thread B: will manage two data structures for set B
- hash_map with key = number and value = true if A intersection B
- hash_set for B - A
Thread C: will manage two data structures for A U B and A intersection B
- A U B: hash_map with key = number and value = bit fields(true if number contained in A, true if number contained in B)
- A intersection B: hash_set

If a number N is about to come to A, the producer notifies Thread A and Thread C
Thread A:
- updates hash_map with N
- waits for Thread C is done with N
Thread C:
- updates hash_map with N
- if N is contained in A and B, update hash_set for A intersection B and notifies Thread A with updated N, otherwise, just notifies Thread A
Thread A:
- wakes up
- if A intersection B is updated with N, it updates its hash_set. otherwise, just finish.

Similar procedure can be applied to a new number to set B.

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

For storing this numbers coming at high speed...maybe ask the interviewer...do we need to store all the numbers?....if yes....than Mapreduce might be a good option. Maybe implement an hdfs architecture for storing

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