Introduction
Advanced Data Structure problems combine multiple concepts to solve practical programming challenges efficiently. These problems often require choosing the right data structure, managing multiple operations, and improving time complexity. In this chapter, you will practice 10 advanced problems using JavaScript, including LRU Cache, sliding window maximum, Trie-based searching, interval merging, Union-Find, monotonic stacks, and advanced graph-based operations.
Question 1: Design an LRU Cache
Question
Create an LRU (Least Recently Used) Cache that can store a maximum of 3 items. When the cache becomes full, remove the least recently used item.
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
let value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
}
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
let firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
}
}
let cache = new LRUCache(3);
cache.put("A", 100);
cache.put("B", 200);
cache.put("C", 300);
console.log(cache.get("A"));
cache.put("D", 400);
console.log(cache.get("B"));
console.log(cache.get("C"));
console.log(cache.get("D"));
Solution
The JavaScript Map maintains insertion order.
When an item is accessed:
- Remove it from the Map.
- Add it again.
- It becomes the most recently used item.
When the capacity is exceeded, the first key is removed because it is the least recently used.
Output
100
-1
300
400
Question 2: Find Maximum Value in Every Sliding Window
Question
Given an array and window size 3, find the maximum value in every sliding window.
function maxSlidingWindow(arr, k) {
let result = [];
let deque = [];
for (let i = 0; i < arr.length; i++) {
while (deque.length && deque[0] <= i - k) {
deque.shift();
}
while (
deque.length &&
arr[deque[deque.length - 1]] <= arr[i]
) {
deque.pop();
}
deque.push(i);
if (i >= k - 1) {
result.push(arr[deque[0]]);
}
}
return result;
}
console.log(
maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)
);
Solution
The deque stores indexes of useful elements.
For every new element:
- Remove indexes outside the current window.
- Remove smaller elements from the back.
- The front always contains the index of the maximum value.
Output
[3, 3, 5, 5, 6, 7]
Question 3: Build a Trie for Word Searching
Question
Create a Trie that can insert words and check whether a complete word exists.
class TrieNode {
constructor() {
this.children = {};
this.isEnd = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let current = this.root;
for (let char of word) {
if (!current.children[char]) {
current.children[char] = new TrieNode();
}
current = current.children[char];
}
current.isEnd = true;
}
search(word) {
let current = this.root;
for (let char of word) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}
return current.isEnd;
}
}
let trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
console.log(trie.search("cat"));
console.log(trie.search("can"));
console.log(trie.search("car"));
Solution
A Trie stores characters level by level.
For example:
cat
car
share the characters:
c → a
The isEnd property tells us whether a complete word ends at a particular node.
Output
true
false
true
Question 4: Merge Overlapping Intervals
Question
Given a list of intervals, merge all intervals that overlap.
function mergeIntervals(intervals) {
if (intervals.length === 0) {
return [];
}
intervals.sort((a, b) => a[0] - b[0]);
let result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
let last = result[result.length - 1];
let current = intervals[i];
if (current[0] <= last[1]) {
last[1] = Math.max(last[1], current[1]);
} else {
result.push(current);
}
}
return result;
}
console.log(
mergeIntervals([
[1, 3],
[2, 6],
[8, 10],
[9, 12]
])
);
Solution
First, sort the intervals according to their starting values.
Then compare each interval with the last merged interval.
For example:
[1,3] + [2,6] → [1,6]
[8,10] + [9,12] → [8,12]
Output
[[1, 6], [8, 12]]
Question 5: Detect a Cycle Using Union-Find
Question
Given edges of an undirected graph, determine whether adding an edge creates a cycle.
class UnionFind {
constructor(n) {
this.parent = new Array(n);
for (let i = 0; i < n; i++) {
this.parent[i] = i;
}
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(a, b) {
let rootA = this.find(a);
let rootB = this.find(b);
if (rootA === rootB) {
return false;
}
this.parent[rootB] = rootA;
return true;
}
}
function hasCycle(n, edges) {
let uf = new UnionFind(n);
for (let [a, b] of edges) {
if (!uf.union(a, b)) {
return true;
}
}
return false;
}
console.log(
hasCycle(4, [
[0, 1],
[1, 2],
[2, 3],
[3, 0]
])
);
Solution
Union-Find keeps track of connected components.
When two vertices already belong to the same component, connecting them again creates a cycle.
The edge:
3 → 0
connects vertices that are already connected.
Output
true
Question 6: Find the Next Greater Element
Question
For every element in an array, find the first greater element appearing on its right.
function nextGreaterElement(arr) {
let result = new Array(arr.length).fill(-1);
let stack = [];
for (let i = 0; i < arr.length; i++) {
while (
stack.length &&
arr[i] > arr[stack[stack.length - 1]]
) {
let index = stack.pop();
result[index] = arr[i];
}
stack.push(i);
}
return result;
}
console.log(
nextGreaterElement([4, 5, 2, 10, 8])
);
Solution
A monotonic stack helps find the next greater element efficiently.
When the current value is greater than the value represented by the stack’s top index, that current value becomes its next greater element.
Output
[5, 10, 10, -1, -1]
Question 7: Find the Kth Largest Element
Question
Find the 3rd largest element from the array without sorting the entire array.
function kthLargest(arr, k) {
let heap = [];
for (let num of arr) {
heap.push(num);
heap.sort((a, b) => a - b);
if (heap.length > k) {
heap.shift();
}
}
return heap[0];
}
console.log(
kthLargest([7, 10, 4, 3, 20, 15], 3)
);
Solution
We maintain only the k largest elements.
For k = 3, the structure keeps the three largest values seen so far.
At the end:
10, 15, 20
are the three largest values.
Therefore, the 3rd largest value is 10.
Output
10
Question 8: Find Connected Components in a Graph
Question
Given an undirected graph, count how many separate connected components exist.
function countComponents(n, edges) {
let graph = Array.from({ length: n }, () => []);
for (let [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
}
let visited = new Array(n).fill(false);
let count = 0;
function dfs(node) {
visited[node] = true;
for (let neighbor of graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor);
}
}
}
for (let i = 0; i < n; i++) {
if (!visited[i]) {
count++;
dfs(i);
}
}
return count;
}
console.log(
countComponents(6, [
[0, 1],
[1, 2],
[3, 4]
])
);
Solution
The graph contains:
Component 1 → 0, 1, 2
Component 2 → 3, 4
Component 3 → 5
Every time DFS starts from an unvisited node, we have found a new connected component.
Output
3
Question 9: Find Top K Frequent Elements
Question
Find the 2 most frequently occurring elements in an array.
function topKFrequent(arr, k) {
let frequency = new Map();
for (let num of arr) {
frequency.set(
num,
(frequency.get(num) || 0) + 1
);
}
let items = [...frequency.entries()];
items.sort((a, b) => b[1] - a[1]);
return items
.slice(0, k)
.map(item => item[0]);
}
console.log(
topKFrequent([1, 1, 1, 2, 2, 3], 2)
);
Solution
First, store the frequency of every number.
The frequency table becomes:
1 → 3
2 → 2
3 → 1
Then sort by frequency in descending order and select the first two elements.
Output
[1, 2]
Question 10: Find Shortest Path in an Unweighted Graph
Question
Find the shortest distance from node 0 to node 5.
function shortestPath(graph, start, target) {
let queue = [[start, 0]];
let visited = new Set([start]);
while (queue.length > 0) {
let [node, distance] = queue.shift();
if (node === target) {
return distance;
}
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, distance + 1]);
}
}
}
return -1;
}
let graph = [
[1, 2],
[0, 3],
[0, 4],
[1, 5],
[2, 5],
[3, 4]
];
console.log(shortestPath(graph, 0, 5));
Solution
Because every edge has the same cost, BFS can be used to find the shortest path.
Possible shortest paths include:
0 → 1 → 3 → 5
and
0 → 2 → 4 → 5
Both contain 3 edges.
Output
3
Key Takeaways
- Advanced problems often combine multiple data structures.
- LRU Cache can be implemented using a Map and ordering logic.
- Deques are useful for sliding-window problems.
- Tries are efficient for prefix and word-search operations.
- Sorting is useful for interval merging.
- Union-Find helps manage connected components and detect cycles.
- Monotonic stacks can solve next-greater-element problems efficiently.
- Heaps are commonly used for Kth-largest and Top-K problems.
- Graph traversal can identify connected components.
- BFS can find shortest paths in unweighted graphs.
- Choosing the correct data structure can greatly improve an algorithm’s efficiency.
FAQs
1. What are Advanced Data Structure problems?
Advanced Data Structure problems require combining data structures and algorithms to solve more complex programming tasks efficiently.
2. Which data structures are commonly used in advanced problems?
Common structures include heaps, tries, hash tables, deques, stacks, queues, graphs, trees, and Union-Find.
3. What is an LRU Cache?
An LRU Cache stores a limited number of items and removes the item that has not been used for the longest time when the cache becomes full.
4. Why are Tries useful?
Tries are useful for storing and searching strings, especially when prefix-based searching is required.
5. What is Union-Find used for?
Union-Find is commonly used for managing connected components, detecting cycles, and solving network connectivity problems.
6. When should I use a monotonic stack?
A monotonic stack is useful when a problem asks for the next greater, next smaller, previous greater, or previous smaller element.
7. Why are advanced data structure problems important for programming?
They help you learn how to select the right data structure, reduce unnecessary operations, and design efficient solutions for real-world and interview-style problems.
Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.
