Explore topic-wise InterviewSolutions in .

Correct ANSWER is (a) O(1)

The BEST explanation: Time complexity of search function in a hash table is O(1). Condition is that the NUMBER of COLLISIONS should be low.

Correct CHOICE is (a) O(1)

To explain: Time complexity of delete function in a hash table is O(1). CONDITION is that the hash function should be such that the NUMBER of collisions should be low.

The correct choice is (a) it takes less memory

Easy explanation - SINGLY linked list takes LESSER space as compared to DOUBLY linked list. But the time COMPLEXITY of the singly linked list is more than a doubly linked list.

Correct answer is (b) False

Easy EXPLANATION - Collision is caused when a hash function returns repeated values. So collisions can be REDUCED by developing a better hash function. Whereas separate CHAINING using list head is a collision HANDLING technique so it has no relation with a NUMBER of collisions taking place.

Correct choice is (a) it is simpler to implement

For explanation: Open ADDRESSING is the TECHNIQUE which is used for handling collisions in a hash table. It has a BETTER cache performance as EVERYTHING is STORED in the same table.

Correct option is (B) It saves SPACE

The best I can EXPLAIN: A bit vector is an array of BITS of only 0s and 1s, a bit vector of length m takes much less space than an array of m pointers. The complexity to implement bit vector is larger than in normal case.

Right choice is (d) O(1)

The explanation is: As every KEY has a unique array POSITION, it takes constant time to delete an element, although the DELETED position must be SPECIFIED by nil.

The correct CHOICE is (b) It saves space

Explanation: Using a dynamic set, the size of the ARRAY is restricted to the number of keys, hence saves space. The complexity to implement dynamic array is LARGER than in NORMAL case.

Right choice is (d) O(1)

The best I can explain: As every KEY has a unique array POSITION, it takes CONSTANT TIME to insert an element.

The CORRECT answer is (d) O(1)

For explanation: Since every key has a UNIQUE ARRAY position, SEARCHING TAKES a constant time.

Right CHOICE is (b) When the universe U of keys is reasonably SMALL

The best explanation: Since each key is associated with a SLOT in the array, it is better to use direct addressing when the universe of keys is small as the array size grows with the increase in number of keys.

Correct option is (a) True

Best explanation: MinHash was originally used to remove the duplicate webpages from a search engine. But in data MINING, MinHash used as a tool for ASSOCIATION RULE LEARNING by Cohen at 2001. Google conducted a survey to compare the PERFORMANCE by two technique MinHash and SimHash.

Right option is (a) True

The explanation is: MinHash was originally used to remove the duplicate webpages from a search ENGINE. But in DATA MINING, MinHash used as a TOOL for ASSOCIATION rule learning by Cohen at 2001.

The correct CHOICE is (d) Ω (n)

Explanation: The TIME REQUIRED for single variant hashing to maintain the MINIMUM hash queue is O (n). Ω (n) bits are NEEDED to specify the single permutation by min-wise independent family.

Right choice is (d) O (n)

The EXPLANATION is: The expected error for estimating the Jaccard index using MinHash SCHEME for k DIFFERENT hash functions is O (1/k½). The TIME required for single variant hashing to maintain the MINIMUM hash queue is O (n).

The CORRECT choice is (d) O (1/k½)

The BEST explanation: The expected ERROR for estimating the Jaccard index USING MinHash scheme for K different hash functions is O (1/k½). The expected error by the estimator Chernoff bound on the samples performed without replacement is O (1/k½).

The correct ANSWER is (d) 400

Easy EXPLANATION - The expected error for estimating the Jaccard index using MinHash scheme for k different hash functions is O (1/k½). 400 hashes will be needed for calculating Jaccard index with an expected error less than or equal to 0.05.

Right option is (d) O (1/k½)

Best explanation: Jaccard Coefficient Index is defined as the ratio of total elements of intersection and UNION of two sets. For two DISJOINT sets, the value of the Jaccard index is zero. The EXPECTED error for ESTIMATING the Jaccard index using MinHash scheme for k DIFFERENT hash functions is O (1/k½).

The correct option is (a) Jaccard INDEX is CLOSER to 1

Easy explanation - Jaccard Coefficient Index is defined as the ratio of total elements of intersection and union of two sets. For two disjoint sets, the value of the Jaccard index is zero. The MEMBERS of two set more common relatively when the Jaccard Index is Closer to 1.

Correct answer is (d) 0

For explanation: MinHash HELPS in the quick estimation of similarity between two sets. Jaccard Coefficient is used for the similarity between two sets. Jaccard Coefficient INDEX is defined as the ratio of TOTAL elements of intersection and union of two sets. For two disjoint sets, the value of the Jaccard index is ZERO.

Right option is (b) Jaccard Coefficient Index

For EXPLANATION: MinHash helps in the quick estimation of similarity between two sets. Jaccard Coefficient is used for similarity between two sets. Jaccard Coefficient Index is defined as the RATIO of TOTAL elements of INTERSECTION and UNION of two sets.

