1,241 views
1 votes
1 votes
A hash function h maps 16-bit inputs to 8-bit hash values. What is the largest k such that in any set of 1,000 inputs, there are at least k inputs that h maps to the same hash value?

A) 3

B) 4

C) 10

D) 64

1 Answer

6 votes
6 votes

Input =16 bit ; so total no of inputs = 2^16 (but here in qurestion no use of this information )

8 bit hash value so size of hash table = 2^8 =256

now we have to insert 1000 value in 256 cells.

if 3 values maps to same hash cell then = 256*3 =768 ( means if one hash table cell is mapped to 3 input only 768 input are covered)

if 4 values maps to same hash cell then = 256*4 =1024 ( means if one hash table cell is mapped to 4 input than we can cover 1024 input. But we have only 1000 input)

So some hash table cell will mapped to 3 input and some hash table cell will be mapped to 4 inputs . 

 so 4 is the largest k such that in any set of 1,000 inputs, there are at least 4 inputs that h maps to the same hash value.

so ans is option (B).

Related questions

0 votes
0 votes
2 answers
2
Pranabesh Ghosh 1 asked Aug 30, 2016
552 views
Given an array of integers what is the worst case time complexity that would find pair of integers which are same?A) O(nlogn)B) O(n)C) O()D) O(nloglogn)
4 votes
4 votes
1 answer
3
Pranabesh Ghosh 1 asked Aug 30, 2016
671 views
A min heap with 1000 elements is stored in an array. What is the maximum possible index number for 9th min element?A) 254B) 100C) 9D) 511
2 votes
2 votes
1 answer
4
Pranabesh Ghosh 1 asked Aug 30, 2016
735 views
Suppose that an application have a huge number of insert operations, but only few delete max operations. Which priority-queue implementation would be most effective:A) Ma...