Top 100 coding questions in Python

I have shared basic to advanced-level interview questions and answers.

BASIC LEVEL (1-20)

1. Reverse a String

def reverse_string(s):
    return s[::-1]

# Test
print(reverse_string("hello"))  # "olleh"

2. Check if a string is a palindrome

def is_palindrome(s):
    s = s.lower().replace(" ", "")
    return s == s[::-1]

# Test
print(is_palindrome("A man a plan a canal Panama"))  # True

3. Find Factorial

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n-1)

# Test
print(factorial(5))  # 120

4. Fibonacci Sequence

def fibonacci(n):
    a, b = 0, 1
    result = []
    for _ in range(n):
        result.append(a)
        a, b = b, a + b
    return result

# Test
print(fibonacci(10))  # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

5. Check Prime Number

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

# Test
print(is_prime(17))  # True

6. Find Maximum in List

def find_max(lst):
    if not lst:
        return None
    max_val = lst[0]
    for num in lst:
        if num > max_val:
            max_val = num
    return max_val

# Test
print(find_max([3, 7, 2, 9, 1]))  # 9

7. Remove Duplicates from List

def remove_duplicates(lst):
    return list(set(lst))

# Test
print(remove_duplicates([1, 2, 2, 3, 4, 4, 5]))  # [1, 2, 3, 4, 5]

8. Count Character Frequency

from collections import Counter

def char_frequency(s):
    return dict(Counter(s))

# Test
print(char_frequency("hello"))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

9. Check Anagram

def is_anagram(s1, s2):
    return sorted(s1.lower()) == sorted(s2.lower())

# Test
print(is_anagram("listen", "silent"))  # True

10. Find Missing Number in Array

def find_missing(arr):
    n = len(arr) + 1
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(arr)
    return expected_sum - actual_sum

# Test
print(find_missing([1, 2, 3, 5]))  # 4

11. Find Second Largest Number

def second_largest(arr):
    unique_arr = list(set(arr))
    unique_arr.sort()
    return unique_arr[-2] if len(unique_arr) >= 2 else None

# Test
print(second_largest([10, 5, 8, 10, 7]))  # 8

12. Check Armstrong Number

def is_armstrong(n):
    digits = str(n)
    power = len(digits)
    return n == sum(int(d) ** power for d in digits)

# Test
print(is_armstrong(153))  # True (1³ + 5³ + 3³ = 153)

13. Sum of Digits

def sum_of_digits(n):
    return sum(int(d) for d in str(abs(n)))

# Test
print(sum_of_digits(1234))  # 10

14. Find GCD

import math

def find_gcd(a, b):
    return math.gcd(a, b)

# Alternative without math
def find_gcd_manual(a, b):
    while b:
        a, b = b, a % b
    return a

# Test
print(find_gcd(48, 18))  # 6

15. Find LCM

def find_lcm(a, b):
    return abs(a * b) // math.gcd(a, b)

# Test
print(find_lcm(4, 6))  # 12

16. Count Vowels in String

def count_vowels(s):
    vowels = set('aeiouAEIOU')
    return sum(1 for char in s if char in vowels)

# Test
print(count_vowels("Hello World"))  # 3

17. Check if String Contains Only Digits

def is_digit_string(s):
    return s.isdigit()

# Test
print(is_digit_string("12345"))  # True
print(is_digit_string("12a45"))  # False

18. Find Intersection of Two Lists

def intersection(lst1, lst2):
    return list(set(lst1) & set(lst2))

# Test
print(intersection([1, 2, 3, 4], [3, 4, 5, 6]))  # [3, 4]

19. Find Union of Two Lists

def union(lst1, lst2):
    return list(set(lst1) | set(lst2))

# Test
print(union([1, 2, 3], [3, 4, 5]))  # [1, 2, 3, 4, 5]

20. Check Balanced Parentheses

def is_balanced(s):
    stack = []
    brackets = {'(': ')', '{': '}', '[': ']'}

    for char in s:
        if char in brackets:
            stack.append(char)
        elif char in brackets.values():
            if not stack or brackets[stack.pop()] != char:
                return False
    return len(stack) == 0

# Test
print(is_balanced("({[]})"))  # True
print(is_balanced("({[})"))   # False

