RocketFuel Codesprint at IIT-Bombay

Rocketfuel is a targeted digital advertising company. It offers the profile of Rocket Scientist, which involves doing work related to AI, Machine Learning and Big Data Analytics. The work location was Redwood City, California. Following questions were asked at Rocketfuel's codesprint for placements at IIT-Bombay. The interface used was InterviewStreet and the total duration of the sprint was 4 hours. 

Problem #1
In this problem your goal is to write a program to examine the outputs from a sequence of operations on a data structure called a single-output deque, and deduce the sequence of operations that produced that output.

An ordinary deque is data structure that represents a list and supports the following four operations:
pushFront(x): add x to the beginning of the list so that it becomes the first element of the list
pushBack(x): add x to the end of the list so that it becomes the last element of the list
popFront(): remove and return the first element of the list
popBack(): remove and return the last element of the list

In this problem, we are considering the behavior of a single-output deque, which is the same as a deque except that it supports only pushFront, pushBack, and popBack.
Furthermore, we modify pushFront and pushBack so that they do not accept an argument. Instead, pushFront and pushBack push the contents of a counter (whose initial value is 1) to the beginning or end of the deque and increment the counter.

Consider the following examples:
(pushBack, pushBack, pushFront) results in the following sequence of list states:
(1)
(1, 2)
(3, 1, 2)
(pushFront, pushFront, pushBack, popBack, pushBack, popBack) results in the following sequence of states and outputs:
(1)
(2, 1)
(2, 1, 3)
(2, 1) output: 3
(2, 1, 4)
(2, 1) output 4
In the previous example, the output of the entire sequence of operations can be written as (3, 4).
Your program will receive exactly one line of input, a comma-separated list of integers with no spaces in the following format:
x_1,x_2,...,x_N
where 1 <= N <= 100,000 and the sequence (x_1, x_2,..., x_N) is a permutation of the set of integers {1, 2,..., N} (i.e., the sequence is not empty, and there are no repeated or missing values).
Your program should produce exactly one line of output, a comma-separated list of operations with no spaces in the following format:
op_1,op_2,...,op_2N
where each op_i is a string from the set {pushFront, pushBack, popBack}. The output of the sequence of operations (op_1, op_2,..., op_2N) should be the sequence (x_1, x_2,..., x_N). If it is not possible to produce the output (x_1, x_2,..., x_N) with any sequence of single-output deque operations, simply print the string “impossible”. If there are multiple sequences of operations that result in the sequence received in the input, choose the output that is smallest lexicographically, ordered by standard alphabetical ordering.

Sample Testcases
Input:
3,2,1
Output:
pushBack,pushBack,pushBack,popBack,popBack,popBack

Input:
1,2,3
Output (note choice of pushBack over pushFront):
pushBack,popBack,pushBack,popBack,pushBack,popBack

Input:
4,1,5,2,3
Output (pushFront is needed in some cases):
pushBack,pushFront,pushFront,pushBack,popBack,popBack,pushBack,popBack,popBack,popBack

Input:
5,1,4,2,3
Output (some sequences are impossible):
impossible

To help with solving this problem in a timely manner, we provide the following hints that may help you work out one way of writing an efficient program to solve this problem:
1. Note that if the first element of the input sequence is 4, then the 5th element of the output must be popBack (unless the output is impossible). The reason for this is that at least 4 pushes must be executed to get 4 into the deque, and the 4th push must be a pushBack so that 4 is ready to be popped from the back of the deque. More than 4 pushes could be executed, but elements 5 and above must be pushed to the front, and this could easily be done after 4 was popped instead of before. Since popBack is lexicographically smaller than pushFront, we prefer to execute popBack as early as possible.
2. Consider simulating the deque as a way to efficiently determine which operations were performed on it. For example, as above, if the first element of the input is a 4, simulate a deque having the elements 1 through 4 pushed into it. Since you do not know whether each element was pushed to the front or the back, try pushing it on both sides and figuring out which side is correct later in the simulation.


Problem #2
After venturing into deep space to use your computer science skills on various projects at the frontier of civilization. You are abducted by the mafia, who had placed a losing bid for some contracts you won. Fortunately, you were able to hide your earnings in a secret location before you were taken away to the mafia headquarters to be questioned.

The mafia headquarters is situated on a space station orbiting the planet, and this particular space station houses a large zero-gravity amusement park. A single guard begins escorting you to the questioning room, and you quickly strike up a conversation. As you are walking past the arcade, the guard claims to be the top pinball player on the station, so you offer a challenge. If you can beat the guard in a single game of pinball, the guard will let you go, and if you lose, you will tell the guard where you stashed the money you received for the irrigation project on the planet below.

The guard accepts your challenge, but you now have another problem. You've never played the particular type of pinball that is played on the station, so you have to quickly learn how to play optimally so that you can achieve a higher score than the guard. Pinball games in this arcade have the following format. You can place a ball anywhere inside the rectangular playing area of the pinball machine and then bump the ball so that it travels in any of the 45 degree diagonal directions. You then allow the ball to bounce around the machine and the ball crosses over various lights that are situated randomly around the board. The goal is to cross as many lights as possible.

