Search algorithms

Question 1

Time complexity of linear search

Answer 1

O(n)

Question 2

Time complexity of hash table search

Answer 2

O(1)

Question 3

Time complexity of binary search

Answer 3

O(logn)

Question 4

For a hash table, a perfect hash function should:

Answer 4

Takes an input key of any length

Returns an output hash index of fixed size

Question 5

For a hash table, a hash index should be:

Answer 5

Unique to the key

Same for equal keys

Question 6

For a hash table, a key should be:

Answer 6

Immutable (so that its hashed index is always the same)

Question 7

Name 2 collision resolution methods for hashtable

Answer 7

Separate chaining, linear probing (open addressing)

Question 8

What is hashing?

Answer 8

Hashing is the process of calculating the address (index) of a piece of data from its key using a hash function

Question 9

The key steps for Binary Search are:

Answer 9

1. Handle the base case (empty/single-element array)
2. Initialise l = 0 and r = array.length-1
3. Determine middle index mid
4. Check element at mid: if match, return mid; if less than key, update r to mid-1; if greater than key, update l to mid+1
5. If l==r (and no match found), return none or raise error, else repeat from step 3

Question 10

The key steps for Linear Search are:

Answer 10

1. Iterate through the array and compare the element in the array with
   the search value
2. Return first search value that matches element.
3. Return None if whole array is iterated through without matching values

Question 11

Time complexity of hash table removal

Answer 11

O(1)

Question 12

Time complexity of hash table insertion

Answer 12

O(1)