There are 2 ways of doing that

1. DFS
2. BFS

For the DFS way start with node n, if it is not visited, mark it visited, and then see what all node it points to, go over each of them. Once you are done with a node completely, then add this node to the ans.

For the BFS way, use a queue and find the indegree of each of the nodes, at each iteration loop over all the nodes with indegree == 0, then go over each of the node that it points to, for each of those pointed nodes reduce the indegree of those nodes by 1. Once we explored the node with indegree == 0 add it to the ans list.

1. If a function returns -1 vs non 0 values remember to write code to handle it.
2. Check the boundary conditions, always. Got a stack overflow error on this due to this issue.
3. If a number is very close to the edge of max limit of any data type (like int) then move on to next datatype (like long).

back to parent

Relavant algorithms

1. KMP
2. Rabin Karp

back to parent

substring search algorithm

Given a text and a pattern, if we need to know if we can find the pattern in the text.

The approach is

1. We calculate hashes of strings. So we create a hash function.
2. Choose a prime number for the hash function, say 101, it needs to be large.
3. Then use the algorithm like ascii(ch1)p + ascii(ch2)pp + aschii(ch3)ppp + ...
4. Step 3 gives the hash of the string.

back to parent

Say you have 2 algorithms of time complexity like O(m+n), O(mlogn), which one is better?

To answer this question we need to consider the values of m and n. If m and n are near each other in side then the linear time complexity one is better. If one is much bigger than the other the the logarithmic time complexity is better as log(x) will drastically reduce the value of m.

Say we have a sorted array and we need to randomize it, how can we do that? This is the fisher yates problem,https://www.youtube.com/watch?v=4zx5bM2OcvA Basically we can use a wall/partition concept here and move the found random elements on the left side of the wall and rest to the right, then math.random(start, end), where start = wall+1

If a matrix has most of the elements as 0 (or something else) and only a few elements as 1 (or something else) then it is called a sparse matrix.

There are 2 ways of representating the sparse matrix First,

sliding window maximum

• We need the MAX in the sliding window, and the max item will not fluctuate between max and not max, for example if it's max it will not become not max and again become max. So this hints at not using priority queue.

• Store the indexes of elements in the sliding window in dequeue, dequeue because we need to check if new element is more than the last element of the queue. Also, we need to check if first element of dequeue is less than i-k+1.

For the problems like find the kth largest element, we can find the kth element, by counting the order of evaluation of the nodes, the problem is, to loop through all the nodes, we either need to use

• recursive solution
• iterative solution

In both the cases we are using a stack/stack space of O(n)

We can eliminate the use of a stack by using a threaded binary tree. Threaded binary tree is a tree where a child node has a link to one of the previous root nodes. In case of morris traversal, the leaf node has the right pointer to the next element in the in-order sequence.