Algorithm and data structure
  • Algorithm and data structure
  • Break Away: Programming And Coding Interviews & Cracking coding interview
    • System design and scalability
    • Performance and Complexity
    • Big O Notation
    • Sorting trade-off
    • Selection sort
    • Bubble sort
    • Insertion sort
    • Shell sort
    • Merge sort
    • Quick sort
    • Binary search
    • Recursion
    • Binary tree
    • Breadth First Traversal
    • Depth First Pre-Order
    • Binary search tree
    • Stack
    • Queue
    • Linked list
    • Doubly linked list
    • String
    • Pointer and array
    • Bit manipulation
    • General programming problems
    • Priority queue
    • Balanced binary search tree
    • Binary heap
    • Heap sort
    • Graphs
    • Topological sort
  • Leetcode
    • 1. Two Sum
    • 2. Add Two Numbers
    • 3. Longest Substring Without Repeating Characters
    • 4. Median of Two Sorted Arrays
    • 5. Longest Palindromic Substring
    • 6.ZigZag Conversion
    • 7. Reverse Integer
    • 8. String to Integer (atoi)
    • 9. Palindrome Number
    • 11. Container With Most Water
    • 12. Integer to Roman
    • 13. Roman to Integer
    • 14. Longest Common Prefix
    • 15. 3Sum
    • 16. 3Sum Closest
    • 17. Letter Combinations of a Phone Number
    • 18. 4Sum
    • 19. Remove Nth Node From End of List
    • 20. Valid Parentheses
    • 21. Merge Two Sorted Lists
    • 22. Generate Parentheses
    • 23. Merge k Sorted Lists
    • 24. Swap Nodes in Pairs
    • 25. Reverse Nodes in k-Group
    • 26. Remove Duplicates from Sorted Array
    • 27. Remove Element
    • 28. Implement strStr()
    • 29. Divide Two Integers
    • 30. Substring with Concatenation of All Words
    • 31. Next Permutation
    • 32. Longest Valid Parentheses
    • 33. Search in Rotated Sorted Array
    • 34. Find First and Last Position of Element in Sorted Array
    • 35. Search Insert Position (Easy)
    • 36. Valid Sudoku
    • 37. Sudoku Solver
    • 38. Count and Say
    • 39. Combination Sum
    • 40. Combination Sum II
    • 41. First Missing Positive
    • 43. Multiply Strings
    • 45. Jump Game II
    • 46. Permutations (Medium)
    • 47. Permutations II (Medium)
    • 48. Rotate Image
    • 49. Group Anagrams
    • 50. Pow(x, n)
    • 51. N-Queens
    • 52. N-Queens II
    • 53. Maximum Subarray
    • 54. Spiral Matrix
    • 55. Jump Game
    • 56. Merge Intervals
    • 57. Insert Interval
    • 58. Length of Last Word
    • 59. Spiral Matrix II
    • 61. Rotate List
    • 62. Unique Paths
    • 63. Unique Paths II
    • 64. Minimum Path Sum
    • 66. Plus One
    • 67. Add Binary
    • 69. Sqrt(x)
    • 70. Climbing Stairs
    • 73. Set Matrix Zeroes
    • 74. Search a 2D Matrix
    • 75. Sort Colors
    • 76. Minimum Window Substring
    • 77. Combinations
    • 78. Subsets
    • 79. Word Search
    • 80. Remove Duplicates from Sorted Array II
    • 81. Search in Rotated Sorted Array II
    • 82. Remove Duplicates from Sorted List II
    • 83. Remove Duplicates from Sorted List
    • 84. Largest Rectangle in Histogram
    • 86. Partition List
    • 88. Merge Sorted Array
    • 89. Gray Code
    • 90. Subsets II
    • 92. Reverse Linked List II
    • 94. Binary Tree Inorder Traversal (Medium)
    • 95. Unique Binary Search Trees II
    • 96. Unique Binary Search Trees
    • 98. Validate Binary Search Tree
    • 100. Same Tree (Easy)
    • 101. Symmetric Tree
    • 102. Binary Tree Level Order Traversal
    • 103. Binary Tree Zigzag Level Order Traversal
    • 104. Maximum Depth of Binary Tree
    • 105. Construct Binary Tree from Preorder and Inorder Traversal
    • 106. Construct Binary Tree from Inorder and Postorder Traversal
    • 107. Binary Tree Level Order Traversal II (Easy)
    • 108. Convert Sorted Array to Binary Search Tree
    • 109. Convert Sorted List to Binary Search Tree
    • 110. Balanced Binary Tree
    • 111. Minimum Depth of Binary Tree
    • 112. Path Sum
    • 113. Path Sum II
    • 114. Flatten Binary Tree to Linked List
    • 116. Populating Next Right Pointers in Each Node
    • 117. Populating Next Right Pointers in Each Node IIㄟˋ大
    • 118. Pascal's Triangle
    • 119. Pascal's Triangle II
    • 120. Triangle
    • 121. Best Time to Buy and Sell Stock
    • 122. Best Time to Buy and Sell Stock II
    • 123. Best Time to Buy and Sell Stock III
    • 125. Valid Palindrome
    • 654. Maximum Binary Tree
    • 127. Word Ladder
    • 129. Sum Root to Leaf Numbers
    • 130. Surrounded Regions (Medium)
    • 131. Palindrome Partitioning
    • 133. Clone Graph
    • 134. Gas Station
    • 136. Single Number
    • 137. Single Number II
    • 138. Copy List with Random Pointer
    • 139. Word Break
    • 141. Linked List Cycle
    • 143. Reorder List
    • 144. Binary Tree Preorder Traversal
    • 145. Binary Tree Postorder Traversal
    • 147. Insertion Sort List
    • 148. Sort List
    • 151. Reverse Words in a String
    • 152. Maximum Product Subarray
    • 153. Find Minimum in Rotated Sorted Array
    • 154. Find Minimum in Rotated Sorted Array II
    • 155. Min Stack
    • 160. Intersection of Two Linked Lists
    • 164. Maximum Gap
    • 169. Majority Element (Easy)
    • 173. Binary Search Tree Iterator
    • 174. Dungeon Game (Hard)
    • 189. Rotate Array
    • 198. House Robber (Easy)
    • 199. Binary Tree Right Side View (Medium)
    • 203. Remove Linked List Elements
    • 206. Reverse Linked List
    • 213. House Robber II (Medium)
    • 215. Kth Largest Element in an Array (Medium)
    • 222. Count Complete Tree Nodes
    • 226. Invert Binary Tree
    • 230. Kth Smallest Element in a BST
    • 232. Implement Queue using Stacks
    • 234. Palindrome Linked List (Easy)
    • 235. Lowest Common Ancestor of a Binary Search Tree
    • 236. Lowest Common Ancestor of a Binary Tree
    • 237. Delete Node in a Linked List
    • 240. Search a 2D Matrix II
    • 242. Valid Anagram
    • 257. Binary Tree Paths
    • 283. Move Zeroes
    • 337. House Robber III (Medium)
    • 347. Top K Frequent Elements
    • 349. Intersection of Two Arrays
    • 409. Longest Palindrome (Easy)
    • 437. Path Sum III
    • 442. Find All Duplicates in an Array
    • 449. Serialize and Deserialize BST
    • 450. Delete Node in a BST
    • 543. Diameter of Binary Tree
    • 572. Subtree of Another Tree
    • 653. Two Sum IV - Input is a BST
    • 654. Maximum Binary Tree
    • 700. Search in a Binary Search Tree
    • 701. Insert into a Binary Search Tree
    • 783. Minimum Distance Between BST Nodes
    • 876.Middle of the Linked List
    • 942. DI String Match
  • Notes of algorithms
    • Binary Tree traversal
    • 廣度優先搜尋 (Breadth-first Search)
    • Divide and Conquer
    • Linked list: Insert Node
    • Dynamic programming
    • 深度優先搜尋 (Depth-first Search)
    • Lowest Common Ancestor (LCA)
    • Asymptotic notation
    • Binary search tree
    • AVL Tree (Height Balanced BST)
    • Linked list: Split the list
    • Linked list: Traverse the list
    • Linked list: Delete node
    • Heap sort
    • Cartesian tree
  • C++
