Question 1: Compress string by counting consecutive characters.

Write a function that compresses a string using counts of consecutive characters.
If the compressed string is not shorter than the original, return the original string.

Example:
"aaabbc" → "a3b2c1"

Sample Inputs and Outputs

Example 1

Input:
s = "aabcccccaaa"

Output:
"a2b1c5a3"

Example 2

Input:
s = "abcd"

Output:
"abcd"
Explanation: Compressed string "a1b1c1d1" is longer than the original, so return the original.

C# Code

// C#
public static string CompressString(string s) {
    if (string.IsNullOrEmpty(s)) return s;
    
    StringBuilder compressed = new StringBuilder();
    int count = 1;
    
    for (int i = 1; i < s.Length; i++) {
        if (s[i] == s[i - 1]) {
            count++;
        } else {
            compressed.Append(s[i - 1]).Append(count);
            count = 1;
        }
    }
    compressed.Append(s[s.Length - 1]).Append(count);
    
    return compressed.Length < s.Length ? compressed.ToString() : s;
}

Java Code

// Java
public static String compressString(String s) {
    if (s.isEmpty()) return s;
    
    StringBuilder compressed = new StringBuilder();
    int count = 1;
    
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i - 1)) {
            count++;
        } else {
            compressed.append(s.charAt(i - 1)).append(count);
            count = 1;
        }
    }
    compressed.append(s.charAt(s.length() - 1)).append(count);
    
    return compressed.length() < s.length() ? compressed.toString() : s;
}

Python Code

# Python
def compress_string(s: str) -> str:
    if not s:
        return s
    
    compressed = []
    count = 1
    
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            count += 1
        else:
            compressed.append(s[i-1] + str(count))
            count = 1
    
    compressed.append(s[-1] + str(count))
    result = ''.join(compressed)
    
    return result if len(result) < len(s) else s

Question 2: Generate all permutations of a string.

Write a function that generates all possible permutations of a given string.
The function should return a list of strings containing all unique arrangements of the characters.

Sample Inputs and Outputs

Example 1

Input:
s = "abc"

Output (order may vary):
["abc", "acb", "bac", "bca", "cab", "cba"]

Example 2

Input:
s = "aa"

Output:
["aa"]

C# Code

// C#
public static List<string> GeneratePermutations(string s) {
    List<string> result = new List<string>();
    Backtrack(s.ToCharArray(), 0, result);
    return result;
}

private static void Backtrack(char[] chars, int start, List<string> result) {
    if (start == chars.Length) {
        result.Add(new string(chars));
        return;
    }
    
    for (int i = start; i < chars.Length; i++) {
        Swap(chars, start, i);
        Backtrack(chars, start + 1, result);
        Swap(chars, start, i);
    }
}

private static void Swap(char[] chars, int i, int j) {
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
}

Java Code

// Java
public static List<String> generatePermutations(String s) {
    List<String> result = new ArrayList<>();
    backtrack(s.toCharArray(), 0, result);
    return result;
}

private static void backtrack(char[] chars, int start, List<String> result) {
    if (start == chars.length) {
        result.add(new String(chars));
        return;
    }
    
    for (int i = start; i < chars.length; i++) {
        swap(chars, start, i);
        backtrack(chars, start + 1, result);
        swap(chars, start, i);
    }
}

private static void swap(char[] chars, int i, int j) {
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
}

Python Code

# Python
def generate_permutations(s: str) -> list:
    def backtrack(start):
        if start == len(chars):
            result.append(''.join(chars))
            return
        
        for i in range(start, len(chars)):
            chars[start], chars[i] = chars[i], chars[start]
            backtrack(start + 1)
            chars[start], chars[i] = chars[i], chars[start]
    
    result = []
    chars = list(s)
    backtrack(0)
    return result

Question 3: Implement Least Recently Used (LRU) cache.

Design a data structure that implements a Least Recently Used (LRU) cache.

It should support the following operations:

Get(key) – Returns the value of the key if it exists in the cache; otherwise, returns -1.
Put(key, value) – Inserts or updates the value of the key. If the cache exceeds its capacity, evict the least recently used item before inserting the new item.

Follow-up: Both operations should ideally run in O(1) time.

Sample Input and Output

Example 1

