General

Question 1

What is a graph?

Answer 1

A graph is a non linear data structure consisted of vertices and edges

Question 2

What are the 4 types of graphs?

Answer 2

Undirected graph, Directed graph, Weighed graph and Unweighed graph.

Question 3

What is a vertex in a graph?

Answer 3

A vertex is an element from the graph, a node.

Question 4

What is an edge?

Answer 4

An edge is a pair of connected vertices (v1,v2).

Question 5

What is an undirected graph?

Answer 5

An undirected graph is a graph where the edges between vertices has no direction and have a two way relationship. Ex: doubly linked list.

Question 6

What is a directed graph

Answer 6

A directed graph is graph where the edges have a specific direction and have a one way relationship. Ex: single linked list.

Question 7

What is a weighed graph?

Answer 7

A weighed graph is a graph where the edges have weight.
This weight can be represented by any type of value like time, distance, quantity, etc.
In a map, the weight between two vertices, or the edge weight, would be the distance.

Question 8

What is a path?

Answer 8

A path is the sequence of vertices to go through between one vertex and the other. From vertex “a” to vertex “n” there can be multiple paths between two vertices.

Question 9

What is path length in a graph?

Answer 9

The number of vertices in a determined path.

Question 10

What is a graph cycle?

Answer 10

A graph cycle is a path that starts and ends on the same vertex.

Question 11

What is a negative weight cycle?

Answer 11

In a graph if the sum of all the weights in a cycle is negative it’s called a negative weight cycle.

Question 12

What is graph connectivity?

Answer 12

If there is at least one path between two vertices, it means those vertices are connected.

Question 13

What is a vertex degree?

Answer 13

The term degree applies to unweighed graphs. The degree of a vertex is the number of edges connecting the vertex.

If A connects to B, D and C it means that A has the edges (A,B), (A,D) and (A,C) hence A vertex degree is 3.

Question 14

Does a vertex on a weighed graph has degrees?

Answer 14

No. Degrees only apply to unweighed graphs.

Question 15

What is indegree in a vertex from a directed graph?

Answer 15

In a directed graph indegree is the number of edges coming TO the vertex.

If there are two edges (A, B) and (D, B) and the direction is from left to right, then B indegree is 2 because there are two edges coming TO vertex B from other vertices

Question 16

What is outdegree in a vertex from a directed graph?

Answer 16

In a directed graph outdegree is the number of edges coming FROM the vertex.

If there are two edges (A, B) and (A, D) and the direction is read from left to right, then A outdegree is 2 because there are two edges coming FROM vertex A to other vertices.

Question 17

What is a disjoint set?

Answer 17

Disjoint sets (also known as union-find) is a data structure where two or more sets don't have any element in common (intersection). 
Ex: [1,2,3] [4,5] are disjoint sets because they don't have any intersection.

In graph this can be translated by isolated paths that don’t have any element in common.

Ex: Edge (1,2) and Edge (2,5) vs Edge (3,4) and Edge (4,6)

Question 18

What is a common use for a disjoint sect data structure?

Answer 18

A disjoint sect data structure can be used to identify the relationship between two vertices (connected or not).

E.g. in a social media whether two people are connected or not at any level.

Question 19

What are the two main functions from a DisjointSet?

Answer 19

Union(v1,v2) and Find(v1)

Question 20

How the union function in a disjoint set works?

Answer 20

Union will connect two vertices with each other.

The simplest representation uses an array where the index is the vertex and the value is the parent vertex (in case of a numeric representation).

Question 21

How the find function in a disjoint set works?

Answer 21

The find function will find the ROOT for a given vertex.

If two vertices have the same root it means they are connected.

Question 22

How the quick find implementation works on a disjoint set?

Answer 22

The union(v1,v2) function will store the root nodes instead of parent nodes. To do that it needs to replace all vertices values that reference rootY with rootX (selected head).
eg: rootX and rootY, replace all vertices with rootY value by rootX.

The find(v) function will return the root which is the value on the vertex index.

union(v1,v2) time complexity O(n)
find(v) time complexity O(1)

Question 23

How quick union implementation works on a disjoint set?

Answer 23

The union(v1, v2) function will store the parent vertex for each vertex instead of the root vertex.

The find(v) function will keep searching the parent until the vertex and parent are the same.

union(v1,v2) time complexity 0(n) (based on the find function)
find(v) time complexity O(n) (with n being the height of the tree)

Question 24

What is more efficient quick find or quick union in a disjoint set?

Answer 24

Quick union is more efficient because only on the worst case the union function will be O(n).

On quick find the union function will always be O(n) no matter what since it needs to go over the whole array every time you call union method.

Question 25

Is there a way to make quick union function faster in a disjoint set?

Answer 25