Powered by GitBook
On this page
  • 1.How to approach?
  • 2. What is the best case?
  • 3. What is the recursive case?
  • 4. Examples
  • 1. Binary search
  • 2.Find all subsets of a set (take Θ (2^n) time )
  • 4.Same binary tree (take Θ (n) time )
  • binary tree
  • Algorithm
  • Code
  • 5.Implement the paintfill feature from MS paint
  • Base case
  • Recursive case
  • 6.Build a car given all tasks and each task's dependencies
  • Base case
  • Recursive case
  • Complexity
  • 7.Find all anagrams of a given word
  • 8.Find a path a rat can travel
  • Base case
  • Recursive case
  • 9.Place 8 queens on a chessboard so they don't kill each other
  • Rule
  • Tips
  • Base case
  • Recursive case
  • Implementation
  • Complexity
  1. Break Away: Programming And Coding Interviews & Cracking coding interview

Recursion

1.How to approach?

  • Recursive solutions are built of solutions to subproblem

  • Three most common approach:

Bottom-Up Approach

  • Most intuitive

  • We start with how to solve the problem for a simple case then we figure out how to solve the problem for more components and so on. (先解決一個, 再處理下一個)

Top-Down Approach

  • Divid the problem for case N into subproblems (將問題分為許多子問題)