LRUCache cache = new LRUCache(2); // capacity = 2 cache.Put(1, 1); cache.Put(2, 2); cache.Get(1); // returns 1 cache.Put(3, 3); // evicts key 2 cache.Get(2); // returns -1 (not found) cache.Put(4, 4); // evicts key 1 cache.Get(1); // returns -1 (not found) cache.Get(3); // returns 3 cache.Get(4); // returns 4

Explanation

The cache has a capacity of 2.
When inserting a new element that exceeds the capacity, the least recently used element is removed.
Accessing a key updates it as the most recently used.

C# Code

// C#
public class LRUCache {
    class Node {
        public int Key, Value;
        public Node Prev, Next;
        public Node(int k, int v) { Key = k; Value = v; }
    }
    
    private Dictionary<int, Node> cache;
    private int capacity;
    private Node head, tail;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new Dictionary<int, Node>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.Next = tail;
        tail.Prev = head;
    }
    
    public int Get(int key) {
        if (!cache.ContainsKey(key)) return -1;
        
        Node node = cache[key];
        Remove(node);
        AddToFront(node);
        return node.Value;
    }
    
    public void Put(int key, int value) {
        if (cache.ContainsKey(key)) {
            Remove(cache[key]);
        }
        
        Node node = new Node(key, value);
        cache[key] = node;
        AddToFront(node);
        
        if (cache.Count > capacity) {
            Node lru = tail.Prev;
            Remove(lru);
            cache.Remove(lru.Key);
        }
    }
    
    private void AddToFront(Node node) {
        node.Next = head.Next;
        node.Prev = head;
        head.Next.Prev = node;
        head.Next = node;
    }
    
    private void Remove(Node node) {
        node.Prev.Next = node.Next;
        node.Next.Prev = node.Prev;
    }
}

Java Code

// Java
class LRUCache {
    class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }
    
    private Map<Integer, Node> cache;
    private int capacity;
    private Node head, tail;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        
        Node node = cache.get(key);
        remove(node);
        addToFront(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            remove(cache.get(key));
        }
        
        Node node = new Node(key, value);
        cache.put(key, node);
        addToFront(node);
        
        if (cache.size() > capacity) {
            Node lru = tail.prev;
            remove(lru);
            cache.remove(lru.key);
        }
    }
    
    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

Python Code

# Python
class LRUCache:
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = self.Node(0, 0)
        self.tail = self.Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.value
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        
        node = self.Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)
        
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
    
    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
    
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

Question 4: Find kth largest element in unsorted array.

Given an unsorted array of integers nums and an integer k, write a function to return the kth largest element in the array.

Note: The kth largest element is the element that would be in that position if the array were sorted in descending order.

Sample Inputs and Outputs

Example 1

Input:
nums = [3, 2, 1, 5, 6, 4]
k = 2

Output:
5

Explanation:
The sorted array in descending order is [6, 5, 4, 3, 2, 1]. The 2nd largest element is 5.

Example 2

Input:
nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]
k = 4

Output:
4

Explanation:
The 4th largest element in descending order [6, 5, 5, 4, 3, 3, 2, 2, 1] is 4.

C# Code

// C#
public static int FindKthLargest(int[] nums, int k) {
    PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();
    
    foreach (int num in nums) {
        minHeap.Enqueue(num, num);
        if (minHeap.Count > k) {
            minHeap.Dequeue();
        }
    }
    
    return minHeap.Peek();
}

// Alternative with SortedSet for C# 9 and below
public static int FindKthLargestAlternative(int[] nums, int k) {
    var minHeap = new SortedSet<int>();
    
    foreach (int num in nums) {
        minHeap.Add(num);
        if (minHeap.Count > k) {
            minHeap.Remove(minHeap.Min);
        }
    }
    
    return minHeap.Min;
}

Java Code

// Java
public static int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    return minHeap.peek();
}

Python Code

# Python
import heapq

def find_kth_largest(nums: list, k: int) -> int:
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]

Question 5: Check if binary tree is valid BST.

Given the root of a binary tree, determine if it is a valid Binary Search Tree (BST).

A valid BST satisfies the following conditions:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both left and right subtrees must also be BSTs.

Sample Inputs and Outputs

Example 1

Input:

2 / \ 1 3

Output:
true

Example 2

Input:

5 / \ 1 4 / \ 3 6

Output:
false

Explanation: Node 4 has a left child 3, which is not greater than 5 (the root), so it violates BST rules.