Yes there is. It’s using union by rank.

Question 26

What is union by rank function in a disjoint set?

Answer 26

Union by rank optimizes quick union by balancing the tree by rank with the rank being the height of the tree.

The root from the smaller rank (height) is joined into the root from highest rank (height).

e.g:
rank[rootX] > rank[rootY] : array[rootY] = rootX;
rank[rootX] < rank[rootY] : array[rootX] = rootY;
rank[rootX] == rank[rootY] : array[rootX] = rootY; rank[rootX]++;

find(v) time complexity O(logN)
union(v1,v2) time complexity O(logN)

TLDR;

Instead of selecting rootX or rootY for all operations, we find the bigger height and do the union with the root from the smallest height into the root from the bigger height. If the height is the same select any of them and increase the height of the selected by 1;

public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            root[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            root[rootX] = rootY;
        } else {
            root[rootY] = rootX;
            rank[rootX] += 1;
        }
    }
}

Question 27

What is path compression strategy in a disjoint set?

Answer 27

Path compression is used to optimize the find function so after finding the root we update the parent of all children to be the root vertex. (recursion)

Next time we try to find the root again on any vertex from that path it will be pointing directly to root instead of their immediate parent.

public int find(int x) {
    if (x == root[x]) {
        return x;
    }
    return root[x] = find(root[x]);
}

Question 28

What changes when we use path compression on a disjoint set implementation?

Answer 28

The tree now has all the nodes pointing directly to their root.

By using path compression we reduce the complexity of quick union find() and union() methods from O(n) to O(logN) since now the worst case is equal the height of the tree.

Question 29

What is the most optimal way to implement a disjoint set algorithm?

Answer 29

The most optimal way would be using union by rank + path compression.

This will still have the worst case as lesser than O(logN) but the average case would be constant since for each path we will be traversing the height of the tree at most once;

Question 30

How do we check if two vertices are connected on a Disjoint set?

Answer 30

If they have the same root vertex it means they are connected.

Question 31

What are the 3 basic functions from a Disjoint Set?

Answer 31

union(x,y), find(x), connected(x,y)

public boolean connected(int x, int y) {
    return find(x) == find(y);
}

Question 32

How to identify the number of different sets from a disjoint set?

Answer 32

To identify the number of different sets from a disjoint set we should count how many roots we have. To do that we just compare which value is equals the index.

e.g: if(root[i] == i) sets++;

Alternatively we could also start the DisjointSet with the maximum number of sets and decrease this count as part of the union method whenever we have a successful union.

Question 33

How to identify a cycle using disjoint sets?

Answer 33

When union function is called but the roots from the two vertices are the same it means we have a cycle IF and ONLY IF there are no self loops(union(1,1)) or duplicate edges (union(1,2); union(1,2));

Question 34

How to identify if a graph is a valid tree Using a disjoint set?

Answer 34

to be a valid tree:
the number of edges must be equal to n-1,
all nodes must be interconnected (have the same root)
having no cycles between them

So after removing duplicate edges and self cycles (union(1,1)) If the union function at any point of time does not do a union it means the graph has a cycle and thus is not a valid tree.

Question 35

What is a spanning tree?

Answer 35

Is a weighed undirected connected graph where all the vertices are connected without any cycle.

Question 36

What is a spanning forest?

Answer 36

A spanning forest is a set of spanning trees.

Question 37

What is a minimum spanning tree?

Answer 37

Is a spanning tree (all weighed undirected edges connected without cycles between them) where the sum of all edges is the minimal value for that graph.

Question 38

What DFS stands for?

Answer 38

Depth First Search. (Go as deep as possible)

Question 39

What DFS is mainly used for according to graph theory?

Answer 39

It’s used to traverse all vertices in a graph and it’s used to traverse all paths between any two vertices.

Traverse all vertices and traverse all paths between two vertices.

Question 40

Which data structure DFS uses to traverse the nodes?

Answer 40

DFS uses a stack to traverse the nodes.

Usually it can be used with a real stack or a implicit one when using recursion.

Question 41

How do we check if a path from node A to B exists using DFS?

Answer 41

We could start the DFS from start node marking it as visited and keeping a flag whenever we find a new connection.

We then go over each edge checking if one of them is already visited and if it is mark the other as visited too.

We need to keep going through the list of edges until we find the end node or no new connection is found.

PseudoCode:

mark start as visited
update newConnection to true
while !visited[end] && newConnection :
    update newConnection to false
    loop into each edge:
        if any of the edges is visited and the other not: 
            mark the other edge as visited
            update newConnection to true
return visited[end]

Question 42

How do we find all paths from start to end using DFS algorithm?

Answer 42

We basically want to start from start vertex and go into each neighbor recursively until we either reach the target vertex or there are no more vertices to explore.

