SDE - 1

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.

You must implement the Stack data structure using a Singly Linked List.

Create a class named 'Stack' which supports the following operations(all in O(1) time):

getSize: Returns an integer. Gets the current size of the stack

isEmpty: Returns a boolean. Gets whether the stack is empty

push: Returns nothing. Accepts an integer. Puts that integer at the top of the stack

pop: Returns nothing. Removes the top element of the stack. It does nothing if the stack is empty.

getTop: Returns an integer. Gets the top element of the stack. Returns -1 if the stack is empty

You are given a Singly Linked List of integers. Return true if it has a cycle, else return false.

A cycle occurs when a node's next points back to a previous node in the list.

Example:

In the given linked list, there is a cycle, hence we return true.

You are given a single non-negative integer ‘N’ who’s binary representation consists of a single ‘1’ digit and the rest of the digits are ‘0’s. Your task is to find the position of the only ‘1’ digit. In other words, your task is to find the position of the only set bit in the binary representation of the input integer ‘N’.

The position of the set bit must be counted from the LSB (Least Significant Bit) end of the Binary number. If the count of set bits in the Binary number is not equal to 1, then your function should return ‘-1’ as output.

Example:-

INPUT   : N = 4
OUTPUT  : 3

In the above example, N = 4, whose Binary representation is “0100”. It is clearly visible that the binary number contains a single set bit, at a position 3 from the LSB end. Hence the output is 3

INPUT : N = 8
OUTPUT: 4

In the above example, N = 8, whose Binary representation is “1000”. It is clearly visible that the binary number contains a single set bit, at a position 4 from the LSB end. Hence the output is 4

INPUT   : N = 9
OUTPUT  : -1

In the above example, N = 9, whose Binary representation is “1001”.  Now, the binary number contains 2 set bits, at a position 4 and 1 from LSB end. Hence the output is -1.

INPUT   : N = 0
OUTPUT  : -1

In the above example, N = 0, whose Binary representation is “0000”.  Now, the binary number contains no set bits at all. Hence the output will be -1.

You are given an array of integers 'ARR' of length 'N' and an integer Target. Your task is to return all pairs of elements such that they add up to Target.

Note:

We cannot use the element at a given index twice.

Follow Up:

Try to do this problem in O(N) time complexity. 

What is Priority Inversion?

What happens when you boot your system?

What is an IP address and how many bits are required to represent an IP address?

Tell me about yourself.
Why do you want to join Cisco?
What are some products of Cisco that you know?
Who are the competitors of Cisco?
Then, she asked my location preference and told me about the CTC breakup.