INTERMEDIATE LEVEL (21-60)

21. Two Sum Problem

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Test
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

22. Find Duplicates in Array

def find_duplicates(arr):
    seen = set()
    duplicates = set()
    for num in arr:
        if num in seen:
            duplicates.add(num)
        else:
            seen.add(num)
    return list(duplicates)

# Test
print(find_duplicates([1, 2, 3, 2, 4, 5, 3]))  # [2, 3]

23. Move Zeros to End

def move_zeros(nums):
    non_zero = [num for num in nums if num != 0]
    return non_zero + [0] * (len(nums) - len(non_zero))

# In-place version
def move_zeros_inplace(nums):
    pos = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[pos], nums[i] = nums[i], nums[pos]
            pos += 1
    return nums

# Test
print(move_zeros([0, 1, 0, 3, 12]))  # [1, 3, 12, 0, 0]

24. Rotate Array

def rotate_array(nums, k):
    k = k % len(nums)
    return nums[-k:] + nums[:-k]

# Test
print(rotate_array([1, 2, 3, 4, 5, 6, 7], 3))  # [5, 6, 7, 1, 2, 3, 4]

25. Find Majority Element

def majority_element(nums):
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1

    # Verify if candidate is majority
    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return None

# Test
print(majority_element([3, 2, 3]))  # 3

26. Binary Search

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Test
print(binary_search([1, 2, 3, 4, 5, 6], 4))  # 3

27. Merge Sorted Arrays

def merge_sorted(arr1, arr2):
    i, j = 0, 0
    merged = []

    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1

    merged.extend(arr1[i:])
    merged.extend(arr2[j:])
    return merged

# Test
print(merge_sorted([1, 3, 5], [2, 4, 6]))  # [1, 2, 3, 4, 5, 6]

28. First Non-Repeating Character

from collections import OrderedDict

def first_non_repeating(s):
    char_count = OrderedDict()

    for char in s:
        char_count[char] = char_count.get(char, 0) + 1

    for char, count in char_count.items():
        if count == 1:
            return char
    return None

# Test
print(first_non_repeating("swiss"))  # 'w'

29. Implement Stack using List

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

30. Implement Queue using List

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

31. Reverse Linked List

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list(head):
    prev = None
    current = head

    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp

    return prev

32. Detect Cycle in Linked List

def has_cycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

33. Find Middle of Linked List

def find_middle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

34. Implement Binary Tree

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

class BinaryTree:
    def inorder_traversal(self, root):
        result = []
        self._inorder(root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)

35. Tree Traversals

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

def level_order(root):
    if not root:
        return []

    result, queue = [], [root]
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

36. Maximum Depth of Binary Tree

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

37. Validate Binary Search Tree

def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True

    if not (min_val < root.val < max_val):
        return False

    return (is_valid_bst(root.left, min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

38. Find All Permutations

def permutations(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return

        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return result

# Test
print(permutations([1, 2, 3]))  # [[1,2,3], [1,3,2], [2,1,3], ...]

39. Find All Subsets

def subsets(nums):
    result = [[]]

    for num in nums:
        result += [subset + [num] for subset in result]

    return result

# Test
print(subsets([1, 2, 3]))  # [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

40. Longest Substring Without Repeating Characters

def length_of_longest_substring(s):
    char_set = set()
    left = 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

# Test
print(length_of_longest_substring("abcabcbb"))  # 3

41. Container With Most Water

def max_area(height):
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

# Test
print(max_area([1,8,6,2,5,4,8,3,7]))  # 49

42. 3Sum Problem

def three_sum(nums):
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue

        left, right = i + 1, len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result

# Test
print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2], [-1,0,1]]

43. Merge Intervals

def merge_intervals(intervals):
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for current in intervals[1:]:
        prev = merged[-1]
        if current[0] <= prev[1]:
            prev[1] = max(prev[1], current[1])
        else:
            merged.append(current)

    return merged

# Test
print(merge_intervals([[1,3], [2,6], [8,10], [15,18]]))  # [[1,6], [8,10], [15,18]]

44. Find Peak Element

def find_peak_element(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1

    return left

# Test
print(find_peak_element([1,2,3,1]))  # 2

45. Search in Rotated Sorted Array

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

# Test
print(search_rotated([4,5,6,7,0,1,2], 0))  # 4

46. Word Break Problem

def word_break(s, word_dict):
    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)]

