SDE - 1

You have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix.

Your task is to find the length of the shortest path from the source cell to the destination cell only consisting of 1s. If there is no path from source to destination cell, return -1.

Note:

1. Coordinates of the cells are given in 0-based indexing.
2. You can move in 4 directions (Up, Down, Left, Right) from a cell.
3. The length of the path is the number of 1s lying in the path.
4. The source cell is always filled with 1.

For example -

1 0 1
1 1 1
1 1 1
For the given binary matrix and source cell(0,0) and destination cell(0,2). Few valid paths consisting of only 1s are

X 0 X     X 0 X 
X X X     X 1 X 
1 1 1     X X X 
The length of the shortest path is 5.

You have been given a Singly Linked List of integers, determine if it forms a cycle or not. If there is a cycle, remove the cycle and return the list.

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

Given a integer array nums of length ‘N’ and an integer ‘K’, return the number of pairs ‘(i, j)’ such that:

1 <= ‘i’ < ‘j’ <= ‘N’ and ‘nums[i] * nums[j]’ is divisible by ‘K’.

EXAMPLE :

‘N’ = 5, ‘K’ = 4, ‘nums’ = [2, 6, 1, 7, 8]
Output: 5
Explanation: (1, 2), (1, 5), (2, 5), (3, 5), and (4, 5) pairs have their products divisible by K.

You are given an ‘N x N’ matrix ‘GRID’. Initially, every cell is locked, and ‘GRID[i][j]’ represents the time at which the cell at ‘(i, j)’ will unlock. You can move from one cell to another 4-dimensionally adjacent cell if and only if both cells are unlocked. You can move through infinite cells in zero time. Also, you cannot leave the boundaries of the grid.

If you start at the cell ‘(0, 0)’, what is the least time required to reach the last cell ‘(N - 1, N - 1)’.

Example:

‘GRID’ =

We cannot reach the cell ‘(2, 2)’ until the time is ‘5’. When the time is ‘5’, we move along the path: 
0 -> 1 -> 4 -> 3 -> 5

The cell with value ‘1’ will be unlocked when the time is ‘1’.
At time = 1: 0 -> 1

Similarly, the cell with value ‘4’ is unlocked when the time is ‘4’. At that time the cell with value ‘3’ will also be unlocked, as it unlocks at time ‘3’.    
At time = 4: 0 -> 1 -> 4 -> 3

The cell with value ‘5’ will be unlocked when the time is ‘5’.
At time = 5: 0 -> 1 -> 4 -> 3 -> 5

So, the least time to reach cell ‘(2, 2)’ is ‘5’.

Note:

1. All elements in the ‘GRID’ are unique.

2. ‘GRID[i][j]’ is a permutation of [0, 1, … , (N ^ 2) - 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 ‘Arr’ consisting of ‘N’ distinct integers and a positive integer ‘K’. Find out Kth smallest and Kth largest element of the array. It is guaranteed that K is not greater than the size of the array.

Example:

Let ‘N’ = 4,  ‘Arr’ be [1, 2, 5, 4] and ‘K’ = 3.  
then the elements of this array in ascending order is [1, 2, 4, 5].  Clearly, the 3rd smallest and largest element of this array is 4 and 2 respectively.

Design and implement a data structure which supports the following operations:

insert(X): Inserts an element X in the data structure and returns true if the element was not present, and false otherwise.

remove(X): Removes the element X from the data structure, if present. Returns true if the element was present and false otherwise.

search(X): Search the element X in the data structure. Returns true if the element was present and false otherwise.

getRandom(): Return a random element present in the data structure.

Four types of queries denote these operations:

Type 1: for insert(X) operation.
Type 2: for remove(X) operation.
Type 3: for search(X) operation.
Type 4: for getRandom() operation.

Note:

It is guaranteed that at least one element will be present in the data structure when getRandom() operation is performed.

Follow Up:

Can you implement every operation such that it works in O(1) time?