Data Structure/Algos

Question 1

BST Insert/Add

Answer 1

// if insert/add at head need node** head
if val < head.val;
if left is null then add, else go left;
elif val > head.val;
if right is null then add, else go right;
else
error // already exists

Question 2

BST remove/delete

Answer 2

// algorithm must stay at parent and check ahead for value

1. hang right child on parents child node
2. hang left child on right childs far left node

Question 3

BST find_min

Answer 3

recursively left until left is null, return head->val;

Question 4

BST find

Answer 4

if (val == head->val)
  return head;
elif (val < head->val)
  go left
elif (val > head->val)
  go right

Question 5

BST preorder visit

Answer 5

preorder()
visit();
preorder(left);
preorder(right);

Question 6

BST inorder visit

Answer 6

inorder()
inorder(left);
visit();
inorder(right);

Question 7

BST postorder visit

Answer 7

postorder()
postorder(left);
postorder(right);
visit();

Question 8

BST find_next

Answer 8

// if right child of node is NOT null then its far left child is the next. Simple.
// otherwise if the node is a right child there is NO next.
// otherwise if the node is a left child its parent is next.
if (node->right != NULL)
return FindMin(node->right);
else
FindNext_();

void FindNext_(T val, struct BstNode** next, struct BstNode* head)
        {
                if (head == NULL || head->val == val)
                        return;
                if (head->val > val)
                {
                        *next = head;
                        FindNext_(val, next, head->left);
                }
                else if (head->val < val)
                {
                        //could still be a left child and parent is the next, but may have to traverse right
                        //to eventually get there
                        FindNext_(val, next, head->right);
                }
        }

Question 9

quicksort()

Answer 9

quicksort(*array, low, high)
  if (low < high)
    pivot = partition(array,low,high)
    quicksort(array,low,pivot-1)
    quicksort(array,pivot+1,high)

Question 10

quicksort::partition()

Answer 10

partition(*array, low, high)
  pivot = array[low]
  small = low
  for(i,low+1:high)
    if (array[i] <= pivot)
      small++
      swap(array[i],array[small])
  swap(array[low],array[small]) //move pivot to pivot idx
  return small // index of pivot

Question 11

quicksort description

Answer 11

1. choose a pivot
2. “partition” array around pivot (move small below and high above)
3. recurse 1. with array below pivot and above pivot (excluding pivot)

Question 12

mergesort description

Answer 12

1. divide the list into two halfs by pointing 2 pointers to the head and iteratoring over the list incrementing 1 pointer twice as fast
2. recurse 1. with first half
3. recurse 1. with second half
4. merge the two halves by iterating over them both taking and incrementing only the lowest value (so next iteration the higher value is again compare)

Question 13

mergesort()

Answer 13

mergesort(**head)
  *a = *head
  *b
  divide(a, &b)
  mergesort(a)
  mergesort(&b)
  merge(a, b, head)

Question 14

mergesort::divide()

Answer 14

divide(*a, **b)
  //iterator over the list incrementing one pointer twice as fast - so when it reaches the end the other pointer will point to the middle

Question 15

mergesort::merge()

Answer 15

//new head will be smallest of two heads
//iterate over the lists together taking and moving past the smallest only each time
// ex:
while a!null and b!null
if a.val < b.val
  tail.next = a
  a = a.next
else
  tail.next = b
  b = b.next
tail = tail.next
//one list finishes first, so special case to grab last value
if a is null
  tail.next = b
else
  tail.next = a