# Test
print(word_break("leetcode", ["leet", "code"]))  # True

47. Longest Palindromic Substring

def longest_palindrome(s):
    if not s:
        return ""

    start, max_len = 0, 1

    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    for i in range(len(s)):
        # Odd length
        l1, r1 = expand_around_center(i, i)
        # Even length
        l2, r2 = expand_around_center(i, i + 1)

        if r1 - l1 + 1 > max_len:
            start, max_len = l1, r1 - l1 + 1
        if r2 - l2 + 1 > max_len:
            start, max_len = l2, r2 - l2 + 1

    return s[start:start + max_len]

# Test
print(longest_palindrome("babad"))  # "bab" or "aba"

48. Implement LRU Cache

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

49. Find Kth Largest Element

import heapq

def find_kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]

# Alternative using quickselect
def find_kth_largest_quickselect(nums, k):
    k = len(nums) - k

    def quickselect(left, right):
        pivot = nums[right]
        p = left

        for i in range(left, right):
            if nums[i] <= pivot:
                nums[p], nums[i] = nums[i], nums[p]
                p += 1

        nums[p], nums[right] = nums[right], nums[p]

        if p < k:
            return quickselect(p + 1, right)
        elif p > k:
            return quickselect(left, p - 1)
        else:
            return nums[p]

    return quickselect(0, len(nums) - 1)

# Test
print(find_kth_largest([3,2,1,5,6,4], 2))  # 5

50. Top K Frequent Elements

from collections import Counter
import heapq

def top_k_frequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

# Alternative
def top_k_frequent_bucket(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]

    for num, freq in count.items():
        buckets[freq].append(num)

    result = []
    for i in range(len(buckets) - 1, 0, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]

    return result

# Test
print(top_k_frequent([1,1,1,2,2,3], 2))  # [1,2]

ADVANCED LEVEL (51-80)

51. Serialize and Deserialize Binary Tree

class Codec:
    def serialize(self, root):
        def dfs(node):
            if not node:
                result.append("null")
                return
            result.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        result = []
        dfs(root)
        return ",".join(result)

    def deserialize(self, data):
        def dfs():
            val = next(vals)
            if val == "null":
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        vals = iter(data.split(","))
        return dfs()

52. Find Median from Data Stream

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max heap (store negatives)
        self.large = []  # min heap

    def add_num(self, num):
        heapq.heappush(self.small, -num)

        if (self.small and self.large and 
            -self.small[0] > self.large[0]):
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)

        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        elif len(self.large) > len(self.small) + 1:
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)

    def find_median(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        elif len(self.large) > len(self.small):
            return self.large[0]
        else:
            return (-self.small[0] + self.large[0]) / 2.0

53. Regular Expression Matching

def is_match(s, p):
    memo = {}

    def dp(i, j):
        if (i, j) in memo:
            return memo[(i, j)]

        if j == len(p):
            return i == len(s)

        first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')

        if j + 1 < len(p) and p[j + 1] == '*':
            ans = (dp(i, j + 2) or 
                   (first_match and dp(i + 1, j)))
        else:
            ans = first_match and dp(i + 1, j + 1)

        memo[(i, j)] = ans
        return ans

    return dp(0, 0)

# Test
print(is_match("aa", "a*"))  # True

54. Wildcard Matching

def is_match_wildcard(s, p):
    s_len, p_len = len(s), len(p)
    dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]
    dp[0][0] = True

    for j in range(1, p_len + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]

    for i in range(1, s_len + 1):
        for j in range(1, p_len + 1):
            if p[j-1] == '*':
                dp[i][j] = dp[i-1][j] or dp[i][j-1]
            elif p[j-1] == '?' or s[i-1] == p[j-1]:
                dp[i][j] = dp[i-1][j-1]

    return dp[s_len][p_len]

55. Edit Distance

def min_edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j],    # delete
                                   dp[i][j-1],    # insert
                                   dp[i-1][j-1])  # replace

    return dp[m][n]

