CareerCup

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.

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.

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.

If array contains negative, can bit array handle it?

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

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

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

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

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 :)

Quicksort worst case is O(n^2)

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

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

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

I think he means an intersection of two arrays

You are assuming the array is sorted

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

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?

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

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

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

You need sizeof(int)*CHAR_BIT instead.

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

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.

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.

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!

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)

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

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.

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

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.

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.

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