Goldman Sachs Interview Question for Java Developers


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.

- Miguel Oliveira September 11, 2013 | Flag Reply
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.

- Jie September 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

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

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

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)

- PKT October 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Miguel Oliveira October 22, 2013 | Flag
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;
}

- Painter Mathavan August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Painter Mathavan August 11, 2015 | Flag
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) ).

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

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

- meow December 20, 2013 | Flag
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'.

- masterjaso September 11, 2013 | Flag Reply
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..

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

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

It's funny

- bigphatkdawg September 19, 2013 | Flag
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)

- Sameer Shukla February 12, 2014 | Flag Reply
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.

- Anonymous March 14, 2014 | Flag Reply
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;
}

- Anonymous August 10, 2015 | Flag Reply


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