g********t
发帖数: 39 | 1 贡献刚做的online test，职位是Machine Learning related。
Question 1 / 2 (LaserMaze)
You are standing in a rectangular room and are about to fire a laser toward
the east wall. Inside the room a certain number of prisms have been placed.
They will alter the direction of the laser beam if it hits them. There
are north-facing, east-facing, west-facing, and south-facing prisms. If the
laser beam strikes an east-facing prism, its course will be altered to be
East, regardless of what direction it had been going in before. If it hits
a south-facing prism, its course will be altered to be South, and so on. You
want to know how far the laser will travel before it hits a wall.
INPUT
Your program must read the room description from standard input. The room
is represented as a character array. Each line of input from STDIN
represents a row of the array. The width and height of the array are the
width and height of the room. The characters inside the array denote the
placement of the prisms and the laser's starting position.
The number of rows and columns in the array will not be explicitly specified
in the input, so your program will have to keep reading from STDIN until
there are no more lines to read and determine the total number of rows and
columns based on the input. However, the number of lines of input will be
at most 50. Each line will contain the same number of characters.
The resulting character array will contain exactly one '@' character,
representing the laser's position in the room, and any number of characters
from the set {"^", "V", "<", ">", "-"}. The first four of these represent
prisms that are guaranteed to direct the laser in the direction in which
they are pointing. The "^" character directs the laser north, "<" directs
it to the west, and so on. The "-" character represents empty space.
OUTPUT
Your program should print to standard out a single string, terminated by a
newline, representing the distance that the laser will travel before hitting
a wall. For example, if the laser travels a distance of 14 cells before
hitting a wall, then your program should print the string "14" to STDOUT.
Your program should treat the "@'"symbol the same as the "-" character, that
is, as empty space. So the laser will pass through the original location
from which it was fired.
If the laser will get caught in an infinite loop, then your program should
print "-1" to STDOUT.
Directions:
Please make sure you choose the proper coding language, as directed by your
contact at Rocket Fuel who gave you the assignment. For applicants to back-
end groups, this will generally be JAVA, C++, or C. For applicants to
front-end groups, this will generally be Javascript. All else being equal,
our preference is for JAVA. For JAVA, you must name your main class
Solution or the code will not compile.
NOTE: If you download the attached .zip file of examples, and you are
running Windows, do not look at them using the windows program "Notepad",
because this will not show the carriage returns properly in the input files.
Look at them with WordPad. Each input file should consist of multiple
lines, each of the same length.
What We Are Looking For:
Whichever language you code in, please use best coding practices. We are
looking for clear, concise, well-documented, modular code that reflects good
design, object-oriented principles, and an understanding of appropriate
data structures. It is not enough to write code that is merely correct, or
even code that is merely terse and correct. We want to see code that is as
beautiful as you can make it according to your personal coding aesthetic.
Examples:
The following examples will help you understand what the input looks like,
and what proper corresponding output should look like.
Input:
@--
---
---
Output: 3
Input:
@-v
---
---
---
Output: 6
Input:
@-v-
----
--<-
Output: 7
Input:
@-v
---
-^<
Output: 8
Input:
@-v
->-
-^<
Output: 8
Input:
@-v
->v
-^<
Output: -1
*Note: Please see the hint under the directions for one way to solve the
problem. Only attempt an alternative solution if you are confident you can
get it working in time.
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 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 of score 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, C++, or Python (all else being equal,
we prefer Java). Your solution should run in o(N^2) time on all inputs (i.e.
, strictly less than O(N^2) -- a Theta(N^2) algorithm such as naive brute
force will not be fast enough -- please see http://en.wikipedia.org/wiki/Big_O_notation if you are not familiar with big-o, little-o, and Theta). A very fast Theta(N^2)-time implementation may pass all test cases, but please strive for better asymptotic performance as we review all submissions manually for code quality and asymptotic performance.
Hint: One possible way to achieve o(N^2) time (there are several other
acceptable methods) is to use a data structure with K buckets (e.g., K = 300
or some function of input size), each of which is initially empty and is
defined by two times. Each bucket will eventually contain racers whose start
times fall between the bucket's start and end time. The bucket boundaries
should be chosen such that they ultimately will contain the same number of
racers. You can now iterate through the racers in end time order and, as you
iterate over each racer, fill in the bucketed data structure such that you
can use it to quickly count the number of racers that finished before and
started after that racer.
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.
Example:
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.
不方便贴太久，一会儿需要的同学请站内信。。。 | a********y
发帖数: 1262 | |
|
