Recursion and Sorting Algorithms

2022-03-26 715 words 4 minutes

Contents

Recursion

function calls itself.
Boil down a big problem to smaller ones.
Implementation:
- Base case: smallest problem to solve.
- Subproblem: smaller size of the pre-problem. (when we have the result of the subproblem, the what you need to do to solve the pre-problem based on subproblem)
- Recursive rule: how to make the problem smaller. (if we can solve the problem but with a smaller size, then what is left to do for the current problem size)

Fibonacci

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public class Solution {
  public int fibonacci(int K) {
    // Write your solution here
    if (K <= 0) {
      return 0;
    } else if (K == 1) {
      return 1;
    }

    return fibonacci(K - 1) + fibonacci(K - 2);
  }
}

How to analyze time and space complexity

Time Complexity: The sum of time complexity of all nodes in the recursive tree.
Space Complexity: The sum of space complexity of all nodes on a path from top to bottom.
Space Complexity = heap memory + stack memory
Call Stack: it is a global accessible resource that can tell what happened before each break point in each level.

a to the power of b

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18



public class Solution {
  public long power(int a, int b) {
    // Write your solution here
    if (b == 0) {
      return 1;
    }

    long halfRes = power(a, b/2);

    if (b % 2 == 0) {
      return halfRes * halfRes;
    } else {
      return a * halfRes * halfRes;
    }
  }
}

Sorting Algorithm

Code Explanation Tips

Document your assumption.
Explain your approach and how you intend to solve the problem.
Provide code comments where applicable
Explain the big-O run time complexity of your solution, justify your answer.
Identify any additional data structures you used, and justify why you used them.
Only provide your best answer to each part of the question.
When explaining an algorithm you wrote, you should explain in a modular step, like what is a code block doing.

Selection Sort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public class Solution {
  public int[] solve(int[] array) {
    // Write your solution here
    for (int i = 0; i < array.length - 1; i++) {
      int tempMin = i;
      for (int j = i + 1; j < array.length; j++) {
		if (array[j] < array[tempMin]) {
          tempMin = j;
        }
      }
      int temp = array[i];
      array[i] = array[tempMin];
      array[tempMin] = temp;
    }

    return array;
  }
}

Merge Sort

how to merge two arrays

We get the smaller one stored first and then move this one’s index, and then repeat this process.

Also, we need a temporary space to buffer the result. like if the array size is 8, then the temporary space size is 8 (int[] space = new int[8];)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


/**
 * method 1
 */

public class Solution {
  public int[] mergeSort(int[] array) {
    // Write your solution here
    if (array == null || array.length <= 1) {
      return array;
    }

    return merge(array, 0, array.length - 1);
  }

  private int[] merge(int[] array, int left, int right) {
    if (left == right) {
      return new int[]{array[left]};
    }

    int mid = left + (right - left) / 2;    
    int[] leftRes = merge(array, left, mid);
    int[] rightRes = merge(array, mid + 1, right);

    return mergeHelper(leftRes, rightRes);
  }

  private int[] mergeHelper(int[] leftRes, int[] rightRes) {
    int left = 0;
    int right = 0;
    int l = leftRes.length;
    int r = rightRes.length;
    int[] result = new int[l + r];

    int i = 0;
    while (left < l && right < r) {
      if (leftRes[left] < rightRes[right]) {
        result[i++] = leftRes[left++];
      } else {
        result[i++] = rightRes[right++];
      }
    }

    while (left < l) {
      result[i++] = leftRes[left++];
    }
    while (right < r) {
      result[i++] = rightRes[right++];
    }

    return result;
  }
}