SDE - 1

The Ultimate Ninja Ankush, after training hard, goes for a good meal at the ninja cafe, for that he follows the path given on the map, which may or may not lead him to the ninja cafe. The map is a directed graph. Since he is also very lazy, he wants to minimize the effort to travel. The effort is defined as the product of all the distance it takes to reach from the dojo (source) to the ninja cafe (destination). Can you help him find the path with the minimum effort it would take The Ultimate Ninja Ankush to reach the destination?

More Formally, you are given a directed graph with ‘N’ nodes and ‘M’ edges where the distance of each edge is greater than 0, also given a source ‘src’ and a destination ‘dest’. The task is to find the minimum product of edges from src’ to ‘dest’. If there is no path from ‘src’ to ‘dest’, then return -1.

For example

Given:
‘N’ = 3, ‘M’ = 3. 
‘edges’ = 
    [[0 1 1],
     [1 2 1],
     [0 2 3]]
‘src’ = 0, ‘dest’ = 2.

There are two possible paths, that is to go from node-0 to node-2 directly, which will take 2 units of effort, or go from node-0 to node-1 and then node-1 to node-2, which will take 1 unit of effort.

You have been given two arrays, 'AT' and 'DT', representing the arrival and departure times of all trains that reach a railway station.

Your task is to find the minimum number of platforms required for the railway station so that no train needs to wait.

Note :

1. Every train will depart on the same day and the departure time will always be greater than the arrival time. For example, A train with arrival time 2240 and departure time 1930 is not possible.

2. Time will be given in 24H format and colons will be omitted for convenience. For example, 9:05AM will be given as "905", or 9:10PM will be given as "2110".

3. Also, there will be no leading zeroes in the given times. For example, 12:10AM will be given as “10” and not as “0010”.

You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a square matrix of order 'N' * 'N' where the cells with value 0 represent the maze’s blocked locations while value 1 is the open/available path that the rat can take to reach its destination. The rat's destination is at ('N' - 1, 'N' - 1). Your task is to find all the possible paths that the rat can take to reach from source to destination in the maze. The possible directions that it can take to move in the maze are 'U'(up) i.e. (x, y - 1) , 'D'(down) i.e. (x, y + 1) , 'L' (left) i.e. (x - 1, y), 'R' (right) i.e. (x + 1, y).

Note:

Here, sorted paths mean that the expected output should be in alphabetical order.

For Example:

Given a square matrix of size 4*4 (i.e. here 'N' = 4):
1 0 0 0
1 1 0 0
1 1 0 0
0 1 1 1 
Expected Output:
DDRDRR DRDDRR 
i.e. Path-1: DDRDRR and Path-2: DRDDRR

The rat can reach the destination at (3, 3) from (0, 0) by two paths, i.e. DRDDRR and DDRDRR when printed in sorted order, we get DDRDRR DRDDRR.

You have been given an array/list ‘ARR’ consisting of ‘N’ positive integers. Your task is to return the Next Greater Element(NGE) for every element.

The Next Greater Element for an element ‘X’ is the first element on the right side of ‘X’ in the array 'ARR', which is greater than ‘X’. If no such element exists to the right of ‘X’, then return -1.

For example:

For the given array 'ARR' = [7, 12, 1, 20]

The next greater element for 7 is 12.
The next greater element for 12 is 20. 
The next greater element for 1 is 20. 
There is no greater element for 20 on the right side.

So, the output is [12, 20, 20, -1].

What are semaphores? (Learn)
Follow-up questions - 
What is the critical section problem? (Learn)
Code it with a multithreading program. (Learn)
What is thread? What is process? Differences between them. (Learn)
Execution flow in a multithreaded program, with preemption and critical section problems happening. And how semaphores are helping to overcome this problem.

Other methods to solve critical section problems -  
Locking Mechanism (With pseudo code) (Learn)
Mutex. What is it? Semaphore vs mutex (Learn)

He asked me for some system calls like a fork.  (Learn)
And some basic Linux commands.

What is Dynamic Programming? Explain with an example. (Learn)

Ninjas are often known for their stealth execution and accuracy to get the job done right. While honing their art of moving through dense forests stealthily, they need the maximum number of continuous trees one after the other for practicing.

Trees are represented by 1s and empty places by 0s (basically a binary representation of a given integer). You are also given an extra tree which you can plant at any empty place (i.e. you can flip one of the zeroes in the binary representation to 1). The tree should be planted such that the maximum number of consecutive trees is maximized.

Your task is to report the maximum number of consecutive trees after plantation.

Note:

You may also choose not to plant that extra tree at all.

For Example:

Input: 54
Output: 5

The binary representation of 54 is 110110.
After flipping the third bit from the left, we get consecutive 5 bits. i.e. 111110.

He choose my Android Project to have a indepth discussion (Android chat application using end-to-end encryption using AES).
He asked me to present the code, i opened android studio, with my screen being presented.
I explained the folder structure, and how everything is working, and how we are interacting with the database (Firebase).
Then he asked on what basis we are fetching the user list, and i also showed the data stored (in Firebase console).
Then he asked about the encryption part, why we are doing it.

Then he saw that, i was storing the chat data, twice in the database, on in the room for sender and one for the receiver. Basically i was concatenating the user IDs to create room , so there were two rooms created, 

He asked me to change the logic so that, chat gets stored once only, so i had to create a common room, such that both sender and receiver can fetch the chat details. To create a common room for both users, i used character by character ASCII sum of both user IDs, so it will be common on both sides, and chat data can be fetched from the database using a common Room ID.