Implement HashMap with put/get methods and expiration support.
Part 1: Basic HashMap
class HashMap<K, V> {
put(key: K, value: V): void;
get(key: K): V | null;
}
Requirements:
- O(1) average operations
- Handle collisions
- Thread safety considerations
Part 2: Expiring HashMap
interface ExpiringEntry<V> {
value: V;
expiresAt: number;
}
class ExpiringHashMap<K, V> {
put(key: K, value: V, ttlMs: number): void;
get(key: K): V | null;
cleanup(): void;
}
Implementation:
- Background cleanup
- Atomic operations
- Memory management
Square elements of sorted array maintaining order.
function squareArray(nums: number[]): number[]
Examples:
1. Input: [1,2,3,4]
Output: [1,4,9,16]
2. Input: [-6,1,2,3,4]
Output: [1,4,9,16,36]
Variations:
1. Immutable Input
- Create new array
- Space complexity O(n)
2. With Negatives
- Two pointer approach
- Handle sign changes
Find unique intersection of two arrays.
function intersection(
nums1: number[],
nums2: number[]
): number[]
Examples:
1. Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
2. Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Constraints:
- 1 <= nums1.length, nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 1000
- Return unique elements
- Any order acceptable
Merge k sorted linked lists into one sorted list.
interface ListNode {
val: number;
next: ListNode | null;
}
function mergeKLists(
lists: ListNode[]
): ListNode | null
Approaches:
1. Priority Queue
- Time: O(N log k)
- Space: O(k)
2. Divide and Conquer
- Time: O(N log k)
- Space: O(1)
Implement HashMap that maintains insertion order.
class LinkedHashMap<K, V> {
put(key: K, value: V): void;
get(key: K): V | null;
remove(key: K): boolean;
keys(): K[];
}
Requirements:
1. Data Structures
- Hash table for O(1) access
- Doubly linked list for order
2. Operations
- Maintain insertion order
- O(1) average operations
- Iterator support
Find LCA using parent pointers in binary tree.
interface TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
parent: TreeNode | null;
}
function findLCA(
p: TreeNode,
q: TreeNode
): TreeNode
Approaches:
1. Path Recording
- Track path to root
- Find first intersection
2. Two Pointer
- Switch pointers at root
- Find meeting point
Implement Least Recently Used (LRU) cache.
class LRUCache {
constructor(capacity: number);
get(key: number): number;
put(key: number, value: number): void;
}
Requirements:
1. Data Structures
- HashMap for O(1) lookup
- Doubly linked list for LRU
2. Operations
- O(1) get/put
- Automatic eviction
- Capacity management
Implement read/write lock for concurrent access.
class RWLock {
acquireRead(): void;
releaseRead(): void;
acquireWrite(): void;
releaseWrite(): void;
}
Requirements:
1. Multiple Readers
- Allow concurrent reads
- Block during writes
2. Exclusive Writer
- Block all access
- Prevent starvation
3. Thread Safety
- Atomic operations
- Deadlock prevention
Match string against pattern with + operator.
function matches(s: string, p: string): boolean
Examples:
Input: s = "google", p = "go+gle"
Output: true
Rules:
- '+' means 1 or more occurrences
- Match exact characters
- Case sensitive comparison
Approach:
1. State tracking
2. Character counting
3. Pattern validation
Find top 50 players by highest score.
interface Player {
name: string;
score: number;
}
function getTopPlayers(
players: Player[]
): Player[]
Requirements:
1. Score Processing
- Keep highest score per player
- Sort by score descending
- Return top 50
2. Optimization
- Efficient duplicate handling
- Memory usage
- Large dataset support
Find indices of smallest numbers >= target in sorted array.
function findSmallestGreater(
arr: number[],
target: number
): number[]
Example:
Input: arr = [1,3,3,4,5,6,7], target = 3
Output: [1,2] (indices of 3s)
Approach:
1. Binary search for lower bound
2. Linear scan for duplicates
3. Return all valid indices