# Test
print(min_edit_distance("horse", "ros"))  # 3

56. Coin Change Problem

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# Test
print(coin_change([1, 2, 5], 11))  # 3 (5+5+1)

57. Longest Increasing Subsequence

def length_of_lis(nums):
    dp = [1] * len(nums)

    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp) if dp else 0

# O(n log n) solution
def length_of_lis_optimized(nums):
    import bisect
    tails = []

    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return len(tails)

# Test
print(length_of_lis([10,9,2,5,3,7,101,18]))  # 4

58. Maximum Subarray Sum (Kadane’s Algorithm)

def max_subarray_sum(nums):
    max_current = max_global = nums[0]

    for i in range(1, len(nums)):
        max_current = max(nums[i], max_current + nums[i])
        max_global = max(max_global, max_current)

    return max_global

# Test
print(max_subarray_sum([-2,1,-3,4,-1,2,1,-5,4]))  # 6

59. House Robber

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[-1]

# Test
print(rob([1,2,3,1]))  # 4

60. Climbing Stairs

def climb_stairs(n):
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

# Test
print(climb_stairs(5))  # 8

61. Unique Paths

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

# Test
print(unique_paths(3, 7))  # 28

62. Decode Ways

def num_decodings(s):
    if not s or s[0] == '0':
        return 0

    dp = [0] * (len(s) + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, len(s) + 1):
        one_digit = int(s[i-1:i])
        two_digits = int(s[i-2:i])

        if 1 <= one_digit <= 9:
            dp[i] += dp[i-1]
        if 10 <= two_digits <= 26:
            dp[i] += dp[i-2]

    return dp[-1]

# Test
print(num_decodings("12"))  # 2 (AB or L)

63. Word Search

def exist(board, word):
    def dfs(i, j, k):
        if k == len(word):
            return True
        if (i < 0 or i >= len(board) or 
            j < 0 or j >= len(board[0]) or 
            board[i][j] != word[k]):
            return False

        temp = board[i][j]
        board[i][j] = '#'

        found = (dfs(i+1, j, k+1) or
                dfs(i-1, j, k+1) or
                dfs(i, j+1, k+1) or
                dfs(i, j-1, k+1))

        board[i][j] = temp
        return found

    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(i, j, 0):
                return True
    return False

# Test
board = [['A','B','C','E'],
         ['S','F','C','S'],
         ['A','D','E','E']]
print(exist(board, "ABCCED"))  # True

64. Number of Islands

def num_islands(grid):
    if not grid:
        return 0

    def dfs(i, j):
        if (i < 0 or i >= len(grid) or 
            j < 0 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

# Test
grid = [
    ['1','1','1','1','0'],
    ['1','1','0','1','0'],
    ['1','1','0','0','0'],
    ['0','0','0','0','0']
]
print(num_islands(grid))  # 1

65. Course Schedule (Cycle Detection)

def can_finish(num_courses, prerequisites):
    from collections import defaultdict

    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    visited = [0] * num_courses  # 0=unvisited, 1=visiting, 2=visited

    def has_cycle(course):
        if visited[course] == 1:
            return True
        if visited[course] == 2:
            return False

        visited[course] = 1

        for neighbor in graph[course]:
            if has_cycle(neighbor):
                return True

        visited[course] = 2
        return False

    for course in range(num_courses):
        if has_cycle(course):
            return False

    return True

# Test
print(can_finish(2, [[1,0]]))  # True

66. Minimum Window Substring

from collections import Counter

def min_window(s, t):
    if not s or not t:
        return ""

    dict_t = Counter(t)
    required = len(dict_t)

    left = right = 0
    formed = 0
    window_counts = {}

    ans = float("inf"), None, None

    while right < len(s):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1

        if char in dict_t and window_counts[char] == dict_t[char]:
            formed += 1

        while left <= right and formed == required:
            char = s[left]

            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)

            window_counts[char] -= 1
            if char in dict_t and window_counts[char] < dict_t[char]:
                formed -= 1

            left += 1

        right += 1

    return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]

# Test
print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"

67. Sliding Window Maximum

from collections import deque