"This game isn't too difficult", you think, but the guard then explains that you are allowed to bump the ball one additional time, potentially changing the ball's direction, again in one of the 4 diagonal directions on the board. Thus, your strategy for the game, given the size of the board and the position of the lights, is to choose a starting position, starting direction, bump time, and bump direction so as to maximize the number of lights you cross.

Note that you can only get points for crossing each light once, so the game is over after you have bumped the ball twice (once to start, and once to redirect the ball) and it is clear that the ball will not cross any additional lights even if it is allowed to roll indefinitely. Further, the machine is frictionless and experiencing zero-gravity, so the ball travels in a straight line until it hits one (or two, simultaneously) sides of the rectangular pinball board in a perfectly elastic collision. You can only place the ball at integral coordinates on the board, and you can only bump the ball at integral coordinates.

Since you are an expert computer scientist, your job is to write a program to help you play optimally. Your program should accept input of the following form:

N M K

X1 Y1

X2 Y2

.

.

.

XK YK

where N is the number of rows on the pinball board, M is the number of columns on the pinball board, and K is the number of lights that are placed on the board. The values Xi and Yi represent, respectively, the row and column of the the ith light on the pinball board (0-indexed). Your program should simply output the number of lights that can be crossed using an optimal strategy. For example, the following input:

5 5 4

0 2

0 3

2 2

3 1

represents the following board:

..@@.
.....
..@..
.@...
.....

where each '@' symbol represents a light and each '.' symbol represents space in the interior of the pinball board. For this board, it is possible to cross up to 3 lights, depending on your strategy, so your program should output one line consisting of the number 3. For example, you could start the ball in the upper-right corner at position (0, 4) and then bump the ball up and to the left at position (3, 1) so that your ball follows the following pattern (the 1-indexed timestamp corresponding to the first time a position is reached by the ball is indicated by a single hexadecimal digit -- A == 10 and B == 11):

..7@1
.6.2.
5.3.9
.4.A.
..B..

You may assume that the input will be well-formed, so that the line N M K is followed by exactly K lines, each of which consists of a distinct ordered pair of integers Xi and Yi, such that 0 <= Xi < N and 0 <= Yi < M. All values on a single line will be separated by a single space. The values of N and M can be as large as 1600 and K can be as large as min(N * M, 10000). Points can be earned for test cases of increasing size up to the stated bounds.

Problem #3
Suppose you are a fan of auto-racing and want to figure out which drivers are likely to perform well in an upcoming race. Luckily you have access to a log of the times that each racer started and finished their test race the day before.

The particular rating algorithm you have chosen is to assign each racer R a score that equals the number of other racers who both started after R started and also finished before R finished.

Note that a lower score generally suggests that the racer is faster, and this rating algorithm keeps from penalizing fast racers who have slow times simply because they are stuck behind a crash or slow racer. Additionally, this rating algorithm does not reward fast racers who pass tons of slow racers in comparison to fast racers who race when there are not many slow racers on the track to pass (compare this with rating a racer based on the net number of passes).

More formally, you want to write a program that will read the test race log from standard input. The first line of the log contains a single integer n from 0 to 70,000 that represents the number of racers in the log. The next n lines of the test race log have the following format:

racerId startTime endTime

where racerId is an integer in the range [0,10^9] and startTime and endTime are both integers such that 0 <= startTime < endTime <= 10^18. Each racerId will be distinct. Also, the collection of all start and end times will not contain any duplicate elements.

Given such an input, you should print output in the following format:

racerId score

where score is the score as defined above for racer racerId. The output lines should be sorted in ascending order ofscore with ties broken by sorting by racerId, also in ascending order. This can be accomplished with a simple sort at the end.

Directions:

Please code this problem in Java, C, or C++. Your solution should run in less than O(N^2) on all inputs.

Hint: The naive brute force solution is too slow to run within the time limit. You will need to think of a faster solution. Specifically, we are looking for a solution that is guaranteed to be less than O(N^2) on all inputs. One possible way to accomplish this (there are several other acceptable methods) is to use a data structure with K buckets (e.g., K = 300), each of which is initially empty and is defined by two times. Each bucket  will eventually contain racers whose start time falls between the two times. The bucket boundaries should be chosen such that they ultimately will contain the same number of racers. Then iterate through the racers in end time order and, as you iterate over each racer, build up this bucketed data structure in such a way that you can use it to quickly count the number of racers that finished before him but started after him.

What We Are Looking For:

For this problem, we simply want to see that you can implement the algorithm correctly, without particular regard to principles of object orientation or modularity.  Do give us at least minimal documentation to help us understand what you are trying to accomplish in certain key places of the algorithm.

Sample Testcases 

input:

5

2 100 200

3 110 190

4 105 145

1 90 150

5 102 198

output:

3 0

4 0

1 1

5 2

2 3

Note in the above example that racer 3 has a score of 0 because no one starts after racer 3 (a drawback to this scoring system is the last racer always has a score of 0). Racer 4 also has a score of 0 because the only racer who starts after racer 4's start time (racer 3) has a later finish time. Racer 3 is listed ahead of racer 4 despite having a slower time because racer 3's id is lower. At the other end, racer 2 has a score of 3 because racers 3, 4, and 5 start after racer 2 and finish before racer 2 finishes.