Algorithms

Question 1

a) Explain the differences and similarities between Ruby vs C.
b) Discuss arrays in C (i.e. #find, #push, #delete), and what is a static array.

Answer 1

a)
Ruby is a wrapper for C. C is a wrapper for assembly language, an even lower level language.

Ruby:

1. Slower runtimes than C code. But does not need a compiler and is easier to learn and write code.
2. Offers many built-in functionality, whereas C, operates on a “no hidden mechanism” principle (does not mask what’s going on behind the scenes).

One example of “no hidden mechanism” principle is how Ruby and C implements arrays.

b)
Static array: Array size in C are fixed from the time they are constructed. C must allocate contiguous memory in which the array is stored, not arbitrarily large amounts of memory for the array. You as the programmer specify the size.

C stores location of array in memory (M) and array length (L). Therefore:
#find(i) is O(1).
To find the i element in static array, simply add M + i to find i element. Arithmetic and lookup takes constant time. 

#push is O(1).
To append a value to end of static array, simply add M + L to get next available space in array, and assign memory location to new value. Arithmetic and value assignment takes constant time. 

#delete is O(n).
i.e. You have [a, b, c, d], and you want to delete("b"). 
After deleting 'b', you have to copy remaining elements to ensure memory allocation is contiguous. There cannot be  gaps in memory allocation. It takes on average n/2 to copy all elements. And n - 1 for worst case (i.e. if second to last element in array is deleted). 

Static arrays typically only have a get and set method.

Question 2

In a 64-bit architecture, how many bytes are in each cell?

Answer 2

8 bytes = 64 bit architecture
For example, if there are 4 contiguous memory cells, and the first cell to the left has a memory address of 800. Then the next memory address is 808, then 816, and so forth.

Question 3

How do arrays in Ruby work? How are we able to keep pushing elements to an array without specifying an initial size of the array? Define dynamic arrays.

Answer 3

We use static arrays to build DYNAMIC ARRAYS. A dynamic array is a data structure that resizes dynamically by doubling current size of array when static array reaches full capacity.

What do we need to keep track of to implement a dynamic array?

1. length of stored data
2. location in memory
3. capacity

For example, if you initially create a static array of size 4 and it is filled, when you try to add a fifth element, we find a new space in memory that is twice the original allocated size. You then copy over the 4 elements and push in the fifth element. The old memory allocation is freed.

#push is O(1)
The average, or amortized time complexity is O(1). This is because as the array size gets larger every time array is doubled, and we continue to push elements into array, there are significantly more O(1) #push than there is O(n), which only occurs during resizing. 

The worse case is O(n). But it makes sense to think of #push in an average because we know the array size increases in a predictable way. Thus, the average case will give us a better picture of how #push performs as array grows.

This means that if we build our dynamic array this way, by doubling memory allocation each time array is filled, then #find (O(1)), #push (O(1)), #delete(O(n)) on average, takes same amount of time as static array.

Question 4

How do Ring Buffers work? Why is it useful? What are the four things you need to keep track of when implementing a ring buffer?

Answer 4

Ring Buffer is another data structure that resembles a circular array, used to improve #unshift to O(1) amortized and #shift O(1).

As of now, using a dynamic array will cause #unshift to be O(n) because by adding an element at the beginning of the array, we have to copy over remaining elements to a new memory location, which takes O(n).

Things to keep track of (4 things):

1. length of stored data
2. location in memory
3. capacity
4. start location (memory location of arr[0]). The start idx only changes when using #shift/#unshift. Using #pop/#push does not change start idx/location.

As a side note, Ruby does not fully implement a ring buffer. May be due to C libraries making it really difficult to implement.
But Ruby does at least implement a partial ring buffer. So #shift is O(1) but #unshift is O(n).

Source: Dynamic Arrays: Ring Buffer video https://vimeo.com/202125903

Question 5

LRU Caching?

Answer 5

Least Recently Used

Question 6

Breadth First Search

Answer 6

BFS is an algorithm. Difference between an algorithm and a method?
An algorithm is an idea, an unambiguous or unrealized process for potentially solving a problem. A method is an implementation of an algorithm into code.

BFS uses a queue to implement BFS, which is first-in-first-out (FIFO). Think of a queue as a cafeteria line (or an array), the first one in line is the first one to get food. You #dequeue by using #shift to remove first value in array.

pseudo code to find a specific value:
queue = [root]
until queue.empty?
   el = queue.shift
   el.children.each { |child| queue << child }
   return true if el == val 
end

Question 7

Name and define different abstract data types (ADT)?

Answer 7

ADTs can be thought of as a high-level description of a data structure.

Examples:
Set - Stores unordered, unique items. It is array like

Maps - Can be implemented using a 2D array. A map stores information in key-value pairs, where the keys are always unique. When implemented with arrays, a map might look something like this: my_map = [[k1, v1], [k2, v2], [k3, v2], …]

Stack - A linear data structure that follows LIFO (i.e. elevator entry/exit). A stack is used in Depth First Search.

Queues - A linear data structure that follows FIFO (i.e. cafeteria line) A queue is used in Breadth First Search.

Question 8

What is a hashing function?

Answer 8

The output is of constant length
Features:
Deterministic - meaning the output is always the same if the input is the same.
Uniform - You are just as likely to get an output regardless of what new input is being passed.
One-way function - There’s no way, that given an output, to predict what the input was.

Examples of hashing functions (i.e. used in hash maps):
murmurhash - used in Ruby
cityhash
crc32

cryptographic hashing fcns: mds, sha2, blowfish. Runs more slowly but is designed to have much few collisions.