Question

Hash tables can contribute to the following problems except

1) Counting distinct values

2) Dynamiic dictonary

3) Symbol table look up

4) Range search

Comments

is it 2 ?

Answer 1

I think answer should be range search..
All the rest are applications of Hashing..

1) Counting distinct values - can be easily done if we know the allowed range of numbers, say n and using the hashing function :-
x mod n
2) and 3) are common applications of hashing..

4) Range search cannot be done by using hashing alone.

Comments

how will you count distinct using has tables?Can it be done in constant time? Only solution i can think is like counting sort where after preparing hash array we check count value of each slot.If it is 1 then distinct else not.But it is 0(n) where n is the size of hash table.

If you also think the same,then why cant we consider the range search also?I can traverse the hash table from a to b and this will be also 0(n) for n hash size(assuming that hash table has enough size to hold input)

---

@  rahul sharma 5

For counting distinct:

1. Make all the slots of hash table=0 i.e hash[i]=0 for every i

2. For every element i, SET hash[i]++

3.Scan through the hash table, the element for which the hash[i]=1 count them

---

thanks @ srivivek95  .why cannot we do range? Because we need hash table depending on min. and max, number and then its complexity depend on the size of range?

Answer 2

Answer is 4) Range search

Hashtables cannot contribute to the problems like Given values a and b, find all the records whose key value is in the given range.