def max_sliding_window(nums, k):
    if not nums:
        return []

    result = []
    dq = deque()

    for i in range(len(nums)):
        # Remove elements out of window
        while dq and dq[0] <= i - k:
            dq.popleft()

        # Remove smaller elements
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Test
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]

68. Trapping Rain Water

def trap(height):
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0

    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water

# Test
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # 6

69. Largest Rectangle in Histogram

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    heights.pop()
    return max_area

# Test
print(largest_rectangle_area([2,1,5,6,2,3]))  # 10

70. Merge K Sorted Lists

import heapq

def merge_k_lists(lists):
    heap = []

    # Push first element from each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, list_idx, element_idx = heapq.heappop(heap)
        result.append(val)

        if element_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][element_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, element_idx + 1))

    return result

# Test
lists = [[1,4,5], [1,3,4], [2,6]]
print(merge_k_lists(lists))  # [1,1,2,3,4,4,5,6]

71. Sort Colors (Dutch National Flag)

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

# Test
nums = [2,0,2,1,1,0]
sort_colors(nums)
print(nums)  # [0,0,1,1,2,2]

72. Find First and Last Position

def search_range(nums, target):
    def find_left():
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    def find_right():
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right

    left_idx = find_left()
    right_idx = find_right()

    if left_idx <= right_idx:
        return [left_idx, right_idx]
    return [-1, -1]

# Test
print(search_range([5,7,7,8,8,10], 8))  # [3,4]

73. Spiral Matrix

def spiral_order(matrix):
    if not matrix:
        return []

    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        # Top row
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1

        # Right column
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        if top <= bottom:
            # Bottom row
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1

        if left <= right:
            # Left column
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1

    return result

# Test
matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(spiral_order(matrix))  # [1,2,3,6,9,8,7,4,5]

74. Set Matrix Zeros

def set_zeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))

    # Mark zeros
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    # Set zeros
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0

    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

# Test
matrix = [[1,1,1],[1,0,1],[1,1,1]]
set_zeroes(matrix)
print(matrix)  # [[1,0,1],[0,0,0],[1,0,1]]

75. Valid Sudoku

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for i in range(9):
        for j in range(9):
            val = board[i][j]
            if val == '.':
                continue

            box_idx = (i // 3) * 3 + (j // 3)

            if (val in rows[i] or 
                val in cols[j] or 
                val in boxes[box_idx]):
                return False

            rows[i].add(val)
            cols[j].add(val)
            boxes[box_idx].add(val)

    return True

# Test
board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
print(is_valid_sudoku(board))  # True

76. N-Queens Problem

def solve_n_queens(n):
    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False

        # Check diagonal (top-left)
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1

        # Check diagonal (top-right)
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1

        return True

    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return

        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'

    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0)
    return result

# Test
print(len(solve_n_queens(4)))  # 2 solutions for 4x4

77. Sudoku Solver

def solve_sudoku(board):
    def is_valid(row, col, num):
        # Check row
        for j in range(9):
            if board[row][j] == num:
                return False

        # Check column
        for i in range(9):
            if board[i][col] == num:
                return False

        # Check box
        box_row, box_col = (row // 3) * 3, (col // 3) * 3
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False

        return True

    def solve():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(i, j, num):
                            board[i][j] = num
                            if solve():
                                return True
                            board[i][j] = '.'
                    return False
        return True

    solve()
    return board

78. Evaluate Reverse Polish Notation

def eval_rpn(tokens):
    stack = []
    operators = {'+', '-', '*', '/'}

    for token in tokens:
        if token not in operators:
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()

            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            else:  # division
                stack.append(int(a / b))

    return stack[0]

# Test
print(eval_rPN(["2","1","+","3","*"]))  # 9

79. Implement Trie (Prefix Tree)

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        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):
        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):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

80. Design Twitter

from collections import defaultdict
import heapq