Along the way for each vertex we visit we need to keep the current path and backtrack after reaching the stop condition.

The backtracking would be removing the added node from the current path in this case.

The stop condition will be either reach the target vertex or when there are no more vertices to explore.

If you don’t have the graph built and only the edges, build the graph first.

Question 43

How do we clone a Acyclic Directed Graph (ADG) using DFS?

Answer 43

As long as we can reach all nodes from the start node we would basically explore all paths cloning the nodes on the way.

The easy way to do this is with recursion where we basically check if the node is visited and is cloned we use the copy otherwise we clone it and mark it as visited.

Then we add on the cloned one neighbor list the result of the recursive call passing the next neighbor.

The function return will be the cloned node.

Question 44

When trying to find a path using DFS does it matter which node we start checking (start or end of the path)?

Answer 44

It doesn’t, we can’t start checking from the start of the path or end of the path, whatever is easier for us to do.

Sometimes is even easier to find the end of the path first and build the path from end to start like when reconstructing an itinerary.

Question 45

What is recursion?

Answer 45

Recursion is an approach to solve a problem breaking it in subproblems by using a method that calls itself. Each time a recursion occurs it reduces the problem into smaller subproblems until the problem can be solved without a recursive call.

Question 46

What are the two main properties a recursive function must have to not end on an infinite loop?

Answer 46

A base case and a recurrence relation.

Question 47

What is considered a base case on a recursive call?

Answer 47

A base case is a stop condition. A terminating scenario where no more recursion is needed.

E.g: if we wanna traverse an array from start to end recursively, and the recurrence relation is calling the recursive function increasing the index each time then the base case would be when the index is not valid anymore.

Question 48

How many base cases we can have on a recursive function?

Answer 48

We can have several base cases on a recursive function. A recursive function may have N conditions to stop the recursion.

Question 49

What is a recurrence relation on a recursive function?

Answer 49

Recurrence relation it’s the relationship between the result of a problem and the result of its subproblems. It’s a set or rules that reduces all other cases towards the base case(s).

E.g: if we wanna traverse an array from start to end recursively then the recurrence relation would be calling the recursive function increasing the index each time while the base case would be when the index is not valid anymore.

Question 50

How would you revert a single linked list recursively?

Answer 50

recurrence: f(h) = f(h.next) //navigate until the last node
base case: (h == null || h.next == null) return h; //new head

Consider a list with three nodes: 1 -> 2 -> 3

Find new head as last node recursively
newHead = f(head.next);
We are now on the second to last node: // head == 2
Put head ref as the tail of the list making a self loop 2->3->2
head.next.next = head;
Then remove the connection from current head to the next node 3->2
head.next = null;
Return new head:
return newHead; //3
—-
1[2]
2[3]
3[] // list without modification represented as a graph
Find 3 as newHead;

1[2]
2[3]
3[2] // point 3 to 2

1[2]
2[]
3[2] // remove pointer from 2 to 3

1[2]
2[1]
3[2] // point 2 to 1

1[]
2[1]
3[2] // remove pointer from 1 to 2

here we have our new linked list: 3->2->1 with 3 as the new head.

Question 51

How to invert a single linked list iteratively?

Answer 51

Keep a newHead as null at first
Keep your current node pointing to head at first
keep a temp var as the second node

Point currentNode.next to head
head to current
current to second

repeat this process until current node is null
return newHead

Pseudo code:

newHead = null;
current = head;
While current is not null:
    tempNextNode = current.next;
    currentHead.next = newHead
    newHead = current;
    current = tempNextNode;
return newHead;

Question 52

What is memoization?

Answer 52

Memoization is a technique to speed up computer programs storing the results of expensive function calls in a cache and returning the cached result when the function is called again avoiding duplicated processing.

Question 53

How memoization technique affects time and space complexity?

Answer 53

Memoization speed up processing time avoiding duplicated processing but increases space taken adding extra space for the cache.

Question 54

How to calculate time complexity of a recursive function?

Answer 54

It’s the product of the number of recursion invocations (R) and the time complexity of calculation (O(s)) that happens within each recursion call. O(T) = R * O(s). Pay attention on the memoization version which removes duplicated processing.

ex: fibonnaci = f(n-1) + f(n-2) and O(1) complexity to print the result.
2 recursive calls per each recursion n times.
This can be translated as 2 to the power N - 1 since the base case doesn’t call any recursive call.

(21ˆNO(1))-1 = 2^N -1 = 2^N

Question 55

How to calculate space complexity of a recursive function?

Answer 55

There are two parts we should consider, recursion related and non-recursion related space.

For a recursive algorithm, if no other memory consumption, then the recursion related space is space complexity of the algorithm.

