Practice Sorting and Hash Tables
Strengthen your sorting and hash table skills to excel in technical interviews and prepare for advanced DSA
concepts.
Hash Tables
Upon completion of the hash tables module, you will be able to:
- Understand how hash tables work internally
- Use hash tables to speed up algorithm performance
- Identify problems that can be efficiently solved using hash tables
- Implement hash table-based solutions
Sorting Fundamentals
Sorting is the process of arranging elements in a specific order (usually ascending or
descending). Efficient sorting is crucial for optimizing search operations and making data easier to process.
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements,
and swaps them if they are in the wrong order.
# Bubble Sort implementation
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arrj + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
# Time Complexity:
# - Best Case: O(n) when array is already sorted
# - Average Case: O(n²)
# - Worst Case: O(n²)
# Space Complexity: O(1
Sorting Fundamentals
Sorting is the process of arranging elements in a specific order (usually ascending or
descending). Efficient sorting is crucial for optimizing search operations and making data easier to process.
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements,
and swaps them if they are in the wrong order.
# Bubble Sort implementation
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Flag to optimize if array becomes sorted
swapped = False
# Last i elements are already in place
for j in range(n - i - 1):
# Compare adjacent elements
if arr[j] > arr[j + 1]:
# Swap them if they are in wrong order
arr[j], arrj + 1] = arr[j + 1], arr[j]
swapped = True
# If no swapping occurred in this pass, array is sorted
if not swapped:
break
return arr
# Time Complexity:
# - Best Case: O(n) when array is already sorted
# - Average Case: O(n²)
# - Worst Case: O(n²)
# Space Complexity: O(1
Insertion Sort
Insertion Sort builds the final sorted array one item at a time. It's efficient for small data sets and
nearly sorted arrays.
# Insertion Sort implementation
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
# Store current element
current = arr[i]
# Find position for current element in the sorted part
j = i - 1
while j >= 0 and arr[j] > current:
arr[j + 1] = arr[j] # Move elements forward
j -= 1
# Place current element in its correct position
arr[j + 1] = current
return arr
# Time Complexity:
# - Best Case: O(n) when array is already sorted
# - Average Case: O(n²)
# - Worst Case: O(n²)
# Space Complexity: O(1
Hash Tables
A hash table is a data structure that implements an associative array, mapping keys to values.
It uses a hash function to compute an index into an array of buckets or slots, from which the desired value
can be found.
Hash Table Concepts
- Hash Function: Converts keys into array indices
- Collision: When two keys hash to the same index
- Collision Resolution: Techniques like chaining or open addressing
- Load Factor: Ratio of elements to buckets
# Simple Hash Table implementation with chaining
class HashTable:
def __init__(self, size=53):
self.key_map = [None] * size
def _hash(self, key):
total = 0
PRIME = 31
# Hash only the first 100racters for better performance
for i in range(min(len(key), 100)):
char = key[i]
value = ord(char) - 96
total = (total * PRIME + value) % len(self.key_map)
return total
def set(self, key, value):
index = self._hash(key)
if not self.key_map[index]:
self.key_map[index] = []
# Check if key already exists to update
for i in range(len(self.key_map[index])):
if self.key_map[index][i][0] == key:
self.key_map[index][i][1] = value
return
# Key doesn't exist, add new key-value pair
self.key_map[index].append([key, value])
def get(self, key):
index = self._hash(key)
if not self.key_map[index]:
return None
for i in range(len(self.key_map[index])):
if self.key_map[index][i][0] == key:
return self.key_map[index][i][1]
return None
# Time Complexity:
# - Average Case for get/set: O(1
# - Worst Case (hash collisions): O(n)
Using Hash Tables to Solve Problems
Hash tables are excellent for quick lookups and can optimize many algorithms:
# Find the first non-repeating character in a string
def first_non_repeating_char(s):
char_count =[object Object]}
# Count occurrences of each character
for char in s:
char_count[char] = char_count.get(char, 0) + 1 # Find first character with count 1
for i in range(len(s)):
if char_count[s[i]] == 1:
return s[i]
return None # No non-repeating character found
# Time Complexity: O(n)
# Space Complexity: O(k) where k is the size of the character set
Now it's time to practice what you learned!
You should have already created your Code Signal account. If you have not done so yet, please
follow these instructions What is CodeSignal and How to Create Your Account.
Tip: Before you dive into the practice tasks, revisit the core competency and guided
project videos in this sprint.
Complete these tasks in CodeSignal:
ACS2M4
ACS2M5
ACS2M6
- Login to CodeSignal
- Click on the task links above
- Select your preferred language
- Click on NEXT to begin
- Agree with the Terms and Pledges and click START
Once all the questions for each task are completed in Code Signal, click on Finish the
Test.