search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.

Recent questions tagged hashing

0 votes
1 answer 10 views
In Mid Square Method(Hashing), we square the given number and then use appropriate bits from the middle. Can we have so many answers for a particular question? On what basis we choose the middle digit? What if the square is 4 digit 1234, then what will be the middle value? Will it be 23 or 2 or 3. Please explain.
asked Jul 10 in DS Lata Patwal 9 points 10 views
2 votes
1 answer 646 views
Consider a $\textit{dynamic}$ hashing approach for $4$-bit integer keys: There is a main hash table of size $4$. The $2$ least significant bits of a key is used to index into the main hash table. Initially, the main hash table entries are empty. Thereafter, when more keys are hashed into it, to resolve ... in decimal notation)? $5,9,4,13,10,7$ $9,5,10,6,7,1$ $10,9,6,7,5,13$ $9,5,13,6,10,14$
asked Feb 18 in Algorithms Arjun 1.5k points 646 views
0 votes
0 answers 21 views
" if we assume uniform hashing, what is the probability that a collision will occur in a hash table with 100 buckets and 2 keys?" Doesn't this question means that we have a hash table in which there are already 2 keys, and we have to find probability of collision for the next insertion? Or it is asking the probability of collision in the table for these two keys insertion?
asked Jan 14 in Programming Ankita87077 11 points 21 views
0 votes
0 answers 29 views
https://gateoverflow.in/57653/cormen-2nd-edition-exercise-11-2-1 WHY WE CANT DO LIKE THIS …...NUMBER OF COLLISIONS(X) : 0 1 2 3 4 …………………...N-1 P(X): 0/M 1/M 2/M…………………… … ………….(N-1)/M
asked Jan 12 in DS eyeamgj 29 points 29 views
0 votes
0 answers 10 views
A hash table of length $10$ uses open addressing with hash function $h(k) = k \: mod \: 10$, and linear probing. After inserting $6$ ... insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above? $10$ $20$ $30$ $40$
asked Apr 18, 2020 in DS admin 573 points 10 views
0 votes
0 answers 18 views
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols $S1$ to $S7$ initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is $4$ $5$ $6$ $3$
asked Apr 18, 2020 in DS admin 573 points 18 views
0 votes
0 answers 16 views
Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed $0.5$. $5$ $6$ $7$ $10$
asked Apr 18, 2020 in DS admin 573 points 16 views
0 votes
0 answers 12 views
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? $(97 \times 97 \times 97) / 100^3$ $(99 \times 98 \times 97) / 100^3$ $(97 \times 96 \times 95) / 100^3$ $(97 \times 96 \times 95 / (3! \times 100^3)$
asked Apr 18, 2020 in DS admin 573 points 12 views
0 votes
0 answers 17 views
Which one of the following hash functions on integers will distribute keys most uniformly over $10$ buckets numbered $0$ to $9$ for $i$ ranging from $0$ to $2020$? $h(i) = i^2 \text{mod } 10$ $h(i) = i^3 \text{mod } 10$ $h(i) = (11 \ast i^2) \text{mod } 10$ $h(i) = (12 \ast i^2) \text{mod } 10$
asked Apr 18, 2020 in DS admin 573 points 17 views
0 votes
0 answers 13 views
An advantage of chained hash table (external hashing) over the open addressing scheme is Worst case complexity of search operations is less Space used is less Deletion is easier None of the above
asked Apr 18, 2020 in DS admin 573 points 13 views
0 votes
0 answers 31 views
Consider a hash table with $n$ buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is $\frac{1}{n}$. The hash table is initially empty and $K$ ... has occurred in any of the $K$ insertions? What is the probability that the first collision occurs at the $K^{th}$ insertion?
asked Apr 18, 2020 in DS admin 573 points 31 views
0 votes
0 answers 10 views
Consider a hash table of size seven, with starting index zero, and a hash function $(3x + 4)\mod 7$. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence $1, 3, 8, 10$ is inserted into the table using closed hashing? Note that − denotes an empty location in the ... $3$ $1$, −, −, −, −, −, $3$ $1, 10, 8$, −, −, −,$ 3$
asked Apr 18, 2020 in DS admin 573 points 10 views
0 votes
0 answers 53 views
Which of the following statements is true? As the number of entries in a hash table increases, the number of collisions increases. Recursive programs are efficient The worst case complexity for Quicksort is $O(n^2)$ Binary search using a linear linked list is efficient I and II II and III I and IV I and III
asked Apr 18, 2020 in DS admin 573 points 53 views
0 votes
0 answers 9 views
Consider a hash table with $9$ slots. The hash function is $h(k)= k \mod 9$. The collisions are resolved by chaining. The following $9$ keys are inserted in the order: $5, 28, 19, 15, 20, 33, 12, 17, 10$. The maximum, minimum, and average chain lengths in the hash table, respectively, are $3, 0,$ and $1$ $3, 3,$ and $3$ $4, 0,$ and $1$ $3, 0,$ and $2$
asked Apr 18, 2020 in DS admin 573 points 9 views
0 votes
0 answers 21 views
A hash table of length $10$ uses open addressing with hash function $h(k) = k \mod 10$, and linear probing. After inserting $6$ ... $46, 42, 34, 52, 23, 33$ $34, 42, 23, 52, 33, 46$ $46, 34, 42, 23, 52, 33$ $42, 46, 33, 23, 34, 52$
asked Apr 18, 2020 in DS admin 573 points 21 views
0 votes
0 answers 10 views
Insert the characters of the string $K \ R \ P \ C \ S \ N \ Y \ T \ J \ M$ into a hash table of size $10$. Use the hash function $h(x)=( ord (x) – ord ("a") + 1) \mod 10$ and linear probing to resolve collisions. Which insertions cause collisions? Display the final hash table.
asked Apr 18, 2020 in DS admin 573 points 10 views
0 votes
0 answers 14 views
A hash table contains $10$ buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % $10$. If the values $43, 165, 62, 123, 142$ are inserted in the table, in what location would the key value $142$ be inserted? $2$ $3$ $4$ $6$
asked Apr 18, 2020 in DS admin 573 points 14 views
0 votes
0 answers 15 views
Given that hash table $T$ with $25$ slots that stores $2000$ elements, the load factor $a$ for $T$ is _________.
asked Apr 18, 2020 in DS admin 573 points 15 views
0 votes
0 answers 8 views
Which of the following statement(s) is TRUE? A hash function takes a message of arbitrary length and generates a fixed length code. A hash function takes a message of fixed length and generates a code of variable length. A hash function may give the same hash value for distinct messages. I only II and III only I and III only II only
asked Apr 18, 2020 in DS admin 573 points 8 views
0 votes
0 answers 10 views
The keys $12, 18, 13, 2, 3, 23, 5$ and $15$ are inserted into an initially empty hash table of length $10$ using open addressing with hash function $h(k) = k \mod 10$ ...
asked Apr 18, 2020 in DS admin 573 points 10 views
1 vote
1 answer 29 views
Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ is_____________.
asked Apr 18, 2020 in Algorithms admin 573 points 29 views
0 votes
0 answers 4 views
Given the following input $(4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199)$ and the hash function $x$ mod $10$, which of the following statements are true? $9679, 1989, 4199$ hash to the same value $1471, 6171$ hash to the same value All elements hash to the same value Each element hashes to a different value I only II only I and II only III or IV
asked Apr 18, 2020 in DS admin 573 points 4 views
0 votes
0 answers 10 views
Consider a hash table of size $11$ that uses open addressing with linear probing. Let $h(k) = k \mod 11$ be the hash function used. A sequence of records with keys $43 \ 36 \ 92 \ 87 \ 11 \ 4 \ 71 \ 13 \ 14$ is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted? $3$ $4$ $6$ $7$
asked Apr 18, 2020 in DS admin 573 points 10 views
0 votes
0 answers 31 views
Consider a hash table with chaining scheme for overflow handling: What is the worst-case timing complexity of inserting $n$ elements into such a table? For what type of instance does this hashing scheme take the worst-case time for insertion?
asked Apr 18, 2020 in Algorithms admin 573 points 31 views
0 votes
0 answers 126 views
In hashing, collision resolution is carried out by close addressing. Which of the following is close addressing technique – I. Buckets (for contiguous storage) II. Chains (for linked storage) A. Only I B. Only II C. I and II D. None i think Buckets for continuous storage is like arrays so it will use linear probing (open addressing) chains – uses closed addressing.
asked Mar 5, 2020 in Programming rjking7403 7 points 126 views
1 vote
1 answer 47 views
Sequentially means one after another,there may or maynot gap between two, right?? Then how $m^{2}$ should be in denominator ?? What will be ans here, B) or C)??
asked Feb 4, 2020 in Algorithms srestha 1k points 47 views
0 votes
0 answers 113 views
asked Jan 27, 2020 in DS abhinav649 31 points 113 views
0 votes
1 answer 69 views
Identify valid hash function for storing in the address range $\mathbf{1}$ to $\mathbf{1000}$ $\mathbf{h(x) = x \;mod\;1000}$ $\mathbf{(x+1)\;mod\;1000}$ $\mathbf{h(x) = x \;mod\;(1000+1)}$ $\mathbf{h(x) = (x \;mod\;1000)+1}$ My Work: According to me answer is $\mathbf{1}$ but the given answer is $\mathbf{4}$
asked Dec 19, 2019 in Programming `JEET 187 points 69 views
0 votes
1 answer 111 views
You are given a hash table with n keys and m slots, with the simple uniform hashing (assume each key is equally likely to be hashed into each slot). Collisions are resolved by chaining. What is the expected number of slots that end up not being empty ?
asked Dec 2, 2019 in DS Sambhrant Maurya 493 points 111 views
0 votes
0 answers 25 views
https://gateoverflow.in/2272/gate1997-12 I dint understand the answer here. I would really appreciate if anybody could explain it with an example?
asked Dec 2, 2019 in Programming chandrikabhuyan8 165 points 25 views
0 votes
0 answers 68 views
Is hashing topic in data structures has been removed because on the official website of gate iitd I am not seeing the hashing topic listed in the syllabus? Sorry, I know this isn't the type of question that people ask here but I just wanted to know.
asked Aug 8, 2019 in DS setu bhaskar 5 points 68 views
0 votes
0 answers 38 views
Using open addressing with linear probing, we sequentially insert three distinct keys k1, k2 and k3 into a hash table of size m. Assuming simple uniform hashing, what is the probability that we will need three probes, when inserting the third key, k3? a.3/m^2 b. 3/m c.2/m d.2/m^2 anyone please explain above problem in detail….
asked Jul 30, 2019 in Algorithms Manasa.M 11 points 38 views
To see more, click for the full list of questions or popular tags.
...