Goldman Sachs Interview Question
Java DevelopersCountry: India
Interview Type: Phone Interview
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.
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
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} ).
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)
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.
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;
}
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) ).
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'.
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..
Constant time is usually a tip for "use a hash table" and this is a good example for that.
- Miguel Oliveira September 11, 2013