C# Code

// C#
public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; }
}

public static bool IsValidBST(TreeNode root) {
    return Validate(root, long.MinValue, long.MaxValue);
}

private static bool Validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    
    return Validate(node.left, min, node.val) && 
           Validate(node.right, node.val, max);
}

Java Code

// Java
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public static boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private static boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    
    return validate(node.left, min, node.val) && 
           validate(node.right, node.val, max);
}

Python Code

# Python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_valid_bst(root: TreeNode) -> bool:
    def validate(node, min_val, max_val):
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        return (validate(node.left, min_val, node.val) and 
                validate(node.right, node.val, max_val))
    
    return validate(root, float('-inf'), float('inf'))

Question 6: Check if string can be segmented into dictionary words.

Given a string s and a list of words wordDict, determine if s can be segmented into a sequence of one or more dictionary words.
Each word from the dictionary can be used multiple times.

Sample Inputs and Outputs

Example 1

Input:
s = "leetcode"
wordDict = ["leet", "code"]

Output:
true

Explanation:
s can be segmented as "leet code".

Example 2

Input:
s = "applepenapple"
wordDict = ["apple", "pen"]

Output:
true

Explanation:
s can be segmented as "apple pen apple".

C# Code

// C#
public static bool WordBreak(string s, IList<string> wordDict) {
    var wordSet = new HashSet<string>(wordDict);
    bool[] dp = new bool[s.Length + 1];
    dp[0] = true;
    
    for (int i = 1; i <= s.Length; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordSet.Contains(s.Substring(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    
    return dp[s.Length];
}

Java Code

// Java
public static boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordSet = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordSet.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    
    return dp[s.length()];
}

Python Code

# Python
def word_break(s: str, word_dict: list) -> bool:
    word_set = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[len(s)]

Question 7: Find k most frequent elements.

Given an integer array nums and an integer k, return the k most frequent elements.
You may return the answer in any order.

Sample Inputs and Outputs

Example 1

Input:
nums = [1, 1, 1, 2, 2, 3], k = 2

Output:
[1, 2]

Explanation: 1 appears 3 times, 2 appears 2 times.

Example 2

Input:
nums = [1], k = 1

Output:
[1]

Explanation: Only one element is present.

C# Code

// C#
public static int[] TopKFrequent(int[] nums, int k) {
    Dictionary<int, int> frequency = new Dictionary<int, int>();
    foreach (int num in nums) {
        if (frequency.ContainsKey(num)) frequency[num]++;
        else frequency[num] = 1;
    }
    
    PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();
    
    foreach (var entry in frequency) {
        minHeap.Enqueue(entry.Key, entry.Value);
        if (minHeap.Count > k) {
            minHeap.Dequeue();
        }
    }
    
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.Dequeue();
    }
    
    return result;
}

Java Code

// Java
public static int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> frequency = new HashMap<>();
    for (int num : nums) {
        frequency.put(num, frequency.getOrDefault(num, 0) + 1);
    }
    
    PriorityQueue<Map.Entry<Integer, Integer>> minHeap = 
        new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
    
    for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
        minHeap.offer(entry);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll().getKey();
    }
    
    return result;
}

Python Code

# Python
import heapq
from collections import Counter

def top_k_frequent(nums: list, k: int) -> list:
    frequency = Counter(nums)
    min_heap = []
    
    for num, freq in frequency.items():
        heapq.heappush(min_heap, (freq, num))
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    return [num for freq, num in min_heap]

Question 8: Find two lines that form container with most water.

You are given an array of non-negative integers, where each integer represents the height of a vertical line at that index.
Find two lines that, together with the x-axis, form a container that can hold the maximum amount of water.
Return the maximum area of water the container can store.

The area is calculated as:
area = min(height[i], height[j]) * (j - i)

Sample Inputs and Outputs

Example 1

Input:
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

Output:
49
Explanation: The container is formed by lines at index 1 and 8.

C# Code

// C#
public static int MaxArea(int[] height) {
    int left = 0, right = height.Length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int currentArea = Math.Min(height[left], height[right]) * (right - left);
        maxArea = Math.Max(maxArea, currentArea);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

Java Code

// Java
public static int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int currentArea = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

Python Code

# Python
def max_area(height: list) -> int:
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        current_area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, current_area)
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

