Practice - 5 Tasks
Answer the questions below
1fill in blank
easyComplete the code to calculate the next index using linear probing.
DSA Rust
fn linear_probe(index: usize, step: usize, size: usize) -> usize {
(index + [1]) % size
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using the current index instead of the step for increment.
Not using modulo operation to wrap around the table.
✗ Incorrect
In linear probing, the next index is found by adding the step to the current index and taking modulo with the table size.
2fill in blank
mediumComplete the code to insert a key into the hash table using linear probing.
DSA Rust
fn insert(table: &mut [Option<i32>], key: i32) {
let size = table.len();
let mut index = (key as usize) % size;
while table[[1]].is_some() {
index = (index + 1) % size;
}
table[index] = Some(key);
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using the key instead of index to access the table.
Not updating the index correctly in the loop.
✗ Incorrect
We check if the current index is occupied, so we use 'index' to access the table.
3fill in blank
hardFix the error in the search function to correctly find a key using linear probing.
DSA Rust
fn search(table: &[Option<i32>], key: i32) -> Option<usize> {
let size = table.len();
let mut index = (key as usize) % size;
let start = index;
loop {
match table[[1]] {
Some(k) if k == key => return Some(index),
None => return None,
_ => {
index = (index + 1) % size;
if index == start {
return None;
}
}
}
}
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using the key as an index to access the table.
Not checking for the loop wrap-around condition.
✗ Incorrect
We must check the slot at the current index to find the key or an empty slot.
4fill in blank
hardFill both blanks to complete the delete function that marks a slot as deleted using linear probing.
DSA Rust
fn delete(table: &mut [Option<i32>], key: i32) {
let size = table.len();
let mut index = (key as usize) % size;
let start = index;
loop {
match table[[1]] {
Some(k) if k == key => {
table[index] = [2];
return;
},
None => return,
_ => {
index = (index + 1) % size;
if index == start {
return;
}
}
}
}
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Setting the slot to None instead of Some(0).
Using the key as an index.
✗ Incorrect
We check the slot at 'index' and mark it as deleted by setting it to Some(0).
5fill in blank
hardFill all three blanks to complete the function that counts occupied slots in the hash table.
DSA Rust
fn count_occupied(table: &[Option<i32>]) -> usize {
table.iter().filter(|&[1]| [2].is_some() && [3] != 0).count()
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Not using the correct pattern '|&slot|' in the closure parameter.
Comparing the Option directly without unwrapping.
✗ Incorrect
We destructure with '|&slot|', check if 'slot' is Some, and use 'slot.unwrap_or(0)' != 0 to exclude deleted slots (Some(0)).