SDE - 1

You have been given a grid containing some oranges. Each cell of this grid has one of the three integers values:

Value 0 - representing an empty cell.

Value 1 - representing a fresh orange.

Value 2 - representing a rotten orange.

Every second, any fresh orange that is adjacent(4-directionally) to a rotten orange becomes rotten.

Your task is to find out the minimum time after which no cell has a fresh orange. If it's impossible to rot all the fresh oranges then print -1.

Note:

1. The grid has 0-based indexing.
2. A rotten orange can affect the adjacent oranges 4 directionally i.e. Up, Down, Left, Right.

Alice always loves to visit her garden and collect apples. The garden can be represented in the form of ‘N’ * ’N’ grid say ‘MATRIX’, where each cell of the grid can have one of the possible values:

1 -> The cell contains an apple that Alice can pick up and pass through it.

-1 -> The cell contains a bush and Alice can not visit this cell.

0 -> The cell is empty and Alice can pass through it.

Alice is present at the top left corner of the matrix or we can say at point (0,0).

Alice has to reach the bottom right corner of the matrix (‘N’-1,’N’-1) and return back to the starting point (0,0).

1. After picking an apple the cell will become empty.

2. While going towards the bottom right corner, Alice can either move Right or Down at each step.

3. While going towards the top left corner, Alice can either move Left or Up at each step.

4. If there is no path from (0,0) to (‘N’-1, ‘N’-1) then Alice will not pick any apple.

Your task is to help Alice to collect the maximum number of apples during her journey.

For example:

If the given matrix is :
[1, 1, -1, 1]
[1, 0, 1, 1]
[1, 1, 0, 1]
[0, -1, -1, 1]

One of the possible ways to collect maximum apples is :

Path for going towards bottom right corner: 
(0,0) -> (0,1) -> (1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3)

Apples collected are equal to 6.

Path for going towards top left corner:
(3,3) -> (2,3) ->(2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0)

Apples collected are equal to 3.

So Alice can collect a maximum of 9 apples.

The n-th term of Fibonacci series F(n), where F(n) is a function, is calculated using the following formula -

    F(n) = F(n - 1) + F(n - 2), 
    Where, F(1) = 1, F(2) = 1

Provided 'n' you have to find out the n-th Fibonacci Number. Handle edges cases like when 'n' = 1 or 'n' = 2 by using conditionals like if else and return what's expected.

"Indexing is start from 1"

Example :

Input: 6

Output: 8

Explanation: The number is ‘6’ so we have to find the “6th” Fibonacci number.
So by using the given formula of the Fibonacci series, we get the series:    
[ 1, 1, 2, 3, 5, 8, 13, 21]
So the “6th” element is “8” hence we get the output.

You have been given a non-empty grid consisting of only 0s and 1s. You have to find the number of islands in the given grid.

An island is a group of 1s (representing land) connected horizontally, vertically or diagonally. You can assume that all four edges of the grid are surrounded by 0s (representing water).

He then asked me practical applications of data Structures like Trie, BST, Map, Stack etc line by line

He asked me to Design a Threadpool.

He asked me questions from Virtual memory, threads, locks, semaphores etc

He asked questions about polymorphism and asked to code an example

He asked me to design a Vector class

He asked me 2 standard puzzles of 25 horses and 2 ropes

He asked me general questions about my future plans and expectations from the company