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
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!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
function bubbleSort(arr) {
const n = arr.length;
for ( et i = 0; i < n; i++) {
// Flag to optimize if array becomes sorted
let swapped = false;
// Last i elements are already in place
for (let j = 0; j < n - i - 1; j++) {
// Compare adjacent elements
if (arr[j] > arr[j + 1]) {
// Swap them if they are in wrong order
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
// If no swapping occurred in this pass, array is sorted
if (!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
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
// Store current element
let current = arr[i];
// Find position for current element in the sorted part
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]; // Move elements forward
j--;
}
// 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 {
constructor(size = 53) {
this.keyMap = new Array(size);
}
_hash(key) {
let total = 0;
const PRIME = 31;
// Hash only the first 100 characters for better performance
for (let i = 0; i < Math.min(key.length, 100); i++) {
const char = key[i];
const value = char.charCodeAt(0) - 96;
total = (total * PRIME + value) % this.keyMap.length;
}
return total;
}
set(key, value) {
const index = this._hash(key);
if (!this.keyMap[index]) {
this.keyMap[index] = [];
}
// Check if key already exists to update
for (let i = 0; i < this.keyMap[index].length; i++) {
if (this.keyMap[index][i][0] === key) {
this.keyMap[index][i][1] = value;
return;
}
}
// Key doesn't exist, add new key-value pair
this.keyMap[index].push([key, value]);
}
get(key) {
const index = this._hash(key);
if (!this.keyMap[index]) return undefined;
for (let i = 0; i < this.keyMap[index].length; i++) {
if (this.keyMap[index][i][0] === key) {
return this.keyMap[index][i][1];
}
}
return undefined;
}
}
// 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
function firstNonRepeatingChar(str) {
const charCount = {};
// Count occurrences of each character
for (let char of str) {
charCount[char] = (charCount[char] || 0) + 1;
}
// Find first character with count 1
for (let i = 0; i < str.length; i++) {
if (charCount[str[i]] === 1) {
return str[i];
}
}
return null; // 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.