Data structures and Algorithms

Question 1

I know how to handle collisions in a hash table

Answer 1

Use a linked list to store multiple values using the same key

Question 2

I know the difference between an array and linked list

Answer 2

An array is one object that contains elements

A linked list is a data structure consisting of objects often referred to as nodes that typically contain 2 properties, the value of the node and a next property that points to the next node in the linked list.

Question 3

I know how to implement fibonacci with dynamic programming

Answer 3

Use memoization with the recursive solution to fibonacci

var fibonacci = (function () {
  var memo = [0, 1];
  var fib = function (n) {
      var result = memo[n];
      if (typeof result !== 'number') {
        result = fib(n - 1) + fib(n - 2);
        memo[n] = result;
      }
      return result;
    };
  return fib;
}());

Question 4

I can reverse an array in place

Answer 4

function reverse (array) {
  var i = 0,
      n = array.length,
      middle = Math.floor(n / 2),
      temp = null;

  for (; i < middle; i += 1) {
     temp = array[i];
     array[i] = array[n - 1 - i];
     array[n - 1 - i] = temp;
  }
  return array
}

Question 5

I know what a Set is used for

Answer 5

Set objects are collections of values. You can iterate through the elements of a set in insertion order. A value in the Set may only occur once; it is unique in the Set’s collection.

Question 6

I know constant, linear, logarithmic, quadratic, exponential time complexity

Answer 6

• constant: An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input
• linear: An algorithm is said to take linear time, or O(n) time, if its time complexity is O(n). Informally, this means that for large enough input sizes the running time increases linearly with the size of the input.
• logarithmic: An O(log n) algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when n increases.
• quadratic: O(n2) repeating operations for n elements n times
• exponential: O(c^n) where c is a constant.