Algorithms Cheat Sheet

May 25th, 2023

#interviews

In Place Sort

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
// sort an array in place in DESC order
const sortDesc = (arr) => {
  let min = 0;
  let max = arr.length - 1;
  while (min <= max) {
    let first = arr[min];
    let last = arr[max];
    // ascending order
    if (first < last) {
      arr[min] = last;
      arr[max] = first;
      max--;
    } else if (last < first) {
      max--;
    } else if (min === max) {
      min++;
      max = arr.length - 1;
    } else {
      min++;
      last--;
    }
  }
};

sortDesc([1, 2, 3, 4]);
// ==> [4, 3, 2, 1]

Find Target in Sorted Array (Binary Search)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function firstNotSmaller(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let rtrn = -1;
  while (left <= right) {
    let mid = Math.trunc((right + left) / 2);
    if (arr[mid] >= target) {
      rtrn = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return rtrn;
}

firstNotSmaller([1, 2, 3, 4], 4);
// => 3