class Twitter:
    def __init__(self):
        self.tweets = defaultdict(list)  # user_id -> [(timestamp, tweet_id)]
        self.follows = defaultdict(set)  # user_id -> set of followee_ids
        self.timestamp = 0

    def post_tweet(self, user_id, tweet_id):
        self.tweets[user_id].append((self.timestamp, tweet_id))
        self.timestamp += 1

    def get_news_feed(self, user_id):
        # Get all tweets from user and followees
        all_tweets = []
        users = self.follows[user_id] | {user_id}

        for user in users:
            all_tweets.extend(self.tweets[user])

        # Get 10 most recent
        return [tweet_id for _, tweet_id in sorted(all_tweets, reverse=True)[:10]]

    def follow(self, follower_id, followee_id):
        if follower_id != followee_id:
            self.follows[follower_id].add(followee_id)

    def unfollow(self, follower_id, followee_id):
        self.follows[follower_id].discard(followee_id)

ADVANCED ALGORITHMS & DATA STRUCTURES (81-100)

81. LFU Cache

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.key_to_val = {}
        self.key_to_freq = {}
        self.freq_to_keys = defaultdict(OrderedDict)
        self.min_freq = 0

    def get(self, key):
        if key not in self.key_to_val:
            return -1

        freq = self.key_to_freq[key]
        self.key_to_freq[key] = freq + 1
        del self.freq_to_keys[freq][key]
        self.freq_to_keys[freq + 1][key] = None

        if len(self.freq_to_keys[freq]) == 0:
            del self.freq_to_keys[freq]
            if self.min_freq == freq:
                self.min_freq += 1

        return self.key_to_val[key]

    def put(self, key, value):
        if self.capacity <= 0:
            return

        if key in self.key_to_val:
            self.key_to_val[key] = value
            self.get(key)
            return

        if len(self.key_to_val) >= self.capacity:
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.key_to_val[evict_key]
            del self.key_to_freq[evict_key]

        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.min_freq = 1

82. Find Median in Two Sorted Arrays

def find_median_sorted_arrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    total = m + n
    half = total // 2

    left, right = 0, m

    while left <= right:
        i = (left + right) // 2
        j = half - i

        if i < m and nums2[j-1] > nums1[i]:
            left = i + 1
        elif i > 0 and nums1[i-1] > nums2[j]:
            right = i - 1
        else:
            # Found correct partition
            if i == 0:
                max_left = nums2[j-1]
            elif j == 0:
                max_left = nums1[i-1]
            else:
                max_left = max(nums1[i-1], nums2[j-1])

            if total % 2 == 1:
                return min(nums1[i] if i < m else float('inf'),
                          nums2[j] if j < n else float('inf'))

            if i == m:
                min_right = nums2[j]
            elif j == n:
                min_right = nums1[i]
            else:
                min_right = min(nums1[i], nums2[j])

            return (max_left + min_right) / 2.0

    return 0.0

# Test
print(find_median_sorted_arrays([1,3], [2]))  # 2.0

83. Longest Consecutive Sequence

def longest_consecutive(nums):
    num_set = set(nums)
    longest = 0

    for num in num_set:
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            longest = max(longest, current_streak)

    return longest

# Test
print(longest_consecutive([100,4,200,1,3,2]))  # 4

84. Alien Dictionary

from collections import defaultdict, deque

def alien_order(words):
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    # Build graph
    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i+1]
        min_len = min(len(word1), len(word2))

        # Check for invalid case
        if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
            return ""

        for j in range(min_len):
            if word1[j] != word2[j]:
                if word2[j] not in graph[word1[j]]:
                    graph[word1[j]].add(word2[j])
                break

    # Calculate in-degree
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    # Topological sort
    queue = deque([c for c in in_degree if in_degree[c] == 0])
    result = []

    while queue:
        char = queue.popleft()
        result.append(char)

        for neighbor in graph[char]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(in_degree):
        return ""

    return ''.join(result)

# Test
print(alien_order(["wrt","wrf","er","ett","rftt"]))  # "wertf"

85. Minimum Path Sum

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])

    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
    for j in range(1, n):
        grid[0][j] += grid[0][j-1]

    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])

    return grid[m-1][n-1]

# Test
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid))  # 7

86. Palindrome Partitioning

def partition_palindrome(s):
    def is_palindrome(sub):
        return sub == sub[::-1]

    def backtrack(start, path):
        if start == len(s):
            result.append(path[:])
            return

        for end in range(start + 1, len(s) + 1):
            if is_palindrome(s[start:end]):
                path.append(s[start:end])
                backtrack(end, path)
                path.pop()

    result = []
    backtrack(0, [])
    return result

