Data Structures

Question 1

What are data structures?

Answer 1

These are collections of values, the relationships among them, and the functions or operations that can be applied to the data.

Question 3

What is a (Singly) Linked List?

Answer 3

A data structure that contains a head, tail, and length property. It consists of nodes, and each node has a value and a pointer to another node, or null.

Question 4

Describe the steps for the push method on a Singly Linked List in pseudocode.

Answer 4

1. the function accepts a value
2. create a new node using the passed value
3. if no head property on list, set the:
   
   1. head and tail property of the list to the new node
4. otherwise set the:
   
   1. next property on the tail node to the new node
   2. tail property on the list to the new node
5. increment the list length property by one
6. return the linked list.

Question 5

Describe the steps for the pop method on a Singly Linked List in pseudocode.

Answer 5

1. the function accepts no value
2. if no nodes in the list, return undefined
3. loop over the list, until reaching the tail
4. set the tail of list to be the 2nd to last node
5. decrement the length of list by 1
6. return the value of removed node

Question 6

Describe the steps for the shift method on a Singly Linked List in pseudocode.

Answer 6

1. the function accepts no value
2. if there are no nodes, return undefined
3. store current head property of list in variable
4. set head property of list to the current head’s next property
5. decrement length by 1
6. return the value of node removed

Question 7

Describe the steps for the unshift method on a Singly Linked List in pseudocode.

Answer 7

1. this function accepts a value
2. creates a new node with the passed value
3. if list has no head property, set the:
   
   1. head and tail to new node
4. otherwise, set the
   
   1. new node’s next property to the current head
   2. set the head property to the new node
5. increment list length by 1
6. return the linked list

Question 8

Describe the steps for the insert method on a Singly Linked List in pseudocode.

Answer 8

1. this function should accept an index and a value
2. check for valid index value, otherwise return null
3. create new node with value
4. if the index is 0, unshift new node to start of list
5. if index is list length, push new node to end of list
6. otherwise, get existing node at position of index - 1
7. set next property of new node to next of existing node
8. set next property of existing node to new node
9. increment length
10. return true

Question 9

Describe the steps for the remove method on a Singly Linked List in pseudocode.

Answer 9

1. this function should accept an index
2. check for valid index value, otherwise return null
3. if the index is 0, shift from start of list
4. if index is list length - 1, pop from end of list
5. otherwise, get existing node at position of index - 1
6. set next property of existing node to be the next of the next node
7. decrement list length
8. return value of removed node

Question 10

What are the Big O time complexities of Singly Linked Lists for:

1. Insertion at beginning or end

Answer 10

1. Insertion

Question 11

What is a Queue? Give some examples what they are used for.

Answer 11

The concept of an ordered collection of data items, where the addition of new items (enqueue) takes place at one end, and the removal of existing items (dequeue) always takes place at the other end.

It is a FIFO (First In First Out) data structure.

They are used for the order of processing background tasks, uploading resources, printing/taks processing, and much more.

Question 12

What is a Stack? Give some examples what they are used for.

Answer 12

The concept of an ordered collection of data items, where the addition of new items (pushing) and the removal of existing items (popping) always takes place at the same end.

It is a LIFO (Last In First Out) data structure.

They are used for function invocations, operations like undo/redo, for page routing (back and forth in history), and much more.

Question 13

What is a Tree? What elements does it consist of?

Answer 13

A non-linear data structure that consists of nodes in a parent / child relationship.

• Root: the top node
• Edge: connection between one node and antother
• Parent: node that has an edge to a child node
• Child: a node directly connected to another, when moving away from the Root
• Siblings: group of nodes with the same parent
• Leaf: node with no children

Question 14

Name the two main strategies for traversing a tree.

Answer 14

The strategies are:

• Breadth First Search (BFS)
  
  • search horizontally (siblings) first, then move vertically (children)
• Depth First Search (DFS)
  
  • search vertically (children) first, then move horizontally (siblings)

Question 15

What is the difference between a Binary Tree and a Binary Search Tree?

Answer 15

Both have at most two children for each parent, but in a Binary Search Tree every node to the left of a parent is less than its value and every node to the right is greater.

By definition a Binary Search Tree has distinct keys and duplicates are not allowed.

Question 16

What are the 3 variants of traversing within Depth First Search (DFS), and when are they commonly used?

Answer 16

• Pre-Order:
  
  • Can be used to “export” a tree structure to be easily reconstructed or copied; starts with root, left values, right values
• In-Order:
  
  • Used commonly with Binary Search Tree; returns all node within their underlying order; from lowest to highest.
• Post-Order:
  
  • Used commonly to delete a tree; starts at bottom with children of parent, and then parent.

Question 17

What are the rules of a Min Binary Heap and Max Binary Heap?

Answer 17

Data structures where:

• each parent has at most two children
• the value of each parent node is always greater (Max) or smaller (Min) than its child nodes
• there is no implied ordering between sibling nodes
• all the children of each node are as full as possible, and left children are filled out first

Question 19

When storing a Binary Heap in an array, how to determine the index of parent and child nodes?

Answer 19

For any node at index n,

• its parent is at floored index (n-1)/2
• its left child is at index 2n+1, and right child at 2n+2

Question 20

What is meant with ‘bubble down’ or ‘down-heap’ ?

Answer 20

The procedure for extracting (removing) the root element from a Heap and restoring the data structures properties.

Question 21

Describe the approach for extracting (removing) the maximum value from a Max Heap when using an array.

Answer 21

1. swap the first (maximum) and last array value
2. pop and store the last value (maximum)
3. set parent index to 0
4. find the biggest child value
5. if child value is greater than parent value
   
   1. swap child and parent value
   2. set parent index to child index
   3. repeat from step 4
6. return maximum value

Question 22

What is a Priority Queue? And what data structure is mostly used?

Answer 22

• An abstract data type where each element has a priority. Elements with higher priorities are served before elements with lower priorities.
• The classic way to implement is by using a Binary Heap.

Question 23

What is the Big O time complexity of Binary Heaps?

Answer 23

Big O time complexity of Binary Heaps:

• Insertion: O(log n)
• Removal: O(log n)
• Search: O(n)

Question 24

What are Hash Tables called in Python and JavaScript?

Answer 24

The are called:

• Dictionaries in Python
• Objects and Maps in JavaScript

Question 25

What is the Big O of Hash Tables?

Answer 25

Time complexity of Hash Tables (in average case):

• Insert: O(1)
• Delete: O(1)
• Access (by key): O(1)