Question 9: Return all elements of matrix in spiral order.

Given a 2D matrix, write a function that returns all its elements in spiral order, starting from the top-left element and moving clockwise.

Sample Inputs and Outputs

Example 1

Input:

matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]

Output:
[1, 2, 3, 6, 9, 8, 7, 4, 5]

Example 2

Input:

matrix = [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ]

Output:
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

C# Code

// C#
public static List<int> SpiralOrder(int[][] matrix) {
    List<int> result = new List<int>();
    if (matrix.Length == 0) return result;
    
    int top = 0, bottom = matrix.Length - 1;
    int left = 0, right = matrix[0].Length - 1;
    
    while (top <= bottom && left <= right) {
        // Right
        for (int i = left; i <= right; i++) {
            result.Add(matrix[top][i]);
        }
        top++;
        
        // Down
        for (int i = top; i <= bottom; i++) {
            result.Add(matrix[i][right]);
        }
        right--;
        
        // Left
        if (top <= bottom) {
            for (int i = right; i >= left; i--) {
                result.Add(matrix[bottom][i]);
            }
            bottom--;
        }
        
        // Up
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result.Add(matrix[i][left]);
            }
            left++;
        }
    }
    
    return result;
}

Java Code

// Java
public static List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix.length == 0) return result;
    
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        // Right
        for (int i = left; i <= right; i++) {
            result.add(matrix[top][i]);
        }
        top++;
        
        // Down
        for (int i = top; i <= bottom; i++) {
            result.add(matrix[i][right]);
        }
        right--;
        
        // Left
        if (top <= bottom) {
            for (int i = right; i >= left; i--) {
                result.add(matrix[bottom][i]);
            }
            bottom--;
        }
        
        // Up
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result.add(matrix[i][left]);
            }
            left++;
        }
    }
    
    return result;
}

Python Code

# Python
def spiral_order(matrix: list) -> list:
    if not matrix:
        return []
    
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    
    while top <= bottom and left <= right:
        # Right
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1
        
        # Down
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        
        # Left
        if top <= bottom:
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1
        
        # Up
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    
    return result

Question 10: Find minimum number of conference rooms required.

You are given an array of meeting time intervals where each interval is represented as [start, end].
Write a function to determine the minimum number of conference rooms required to hold all the meetings.

Sample Inputs and Outputs

Example 1

Input:
intervals = [[0, 30], [5, 10], [15, 20]]

Output:
2

Explanation:

Meeting [0, 30] overlaps with [5, 10] → 2 rooms needed.
[15, 20] can use a room freed by [5, 10].

Example 2

Input:
intervals = [[7, 10], [2, 4]]

Output:
1

Explanation:

No meetings overlap, so only 1 room is needed.

C# Code

// C#
public static int MinMeetingRooms(int[][] intervals) {
    if (intervals.Length == 0) return 0;
    
    int[] starts = new int[intervals.Length];
    int[] ends = new int[intervals.Length];
    
    for (int i = 0; i < intervals.Length; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }
    
    Array.Sort(starts);
    Array.Sort(ends);
    
    int rooms = 0, endPtr = 0;
    
    foreach (int start in starts) {
        if (start < ends[endPtr]) {
            rooms++;
        } else {
            endPtr++;
        }
    }
    
    return rooms;
}

Java Code

// Java
public static int minMeetingRooms(int[][] intervals) {
    if (intervals.length == 0) return 0;
    
    int[] starts = new int[intervals.length];
    int[] ends = new int[intervals.length];
    
    for (int i = 0; i < intervals.length; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }
    
    Arrays.sort(starts);
    Arrays.sort(ends);
    
    int rooms = 0, endPtr = 0;
    
    for (int start : starts) {
        if (start < ends[endPtr]) {
            rooms++;
        } else {
            endPtr++;
        }
    }
    
    return rooms;
}

Python Code

# Python
import heapq

def min_meeting_rooms(intervals: list) -> int:
    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[0])
    min_heap = []
    
    for interval in intervals:
        if min_heap and interval[0] >= min_heap[0]:
            heapq.heappop(min_heap)
        heapq.heappush(min_heap, interval[1])
    
    return len(min_heap)

Question 11: Find minimum coins needed to make amount.

You are given:

An integer array coins representing different coin denominations
An integer amount representing the total amount of money

