Rules of Dijkstra’s Algorithm

Question 1

Rule 1 Dijkstra’s algorithm

Answer 1

We make the starting vertex our current vertex.

Question 2

Rule 2 Dijkstra’s algorithm

Answer 2

We check all the vertices adjacent to the current vertex and calculate and record the weights from the starting vertex to all known locations.

Question 3

Rule 3 Dijkstra’s algorithm

Answer 3

To determine the next current vertex, we find the cheapest unvisited known vertex that can be reached from our starting vertex.

Question 4

Rule 4 Dijkstra’s algorithm

Answer 4

Repeat the first three steps until we have visited every vertex in the graph.

Question 5

Data structures operations

Answer 5

Read, Search, Insert, Delete

Question 6

Array Search Worst Case

Answer 6

N steps

Question 7

Array Insertion Worst Case

Answer 7

N + 1 steps

Question 8

Array Deletion Worst Case

Answer 8

N steps

Question 9

Set Search Worst Case

Answer 9

N steps

Question 10

Set Insertion Worst Case

Answer 10

2N + 1 steps

Question 11

Set Deletion Worst Case

Answer 11

N steps

Question 12

Ordered Arrays

Answer 12

Sorted

Question 13

O(log N)

Answer 13

the Big O way of describing an algorithm that increases one step each time the data is doubled

Question 14

Compaction

Answer 14

means throwing away duplicate keys in the log, and keeping only the most recent update for each key

Question 15

Bubble Sort

Answer 15

O(N^2)

Question 16

Selection Sort

Answer 16

O(N^2)

Question 17

Insertion Sort

Answer 17

O(N^2) Better for average case scenarios where data is randomly sorted.

Question 18

linear search

Answer 18

O(N)

Question 19

Constant search

Answer 19

O(1)

Question 20

binary search

Answer 20

O(log N)

Question 21

LSM-Tree

Answer 21

Log-Structured Merge Tree

Question 22

B-Tree WAL

Answer 22

write-ahead log for recovery

Question 23

SSTable

Answer 23

Sorted String Table

Question 24

storage engine types

Answer 24

B-Tree and log-structured indexes

Question 25

Vertex

Answer 25

The node in a graph database which holds information

Question 26

Edge

Answer 26

The path between two vertices in a graph database

Question 27

Kafka

Answer 27

has better throughput, built-in partitioning, replication and inherent fault-tolerance then traditional message broker

Question 28

Point to Point Messaging System

Answer 28

In a point-to-point system, messages are persisted in a queue

Question 29

Publish-Subscribe Messaging System

Answer 29

In the publish-subscribe system, messages are persisted in a topic

Question 30

Dimension table

Answer 30

A Dimension Table is a table in a star schema of a data warehouse

Question 31

Fact Table

Answer 31

A fact table is a table that contains the measures of interest. Ex: sales amount by each store, each day