Goldman Sachs Interview Question for Java Developers


Country: India
Interview Type: Phone Interview




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

Come on, how do you possibly think you can go through N elements in constant time?

The constant time part is about using a hash table to check if a number was already seen in the list. And also insert numbers in the hash table in constant time.

- Miguel Oliveira September 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store the list in LinkedHasSet. You will get expected output.

- Ghosh September 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Constant time is impossible when you must evaluate each element at least once to determine if it's a duplicate or not.

That being said, you can get constant time in determining if the element is indeed a duplicate by iterating through your list and inserting each value into a hash table. Use the numbers as the key values, and they hash table will automatically filter out any duplicates upon insertion.

A quick code example in Java:

HashMap<Integer, Integer> hm = new HashMap();
        int[] a = {0,5,9,5,6,7,6,9};
        
        for(int i: a){
            hm.put(i, i);
        }
        
        for(Integer i: hm.keySet()){
            System.out.println(hm.get(i));
        }

- masterjaso September 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why do you need to use a HashMap, you can use a HashSet

- Nomad July 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[] = {1,2,1,2,1}
Map<Integer,Integer> map = new HashMap(Integer,Integer)();
for(int i : a){
if(map.get(i)==null){
map.put(i,1);
}else {
int count = map.get(i);
map.put(i,count+1);
}
}
System.out.println("values in map "+map);
}
}

- conjuring September 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

quite simple... if only u have single digit numbers... use hash functn as k mod 10 where k is the number... and if a number already exists at that position.. then its a duplicate number

- Anonymous September 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

WHAT??? hash? mod? For single digit numbers?
If you have single digit numbers, you only have 10 possible numbers.
You only need 10 bits (or 10 boolean flags). Flip bit position i if you see number i.
At the end print out the numbers corresponding to the flags that were marked.

- bigphatkdawg September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Put elements in hashtable and while putting value check if it is present in the hashtable or not. If element is not present in the hashtable put it and print it. If it is present the simply leave this element and move forward. Repeat this process till the end of list.

- Rahul September 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Every here is mentioned HashMap and do this do that.

I am really wondering where is the cream of intellectual people gone.

USE HASHSET ..Just Single Traversal is required

- ThinkIdiots September 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How do you think HashSet is implemented mr intellectual ? ever thought of looking into Java source code ?
It itself uses a Hashmap inside it , so what did you gain ?

- Geek July 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

3-way quick sort, no extra space of HashMap or HashSet. Best in practice for removing duplicates. Average linear bound runtime (because of duplicates).
Essentially the max bound for comparision is reduced drastically from log(n!) to log(n!/x1!x2!...xn!) where x1, x2, x3...xn are number of duplicate occurences of various elements in array. This is approximately = sum (xilogxi/N) which is linear.
Cheers.

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

Use TreeMap

- Anonymous November 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

TreeSet<Integer> ts = new TreeSet<Integer>();
int[] a = {0,5,9,5,6,7,6,9};

for(int i:a){
ts.add(i);
}

System.out.println("TreeMap"+ts);

- Anonymous May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

nums=[0,5,9,5,6,7,6,9]
result=list(set(nums))

- fuubar September 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

in an interview setting, there not much value in using language features like those to answer these types of questions

- Miguel Oliveira September 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 votes

Wondering why not? You aren't expected to code in assembly either.

- fuubar September 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Instead of a hash table you can also use a bit vector to save space.

Read input and set the corresponding bit in the bit vector
If bit is already set skip the input value as its a duplicate (because the bit set indicates we've seen the exact value before)

- kill -9 September 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You only save space if the value of the numbers is quite small, in the order of N, N being the number of elements in the list.

Suppose the value of the numbers in the list can be as high as 10000000000000000000000. The bit vector need to have that many bits, while the hash table continues to have size O(N)

- Miguel Oliveira September 12, 2013 | 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