Write a function to compute the minimum number of coins needed to make up that amount.
If it is not possible to make the amount, return -1.

You may assume you have an infinite supply of each coin.

Sample Inputs and Outputs

Example 1

Input:
coins = [1, 2, 5]
amount = 11

Output:
3

Explanation: 11 = 5 + 5 + 1

Example 2

Input:
coins = [2]
amount = 3

Output:
-1

Explanation: There is no way to make 3 with only 2-coin denominations.

C# Code

// C#
public static int CoinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Array.Fill(dp, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        foreach (int coin in coins) {
            if (coin <= i) {
                dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

Java Code

// Java
public static int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

Python Code

# Python
def coin_change(coins: list, amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

Question 12: Deep clone an undirected graph.

You are given a reference to a node in a connected undirected graph.
Each node contains a value and a list of its neighbors.

Write a function that returns a deep copy (clone) of the graph.
All nodes in the cloned graph should be new objects, and the structure should match the original graph.

Example

Example 1

Input:
A graph with nodes and edges:

1 -- 2 | | 4 -- 3

Output:
A new graph with the same connections, but all nodes are new instances (deep copy).

Example 2

Input:
A single node graph:

1

Output:
A new node with value 1 and no neighbors.

C# Code

// C#
public class Node {
    public int val;
    public IList<Node> neighbors;
    
    public Node(int _val) {
        val = _val;
        neighbors = new List<Node>();
    }
}

public static Node CloneGraph(Node node) {
    if (node == null) return null;
    
    Dictionary<Node, Node> visited = new Dictionary<Node, Node>();
    return DFS(node, visited);
}

private static Node DFS(Node node, Dictionary<Node, Node> visited) {
    if (visited.ContainsKey(node)) {
        return visited[node];
    }
    
    Node clone = new Node(node.val);
    visited[node] = clone;
    
    foreach (Node neighbor in node.neighbors) {
        clone.neighbors.Add(DFS(neighbor, visited));
    }
    
    return clone;
}

Java Code

// Java
class Node {
    public int val;
    public List<Node> neighbors;
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<>();
    }
}

public static Node cloneGraph(Node node) {
    if (node == null) return null;
    
    Map<Node, Node> visited = new HashMap<>();
    return dfs(node, visited);
}

private static Node dfs(Node node, Map<Node, Node> visited) {
    if (visited.containsKey(node)) {
        return visited.get(node);
    }
    
    Node clone = new Node(node.val);
    visited.put(node, clone);
    
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfs(neighbor, visited));
    }
    
    return clone;
}

Python Code

# Python
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node: 'Node') -> 'Node':
    if not node:
        return None
    
    visited = {}
    
    def dfs(original):
        if original in visited:
            return visited[original]
        
        clone = Node(original.val)
        visited[original] = clone
        
        for neighbor in original.neighbors:
            clone.neighbors.append(dfs(neighbor))
        
        return clone
    
    return dfs(node)

Question 13: Count number of islands in grid.

Given a 2D grid of '1's (land) and '0's (water), write a function to count the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Sample Inputs and Outputs

Example 1

Input:

grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]

Output:
3

Explanation:
There are three separate islands in the grid.

Example 2

Input:

grid = [ ['1','0','1','0'], ['0','1','0','1'], ['1','0','1','0'] ]

Output:
6

C# Code

// C#
public static int NumIslands(char[][] grid) {
    if (grid.Length == 0) return 0;
    
    int count = 0;
    for (int i = 0; i < grid.Length; i++) {
        for (int j = 0; j < grid[0].Length; j++) {
            if (grid[i][j] == '1') {
                count++;
                DFS(grid, i, j);
            }
        }
    }
    return count;
}

private static void DFS(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.Length || j >= grid[0].Length || grid[i][j] != '1') {
        return;
    }
    
    grid[i][j] = '0';
    
    DFS(grid, i + 1, j);
    DFS(grid, i - 1, j);
    DFS(grid, i, j + 1);
    DFS(grid, i, j - 1);
}

Java Code

