# Question 1

Click here to Practice

Submit Problem to OJ

## Hungry Rabbit

There is m*n table with a rabbit in one of the cell - rabbit is initiall at position [startR, startC] . rabbit is Hungry, want to eat something and crying. He is trying to come out of the table, rabbit is allowed to move to one of the four adjacent cells of a table, rabbit can move at most max no of moves(maxMoves).

Given integers m, n, maxMoves, startR, startC, return number of paths to move the rabbit out of the cell. The result might be very Large, return it using modulo 10^9+7

**Example 1**

Input m= 2, n = 2, maxMoves = 2, startR = 0, startC = 0

Output: 6

**Example 2**

Input m= 1, n = 3, maxMoves = 3, startR = 0, startC = 1

Output: 12

**Constraints:**

1 <= m, n <= 50

0 <= maxMove <= 50

0 <= startRow < m

0 <= startColumn < n

**Sample input**

```
1
4
3
0
1
```

**Sample output**

```
14
```

# Question 2

## OYO Expansion

**OYO** plans to expand its network by adding **n** new rooms numbered **0 to n-1** to your colony. You are given an expansion plan as a 0-indexed integer array **previousRoom** of length **n**, where **previousRoom[j]** indicates that you must build room **previousRoom[j]** before building current room j, and these two rooms need to be directly linked. Room **0** is built already, so **previousRoom[0] = -1**. When all the rooms are constructed according to the expansion plan, every room will be accessible from room 0.

You can only construct one room at a time, and connecting rooms are the only ones that allow you to move freely between them any room can be built as long as the previous room has already been built.

Returns the number of different orders in which all rooms can be built. Since the answer can be large, return it **modulo 10^9+7**

**Example 1:**

```
Input: n = 3
previousRoom[] = [-1,0,1]
Output: 1
Explanation: There is only one way to build the additional rooms: 0 --- 1 --- 2
```

**Example 2:**

```
Input: n = 5
previousRoom[ ] = [-1,0,0,1,2]
Output: 6
Explanation: The 6 ways are:
0 --- 1 --- 3 --- 2 --- 4
0 --- 2 --- 4 --- 1 --- 3
0 --- 1 --- 2 --- 3 --- 4
0 --- 1 --- 2 --- 4 --- 3
0 --- 2 --- 1 --- 3 --- 4
0 --- 2 --- 1 --- 4 --- 3
```

# Question 3

## War For Chocolates

Tuntun mausi challenged Hari and his team to solve a problem. Hari, Mohit and Sam are trying to solve this problem but are unable to do so. As you are a good friend of Hari, he asks for your help.

Given an array, For each element find the value of nearest element to the right which is having frequency greater than as that of current element. If there does not exist an answer for a position, then print '-1'.

Please help Hari and his team to solve this problem to get the Chocolates.

**Input** First line contains T denoting the no of test cases. First line of each test case contains N denoting the no of elements in array. Second line of each test case contains N integers (A1.......An) denoting the given array.

**Output** For each test case print space separated N numbers denoting the answer corresponding answer.

**Constraints**

*20 points*: T<=100 1<=N<=10^2 1=Ai<=10^2

*80 points*: T<=100 1<=N<=10^5 1<=Ai<=10^5

**Time Limit** 2.5 seconds

**Sample input**

```
3
10
1 3 7 2 5 1 4 2 1 5
5
1 1 1 1 1
6
1 1 2 2 2 3
```

**Sample output**

```
-1 2 2 1 1 -1 2 1 -1 -1
-1 -1 -1 -1 -1
2 2 -1 -1 -1 -1
```

not at all intuitive :(