Associate Software Engineer

Given a directed acyclic graph having ‘N’ nodes. A matrix ‘edges’ of size M x 2 is given which represents the ‘M’ edges such that there is an edge directed from node edges[i][0] to node edges[i][1].

Find the smallest set of vertices from which all the nodes in the graph are reachable.

Note :

Nodes are numbered from 0 to N - 1.

The graph given is connected.

Print the vertices in sorted order.

For Example :

The following is an example of DAG i.e a directed graph with no cycles in it. 

In the above graph, we can reach all the vertices from node a.

You have been given a matrix of ‘N’ rows and ‘M’ columns filled up with integers. Find the minimum sum that can be obtained from a path which from cell (x,y) and ends at the top left corner (1,1).

From any cell in a row, we can move to the right, down or the down right diagonal cell. So from a particular cell (row, col), we can move to the following three cells:

Down: (row+1,col)
Right: (row, col+1)
Down right diagonal: (row+1, col+1)

You have been given an array 'ARR' of ‘N’ integers. You have to return the minimum number of jumps needed to reach the last index of the array i.e ‘N - 1’.

From index ‘i’, we can jump to an index ‘i + k’ such that 1<= ‘k’ <= ARR[i] .

'ARR[i]' represents the maximum distance you can jump from the current index.

If it is not possible to reach the last index, return -1.

Note:

Consider 0-based indexing.

Example:

Consider the array 1, 2, 3, 4, 5, 6 
We can Jump from index 0 to index 1
Then we jump from index 1 to index 2
Then finally make a jump of 3 to reach index N-1

There is also another path where
We can Jump from index 0 to index 1
Then we jump from index 1 to index 3
Then finally make a jump of 2 to reach index N-1

So multiple paths may exist but we need to return the minimum number of jumps in a path to end which here is 3.

You are given an array/list ‘arr’ of size ‘n’. Your task is to find the maximum product possible by taking any subset of the array/list ‘arr’.

Since the product can be large, return it modulo 10^9+7

For example:

Let arr=[-1,-1,-2,4,3] 

We can take the subset {-1,-2,4,3} which will have the product as 24. We can verify that this is the largest product possible. Hence we return 24.

1. What is Multithreading? 
2. What is semaphore, mutex?
3. What is critical section?

Define TCP model and/or OSI model.
The flow of data when a link is clicked.

You are given a stream of 'n' non-negative integers as the input, and you have to group the stream of integers in the form of disjoint intervals.

Your task is to Implement the ‘DisjointIntervals’ class having the two functions:

1) The first function is ‘addInteger(int val)’, which takes an integer ‘val’ as an argument and adds it to the stream.

2) The second function is ‘getDisjointIntervals()’, which returns a summary of the integers in the stream currently as a list of disjoint intervals.

Example:

Input: 'n' = 5 , stream =  [
                  [1, 1],
                  [1, 3],
                  [2],
                  [1, 2],
                  [2],
                ]

Output: [
          [ [1, 1],  [3, 3] ],
          [ [1,3] ] 
        ]

Explanation: First of all, 1 is added to the stream, and the disjoint interval will be {1, 1}. When 3 will be added to the stream, then the disjoint intervals will be {1, 1}, {3, 3}. But when 2 is added to the stream then the disjoint interval will be {1, 3} as 2 lies between these two sets of disjoint intervals, and both the intervals {1, 1} and {3, 3} merge.

1. What is DHCP?
2. What is IP?
3. What is the difference between IPV4 and IPV6?
4. Explain Data Link layer.
5. Explain DNS.