Searching & Hash Tables — Deep Dives · Coding Interview Guide

Challenges on this page

Sequential Search
Binary Search
Hash Table

01Sequential Search

Source notebook: Sequential Search Udemy.ipynb

Sequential Search

Check out the video lecture for a full breakdown, in this Notebook all we do is implement Sequential Search for an Unordered List and an Ordered List.

Sequential Search

Python

def seq_search(arr,ele):
    """
    General Sequential Search. Works on Unordered lists.
    """
    
    # Start at position 0
    pos = 0
    # Target becomes true if ele is in the list
    found = False
    
    # go until end of list
    while pos < len(arr) and not found:
        
        # If match
        if arr[pos] == ele:
            found = True
            
        # Else move one down
        else:
            pos  = pos+1
    
    return found

Python

arr = [1,9,2,8,3,4,7,5,6]

Python

print seq_search(arr,1)

Output

True

Python

print seq_search(arr,10)

Output

False

Ordered List

If we know the list is ordered than, we only have to check until we have found the element or an element greater than it.

Python

def ordered_seq_search(arr,ele):
    """
    Sequential search for an Ordered list
    """
    # Start at position 0
    pos = 0
    
    # Target becomes true if ele is in the list
    found = False
    
    # Stop marker
    stopped = False
    
    # go until end of list
    while pos < len(arr) and not found and not stopped:
        
        # If match
        if arr[pos] == ele:
            found = True
            
        else:
            
            # Check if element is greater
            if arr[pos] > ele:
                stopped = True
                
            # Otherwise move on
            else:
                pos  = pos+1
    
    return found

Python

arr.sort()

Python

ordered_seq_search(arr,3)

Output

True

Python

ordered_seq_search(arr,1.5)

Output

False

Good Job!

02Binary Search

Source notebook: Binary Search Udemy.ipynb

Implementation of Binary Search

In this notebook we will just implement two versions of a simple binary search. View the video lecture for a full breakdown!

Binary Search

Python

def binary_search(arr,ele):
    
    # First and last index values
    first = 0
    last = len(arr) - 1
    
    found = False
    
    
    while first <= last and not found:
        
        mid = (first+last)//2 # or // for Python 3
        
        # Match found
        if arr[mid] == ele:
            found = True
        
        # Set new midpoints up or down depending on comparison
        else:
            # Set down
            if ele < arr[mid]:
                last = mid -1
            # Set up 
            else:
                first = mid + 1
                
    return found

Python

# list must already be sorted!
arr = [1,2,3,4,5,6,7,8,9,10]

Python

binary_search(arr,4)

Output

True

Python

binary_search(arr,2.2)

Output

False

Recursive Version of Binary Search

Python

def rec_bin_search(arr,ele):
    
    # Base Case!
    if len(arr) == 0:
        return False
    
    # Recursive Case
    else:
        
        mid = len(arr)//2
        
        # If match found
        if arr[mid]==ele:
            return True
        
        else:
            
            # Call again on second half
            if ele<arr[mid]:
                return rec_bin_search(arr[:mid],ele)
            
            # Or call on first half
            else:
                return rec_bin_search(arr[mid+1:],ele)

Python

rec_bin_search(arr,3)

Output

True

Python

rec_bin_search(arr,15)

Output

False

Good Job!

03Hash Table

Source notebook: Hash Table Udemy.ipynb

Implementation of a Hash Table

In this lecture we will be implementing our own Hash Table to complete our understanding of Hash Tables and Hash Functions! Make sure to review the video lecture before this to fully understand this implementation!

Keep in mind that Python already has a built-in dictionary object that serves as a Hash Table, you would never actually need to implement your own hash table in Python.

Map

The idea of a dictionary used as a hash table to get and retrieve items using keys is often referred to as a mapping. In our implementation we will have the following methods:

HashTable() Create a new, empty map. It returns an empty map collection.
put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.
get(key) Given a key, return the value stored in the map or None otherwise.
del Delete the key-value pair from the map using a statement of the form del map[key].
len() Return the number of key-value pairs stored
in the map in Return True for a statement of the form key in map, if the given key is in the map, False otherwise.

Python

class HashTable(object):
    
    def __init__(self,size):
        
        # Set up size and slots and data
        self.size = size
        self.slots = [None] * self.size
        self.data = [None] * self.size
        
    def put(self,key,data):
        #Note, we'll only use integer keys for ease of use with the Hash Function
        
        # Get the hash value
        hashvalue = self.hashfunction(key,len(self.slots))

        # If Slot is Empty
        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        
        else:
            
            # If key already exists, replace old value
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data  
            
            # Otherwise, find the next available slot
            else:
                
                nextslot = self.rehash(hashvalue,len(self.slots))
                
                # Get to the next slot
                while self.slots[nextslot] != None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot,len(self.slots))
                
                # Set new key, if NONE
                if self.slots[nextslot] == None:
                    self.slots[nextslot]=key
                    self.data[nextslot]=data
                    
                # Otherwise replace old value
                else:
                    self.data[nextslot] = data 

    def hashfunction(self,key,size):
        # Remainder Method
        return key%size

    def rehash(self,oldhash,size):
        # For finding next possible positions
        return (oldhash+1)%size
    
    
    def get(self,key):
        
        # Getting items given a key
        
        # Set up variables for our search
        startslot = self.hashfunction(key,len(self.slots))
        data = None
        stop = False
        found = False
        position = startslot
        
        # Until we discern that its not empty or found (and haven't stopped yet)
        while self.slots[position] != None and not found and not stop:
            
            if self.slots[position] == key:
                found = True
                data = self.data[position]
                
            else:
                position=self.rehash(position,len(self.slots))
                if position == startslot:
                    
                    stop = True
        return data

    # Special Methods for use with Python indexing
    def __getitem__(self,key):
        return self.get(key)

    def __setitem__(self,key,data):
        self.put(key,data)

Let's see it in action!

Python

h = HashTable(5)

Python

# Put our first key in
h[1] = 'one'

Python

h[2] = 'two'

Python

h[3] = 'three'

Python

h[1]

Output

'one'

Python

h[1] = 'new_one'

Python

h[1]

Output

'new_one'

Python

print h[4]

Output

None

Great Job!

That's it for this rudimentary implementation, try implementing a different hash function for practice!