# Test
print(partition_palindrome("aab"))  # [["a","a","b"],["aa","b"]]

87. Reconstruct Itinerary

from collections import defaultdict

def find_itinerary(tickets):
    graph = defaultdict(list)

    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)

    result = []

    def dfs(airport):
        while graph[airport]:
            dfs(graph[airport].pop())
        result.append(airport)

    dfs("JFK")
    return result[::-1]

# Test
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
print(find_itinerary(tickets))  # ["JFK","MUC","LHR","SFO","SJC"]

88. Minimum Height Trees

from collections import defaultdict, deque

def find_min_height_trees(n, edges):
    if n == 1:
        return [0]

    graph = defaultdict(set)
    for u, v in edges:
        graph[u].add(v)
        graph[v].add(u)

    leaves = deque([node for node in range(n) if len(graph[node]) == 1])

    remaining_nodes = n
    while remaining_nodes > 2:
        leaf_count = len(leaves)
        remaining_nodes -= leaf_count

        for _ in range(leaf_count):
            leaf = leaves.popleft()
            neighbor = graph[leaf].pop()
            graph[neighbor].remove(leaf)
            if len(graph[neighbor]) == 1:
                leaves.append(neighbor)

    return list(leaves)

# Test
print(find_min_height_trees(4, [[1,0],[1,2],[1,3]]))  # [1]

89. Word Ladder

from collections import deque

def ladder_length(begin_word, end_word, word_list):
    word_set = set(word_list)
    if end_word not in word_set:
        return 0

    queue = deque([(begin_word, 1)])

    while queue:
        word, length = queue.popleft()

        if word == end_word:
            return length

        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word in word_set:
                    word_set.remove(next_word)
                    queue.append((next_word, length + 1))

    return 0

# Test
begin = "hit"
end = "cog"
word_list = ["hot","dot","dog","lot","log","cog"]
print(ladder_length(begin, end, word_list))  # 5

90. Count of Smaller Numbers After Self

def count_smaller(nums):
    def merge_sort(arr):
        mid = len(arr) // 2
        if mid:
            left = merge_sort(arr[:mid])
            right = merge_sort(arr[mid:])

            i = j = 0
            for i in range(len(arr)):
                if j == len(right) or (i < len(left) and left[i][1] <= right[j][1]):
                    arr[i] = left[i]
                    i += 1
                else:
                    arr[i] = right[j]
                    result[arr[i][0]] += len(left) - i
                    j += 1
            return arr
        return arr

    result = [0] * len(nums)
    merge_sort(list(enumerate(nums)))
    return result

# Test
print(count_smaller([5,2,6,1]))  # [2,1,1,0]

91. Maximal Rectangle

def maximal_rectangle(matrix):
    if not matrix:
        return 0

    def largest_rectangle(heights):
        stack = []
        max_area = 0
        heights.append(0)

        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] > h:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        heights.pop()
        return max_area

    heights = [0] * len(matrix[0])
    max_area = 0

    for row in matrix:
        for i, val in enumerate(row):
            heights[i] = heights[i] + 1 if val == '1' else 0
        max_area = max(max_area, largest_rectangle(heights))

    return max_area

# Test
matrix = [["1","0","1","0","0"],
          ["1","0","1","1","1"],
          ["1","1","1","1","1"],
          ["1","0","0","1","0"]]
print(maximal_rectangle(matrix))  # 6

92. Burst Balloons

def max_coins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for k in range(left + 1, right):
                dp[left][right] = max(dp[left][right],
                                      dp[left][k] + dp[k][right] +
                                      nums[left] * nums[k] * nums[right])

    return dp[0][n-1]

# Test
print(max_coins([3,1,5,8]))  # 167

93. Serialize and Deserialize N-ary Tree

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class Codec:
    def serialize(self, root):
        if not root:
            return ""

        result = [str(root.val)]
        for child in root.children:
            result.append(self.serialize(child))
        result.append("#")
        return ",".join(result)

    def deserialize(self, data):
        if not data:
            return None

        def helper():
            val = next(vals)
            if val == "#":
                return None

            node = Node(int(val))
            while True:
                child = helper()
                if child is None:
                    break
                node.children.append(child)
            return node

        vals = iter(data.split(","))
        return helper()

