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
public int[] bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) { boolean swapped=false; for (int j=0; j < n - i - 1; j++) { if (arr[j]> arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
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
public int[] bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) { boolean swapped=false; for (int j=0; j < n - i - 1; j++) { if (arr[j]> arr[j +
1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
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)
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
public int[] insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) { int current=arr[i]; int j=i - 1; while (j>= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
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 {
private List> keyMap;
public HashTable(int size) {
keyMap = new ArrayList<>(Collections.nCopies(size, null));
}
private int _hash(String key) {
int total = 0;
int PRIME = 31;
int len = Math.min(key.length(), 100);
for (int i = 0; i < len; i++) { char c=key.charAt(i); int value=c - 'a' + 1; total=(total * PRIME + value)
% keyMap.size(); } return total; } public void set(String key, String value) { int index=_hash(key); if
(keyMap.get(index)==null) { keyMap.set(index, new ArrayList<>());
}
for (Entry entry : keyMap.get(index)) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
keyMap.get(index).add(new Entry(key, value));
}
public String get(String key) {
int index = _hash(key);
if (keyMap.get(index) == null) return null;
for (Entry entry : keyMap.get(index)) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null;
}
static class Entry {
String key;
String value;
Entry(String key, String value) {
this.key = key;
this.value = value;
}
}
}
// 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
public Character firstNonRepeatingChar(String str) {
Map charCount = new HashMap<>();
// Count occurrences of each character
for (char c : str.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
// Find first character with count 1
for (int i = 0; i < str.length(); i++) { if (charCount.get(str.charAt(i))==1) { return str.charAt(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.