Half-and-Half Approach

  • We first figure out which half of the array contains the value

  • e.g., Binary search

Dynamic Programming & Memoization

  • Taking a recursive algorithm and finding the overlapping subproblems

  • Cache the result for future recursive calls

  • e.g., Fibonacci numbers

Typical solution

  • 複雜度: O(N^2) (O(branches ^ depth))

int fibonacci(int i) {
    if (i == 0) {
        return 0;
    }
    if (i == 1) {
        return 1;
    }
    return fibonacci(i - 1) + fibonacci(i - 2)  
}

Top-Down Dynamic Programming (or Memorization)

int fibonacci(int i) {
    return fibonacci(i, new int[n + 1]);  
}

int fibonacci(int i, int[] memo) {
    if (i == 0 || i == 1) {
        return i;
    }
    
    if (memo[i] == 0) {
        memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    }
    return fibonacci(i - 1) + fibonacci(i - 2)  
}

Bottom-Up Programming

int fibonacci(int i) {
    return fibonacci(i, new int[n + 1]);  
}

int fibonacci(int i, int[] memo) {
    if (i == 0 || i == 1) {
        return i;
    }
    memo[0] = 0;
    memo[1] = 1;
    for (int n = 2; n < i; n++) {
        memo[i] = memo[i - 2] + memo[i - 1];
    }
    return memo[i - 1] + memo[i - 2] 
}

2. What is the best case?

  1. There is no part of the list to search and the element has not been found

  2. The search element has been found st the mid point of the portion we're searching

3. What is the recursive case?

  • Binary search smaller portions of the list where the element might be found

4. Examples

1. Binary search

2.Find all subsets of a set (take Θ (2^n) time )

  • 1. What is the best case?

    • When the original set is empty, only the empty set is it's subset

  • 2. What is the recursive case?

    • Add the elements to the existing subsets to create new subsets