// Java
public static int numIslands(char[][] grid) {
    if (grid.length == 0) return 0;
    
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

private static void dfs(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') {
        return;
    }
    
    grid[i][j] = '0'; // Mark as visited
    
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

Python Code

# Python
def num_islands(grid: list) -> int:
    if not grid:
        return 0
    
    def dfs(i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
            return
        
        grid[i][j] = '0'
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)
    
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    
    return count

Question 14: Generate all valid combinations of n pairs of parentheses.

Given an integer n, write a function to generate all combinations of well-formed parentheses consisting of n pairs.

A combination is well-formed if every opening parenthesis '(' has a corresponding closing parenthesis ')'.

Sample Inputs and Outputs

Example 1

Input:
n = 1

Output:
["()"]

Example 2

Input:
n = 2

Output:
["(())", "()()"]

C# Code

// C#
public static List<string> GenerateParenthesis(int n) {
    List<string> result = new List<string>();
    Backtrack(result, "", 0, 0, n);
    return result;
}

private static void Backtrack(List<string> result, string current, int open, int close, int max) {
    if (current.Length == max * 2) {
        result.Add(current);
        return;
    }
    
    if (open < max) {
        Backtrack(result, current + "(", open + 1, close, max);
    }
    if (close < open) {
        Backtrack(result, current + ")", open, close + 1, max);
    }
}

Java Code

// Java
public static List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(result, "", 0, 0, n);
    return result;
}

private static void backtrack(List<String> result, String current, int open, int close, int max) {
    if (current.length() == max * 2) {
        result.add(current);
        return;
    }
    
    if (open < max) {
        backtrack(result, current + "(", open + 1, close, max);
    }
    if (close < open) {
        backtrack(result, current + ")", open, close + 1, max);
    }
}

Python Code

# Python
def generate_parenthesis(n: int) -> list:
    def backtrack(current, open_count, close_count):
        if len(current) == n * 2:
            result.append(current)
            return
        
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)
    
    result = []
    backtrack('', 0, 0)
    return result

Question 15: Find length of longest substring without repeating characters.

Given a string s, find the length of the longest substring that contains no repeating characters.

📝 Sample Inputs and Outputs

Example 1

Input:
s = "abcabcbb"

Output:
3
Explanation: The longest substring without repeating characters is "abc".

Example 2

Input:
s = "bbbbb"

Output:
1
Explanation: The longest substring without repeating characters is "b".

C# Code

