# Algorithms and Data Structures

## Data Structures

• Arrays
• Implement an automatically resizing vector.
•  Description:
•  Implement a vector (mutable array with automatic resizing):
•  Practice coding using arrays and pointers, and pointer math to jump to an index instead of using indexing.
•  new raw data array with allocated memory
• can allocate int array under the hood, just not use its features
• start with 16, or if starting number is greater, use power of 2 – 16, 32, 64, 128
•  size() – number of items
•  capacity() – number of items it can hold
•  is_empty()
•  at(index) – returns item at given index, blows up if index out of bounds
•  push(item)
•  insert(index, item) – inserts item at index, shifts that index’s value and trailing elements to the right
•  prepend(item) – can use insert above at index 0
•  pop() – remove from end, return value
•  delete(index) – delete item at index, shifting all trailing elements left
•  remove(item) – looks for value and removes index holding it (even if in multiple places)
•  find(item) – looks for value and returns first index with that value, -1 if not found
•  resize(new_capacity) // private function
• when you reach capacity, resize to double the size
• when popping an item, if size is 1/4 of capacity, resize to half
•  Time
• O(1) to add/remove at end (amortized for allocations for more space), index, or update
• O(n) to insert/remove elsewhere
•  Space
• contiguous in memory, so proximity helps performance
• space needed = (array capacity, which is >= n) * size of item, but even if 2n, still O(n)
•  Description:
•  C Code (video) – not the whole video, just portions about Node struct and memory allocation.
•  why you should avoid linked lists (video)
•  Gotcha: you need pointer to pointer knowledge: (for when you pass a pointer to a function that may change the address where that pointer points) This page is just to get a grasp on ptr to ptr. I don’t recommend this list traversal style. Readability and maintainability suffer due to cleverness.
•  implement (I did with tail pointer & without):
•  size() – returns number of data elements in list
•  empty() – bool returns true if empty
•  value_at(index) – returns the value of the nth item (starting at 0 for first)
•  push_front(value) – adds an item to the front of the list
•  pop_front() – remove front item and return its value
•  push_back(value) – adds an item at the end
•  pop_back() – removes end item and returns its value
•  front() – get value of front item
•  back() – get value of end item
•  insert(index, value) – insert value at index, so current item at that index is pointed to by new item at index
•  erase(index) – removes node at given index
•  value_n_from_end(n) – returns the value of the node at nth position from the end of the list
•  reverse() – reverses the list
•  remove_value(value) – removes the first item in the list with this value
• Stack
• Queue
•  Using Queues First-In First-Out(video)
•  Queue (video)
•  Circular buffer/FIFO
•  Priority Queues (video)
•  Implement using linked-list, with tail pointer:
• enqueue(value) – adds value at position at tail
• dequeue() – returns value and removes least recently added element (front)
• empty()
•  Implement using fixed-sized array:
• enqueue(value) – adds item at end of available storage
• dequeue() – returns value and removes least recently added element
• empty()
• full()
•  Cost:
• a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you’d need the next to last element, causing a full traversal each dequeue
• enqueue: O(1) (amortized, linked list and array [probing])
• dequeue: O(1) (linked list and array)
• empty: O(1) (linked list and array)
• Hash table
•  Videos:
•  Online Courses:
•  implement with array using linear probing
• hash(k, m) – m is size of hash table
• exists(key)
• get(key)
• remove(key)

## Sorting

If you need more detail on this subject, see “Sorting” section in Additional Detail on Some Subjects

## Graphs

Graphs can be used to represent many problems in computer science, so this section is long, like trees and sorting were.

• Notes from Yegge:
• There are three basic ways to represent a graph in memory:
• objects and pointers
• matrix
• Familiarize yourself with each representation and its pros & cons
• BFS and DFS – know their computational complexity, their tradeoffs, and how to implement them in real code
• When asked a question, look for a graph-based solution first, then move on if none.
•  Skiena Lectures – great intro:
•  Graphs (review and more):
• Full Coursera Course:
• Yegge: If you get a chance, try to study up on fancier algorithms:
•  Dijkstra’s algorithm – see above – 6.006
•  A*
• I’ll implement:
•  DFS with adjacency list (recursive)
•  DFS with adjacency list (iterative with stack)
•  DFS with adjacency matrix (recursive)
•  DFS with adjacency matrix (iterative with stack)
•  single-source shortest path (Dijkstra)
•  minimum spanning tree
• DFS-based algorithms (see Aduni videos above):
•  check for cycle (needed for topological sort, since we’ll check for cycle before starting)
•  topological sort
•  count connected components in a graph
•  list strongly connected components
•  check for bipartite graph

You’ll get more graph practice in Skiena’s book (see Books section below) and the interview books