Goldman Sachs Interview Question: Implement an intersection met... | Glassdoor

Interview Question

New Associate Programmer Analyst Interview(Student Candidate) Salt Lake City, UT

Implement an intersection method for two lists. After

  showing a brute force method, I was asked to improve upon the method and analyze time complexity for both algorithms.
Tags:
algorithm
Answer

Interview Answer

2 Answers

2

1. Traverse through the first list and put all items in a hash table.
2. Traverse through the second list and try to find these items in the hash table created in step 1 -> Add all items found to the intersection list.

O(N) complexity.

Vinod on Nov 19, 2012
0

1. Convert both lists to hashsets
2. Find the intersection of the two hashsets
3. Convert this intersection back into a list

Anonymous on Feb 1, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.