SDE - 1

You have been given an N*M matrix where there are 'N' rows and 'M' columns filled with '0s' and '1s'.

'1' means you can use the cell, and '0' means the cell is blocked. You can move in the 4 following directions from a particular position (i, j):

1. Left - (i, j-1)
2. Right - (i, j+1)
3. Up - (i-1, j)
4. Down - (i+1, j)

Now, for moving in the up and down directions, it costs you $1, and moving to the left and right directions are free of cost.

You have to calculate the minimum cost to reach (X, Y) from (0, 0) where 'X' is the row number and 'Y' is the column number of the destination cell. If it is impossible to reach the destination, print -1.

You are given an array 'ARR' of 'N' positive integers. You need to find the minimum number of operations needed to make all elements of the array equal. You can perform addition, multiplication, subtraction or division with any element on an array element.

Addition, Subtraction, Multiplication or Division on any element of the array will be considered as a single operation.

Example:

If the given array is [1,2,3] then the answer would be 2. One of the ways to make all the elements of the given array equal is by adding 1 to the array element with value 1 and subtracting 1 from the array element with value 3. So that final array would become [2,2,2]. 

You are given an Integer array ‘ARR’ and an Integer ‘K’.

Your task is to find the ‘K’ most frequent elements in ‘ARR’. Return the elements in any order.

For Example:

You are given ‘ARR’ = {1, 2, 2, 3, 3} and ‘K’ = 2. 

The answer will {2, 3} as 2 and 3 are the elements occurring most times.

A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.

Robot is given a task to clean a room. The room can be visualized as a matrix ‘ARR’ containing ‘N’ rows and ‘M’ columns. The cells of the room are denoted as:

1) Cells with a value of 0 indicate empty space in the room.
2) Cells with a value of -1 indicate an obstacle in the room.
3) Cell with a value of 1 indicates the starting position of the robot.
4) Cell with a value of 2 indicates the ending position of the robot.

In each move, the robot is only allowed to move to one of the four adjacent cells if it exists and is not occupied by an obstacle. Robot has to clean this room entirely. To complete this task his path must start from his starting cell and should visit all the empty cells (denoted by value 0) exactly once, and he should finally arrive at the ending cell. You have to find the number of all possible paths using which the robot can clean the room.

Note that the cells corresponding to the starting and ending position of the robot are never occupied by an obstacle. And starting and ending positions will always be in different cells.

For Example :

If ‘N’ = 3, ‘M’ = 3 and ‘ARR’ = [ [1, 0, 0], [0, 0, 0], [0, 0, 2] ]

Then the room is represented as:

The 2 unique paths are marked in the image above.
The first path is: (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2).

The second path is: (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (1, 1) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2).

Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list or null. The task is to create a deep copy of the given linked list and return its head. We will validate whether the linked list is a copy of the original linked list or not.

A deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List rather for each node in the original Linked List, a new node is created.

For example,

Random pointers are shown in red and next pointers in black.

You are given two strings 'S' and 'T' of lengths 'N' and 'M' respectively. Find the "Edit Distance" between the strings.

Edit Distance of two strings is the minimum number of steps required to make one string equal to the other. In order to do so, you can perform the following three operations:

1. Delete a character
2. Replace a character with another one
3. Insert a character

Note:

Strings don't contain spaces in between.