ADVANCED CODING CHALLENGES AND PROBLEM-SOLVING GUIDE
======================================================================
Challenge 1: Reverse a Linked List
----------------------------------------------------------------------
Description:
Implement both iterative and recursive solutions to reverse a singly linked list.
Approach:
Iterative: Use three pointers (previous, current, next) to reverse links.
Recursive: Process nodes from the end, reversing links during unwinding.
Complexity Analysis:
Time: O(n), Space: O(1) iterative, O(n) recursive (call stack)
Challenge 2: Find Longest Palindrome Substring
----------------------------------------------------------------------
Description:
Given a string, find the longest substring that reads the same forwards and
backwards.
Approach:
Expand around centers: For each character, expand outward while characters match.
Consider both odd-length (single center) and even-length (two centers) palindromes.
Complexity Analysis:
Time: O(n²), Space: O(1)
Challenge 3: Implement LRU Cache
----------------------------------------------------------------------
Description:
Design a Least Recently Used cache with O(1) get and put operations.
Approach:
Use a hash map for O(1) lookup and a doubly linked list to track recency.
Move accessed items to the front. Remove from tail when capacity exceeded.
Complexity Analysis:
Time: O(1) for both operations, Space: O(capacity)
Challenge 4: Detect Cycle in Directed Graph
----------------------------------------------------------------------
Description:
Determine if a directed graph contains a cycle.
Approach:
Use DFS with three states: unvisited, visiting, visited.
A cycle exists if we encounter a 'visiting' node during traversal.
Complexity Analysis:
Time: O(V + E), Space: O(V)
Challenge 5: Merge Sort Implementation
----------------------------------------------------------------------
Description:
Implement the merge sort algorithm for sorting an array.
Approach:
Divide array into halves recursively until single elements.
Merge sorted subarrays by comparing elements and maintaining order.
Complexity Analysis:
Time: O(n log n) worst/average/best, Space: O(n)
Challenge 6: Find All Anagrams in Text
----------------------------------------------------------------------
Description:
Given a text and a pattern, find all starting indices of anagrams of the pattern.
Approach:
Use sliding window with character frequency map.
Compare frequency maps for each window of pattern length.
Complexity Analysis:
Time: O(n), Space: O(1) - fixed alphabet size
Challenge 7: Design Rate Limiter
----------------------------------------------------------------------
Description:
Implement a token bucket rate limiter for API throttling.
Approach:
Track tokens available and last refill time.
Refill tokens based on elapsed time. Allow request if tokens available.
Complexity Analysis:
Time: O(1) per request, Space: O(users)
Challenge 8: Binary Search Tree Operations
----------------------------------------------------------------------
Description:
Implement insertion, deletion, and search in a BST.
Approach:
Search: Compare with current node, recurse left/right.
Insert: Find null position following BST property.
Delete: Handle three cases - leaf, one child, two children.
Complexity Analysis:
Time: O(log n) balanced, O(n) worst, Space: O(log n) recursion
Challenge 9: Find Median in Data Stream
----------------------------------------------------------------------
Description:
Design a data structure that supports adding numbers and finding median
efficiently.
Approach:
Use two heaps: max heap for lower half, min heap for upper half.
Balance heaps to maintain equal or differ by one. Median is top of larger heap.
Complexity Analysis:
Time: O(log n) add, O(1) find median, Space: O(n)
Challenge 10: Implement Trie (Prefix Tree)
----------------------------------------------------------------------
Description:
Build a trie data structure for efficient string searching and prefix matching.
Approach:
Each node contains children map and end-of-word flag.
Insert by creating nodes along path. Search by traversing path.
Complexity Analysis:
Time: O(m) insert/search where m is word length, Space: O(ALPHABET_SIZE * N)
Practice Tips
----------------------------------------------------------------------
1. Start with brute force solution, then optimize
2. Always analyze time and space complexity
3. Consider edge cases (empty input, single element, etc.)
4. Test with various inputs including worst-case scenarios
5. Practice explaining your solution clearly
6. Learn common patterns (sliding window, two pointers, etc.)
7. Review and learn from others' solutions