public static void populateSubsets(List<List<Integar>> subsetList, List<INtegar> numberList) {
    //Recursion base case, the empty superset has just one subset, the empty set
    if (numberList.isEpty()) {
        subsetList.add(new ArrayList<>());
        return;
    }
    //Remove the first number from the original set and find the subsets of the remaining numbers
    int currentNum =  numberList.get(0);
    numberList.remove(0);
    
    populateSubsets(subsetList, numberList);
    List<List<Integar>> iteratingList = ArrayList<>();
    iteratingList.addll(subsetList);
    for (List<Integar> subset : iteratingList) {
        List<Integar> newSubset = ArrayList<>();
        newSubset.addAll(subset);
        newSubset.add(currentNum);
        subsetList.add(newSubset);
    }
}

4.Same binary tree (take Θ (n) time )

binary tree

  • A binary tree is one where every node can have a maximum of two children - a left child and right child

  • Two binary trees are the same if :

    • Every corresponding node has the same value

    • The structure of the tree at every corresponding node is the same

Algorithm

  • 1. What is the best case?

    • 1.A null current node on one tree should correspond to a null in the other tree

    • 2.Node values should be the same at every one

  • 2. What is the recursive case?

    • Check that the subtree rooted at every node is the same

Code

  • Node class

public static class Node {
    private int id;
    private Node left;
    private Node right;
    
    public Node(int id) {
        thi.id = id;
    }
    
    public int getId() {
        return id;
    }
    
    public Node getLeft() {
        return left;
    }
    
    public Node getRight() {
        return right;
    }
    
    public void addChildren(Node left, Node right) {
        this.left = left;
        this.right = right;
    }
}
  • same tree

public static boolean sameTree(Node head1, Node head2) {
    if (head1 == null && head2 == null) {
        returnn true;
    }
    if (head1 == null) {
        returnn false;
    } else if (head1 == null) {
        returnn false;
    }
    
    if (sameTree(head1.getLeft(), head2.getLeft()) &&
        sameTree(head1.getRight(), head2.getRight())) {
        return head1.getId() == head2.getId();  
    }
    return false;
}

5.Implement the paintfill feature from MS paint

  • Start with one pixel which has some original color

  • Move outwards, if the neighboring pixels have the same original color, color them as well

  • Repeat until the borders are reached

  • Complexity: O(N)

Base case

  • 當目前的pixel沒有相同的顏色時

  • 當目前的pixel位置超出螢幕範圍時

Recursive case

  • Move outward from the start pixel coloring individual pixels

public static void paintfill(pixel[][] displayScreen, 
         int x, int y, String originalColor, String newColor) {
    //base case
    if (x < 0 || y <0 || 
        x > displayScreen[0].length() || y > displayScreen.length()) {
        return;
    }
    
    if (displayScreen[y][x].getColor() != originalColor) {
        return;
    }
    
    //recursive case
    if (displayScreen[y][x].getColor() == originalColor) {
        displayScreen[y][x].setColor(newColor);
        paintfill(displayScreen, x + 1, y, originalColor, newColor);
        paintfill(displayScreen, x - 1, y, originalColor, newColor);
        paintfill(displayScreen, x, y + 1, originalColor, newColor);
        paintfill(displayScreen, x, y - 1, originalColor, newColor);
    }
}

6.Build a car given all tasks and each task's dependencies

  • Say that all the tasks needed to build the car: A, B, C, D, E, F, G, H

    • B depends on A

    • D depends on E

    • C depends on A, B, D

    • F depends on C

  • An acceptable order of performing the tasks are:

    • E -> D -> A -> B -> C -> F

    • A -> E -> B -> D -> C -> F

  • The tasks and it's dependencies form a directed acyclic graph

  • The graph may not be fully connected

Base case

  • The current task has been executed, it's marked done.

Recursive case

  • Execute dependencies before coming to the current task

Complexity

  • O(N)

public static void buildCar(List<Task> taskList) {
    for (Task task : taskList) {
        task.execute();
    }
}

public static class Task {
    private String id;
    private List<Task> dependencyList;
    private boolean done;
    
    public Task(String id, Task...dependencyArray) {
        this.id = id;
        dependencyList = new ArrayList<Task>();
        for (Task task : dependencyArray) {
            dependencyList.add(task);
        }
    } 
    