94. Flatten Nested List Iterator

class NestedIterator:
    def __init__(self, nested_list):
        self.stack = []
        self._flatten(nested_list)

    def _flatten(self, nested_list):
        for item in reversed(nested_list):
            if item.isInteger():
                self.stack.append(item.getInteger())
            else:
                self._flatten(item.getList())

    def next(self):
        return self.stack.pop()

    def has_next(self):
        return bool(self.stack)

95. Max Points on a Line

from collections import defaultdict

def max_points(points):
    if len(points) <= 2:
        return len(points)

    def get_slope(p1, p2):
        if p1[0] == p2[0]:
            return float('inf')
        return (p2[1] - p1[1]) / (p2[0] - p1[0])

    max_count = 0

    for i in range(len(points)):
        slopes = defaultdict(int)
        same = 0
        vertical = 0

        for j in range(i + 1, len(points)):
            if points[i] == points[j]:
                same += 1
            else:
                slope = get_slope(points[i], points[j])
                slopes[slope] += 1

        if slopes:
            max_count = max(max_count, max(slopes.values()) + same + 1)
        else:
            max_count = max(max_count, same + 1)

    return max_count

# Test
points = [[1,1],[2,2],[3,3]]
print(max_points(points))  # 3

96. Word Search II

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Solution:
    def find_words(self, board, words):
        # Build Trie
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word

        result = []

        def dfs(i, j, node):
            if node.word:
                result.append(node.word)
                node.word = None

            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
                return

            char = board[i][j]
            if char not in node.children:
                return

            board[i][j] = '#'
            for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]:
                dfs(i + di, j + dj, node.children[char])
            board[i][j] = char

        for i in range(len(board)):
            for j in range(len(board[0])):
                dfs(i, j, root)

        return result

# Test
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
print(Solution().find_words(board, words))  # ["oath","eat"]

97. Candy Crush (1D)

def candy_crush(s):
    stack = []

    for char in s:
        if stack and stack[-1][0] == char:
            stack[-1][1] += 1
            if stack[-1][1] >= 3:
                stack.pop()
        else:
            stack.append([char, 1])

    return ''.join(char * count for char, count in stack)

# Test
print(candy_crush("aaabbbc"))  # "c"
print(candy_crush("aabbbacd"))  # "cd"

98. Employee Free Time

def employee_free_time(schedule):
    intervals = []
    for employee in schedule:
        for interval in employee:
            intervals.append(interval)

    intervals.sort()
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    result = []
    for i in range(1, len(merged)):
        result.append([merged[i-1][1], merged[i][0]])

    return result

# Test
schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]
print(employee_free_time(schedule))  # [[3,4]]

99. Race Car

from collections import deque

def racecar(target):
    queue = deque([(0, 1, 0)])  # (position, speed, steps)
    visited = set([(0, 1)])

    while queue:
        pos, speed, steps = queue.popleft()

        if pos == target:
            return steps

        # Accelerate
        next_pos = pos + speed
        next_speed = speed * 2
        if (next_pos, next_speed) not in visited:
            visited.add((next_pos, next_speed))
            queue.append((next_pos, next_speed, steps + 1))

        # Reverse
        next_speed = -1 if speed > 0 else 1
        if (pos, next_speed) not in visited:
            visited.add((pos, next_speed))
            queue.append((pos, next_speed, steps + 1))

    return -1

# Test
print(racecar(3))  # 2

100. Swim in Rising Water

import heapq

def swim_in_water(grid):
    n = len(grid)
    visited = [[False] * n for _ in range(n)]
    heap = [(grid[0][0], 0, 0)]
    visited[0][0] = True

    directions = [(0,1),(1,0),(0,-1),(-1,0)]

    while heap:
        time, i, j = heapq.heappop(heap)

        if i == n-1 and j == n-1:
            return time

        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < n and not visited[ni][nj]:
                visited[ni][nj] = True
                heapq.heappush(heap, (max(time, grid[ni][nj]), ni, nj))

    return -1

# Test
grid = [[0,2],[1,3]]
print(swim_in_water(grid))  # 3