Data Structures

Question 1

Are elements indexed in a Linked List

Answer 1

No

Question 2

Advantages of Linked List

Answer 2

Insert/Delete are quick: Prepend O(1) Append O(n)

Question 3

Implement a Linked List

Answer 3

class Node {
   constructor() {
       var data;
         Node.next() 
         Node (data) {
             this.data = data
          }
    }

Question 4

Binary Search Tree Structure

Answer 4

left nodes < root nodes < right nodes

Question 5

Balanced Binary Tree Method Complexity

Answer 5

insert & find: O(logn)

Question 6

Proper way to Traverse a Binary Tree

Answer 6

Left then root then right

Question 7

Heap Structure

Answer 7

Root is smaller than children(Min Binary Heap), Root is always larger (Max Binary Heap.
Priority Queue is a Min Binary Heap. (2n +1): 2 to get child index, Math.floor(n/2) to get parent index

Question 8

Implement a counting function in a Linked List

Answer 8

function countNodes(Nodehead) {
   //assuming head !== null
   let count = 1
   Node.current = head
   while (current.next != null) {
   current = current.next;
   count += 1;
   }
   return count;
}

Question 9

Hash Tables consist of

Answer 9

keys mapped to values stored as objects in an array

Question 10

Hash Table Time complexity

Answer 10

Constant

Question 11

How do hash table elements get sorted

Answer 11

A key is passed into a hashing function, and the result is the index the key, value pair is stored at

Question 12

Hash function for integers

Answer 12

sum(integers) % array.size = index

Question 13

Hash function for strings

Answer 13

sum(CharCode) % array.size = index

Question 14

Open Addressing method for Collision Handling in Hash Tables

Answer 14

Linear Probing: takes linear time, decent in if the load factor is low. keep looking for the next open index (or plus 3, quadratic). Keys might bunch together

Question 15

Load factor in a Hash Table

Answer 15

load factor = n / k where n is the number of entries and k is the number of buckets in the array

Question 16

Closed Addressing method for Collision Handling in Hash Tables

Answer 16

Chaining: creating a linked list at indexes with more than one hash pointing to it. Search by stepping along the linked list. O(n)

Question 17

Objectives of a Hash function

Answer 17

• minimize collisions
• uniform distribution of hash values
• easy to calculate
• be able to resolve collisions

Question 18

Runtime of a hash function

Answer 18

O(1)

Question 19

Linked List

Answer 19

Data structure that represents a sequence of nodes. Single & double linked. Single only points one direction, double points both directions

Question 20

Linked List disadvantage

Answer 20

does not provide constant time access to look up an index. O(n) time

Question 21

Linked list advantage

Answer 21

add/remove items from the beginning of the list in constant time.

Question 22

Deleting node in linked list

Answer 22

given n, find prev. prev.next = n.next. Check for null pointers and reset the head/tail node as necessary

Question 23

linked list runner technique

Answer 23

iterate through the linked list with 2 pointers simultaneously, with one ahead of the other. the ‘fast’ node could be ahead by a fixed amount or could be hopping multiple nodes.

Question 24

Array advantages

Answer 24

Constant time for lookup

Question 25

Stacks

Answer 25

LIFO, O(1) time for add/remove

Question 26

Queue

Answer 26

FIFO O(1) time for add/remove

Question 27

When to use DFS

Answer 27

If we know the solution lies somewhere deep in a tree or far from the source vertex in graph, use DFS. If our tree is very wide, use DFS as BFS will take too much memory.

Question 28

When to use BFS

Answer 28

If we know the solution is not that far from the source vertex, use BFS. If our tree is very deep, choose BSF over DFS.