Data Structures and Algorithms

Question 1

What are 2 different approaches for deciding when to do work?

Answer 1

Just-In-Time: Waits for a request before doing any work.
Ahead-of-Time: Does all possible work beforehand so it can quickly access results once requested.

Question 2

Name 3 examples when logs come up in algorithms?

Answer 2

1) Binary Search = O(logn)
2) Sorting = O(nlogn)
3) Height of Tree = O (logn+1)

Question 3

What is the equation for the height of a binary tree?

Answer 3

h= log(n+1)

Question 4

What is the equation for the number of nodes on the last line of a binary tree?

Answer 4

n= 2^h -1

Question 5

What is a recursively-defined data structure and give some examples?

Answer 5

A data structure that can be defined using itself.

• The linked list can be defined as a data structure consisting of an object referencing a list (or null).
• Trees like HTML elements tree or an object made of a company’s departments (and subdepartments) are also naturally recursive: they branch and every branch can have other branches.

Question 6

Describe some benefits and drawbacks of using a linked list vs an array.

Answer 6

The “delete element” and “insert element” operations for arrays are expensive. For instance, arr.unshift(obj) operation has to renumber all elements to make room for a new obj, and if the array is big, it takes time. Same with arr.shift(). Push/pop only works at the end.
Linked list have very fast insertion/deletion. Unlike arrays, there’s no mass-renumbering, we can easily rearrange elements.

The main drawback of linked lists is that we can’t easily access an element by its number. In an array that’s easy: arr[n] is a direct reference. But in the list we need to start from the first item and go next N times to get the Nth element.

Question 7

What is a linked list?

Answer 7

The linked list element is recursively defined as an object with:

• value.
• next property referencing the next linked list element or null if that’s the end.

Example:
let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

Question 8

When should you use Array.from over Array.map when iterating over array?

Answer 8

Array.from iterates over each element from 0 to the length of the array, while map only iterates over properties that are actually on the array. If you need to iterate over empty/undefined values in the array, use Array.from

Question 9

What are the Strengths and Weaknesses of Linked Lists. Ideal times to use them?

Answer 9

Strengths:
-Fast operations on the ends
-Flexible size

Weaknesses:
-Costly lookups compared to arrays. You have to take O(i) to get to the ith item
-Can take longer to iterate through than arrays because caching systems make reading from sequential addresses in memory faster (though they are both O(n))

Uses: Stacks and queues only need fast operations on the ends, so linked lists are ideal

Question 10

What is the worst Big O for Linked Lists?
(space, prepend, append, lookup, insert, delete)

Answer 10

space: O(n)
prepend: O(1)
append: O(1)
lookup: O(n)
insert: O(n)
delete: O(n)

Question 11

What are the benefits and drawbacks of queue structures? Ideal times to use them?

Answer 11

Strengths: Fast operations! (all O(1))

Uses:
-Breadth-first search: keeps track of the nodes to visit next
-Printers: uses queues to manage jobs
-Web servers: uses queues to manage requests
-Processes: wait in the CPU scheduler’s queue for their turn

Easy to implement with Linked lists!

Question 12

What values should you construct a queue class with?

Answer 12

First and Last; Optional: length
Often times assign first and last to a node for a linked list.
Can also assign first and last to two arrays (2 stacks to make queue problem)

Question 13

What is Breadth-First Search? What are the advantages and disadvantages?

Answer 13

A method of exploring a tree or graph. You first visit all of the immediate children, hen move on to all those node’s children, etc until we reach the end.

Advantage:
-BFS will find the shortest path

Disadvantage:
-BFS generally requires more memory than DFS

BFS uses a queue to keep track of the nodes to visit next

Uses:
-Shortest Path
-Most related items, i.e. closest connections or friends
-Working with information on upper level

Question 14

What is Depth-First Search? What are the advantages and disadvantages?

Answer 14

A method of exploring a tree or graph. You go as deep as possible down one path before backing up and trying a different one.

Advantages:
-Generally less memory than DFS
-Can be easily implemented with recursion

Disadvantages:
-DFS doesn’t necessarily find shortest path

DFS uses a stack

Uses:
-Figure out if a path exists
-Comparing leaf nodes
-Working with information on the lower level of tree