aascrivener
BAN USER
Comments (3)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote
First, transform the list of commands into a single command. (E.g. go forward 1, turn around, go back one turns into "turn around")
If this command has 0 movement, then we can build a wall. If the command has nonzero movement and the bearing changes, then we can also build a wall. (Draw some pictures to see why this is. For example, if the bearing changes 90 degrees, the robot will draw a box. If it changes 60 degrees, it draws a triangle. It creates more complicated shapes for bearing changes that do not divide 360, but it will still create a contained shape. It may never even reach its original point).
If the command has nonzero movement and no bearing change, it will draw a straight line to infinity and thus no box can contain it.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Test
- aascrivener July 23, 2016Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
You can do this without mergesort.
- aascrivener July 24, 20161. For each number, make a new object storing that number and its index, and put them into another array
2. Sort this array according to the value of the objects.
3. Starting from the end, maintain a binary index tree storing the (original) indices. (By calling update(i, 1))
4. As we go along, find the number of (original) indices that we have seen that are greater than our current (original) index (log n using binary index tree, just compute sum(idx+1,n))
5. Keep a max value, updating it as we go.
O(nlogn) time, O(N) space. If we use out original array for the binary index tree, we only need one extra size n array.