Final TopCoder 2003 Test Questions

Print-friendly Version

Problem Statement - DQuads (Easy)

We have a list of airline flights (directed edges between two nodes in a graph), and want to determine how many distinct directed quadrilaterals (directed cycles of length 4, which contain 4 distinct nodes) there are in the flight graph such that the nodes on opposite corners of the quadrilateral are not connected in either direction. Thus, we would count the graph on the left, but not the one on the right (the diagonal edge can be directed either way, or both ways - it doesn't matter):

      o--->o      o--->o
      ^    ^      ^\   ^
      |    |      | \  |
      |    v      |  \ v
      o<-->o      o<-->o
 

You will be given a String[] flights representing the flights. Element i of flights is a single space delimited list of integers (without extra leading 0's or leading/trailing spaces), where each integer j in the list indicates that there is an edge from i to j. An integer, j may appear more than once in element i meaning that there are multiple flights from i to j, each of which should be considered distinct. However, regardless of how many flights there are from one node to another, a quadrilateral must contain exactly 4 distinct nodes. Two quadrilaterals are considered distinct if and only if the sets of flights that they use are distinct. Thus, there may be many quadrilaterals that use the same four nodes, but different edges. Your task is to write a class DQuads, with a method count, which returns the total number of distinct quadrilaterals.

Problem Statement - Robot (Medium)

A very simple robot moves in a random cardinal or diagonal direction (cardinal directions are north, south, east and west, and diagonal directions are north-east, north-west, south-east, and south-west) each timestep. Thus, the robot has a 12.5% chance of trying to move in each of 8 directions. If the robot moves in a diagonal direction, it moves one unit left or right, and then one unit up or down (both in the same timestep), depending on the direction. If the robot moves in a cardinal direction, it moves 1 unit in that direction. Given a String[], floor representing a bird's eye view of the floor, you are to determine the probability that the robot will end up at location (x,y) after time timesteps. You should return the probability as truncated parts per 1000. In other words, if act is the actual probability, return (int)(act*1000). Each character in floor represents one square unit of the floor and is an 'X', an 'R' or a '.', representing an obstacle, a robot, or an open floor, respectively. There is only one robot, and if it attempts to move into a square occupied by an obstacle, or it attempts to move diagonally when there is an obstacle in either of the locations that it is moving between it instead does not move. More specifically, the robot may move diagonally, if and only if the locations that it moves between and to are clear. Also, the robot can not move outside of the floor. In other words, consider floor to be surrounded by obstacles. Location (x,y) is represented by character x of element y of floor.

Problem Statement - SkewTree (Hard)

In a binary tree, every node has an optional left, and optional right child node. A BST (binary search tree) is a binary tree that satisfies the following properties:

1. Every node has a unique value
2. The value at a given node must be greater than the value at every node in its left subtree
3. The value at a given node must be less than the value at every node in its right subtree

The depth of a node in a BST is defined as such:

1. The top node (root) has depth 0
2. Every node has depth 1 higher than its parent

Usually, when given a list of distinct values, it is best to build a balanced binary search tree - a tree where the size of the left subtree is approximately the same as the size of the right subtree at each node. A balanced tree isn't always the best solution though. Given a int[] values of distinct values and a int[] probs containing the percentage chance of each element being accessed, your method will return the best (lowest) access score achievable by a BST containing the given values. The access score of any BST is computed by adding together the access scores for all of its nodes. The access score for a particular node is calculated by the formula p*(d+1) where p is the probability of that node being accessed, and d is the depth of that node in the tree.