Algorithms

Question 1

Tree: Number of nodes in a full binary tree with L levels?

Answer 1

Nodes = (2 ^ L) - 1

Question 2

Tree: What numbers of calls does recursive function with branching do with input N?

Answer 2

Ncalls = (Branches ^ Levels) - 1, where

Levels = ceiling(N / Decrement) - BaseCaseValue + 1
Levels = ceiling(logN) - ceiling(logBaseCaseValue) + 1

Example:
def f(N):
  if N <= 0:  # BaseCaseValue = 0
    return 1
  return f(N-1) + f(N-1)  # Branches = 2, Decrement = 1

Question 3

Tree: Number of leaves in a full tree with L levels?

Answer 3

Leaves = branches ^ (L - 1)

Question 4

Tree: In a complete binary tree represented as an array what is index of children of a node with index N?

Answer 4

Left child: 2 * N + 1

Right child: 2 * N + 2

Question 5

KMP: What is KMP algorithm?

Answer 5

KMP stands for Knuth-Moris-Pratt and it is an efficient algorithm for finding specific substring in a given string.

Time complexity: O(n + m), where n is a length of the string and m is a length of the substring.

Space complexity: O(m)

Question 6

KMP: In the context of KMP algorithm what will the P-table be for the pattern “abcdabca” ?

Answer 6

0 1 2 3 4 5 6 7
a b c d a b c a
[0, 0, 0, 0, 1, 2, 3, 1]

Question 7

KMP: In the context of KMP algorithm what a value inside P-table means?

Answer 7

Every value in the table means how many characters in the prefix are already matched. Those values help us to skip comparisons which we already know will succeed, and that is where the efficiency of KMP comes from.

Question 8

Bit tricks: Isolate the first set bit from the right?

Answer 8

x = x & ~(x - 1)

Example:
x = 1010

1. (x - 1) = 1001
2. ~(x - 1) = 0110
3. x & ~(x - 1) = 0010

Question 9

Bit tricks: Unset the last set bit from the right?

Answer 9

x = x & (x - 1)

Example:
x = 1110
1. (x - 1) = 1101
2. x & (x - 1) = 1100

Question 10

What is LCM of two numbers and how to find it?

Answer 10

LCM stands for least common multiple and it is a first number that is divisible by the given two numbers A and B.
LCM(a, b) = (a * b) / GCD(a, b)

Question 11

What is the Euclidean Algorithm?

Answer 11

It is an efficient algorithm for finding GCD:

r = a % b
while r:
 a = b
 b = r
 r = a % b
return b

Question 12

Graph: What are common algorithms used to solve shortest path problem in graphs?

Answer 12

• BFS (unweighted graphs)
• Dijkstra (without negative weights)
• Bellman-Ford
• Floyd-Warshall
• A*

Question 13

Graph: What are common algorithms used to solve connectivity problem in graphs (does there exist path from one node to another)?

Answer 13

• use union find data structure

- DFS

Question 14

Graph: What are common algorithms used to detect negative cycles?

Answer 14

• Bellman-Ford

- Floyd-Warshall

Question 15

Graph: What are common algorithms used to find strongly connected components in a directed graph?

Answer 15

• Tarjan’s algorithm

- Kosaraju’s algorithm

Question 16

Graph: What are common algorithms used to find a Minimum Spanning Tree (MST) of a graph?

Answer 16

• Kruskal’s algorithm
• Prim’s algorithm
• Boruvka’s algorithm

Question 17

Graph: What is a time and space complexity of DFS algorithm?

Answer 17

Time: O(V + E)
Space: O(E)

Question 18

Graph: What is a time and space complexity of BFS algorithm?

Answer 18

Time: O(V + E)
Space: O(E)

Question 19

Graph: What is Dijkstra’s Algorithm and what its time and space complexity?

Answer 19

Dijkstra’s algorithm is a Single Source Shortest Path (SSSP) greedy algorithm for graphs with non-negative edge weights.

Typical time complexity: O(E*log(V))
Space complexity: O(E)

Question 20

Graph: What are Lazy Dijkstra’s and Eager Dijkstra’s?

Answer 20

Those are two different implementations of the Dijkstra’s algorithm.

Lazy Dijkstra’s allows duplicate key values in the priority queue, while Eager Dijkstra’s uses Indexed Priority Queue (IPQ) to change priority (distance) of a node instead of inserting a duplicate key.

Lazy implementation is less efficient on dense graphs.

Question 21

What general equation of a linear congruential generator?

Answer 21

seed = (a * seed + c) mod m,
Where a, c and m are specially picked constants.

For range [0, 1): seed / m
For range [l, h]: floor(l + (h - l + 1) * seed / m)