// C#
public static int LengthOfLongestSubstring(string s) {
    HashSet<char> set = new HashSet<char>();
    int left = 0, maxLength = 0;
    
    for (int right = 0; right < s.Length; right++) {
        while (set.Contains(s[right])) {
            set.Remove(s[left]);
            left++;
        }
        set.Add(s[right]);
        maxLength = Math.Max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

Java Code

// Java
public static int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, maxLength = 0;
    
    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(s.charAt(right));
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

Python Code

# Python
def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

Question 16: Merge overlapping intervals.

Given a collection of intervals, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sample Inputs and Outputs

Example 1

Input:
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output:
[[1,6],[8,10],[15,18]]

Explanation:
Intervals [1,3] and [2,6] overlap and are merged into [1,6].

Example 2

Input:
intervals = [[1,4],[4,5]]

Output:
[[1,5]]

Explanation:
Intervals [1,4] and [4,5] overlap at 4, so they are merged into [1,5].

C# Code

// C#
public static int[][] Merge(int[][] intervals) {
    if (intervals.Length <= 1) return intervals;
    
    Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
    
    List<int[]> merged = new List<int[]>();
    int[] current = intervals[0];
    merged.Add(current);
    
    foreach (int[] interval in intervals) {
        if (interval[0] <= current[1]) {
            current[1] = Math.Max(current[1], interval[1]);
        } else {
            current = interval;
            merged.Add(current);
        }
    }
    
    return merged.ToArray();
}

Java Code

// Java
public static int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    
    List<int[]> merged = new ArrayList<>();
    int[] current = intervals[0];
    merged.add(current);
    
    for (int[] interval : intervals) {
        if (interval[0] <= current[1]) {
            current[1] = Math.max(current[1], interval[1]);
        } else {
            current = interval;
            merged.add(current);
        }
    }
    
    return merged.toArray(new int[merged.size()][]);
}

Python Code

# Python
def merge_intervals(intervals: list) -> list:
    if len(intervals) <= 1:
        return intervals
    
    intervals.sort(key=lambda x: x[0])
    merged = []
    current = intervals[0]
    
    for interval in intervals:
        if interval[0] <= current[1]:
            current[1] = max(current[1], interval[1])
        else:
            merged.append(current)
            current = interval
    
    merged.append(current)
    return merged

Question 17: Calculate how much water can be trapped between bars.

Given an array of non-negative integers representing the height of bars, calculate how much water can be trapped after raining.

Each element represents a bar of width 1. Water can be trapped between taller bars.

Sample Inputs and Outputs

Example 1

Input:
height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:
6

Explanation:
Water is trapped in the valleys between the bars, totaling 6 units.

Example 2

Input:
height = [4,2,0,3,2,5]

Output:
9

C# Code

// C#
public static int Trap(int[] height) {
    if (height.Length == 0) return 0;
    
    int left = 0, right = height.Length - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    
    return water;
}

Java Code

// Java
public static int trap(int[] height) {
    if (height.length == 0) return 0;
    
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    
    return water;
}

Python Code

# Python
def trap(height: list) -> int:
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max = right_max = water = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    
    return water

Question 18: Design class to find median from data stream.

Design a class MedianFinder that supports adding numbers from a data stream and finding the median efficiently at any time.

The class should implement the following methods:

AddNum(int num) — Adds an integer number to the data structure.
FindMedian() — Returns the median of all elements added so far.

Notes:

The median is the middle value in an ordered integer list.
If the size of the list is even, the median is the average of the two middle numbers.

Sample Inputs and Outputs

Example 1

Input:

MedianFinder mf = new MedianFinder(); mf.AddNum(1); mf.AddNum(2); mf.FindMedian();

Output:
1.5

C# Code

// C#
public class MedianFinder {
    private PriorityQueue<int, int> maxHeap;
    private PriorityQueue<int, int> minHeap;
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        minHeap = new PriorityQueue<int, int>();
    }
    
    public void AddNum(int num) {
        maxHeap.Enqueue(num, num);
        minHeap.Enqueue(maxHeap.Dequeue(), maxHeap.Count > 0 ? maxHeap.Peek() : num);
        
        if (maxHeap.Count < minHeap.Count) {
            maxHeap.Enqueue(minHeap.Dequeue(), minHeap.Count > 0 ? minHeap.Peek() : num);
        }
    }
    
    public double FindMedian() {
        if (maxHeap.Count > minHeap.Count) {
            return maxHeap.Peek();
        } else {
            return (maxHeap.Peek() + minHeap.Peek()) / 2.0;
        }
    }
}

Java Code

// Java
class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // lower half
    private PriorityQueue<Integer> minHeap; // upper half
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
        
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}

Python Code

# Python
import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # lower half (negative values for max heap)
        self.min_heap = []  # upper half
    
    def add_num(self, num: int) -> None:
        heapq.heappush(self.max_heap, -num)
        heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        
        if len(self.max_heap) < len(self.min_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
    
    def find_median(self) -> float:
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        else:
            return (-self.max_heap[0] + self.min_heap[0]) / 2

Question 19: Check if courses can be finished (no cycles in directed graph).

You are given:

An integer numCourses representing the total number of courses (labeled from 0 to numCourses - 1).
An array prerequisites where each element [a, b] means you must complete course b before course a.

Write a function that returns true if you can finish all courses.
Return false if it is impossible (i.e., there is a cycle in the prerequisites).

Sample Inputs and Outputs

Example 1

Input:
numCourses = 2
prerequisites = [[1,0]]

Output:
true

Explanation:
You can take course 0 first, then course 1.

C# Code

// C#
public static bool CanFinish(int numCourses, int[][] prerequisites) {
    List<List<int>> graph = new List<List<int>>();
    for (int i = 0; i < numCourses; i++) {
        graph.Add(new List<int>());
    }
    
    int[] indegree = new int[numCourses];
    foreach (int[] pre in prerequisites) {
        graph[pre[1]].Add(pre[0]);
        indegree[pre[0]]++;
    }
    
    Queue<int> queue = new Queue<int>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.Enqueue(i);
        }
    }
    
    int count = 0;
    while (queue.Count > 0) {
        int course = queue.Dequeue();
        count++;
        foreach (int neighbor in graph[course]) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                queue.Enqueue(neighbor);
            }
        }
    }
    
    return count == numCourses;
}

Java Code

// Java
public static boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    
    int[] indegree = new int[numCourses];
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
        indegree[pre[0]]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int neighbor : graph.get(course)) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }
    
    return count == numCourses;
}

Python Code