Ex: Print a string in reverse have a stack of O(N) space, hence space complexity is O(N);

When memoization is in place it reduces the max stack size by avoiding duplicated calls to pile up, hence memoization cache size and reductions must be also considered when calculating the space complexity.

Question 56

What is tail recursion?

Answer 56

Tail recursion is when a recursive call doesn’t do any extra calculation when the base case is reached and hence the compiler can optimize and return the base case directly to the first caller.

Tail recursion = find last number on a LinkedList recursively.
recursive relation:
f(node.next); // tail recursion version
1*f(node.next); //non tail recursion - has a calculation so the compiler can’t optimize
base case: node.next == null ? return node;

Question 57

Does Java compiler do tail recursion optimization?

Answer 57

No. Java does not do tail recursion optimization. C and C++ does.

Question 58

How to identify if a problem can be solved by recursion or not?

Answer 58

It’s not easy, but by trying to derive the mathematical formula of the recurrence relation it may indicate that the problem can be solved recursively.

Question 59

When a stack overflow happens on a recursive call?

Answer 59

A stack overflow on a recursive call happens when the recursion stack is so big that no more memory is available to keep recursing. This can be due to the base case is never reached (infinite calls) or the recursion is so deep that it requires more memory space on the stack than available in the program processing it.

Question 60

When stack overflows on a recursive call what ways could we try to explore to solve this issue?

Answer 60

We may try to use tail recursion, memoization, and or reduce the number of operations done like when doing math sum calculations by utilizing half of the answer to sum up with the other half instead of processing each one of them. This would reduce a O(n) problem to O(logN) problem if for each answer we just need to process half of it.

Question 61

When doing merge sort or binary search how to avoid arithmetic overflow when finding the pivot with (start+end)/2?

Answer 61

We can avoid that by doing start + (end-start)/2.

start = 3 end = 9
(3+9)/2 = 12/2 = 6
3+(9-3)/2 = 3+6/2 = 3+3 = 6

Question 62

How to optimize the calculation of x to the power n recursively?

Answer 62

We could take advantage of the previous answers by calculating the half power recursively and multiplying it by itself instead of multiplying x to itself all the time.

Ex:
2^5
is the same as 2^2 * 2^2 * 2^1 hence we just need to calculate 2^2 and multiply the result with itself and x to get the final answer. 2^2 = 4 so 442 = 22222 = 2^5;

Question 63

What are the three parts of a successful Binary Search?

Answer 63

Pre-processing = Sort if collection is unsorted
Binary Search = Loop or recursion to divide search space in half
Post-processing = Determine viable candidates in the space left

Question 64

How does slow and fast pointers (floyd’s cycle detection) approach work?

Answer 64

We have two pointers, one slow and one fast.
Slow goes one step at a time and fast goes two steps at a time.
If they meet it means that is a cycle.

To find the start of the cycle we move slow to the beginning of the list and move both slow and start by one step until they meet. The point they met is the entrance of the cycle.

Question 65

How do we find the entrance of a cycle using slow and fast pointers?

Answer 65

Once the pointers met for the first time, move slow to the beginning of the list (if you use the index as starting point move to the first index if you used first position move to the first position) and then move both slow and start by one step forward until they meet. The point they met is the entrance of the cycle.

Question 66

How to identify cycles in an array?

Answer 66

Whenever we see an array where we are requested to find the duplicate number, we can use Floyd’s cycle detection algorithm to find it.

Start both slow and fast with first index or first value (0 or nums[0])
In a loop we go one step at a time from slow (slow = nums[slow]) and two steps at a time with fast (fast = nums[nums[fast]]) while they are different.

If they meet we know that we have a cycle.

Question 67

How to identify cycles in a linked list?

Answer 67

We can use Floyd’s cycle detection algorithm to find a cycle in a linked list.
We have two pointers, slow and fast starting on the first node.
Slow goes one step at a time (slow = slow.next)
Fast goes two steps at a time (fast = fast.next.next)
We keep this until either fast.next is null or fast == slow
If fast == slow we confirmed that there’s is a cycle.

To find the entrance of the cycle we move slow to the beginning of the linked list and then move both of them one step at a time until they meet again.

Question 68

How do we find the K-th Smallest Pair Distance?

Answer 68

We can use a binary search + sliding window pattern where we do a binary search between the smallest and greatest possible distances. We calculate the midDistance and we calculate the number of distances that are lesser than or equal to midDistance using a sliding window pattern;

— calculate small distances count
left=0
for(int right = 1; right < nums.length; right++) {
while(nums[right] - nums[left] > mid) left++;
count += right-left;
}
return count;
—
Stop condition: left == right
Left condition: smallerDistancesCount >= K-th distance
right = mid;
Right condition smallerDistancesCount < K-th distance
left = mid+1;