SDE - Intern

You’re given an array/list 'ARR' of N elements, where each element is at most K away from its target position(Position if the array was sorted). Now, your task is to devise an algorithm that sorts the given array in O(N log K) time.

For example:

Let us consider 'K' is 3, an element at index 4 in the sorted array, can be at indexes 1, 2, 3, 4, 5, 6, 7 in the given array, because the absolute difference of all these indices with 4 is at most 3.

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).

You have been given a binary tree consisting of ‘N’ nodes where nodes have distinct integer values. Your task is to convert the given Binary Tree to a Binary Search Tree(BST).

Note: The conversion must be done in such a way that keeps the original structure of the Binary Tree.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees. 

For Example:

For the given binary tree :

The BST will be:

Note: Each node is associated with a unique integer value.

Initially we had a lengthy discussion (30 minutes) about my projects and then later on about OS, where we talked about Semaphores and Mutexes and mutual exclusion along with topics like race conditions and DBMS types, this was more of just a conversation and not really questions, I felt like the interviewer was trying to gauge my knowledge of the subjects and didn't dive deep into any topics. 

We then progressed to a system design question. Design an online book reader system.

You and your friend met after a long time and decided to have candies. You brought ‘X’ candies while your friend brought ‘Y’ candies. Since you both were bored you decided to play a game where each of you will play one by one and you will start first. The game goes as follows :

In the ith move, the person will give i candies to the other person.

The person who is unable to donate the required amount of candies will lose. You are required to find out who will win the game.

For Example:

For X = 1, Y = 2 the game goes as follows - 

You will donate 1 candy. So you now have 0 and your friend has 3 candies.

Your friend will donate 2 candies. So you now have 2 and your friend has 1 candy.

You are required to donate 3 candies but you only have 2 candies.

Hence your friend wins.