# Python
from collections import deque

def can_finish(num_courses: int, prerequisites: list) -> bool:
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    
    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1
    
    queue = deque()
    for i in range(num_courses):
        if indegree[i] == 0:
            queue.append(i)
    
    count = 0
    while queue:
        course = queue.popleft()
        count += 1
        for neighbor in graph[course]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    
    return count == num_courses

Question 20: Implement trie data structure.

Implement a Trie (also called a prefix tree) with the following methods:

Insert(string word) – Inserts a word into the trie.
Search(string word) – Returns true if the word exists in the trie.
StartsWith(string prefix) – Returns true if there is any word in the trie that starts with the given prefix.

All words consist of lowercase English letters (a–z).

Sample Inputs and Outputs

Example 1

Insert("apple") Search("apple") → true Search("app") → false StartsWith("app") → true Insert("app") Search("app") → true

Example 2

Insert("hello") Search("hell") → false StartsWith("hell") → true Search("hello") → true

C# Code

// C#
public class Trie {
    class TrieNode {
        public TrieNode[] Children;
        public bool IsEnd;
        
        public TrieNode() {
            Children = new TrieNode[26];
            IsEnd = false;
        }
    }
    
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void Insert(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            int index = c - 'a';
            if (node.Children[index] == null) {
                node.Children[index] = new TrieNode();
            }
            node = node.Children[index];
        }
        node.IsEnd = true;
    }
    
    public bool Search(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            int index = c - 'a';
            if (node.Children[index] == null) return false;
            node = node.Children[index];
        }
        return node.IsEnd;
    }
    
    public bool StartsWith(string prefix) {
        TrieNode node = root;
        foreach (char c in prefix) {
            int index = c - 'a';
            if (node.Children[index] == null) return false;
            node = node.Children[index];
        }
        return true;
    }
}

Java Code

// Java
class Trie {
    class TrieNode {
        TrieNode[] children;
        boolean isEnd;
        
        TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }
    
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) return false;
            node = node.children[index];
        }
        return node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) return false;
            node = node.children[index];
        }
        return true;
    }
}

Python Code

# Python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    
    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

JAVA BASIC

JAVA ADVANCED

JAVA QUIZ

JAVA INTERVIEW QUESTION

Java Topic

Live Coding Interview Questions (21 to 40)

Question 1: Compress string by counting consecutive characters.

Sample Inputs and Outputs

Example 1

Example 2

Question 2: Generate all permutations of a string.

Sample Inputs and Outputs

Example 1

Example 2

Question 3: Implement Least Recently Used (LRU) cache.

Sample Input and Output

Example 1

Explanation

Question 4: Find kth largest element in unsorted array.

Sample Inputs and Outputs

Example 1

Example 2

Question 5: Check if binary tree is valid BST.

Sample Inputs and Outputs

Example 1

Example 2

Question 6: Check if string can be segmented into dictionary words.

Sample Inputs and Outputs

Example 1

Example 2

Question 7: Find k most frequent elements.

Sample Inputs and Outputs

Example 1

Example 2

Question 8: Find two lines that form container with most water.

Sample Inputs and Outputs

Example 1

Question 9: Return all elements of matrix in spiral order.

Sample Inputs and Outputs

Example 1

Example 2

Question 10: Find minimum number of conference rooms required.

Sample Inputs and Outputs

Example 1

Example 2

Question 11: Find minimum coins needed to make amount.

Sample Inputs and Outputs

Example 1

Example 2

Question 12: Deep clone an undirected graph.

Example

Example 1

Example 2

Question 13: Count number of islands in grid.

Sample Inputs and Outputs

Example 1

Example 2

Question 14: Generate all valid combinations of n pairs of parentheses.

Sample Inputs and Outputs

Example 1

Example 2

Question 15: Find length of longest substring without repeating characters.

📝 Sample Inputs and Outputs

Example 1

Example 2

Question 16: Merge overlapping intervals.

Sample Inputs and Outputs

Example 1

Example 2

Question 17: Calculate how much water can be trapped between bars.

Sample Inputs and Outputs

Example 1

Example 2

Question 18: Design class to find median from data stream.

Sample Inputs and Outputs

Example 1

Question 19: Check if courses can be finished (no cycles in directed graph).

Sample Inputs and Outputs

Example 1

Question 20: Implement trie data structure.