Right choice is (a) MinHash

Easiest explanation - In computer science as well as data MINING, to find the similarity between two given sets, a technique called MinHash or min-wise independent PERMUTATION SCHEME is used. It HELPS in the quick estimation of similarity between two sets. It is used in CLUSTERING documents using the similarity of two words or strings.

Right answer is (a) MinHash

The best explanation: In computer science as well as data mining, to FIND the similarity between two given sets, a technique called MinHash or min-wise independent permutation SCHEME is USED. It helps in the quick estimation of the similarity between two sets. It is used in removing duplicate WEB pages from search RESULTS in AltaVista search engine.

The correct answer is (d) Andrei BRODER

Easiest EXPLANATION - In COMPUTER science as well as data MINING, to find the similarity between two given sets, a TECHNIQUE called MinHash or min-wise independent permutation scheme is used. It helps in the quick estimation of the similarity between two sets. It was invented by Andrei Broder in 1997.

Right option is (a) MinHash

The best explanation: In computer SCIENCE as well as data MINING, to find the SIMILARITY between two given sets, a technique called MinHash or min-wise INDEPENDENT permutation scheme is used. It helps in the quick ESTIMATION of the similarity between two sets.

The correct ANSWER is (d) O(n)

The best explanation: In average scenarios, the SYNCHRONISATION takes O(logn) because it is BASED on the traversal and SEARCHING. The worst case occurs when there are no NODES in common, so the synchronisation takes O(n) time.

Right OPTION is (a) True

For explanation: The sequential access in the HASH TREE is more efficient and faster than in B-tree. Because while constructing the hash tree in the expansions and contractions of the FILE is an estimated.

The CORRECT choice is (a) O(logk(n))

For explanation: To insert a RECORD in the hash tree the key is compressed and hashed to get the slot for the ENTRY. So, a hash tree with branching FACTOR k takes O(logk(n)) for INSERTION in worst case.

Correct option is (a) in digital currency

The BEST I can explain: Using Hash tree the DATA VERIFICATION, data SYNCHRONISATION and the consistency verification can be done efficiently. So, the hash tree are digital CURRENCIES to organise the transactions.

Right option is (c) 4

The BEST I can explain: Consider 8 RECORDS A B C D E F G H. These records are stored in Hash tree in as SHOWN in FIGURE below.

The correct choice is (a) Merkle TREE

To explain: Hash tree is generally known as Merkle tree after RALPH Merkle who patented it in 1979. Typically Merkle trees have a branching factor of 2, meaning that each NODE has up to 2 children.

The correct option is (d) HASHING is used for direct ACCESS

Easiest explanation - Hash tree allows direct as WELL as SEQUENTIAL access of the records. Hashing is used for direct access and indexing is GENERALLY used for the sequential access.

The correct choice is (a) True

The explanation is: HASH trees are used in DISTRIBUTED SYSTEMS for efficient data verification. Hash TREE used hashes instead of the full files, hence they are efficient. Because Hashes are ways of ENCODING files that are much smaller than the actual file itself.

Correct choice is (b) Hash list

Best EXPLANATION: Hash list is the list of HASHES of the BLOCKS in a set file. Hash tree is a GENERALIZATION of the hash list in which leaves are labeled with the hash of a data block and every non-leaf node is hash of the labels of its children.

Right CHOICE is (C) 17

Best explanation: The value of m’ is chosen as a PRIME number SLIGHTLY less than the value of m. Here the value of m is 19, hence the value of m’ can be chosen as 17.

Right option is (a) True

To EXPLAIN: Double hashing is ONE of the best methods for open addressing because the permutations produced have MANY CHARACTERISTICS of RANDOMLY chosen permutations.

The correct option is (a) Theta(n)

Easy explanation - The AVERAGE RETRIEVAL TIME when n keys HASH to the same slot is given by Theta(n) as the COLLISION occurs in the hash table.

Correct CHOICE is (b) 128

To explain: In MULTIPLICATION method of CREATING hash functions the table SIZE can be taken in integral POWERS of 2.

m = 2^p

m= 2^7

m = 128.

Right answer is (C) VALUE of m not critical

For explanation: The value of m can be simply in POWERS of 2 since we can easily implement the FUNCTION in most computers. m=2^p where p is an integer.

The correct CHOICE is (d) 2

Easy explanation - In multiplication method 2 steps are INVOLVED. FIRST multiplying the key value by a CONSTANT. Then multiplying this value by m.

The correct option is (c) 15

Easy explanation - The KEY 172 can be placed at POSITION 15 by using the formula

H(k) = k MOD m

H(k) = 172 mod 157

H(k) = 15.

Correct choice is (b) universal HASHING

Easiest explanation - Universal hashing scheme provides better PERFORMANCE than other schemes because it USES a UNIQUE randomisation approach.