Amazon Interview Question for Research Scientists


Country: United States
Interview Type: Phone Interview




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

This solution is O(n + m) complexity and O(n) memory.
You get only one occurrence of distinguishable item in result collection. If you need to find all items - change answer HashSet to List.

Does anybody know the linear solution without additional memory (or O(log n) memory)?

public class FindCommonElements {

    public static void main(String[] args) {
        int a[] = {1, 2, 3, 3, 4, 5};
        int b[] = {3, 3, 4, 5, 5, 6, 7};

        System.out.println(new FindCommonElements().findCommonItems(a, b));
    }

    public Collection<Integer> findCommonItems(int[] first, int[] second) {
        Set<Integer> setFirst = new HashSet<Integer>();

        for (Integer val : first) {
            setFirst.add(val);
        }

        Set<Integer> answer = new HashSet<Integer>();

        for (Integer val : second) {
            if (setFirst.contains(val)) {
                answer.add(val);
            }
        }

        return answer;
    }

}

- krylloff December 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 votes

if arrays are sorted then it is simple ...

1) keep two pointer i and j for both arrays...
2)if a[i]==a[j].
{
. if(no. don't printed already)
print a[i];

i++;j++;
}
else if(a[i]<a[j]) i++;
else if(a[i]>a[j]) j++;

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

Yes. And this is also possible if we use algorithms not based on comparison.

But the question is: is it possible to solve it in common case (not sorted) for O(n) complexity and O(1) memory

- krylloff December 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

the problem is a little abstract, you should confirm with the inteviewer further,maybe he/she is waiting for you. :)
1. is the array sorted? then we can solve it in O(M+N) complexity and O(1) space.
2. is the array number in certain arrange? for example, between 1-100, then we can use counting sort, with O(M+N) complexity and O(1) space.
3. if we count the same common element only once or actually occurence.
4. if all of these are not guaranteed, then maybe hashmap is possibly the best one.

- busycai December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Solution seems reasonable and I don't know if you can do any better other than using a HashSet instead of HashMap. It gets slightly more complicated if there are duplicate elements and we want to count them too. I think it all depends on how they want to twist this question further.

- Sunny December 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;
public class Duplicatesin2Arrays {
public static void main(String[] args) {
int[] array1 ={1,2,3,4,5};
int[] array2 ={3,4,5,6,7};
HashSet hs = new HashSet();
int i;
for(i=0;i<array1.length;i++)
{
hs.add(array1[i]);
}
int j=0;
for(i=0;i<array2.length;i++)
{
if(!hs.add(array2[i]))
{
j++;
System.out.println(array2[i]);
}
}
System.out.println("The number of duplicates present is "+j);
}
}

- premkarthi20 December 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

one more solution could be possible
sort one array and binary search into it each element of other array.
time : (n)log(m), no space

- ravi December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity is : if n, m is number of elements.
nlogn for sorting + mlogn for searching.

- Pankaj January 06, 2014 | 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