Summer 2015 Internship
Programming Challenge

UPDATE: The programming challenge has been extended. Submissions will be received until 5:00PM EST on Monday, February 9, 2015


Usually when an international call is placed, the carrier cannot connect your call directly from the origin to the endpoint. Instead, the service provider must forward the call to another carrier or even a series of carriers, which may then also require passing the call along to additional carriers and so on until the call is finally connected to its destination. This is not free of course and there is a cost associated with maintaining a connection along each leg of the call path. As you may have noticed, carriers usually charge customers a flat rate for connecting to a given destination country. However, because of the existence of many routing options and constant changes in rate agreements between carriers, it is important for carriers to always build the most advantageous call plans in the interest of maximizing their respective margins. Your assignment will be to write scripts that will construct such call plans for a set of test cases.

Assume the following:

  • Telephone numbers are string values presented in [E.164 format](http://en.wikipedia.org/wiki/E.164) (i.e. ‘+15552876649’)
  • Carriers keep a rate table, R, such that R[c1,c2] = r12, where c1 and c2 are carrier names and r12 is the connection rate between them.
  • All carriers have a function called carrier_lookup(), which takes a phone number string as its only parameter and returns the service provider, carrier, for a legal and in-service telephone number, else it returns a null value as defined by their own respective infrastructures.

Input Format:

The single input file will contain several Test cases. Each test case is defined by: one line delimited by spaces containing the number of rows, N, followed by the column headers; another space delimited line with the number of columns, M, followed by the row headers; and N lines, one per each row of the Matrix, containing the rate values separated by spaces. Terminate the input with (no. of rows) N=0. Let ‘*’ denote that there is no rate agreement between two pairs of carriers.You may assume that there are no negative values and that the given adjacency matrices will be symmetric. Headers represent fictional carrier names. Input files may be encoded as UTF-8.

Example Input File:

* 1 * 3 * *
1 * 6 5 1 *
* 6 * * 5 2
3 5 * * 1 *
* 1 5 1 * 4
* * 2 * 4 *
* 1 2 3 4 5
1 * * * * *
2 * * * * *
3 * * * * *
4 * * * * *
5 * * * * *


1. Write a function that maps the optimal call paths from a single carrier source to all possible carriers. For your output file, you need only evaluate the solution for the first carrier listed for a given test case.
2. Write a function that maps the optimal call path for all possible source-destination pairs. 
3. Let’s say a third party is attempting to fix carrier agreements and has the power to dissolve but not modify or create new agreements between carriers. Is there a way for that to make rate agreements and route calls such that the total costs across the entire network are minimized? If so briefly describe how this problem differs from the all-pairs problem stated above and implement an algorithm that will produce such a call path network from the input test case.

Output Format:

The outfile will contain solutions to each solved test case. A single solution to a test case will always be a square adjacency matrix, where the cell value is the minimum connection cost between two carriers along the network of call paths specified by the respective problem. The output format for such a solution is defined by one line delimited by spaces containing 4 space-delimited values: the test case number, the problem number, the number of rows, M, and the number of columns N. This line will be followed by M lines, one per row of the solution matrix, containing the rate values separated by spaces. Terminate the output file with the starting input line as ‘0 0 0 0′. Let the character ‘*’ denote that there is no call path link between two pairs of carriers. Assume there will be no negative values.

The following is an valid example of an output file containing a single solution to the first test case in an input file and answering the third problem. The solution is a 6×6 matrix of values:

2 3 6 6
* 1 * * * *
1 * * * 1 *
* * * * * 2
* * * * 1 *
* 1 * 1 * 4
* * 2 * 4 *
0 0 0 0

Submission Format:
Your responses may vary in implementation but you must include, at minimum, a /src directory containing any source files you may have produced and a README file with a brief writeup describing your approach to each problem and any challenges you may have encountered while implementing your solution.

Entry submissions are permitted in the following languages: Python, Java, C, C++, Ruby.

Please submit a compressed file following with the directory structure:


Good Luck! 

Submit Your Answer

Loading posts...