SDE - 1

There is a chessboard of dimensions 15 X 15, and Alice and Bob start playing a game on it. The game is not chess, and involves just one coin.

The coordinates of the top left cell are (1,1) and the bottom right are (15,15). The coin is initially at (x,y). In each turn, the player whose turn it is can move the coin to any of the four cells (provided they are inside the board):

(x-2,y+1)
(x-2,y-1)
(x+1,y-2)
(x-1,y-2)

The figure below shows the possible moves of a coin at (5,4) (An 8 x 8 board is given in the image, but in the problem, it will always be a 15 x 15 board).

Alice makes the first move. Both Alice and Bob take alternate turns and move until it is not possible to move the coin anymore. The player unable to make a move loses.

For example:

If there is a coin at (1,1), Bob wins the game as Alice can make no move to start the game.

You are given a list of ‘N’ jobs which are to be performed. Each job can be characterized by three parameters-

• Start Time, denoting the start time of the job.
• End Time, denoting the end time of the job.
• Profit associated with the job.

You are required to schedule the jobs in such a way that total profit will be maximized.

Note: Only one job can be scheduled at a time, and jobs can be scheduled at only integer moments of time greater than or equal to one.

For example-

Let there be three jobs ‘A’, ‘B’, and ‘C’-
• Start time, End time and profit associated with job ‘A’ being 1, 1 and 30.
• Start time, End time and profit associated with job ‘B’ being 1, 2 and 40.
• Start time, End time and profit associated with job ‘C’ being 3, 4 and 30.

We will perform job ‘B’ at time t = 1 and job ‘C’ at time t = 3. The total profit will be 70. There is no other sequence of jobs which can fetch us a better overall profit. 

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

1. Push(num): Push the given number in the stack.
2. Pop: Remove and return the top element from the stack if present, else return -1.
3. Top: return the top element of the stack if present, else return -1.
4. getMin: Returns minimum element of the stack if present, else return -1.

For Example:

For the following input: 
1
5
1 1
1 2
4
2
3

For the first two operations, we will just insert 1 and then 2 into the stack which was empty earlier. So now the stack is => [2,1]
In the third operation, we need to return the minimum element of the stack, i.e., 1. So now the stack is => [2,1]
For the fourth operation, we need to pop the topmost element of the stack, i.e., 2. Now the stack is => [1]
In the fifth operation, we return the top element of the stack, i.e. 1 as it has one element. Now the stack is => [1]

So, the final output will be: 
1 2 1

You are given two LinkedList of length ‘N’. Your task is to insert the elements of the second LinkedList in the first LinkedList at the alternate positions.

For example: Let 1 -> 3 -> 5 be the first LinkedList and 2 -> 4 -> 6 be the second LinkedList. Then after merging the first LinkedList will look like 1 -> 2 -> 3 -> 4 -> 5 -> 6.

1. Where do you see yourself after 5 years?

2. Strengths and weakness?