## Goldman Sachs Interview Question for Java Developers

• 0

Country: India
Interview Type: Phone Interview

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

Constant time is usually a tip for "use a hash table" and this is a good example for that.

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

There is no really constant time query. Hash table is almost constant time in check.
But since the input is unsorted list, that means you need O(N) time to pre-process the data. This must be pointed out.

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

hash table operations run in amortized constant time. wikipedia.org / wiki/Amortized_analysis

for more details i suggest you consult a book like Introduction to Algorithms

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

Hash table runs in amortized average/best case constant time.

If you don't amortize OR if you're in a bad case, you are little-omega(1).

Direct Access Table (check CLRS) would give exactly constant time queries (but the space is O(k) where k=max{the set of integers} ).

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

I think qus must mention that your written code should have complexity of O(1) complexity is excluding pre-built APIs and functions.

Because HashMap itself has its own algorithm and complexity to add, delete and searching... and I think HashMap's internal algo is surly not be O(1)

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

O(1) means that the time complexity is constant disregarding the input size. This does *not* mean "instant time". e.g.

``````int func(int n) {
int res = 0;
for (int i = 0; i < 100; i++)
res += i * n;
return res;
}``````

This function runs in constant time, because it always does 100 operations regardless of the value of n.

HashMap operations run in amortized constant time. Just look up the java documentation for example.

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

``````int[] num={3,1,4,7,9,4,7,4,9 };

public boolean checkNum(int[] num, int n){
List list = Arrays.asList(num);
if(list.contains()){
return Boolean.TRUE;
}
return Boolean.FALSE;
}``````

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

``````if(list.contains(n)){
return Boolean.TRUE;
}
return Boolean.FALSE;``````

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

The question was misunderstood and stated incorrectly.

But anways, assuming the said you can spend linear time building a datastructure up front and then they want constant time queries... and only the time mattered....(e.g. infinite memory or the max value of any integer is not that high)...
the answer would be a DIRECT ACCESS TABLE. Which has exactly O(1) access time (not amortized, not average, not best case..... it has exactly O(1) ).

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

+1. usually they will accept the Hash Table answer (because of space problem) but this is more accurate.

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

Inserting the numbers of your unordered list into a hash table will create a data structure that can take as in input, the key value your are seeking, use it's hash value, and return if that element exists or not.

Put/Get in hash tables operate on O(1) except in cases where the load factor is too high and there are large numbers of collisions in the same 'bucket'.

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

just use a hash table... with a hash function k mod 10.. where k is the number...this will work if all the numbers are single digit..

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

LOL you go to many threads and post "just use hash function k mod 10"

It's funny

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

3 approaches according to me

1. Using hashing say Hashset - O(1)

2. Compare the given number with each and every element - O(n)

3. Use binary tree - O(logn)

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

What I guess is the poster missed a condition that number are in limited range.

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

int[] num={3,1,4,7,9,4,7,4,9 };

public boolean checkNum(int[] num, int n){
List list = Arrays.asList(num);
if(list.contains()){
return Boolean.TRUE;
}
return Boolean.FALSE;
}

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.