    public void execute() {
        if (done) {
            return; 
        }
        for (Task task : dependencyArray) {
            task.execute();
        }
        runTask();
    }
    
    private runTask() {
        //perform some operations
        done = true;
    }
}

7.Find all anagrams of a given word

8.Find a path a rat can travel

Base case

  • The rat has reached the end cell.

Recursive case

  • Keep visiting cells by passing through doors when they exist

  • Do not visit cells if they are present in the current path, we don't want the rat to move in circles

public class Cell {
}

public static boolean findPath(Cell current, List<Cell> currentPath) {
    currentPath.add(current);
    if (current.isEnd()) {
        return true;
    }
    
    for (Cell neighbor : current.getNeighbotList()) {
        if (!currentPath.contain(neighbor)) {
            List<Cell> neighborPath = new ArrayList<>();
            neighborPath.addAll(currentPath);
            
            if (findPath(neighbor, neighborPath)) {
                currentPath.clear();
                currentPath.addAll(neighborPath);
                return true;
            }
        }
    }
    return false;
}

9.Place 8 queens on a chessboard so they don't kill each other

Rule

  • Remember the queens can move along their rows, columns and along diagonals

  • Place one queen at a time, one on each row or one on each column

Tips

  • Place a queen in each row or column in a safe position

  • See if the remaining queens can be placed safely with the current position of the queen

  • Recursively do this till the right positions for all queens have been found

Base case

  • The queens have been all placed and we're beyond the boundary of the chessboard

Recursive case

  • Keep placing queens in different positions of the same row or column

  • Check whether the remaining queens can be successfully placed

Implementation

Place the queens

public static boolean placQueen(int[][] chessboard, int col) {
    if (col >= N) {
        return true;
    }
    
    for (int row = 0; row < N; row++) {
        chessboard[row][col] = 1;
        if (!isSafe(chessboard, row, col)) {
            if (placeQueen(chessboard, col + 1)) {
                return true;
            }
        }
        chessboard[row][col] = 0;
    }
    
    return false;
}

Check if current queen position is safe

public static boolean isSafe(int[][] chessboard, int row, int col) {
    if (!isColumnSafe(chessboard, col)) {
        return false;
    }
    if (!isRowSafe(chessboard, row)) {
        return false;
    }
    if (!isLeftDiagonalSafe(chessboard, row, col)) {
        return false;
    }
    
    return isRightDiagonalSafe(chessboard, row, col);
}

Check the row and the column

public static boolean isColumnSafe(int[][] chessboard, int col) {
    int colSum = 0;
    for (int r = 0; r < N; r++) {
        colSum += chessboard[r][col];
    }
    return colSum == 1;
}

public static boolean isRowSafe(int[][] chessboard, int row) {
    int rowSum = 0;
    for (int c = 0; c < N; c++) {
        rowSum += chessboard[row][c];
    }
    return rowSum == 1;
}

Check the left diagonal

public static boolean isLeftDiagonal(int[][] chessboard, int row, int col) {
    int leftDiagSum = 0;
    int r = 0;
    int c = 0;
    if (row > col) {
        r = row - col;
    } else {
        c = col - row;
    }
    while (r < N && c < N) {
        leftDiagSum += chessboard[r++][c++];
    }
    
    return leftDiagSum == 1;
}

Check the right diagonal

public static boolean isRightDiagonal(int[][] chessboard, int row, int col) {
    int leftDiagSum = 0;
    int r = 0;
    int c = 7;
    if (row + col < N) {
        c = Math.min(col + row, N - 1);
    } else {
        r = (col + row) % (N - 1);
    }
    while (r < N && c >= 0 ) {
        rightDiagSum += chessboard[r++][c--];
    }
    
    return rightDiagSum == 1;
}

Complexity

  • O(N!)

PreviousBinary searchNextBinary tree

Last updated 6 years ago