AMCAT coupon code --> AF01 (Upto 150 off)

AMCAT Hash Tables Questions with answers 2019 – Computer Programming

AMCAT Hash Tables Questions with answers under computer programming 2019: Although Computer programming is an optional module in AMCAT exam, still it is recommended for all IT background candidates. Nevertheless, on personal interest of candidates, they can take up the computer section. The best part about this section is that it surely gives special attention to the job aspirant’s profile.Furthermore, we will be seeing AMCAT Hash Tables Questions.

AMCAT Hash Tables Questions with answers 2019 – Computer Programming As has been noted, Hash table is one of the significant topics of Computer programming syllabus for AMCAT. In addition, 1-2 question comes from the topic frequently. It generally takes 50 seconds to solve a problem. Above all, the questions are more theoretical. So if the concept is clear, it is quite easier to answer the question. Moreover, here we will discuss sample questions on Hash tables with answers and explanation.

Outline of Hash Tables

Hashing is especially a technique which is used to uniquely identify a specific object from a group of similar objects. Following are some examples of how hashing is used in our lives include:

Most Employability Test 2019

• In colleges, each student is assigned a unique roll number explicitly that can be used to retrieve information about them.
• Inside libraries, each book is assigned a unique identification number that can be used to determine information about the book, such as its exact position in the library or the users it has been issued to etc.

Under both the above examples the students and books are hashed to a unique number.

Hashing

Assume that you have an object and you want to assign a key to it to make searching process  easy. Hence, to store the key/value pair, you can use a simple array like a data structure where keys (integers) can be used directly as an index to store values. However, in cases where the keys are large and cannot be used directly as an index, you should use hashing.

In hashing, large keys are converted into small keys by using hash functions. The values are then stored in a data structure called hash table. The idea of hashing is to distribute entries (key/value pairs) uniformly across an array. Each element is assigned a key (converted key). By using that key you can access the element in O(1) time. Using the key, the algorithm (hash function) computes an index that suggests where an entry can be found or inserted.

Hashing is implemented in two steps:

1. An element is converted into an integer by using a hash function. This element can be used as an index to store the original element, which falls into the hash table.
2. The element is stored in the hash table where it can be quickly retrieved using hashed key.hash = hashfunc(key)
index = hash % array_size

In this method, the hash is independent of the array size and it is then reduced to an index (a number between 0 and array_size − 1) by using the modulo operator (%).

Hash function

A hash function is any function that is used to map a data set of an arbitrary size to a data set of a fixed size, which falls into the hash table. The values returned through hash function are called hash values, hash codes, hash sums, or simply hashes.

To achieve a good hashing mechanism, it is important to have a good hash function with the following basic requirements:

1. Easy to compute: It should probably be easy to compute and must not become an algorithm in itself.
2. Uniform distribution: It should provide a uniform distribution across the hash table and hence should not result in clustering.
3. Less collisions: Collisions occur when pairs of elements are mapped to the same hash value. These should be avoided.Note: Irrespective of how good a hash function is, collisions will occur. Therefore, to maintain the performance of a hash table, it is important to manage collisions through various collision resolution techniques.

AMCAT Hash Tables Sample Questions pdf

Mock questions for AMCAT Hash Tables

Question 1
What is a hash function? a)

1. Function has allocated memory to keys
2. A function that computes the location of the key in the array
3. Function that creates an array
4. None of the mentioned

Explanation: In a hash table, there are fewer array positions than the keys, so the position of the key in the array is computed using the hash function.

Question 2
What is the search complexity in direct addressing?

1. O(n)
2. O(logn)
3. O(nlogn)
4. O(1)

Explanation: Since every key has a unique array position, searching takes a constant time

Question 3
What is the best that can be the techniques to avoid collision?

1. Make the hash function appear random
2. Use the chaining method
3. Use uniform hashing
4. All of the mentioned

Explanation: Making the hash function random is not really a good choice, although it is considered one of the techniques to avoid collisions along with chaining and simple uniform hashing. Chaining is the best

Sample Questions

Question 4
What is it called when several elements compete for the same bucket in the hash table, ?

1. Diffusion
2. Replication
3. Collision
4. None of the mentioned

Explanation: By definition

Question 5
What is a hash table?

1. A structure that maps values to keys
2. Structure that maps keys to values
3. A structure used for storage
4. Structure used to implement stack and queue

Explanation: A hash table is used to implement associative arrays which has a key-value pair, so the hash table maps keys to values.

Question 6
What is direct addressing?

1. Distinct array position for every possible key
2. Fewer array positions than keys
3. Fewer keys than array positions
4. None of the mentioned

Explanation: Direct addressing is possible only when we can afford to allocate an array that has one position for every possible key.

Question 7
What can be the techniques to avoid collision?

1. Make the hash function appear random
2. Use the chaining method
3. Use uniform hashing
4. All of the mentioned

Explanation: Making the hash function random is not really a good choice, although it is considered one of the techniques to avoid collisions along with chaining and simple uniform hashing.

Question 8

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions? (GATE-CS-2014)
(A) (97 × 97 × 97)/100^3
(B) (99 × 98 × 97)/100^3
(C) (97 × 96 × 95)/100^3
(D) (97 × 96 × 95)/(3! × 100^3)

Explanation: In uniform hashing, the function evenly distributes keys into slots of hash table. Also, each key has an equal probability of being placed into a slot, being independent of the other elements already placed.

Therefore, the probability of remaining first 3 slots empty for first insertion (choosing 4 to 100 slot) = 97/100. As next insertions are independent on previous insertion, the probability for next insertions will also be 97/100. The required probability will be (97/100)^3

Practice more questions on AMCAT Hash Tables Questions to have command on the topic.