Explore algorithm design questions to enhance problem-solving skills in JavaScript. Learn to design an LRU Cache, implement a Trie, find the median of two sorted arrays, and solve the Word Ladder problem using efficient algorithms.
Algorithm design is a critical skill for software engineers, enabling them to tackle complex problems with efficient solutions. In this section, we will explore several open-ended design problems that will enhance your ability to develop algorithms for novel challenges. By practicing these problems, you will improve your creativity and adaptability in problem-solving.
Problem: Create a data structure that follows the Least Recently Used (LRU) cache eviction policy. This cache should support the following operations: get(key) and put(key, value), both in O(1) time complexity.
Solution Approach: To achieve O(1) time complexity for both operations, we can use a combination of a hash map and a doubly linked list. The hash map will store the keys and their corresponding nodes in the linked list, while the doubly linked list will maintain the order of usage, with the most recently used items at the front and the least recently used items at the back.
Implementation:
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
this.head = new Node(null, null);
this.tail = new Node(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_add(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._remove(node);
this._add(node);
return node.value;
}
put(key, value) {
if (this.map.has(key)) {
this._remove(this.map.get(key));
}
const newNode = new Node(key, value);
this._add(newNode);
this.map.set(key, newNode);
if (this.map.size > this.capacity) {
const lru = this.tail.prev;
this._remove(lru);
this.map.delete(lru.key);
}
}
}
Diagram:
graph TD;
A[Head] --> B[Node1]
B --> C[Node2]
C --> D[Tail]
B -->|prev| A
C -->|prev| B
D -->|prev| C
Discussion:
get and put operations efficiently.Problem: Design a trie for efficient retrieval of words based on their prefixes. The trie should support insertion and search operations.
Solution Approach: A trie is a tree-like data structure that stores a dynamic set of strings, where the keys are usually strings. Each node represents a single character of a string, and the path from the root to a node represents a prefix of the string.
Implementation:
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
}
search(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return node.isEndOfWord;
}
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return true;
}
}
Diagram:
graph TD;
A[Root] --> B[a]
B --> C[p]
C --> D[p]
D --> E[l]
E --> F[e]
F -->|isEndOfWord| G[End]
Discussion:
Problem: Find the median of two sorted arrays in logarithmic time.
Solution Approach: To find the median in logarithmic time, we can use a binary search approach to partition the two arrays. The goal is to partition the arrays such that all elements on the left side are less than or equal to all elements on the right side.
Implementation:
function findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
let x = nums1.length;
let y = nums2.length;
let low = 0, high = x;
while (low <= high) {
let partitionX = (low + high) >> 1;
let partitionY = ((x + y + 1) >> 1) - partitionX;
let maxX = (partitionX === 0) ? -Infinity : nums1[partitionX - 1];
let minX = (partitionX === x) ? Infinity : nums1[partitionX];
let maxY = (partitionY === 0) ? -Infinity : nums2[partitionY - 1];
let minY = (partitionY === y) ? Infinity : nums2[partitionY];
if (maxX <= minY && maxY <= minX) {
if ((x + y) % 2 === 0) {
return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;
} else {
return Math.max(maxX, maxY);
}
} else if (maxX > minY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
}
}
throw new Error("Input arrays are not sorted");
}
Diagram:
graph TD;
A[nums1] --> B[PartitionX]
C[nums2] --> D[PartitionY]
B --> E[MaxX]
D --> F[MaxY]
E --> G[MinX]
F --> H[MinY]
Discussion:
Problem: Transform one word into another by changing one letter at a time, using a given dictionary, and find the shortest transformation sequence.
Solution Approach: This problem can be solved using a breadth-first search (BFS) approach to find the shortest path from the start word to the end word.
Implementation:
function ladderLength(beginWord, endWord, wordList) {
const wordSet = new Set(wordList);
if (!wordSet.has(endWord)) return 0;
let queue = [[beginWord, 1]];
while (queue.length > 0) {
let [currentWord, level] = queue.shift();
for (let i = 0; i < currentWord.length; i++) {
for (let c = 97; c <= 122; c++) {
let nextWord = currentWord.slice(0, i) + String.fromCharCode(c) + currentWord.slice(i + 1);
if (nextWord === endWord) return level + 1;
if (wordSet.has(nextWord)) {
queue.push([nextWord, level + 1]);
wordSet.delete(nextWord);
}
}
}
}
return 0;
}
Diagram:
graph TD;
A[beginWord] --> B[Transformation1]
B --> C[Transformation2]
C --> D[endWord]
A --> E[Transformation3]
E --> F[Transformation4]
F --> D
Discussion: