Sorting Algos

Question 1

merge sort

Answer 1

function mergeArrs(arr1, arr2) {
let result = [];
let i = 0;
let j = 0;

while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
        result.push(arr1[i]);
        i++;
    }
    if (arr2[j] < arr1[i]) {
        result.push(arr2[j]);
        j++
    }
}
while (i < arr1.length) {
    result.push(arr1[i]);
    i++
}
while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
}
return result; }

Question 2

merge sort runtime

Answer 2

O(n*log n)

Question 3

insertion sort

Answer 3

function insertion(arr) {
  for (let i = 0; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

Question 4

insertion sort runtime

Answer 4

0(n*n)

Question 6

Pathfinding and Maze Solving

Answer 6

DFS

Question 7

Detecting Cycles in Graphs

Answer 7

DFS

Question 8

Connected Components in Graphs

Answer 8

DFS

Question 9

Topological Sorting (push to stack after visiting all dependencies)

Answer 9

DFS post-order

Question 10

Solving Puzzles and Backtracking

Answer 10

DFS, backtracks when it finds deadends

Question 11

Binary Tree Traversal

Answer 11

DFS

Question 12

Binary Tree Traversal: Preorder

Answer 12

DFS, process root first

Question 13

Binary Tree Traversal: inorder

Answer 13

DFS, process left subtree first

Question 14

Binary Tree Traversal: postorder

Answer 14

DFS, process root last

Question 15

Solving Island Problems in Grids

Answer 15

DFS, explore each island, traverse adjacent cells in multiple directions

Question 16

Generating All Possible Subsets or Combos

Answer 16

DFS - explore each subset by including or excluding each el in set

Question 17

Word Search in Grid

Answer 17

DFS explores each cell recursively to see if it can form word moving in all directions

Question 18

Tree/Graph Cloning

Answer 18

DFS traverses each node in graph, copying it and connections to make identical copy

Question 19

DFS - inorder

Answer 19

function inorder(root) {
let result = [];
function traverse(node) {
if (node) {
traverse(node.left);
result.push(node.value);
traverse(node.right)
}
}
traverse(root)
return result;
}

Question 20

DFS -preorder

Answer 20

function preorder(root) {
let result = [];
function traverse(node) {
if (node) {
result.push(node.value);
traverse(node.left);
traverse(node.right);
}
}
traverse(root)
return result;
}

Question 21

post order

Answer 21

function postorder(root) {
let result = [];
function traverse(node) {
if (node) {
traverse(node.left);
traverse(node.right);
result.push(node.value);
}
}
traverse(root)
return result;
}

Question 22

delete at position in linked list

Answer 22

function deletePosition(list, position) {
if (list === null) return null;
if (position === 1) {
return list.next;
}
let prev = list;
let curr = list.next;
let count = 2;
while (curr && count < position) {
prev = curr;
curr = curr.next;
count++;
}
prev.next = curr.next;
return list;
}

Question 23

delete head linked list

Answer 23

function deleteHead(list, node) {
if (list === null) return null;
list = list.next;
return list;
}

Question 24

delete tail linked list

Answer 24

function deleteNode(list) {
if (!list || list.next === null) return null;
let prev = list;
let curr = list.next;
while (curr.next) {
prev = curr;
curr = curr.next
}
prev.next = null;
return list;
}