Technical : Phone Screen - CodePad (1 hour)

• 1 Design Question
• 1 Algorithmic Question

Q.1
Given a Map area and names of all metro/bus stations in that area, design an API that finds the ‘fastest path' from start location to end location.
You can only use the following transport modes:

1. Walk
2. Metro
3. Bus

APIs given:

getTransportMode(start, end)
Arguments:
start: station name
end: station name
Returns:
list of available transport options
Example:
[‘walk’, ‘m11’, ‘b22’]
Where
either letter m/b followed by a digit
m11 = metro number 11
b22 = bus number 22

getTravelTime(ModeOfTransport, start, end)
Arguments:
ModeOfTransport: Walk or name of bus/metro.
start: station name
end: station name
Returns:
a positive integer for a valid argument and NULL for an invalid argument.
Example: if there is a direct bus/metro from point A to point B, the API will return the time taken to get there but if there is no direct bus/metro from point A to point B then the API will return NULL.

Q.2
Given a sum of elements (n) and a number of elements (k), find the number of distinct arrays under these conditions:

In each array, the there are k elements whose sum is equal to n.
In each array, each element should be greater than or equal to the element on its left.
The elements formed in each array are distinct

Note: elements have to be positive integers
Example:
n = 8 k = 4
Answer: 5
Explanation: [1,1,1,5], [1,1,2,4], [1,1,3,3], [1,2,2,3], [2,2,2,2]
Each array has 4 (k) elements a sum of 8 (n) with each element on the left <= element on the right.
There are 5 possible distinct solutions.