MongoDB

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