SDE - Intern

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.

How to Measure 45 minutes using two identical wires?

Ninja loves playing with numbers. One day Alice gives him some numbers and asks him to find the Kth largest value among them.

Deadlock
Virtual Memory
Paging
Segmentation
Fragmentation

Internal working of a Hashmap

Computer networking concepts were asked in detail ranging from hardware devices to different protocols.

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

Can you solve this problem in O(N) time and O(1) space complexity?

Company related questions like Cisco products, CEO, competitors, stipend, relocation
etc.