## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

The best solution that is O(1) is the array of max int bits. If int is 32 bit that's 512MiB.

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

I agree, this probably the best/only O(1) space solution. This involves a very large (but constant) array of bits, where the bit value represents whether the corresponding number is present in array A. Then iterate through array B checking the corresponding positions in the bit array.

So assuming that we're using 32 bit integers, then the bit array has 2^32 bits = roughly 512 mb. This approach would achieve O(n) execution time and O(1) space. But this solution is only really valid when there is a very large number of elements in array A and B.

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

Doesn't this require creating extra space? E.g. creating an array of 512 mb? Please correct me if I am thinking of constant space O(1) wrong.

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

Yes, it requires an bit array of size 2^32 = 512mb (assuming we're talking about 32 bit integers) . But this is a constant sized array regardless of the size of the input arrays A and B.
So this solution is O(1). a.k.a constant in space complexity.

As mentioned, this solution is only suitable for really large arrays A and B.

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

If array contains negative, can bit array handle it?

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

Yes, the negative sign is just a bit. You would have to change to an unsigned integer to index the array.

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

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

@charsyam :: Can you please explain how can we find the number by traversing the sorted array.

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

Yeah, that should work. Just do a quicksort then do something similar to merge step in mergesort.

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

sorting is O(n*logn) though, not O(n) as requested.

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

Yes. QuickSort is O(nlogn), I'm not sure but, How can we ensure O(n) I just think LookupTable using BitVector size [INT_MAX/8], it is O(1) space :)

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

Quicksort worst case is O(n^2)

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

Instead of a Hash Map.. we can use int Array. Then memory occupied will b less.... about 32 times less.

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

I don't think there is an soln with linear complexity for this question.

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

What do you mean "find values that appear in both arrays and output them"? what exactly "values" mean here. In your example,

int[] a = {1,2,3,4};
int[] b = {2,5,6,7,3,2};

What is the expected output? {2, 3} or {2, 2, 3}?

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

I think this answer satisfies the requirement for O(n) computation complexity and O(1) space complexity

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

This is not an answer :/ It is a clarification regarding the question.

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

I think he means an intersection of two arrays

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

I think you can use bit manipulation if the numbers in array is "close" to each other.
Build an bitmap for each array and set the bit to 1 if the number is exist.
Then use &. The bit remain 1 is the overlap bit.
say I have {0.1,2,3} and {2.5.6,7}
We Have bitmap 11110000 and 00100111
After & we get 00100000 which means 2 is overlapped.

This method is not suit for sparse array like{0.100000}

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

You are assuming the array is sorted

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

if sizeof(a) +sizeof(b) <maxvalue-minvalue of both arrays then its simple O(n)
else
use universal hash(linear probing) on to the array itself instead of
creating a temporary array to store the hash.( complexity may vary but avg would be O(n)).

It works even if the numbers are negative in the array.

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

forgot to mention.
in the second case restoring the original array
is possible if only if (maxv-minv)^2 <maxv value possible of data type

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

doesn't seem like a working algorithm with O(n) complexity and O(1) space.

In "sizeof(a) +sizeof(b) <maxvalue-minvalue", how do you make {-1000, 0, 1000}, {500, 1000} work?

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

sorry for typing error.
its sizeof(a)+sizeof(b)>maxvalue-minvalue.

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

It still doesn't seem working with O(n) complexity and O(1) space when you try to reuse and overwrite input arrays.

How do you make it work for {5,6,7}, {3,4,5} in O(n) complexity and O(1) space?

Remember, when you use hashing and linear probing, you can't lose information by overwriting elements without keeping that element's info somewhere and remember the space requirement is O(1).

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

ask whether there is a high/low bound for arrays.

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

sizeof(int)? sizeof returns number of bytes, not number of bits.

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

I think this can be solved by using a bit vector of size 2 power (sizeof(int)-3)

O(2 power (sizeof(int)-3)) = O(constant) = O(1) space

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

For a 64 bit integer that's enormous, on the order of exabytes I think. In other words though it is technically O(1) that constant and is many orders of magnitude larger than O(n) or even O(n^2).

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

you can do it in 2nlogn+2n (assuming each array has n elements) => sorting each array takes 2 nlog n. iterate through the array takes 2n (like you would do when you merge two sorted arrays)

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

hw abt this?

Do radix sort on both the arrays. Then traverse both arrays simultaneously to find out common elements.

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

This is what i can think of
sort both arrays
keep two pointers one at start of both the arrays
if(a[i]==b[j])
return
else if(a[i]<b[j])
i++
else
j++

The problem with this method is at sort step since i dont know if there is any sorting method which would sort in O(nlogn) time without using extra space. Quick sort takes O(n^2)

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

Really? I find that hard to believe unless you are a super typer. I mean just explaining everything in detail over the phone for one problem can take a bit of time. We were also trying to use a collaborative text editing site that was being finicky and slow.

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

I recently had an interview with Amazon, and was asked one simple question while we were trying to get the code site link working (about 2-3 mins to explain, very simple). Then one 'real' question close to the one asked in this discussion. I'm not sure how you would get more than two technical questions in an hour interview.

I was already 20-30 minutes into the interview after I was done talking about my myself and what I have worked on in the past. Then after the technical questions we talked for another 15+ mins about the company, city, etc, etc etc.

So 1 hour, -15, -2 , -30, +12 (went over the hour a little bit), so I had around 25mins to come up with a solution, code the solution, talk about other directions that could be taken to solve the problem, and coding a 2nd solution to the problem.

If I was perfect (or knew the answer before hand) I could see getting more than one question, but it sounded like the phone interview was meant to have one question asked.

I'll found out in a couple days if I made it to the next step, good luck to you too.

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

Okay, that is what I figured. My interview went almost exactly the same way. I talked with the interviewer about my favorite project I have worked on for a good 10 minutes, then we tried getting the coding site to work, and then worked on code for about 20-25 minutes, and then talked for another 15 or so.

Just making sure my experience was not wildly different from everyone else. Thanks and best of luck to you!

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

Two arrays A and B
1) First do a quick or merge sort on Array A
2) Now Iterate each element in Array B and do a binary search in Array A. If found, then add this element as found.Continue this to all the elements in Array B.
3) Finally u ll have the elements that are found in Array A and B.
If n is no of elements in A and m in B
Complexity - Sort of A( O(nlogn)) + Iterate B and do search in A(O(mlogn) = m+n(logn)

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

Srini, the requirement is o(n) complexity and o(1) space.

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

Please note what my question was asking. I want to do it with complexity O(n) and memory complexity of O(1). Yours has a higher computational complexity. While it may not use memory, it will take longer to run on large datasets.

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

Hi zimmerman....is this your first round.do u know how long it takes to notify for second round or a person is rejected by amazon...

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

When you get your first round scheduled they tell you in the email about the time frame of the entire process. You should here back with a yes or no within 2 business days after a phone interview. And hear back within 5 business days after an onsite interview.

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

It took me about a week to hear back from the first phone interview to schedule a second. It may vary from person to person and with how busy the recruiting people are.

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

It took me 2 weeks to get notified about my second round of phone interview.

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.