MoPub

Coding Challenges

1. Mo’s Revenge

An angry bird named Mo is flying a long journey to exact his revenge on the pigs. To save energy for the fight, the bird will take advantage of jet streams that will lower his flying energy consumption. Before the flight, BirdHQ gave the bird an input file in the following format:

1. First line contains only 1 integer, which is the constant energy it takes to fly 1 mile WITHOUT jet streams.
2. Every subsequent line contains 3 space-separated integers: the start mile marker of the jet stream, the end mile marker of the jet stream, and lastly an integer denoting the overall energy needed to fly that jet stream’s distance.

For instance, the line “3 7 12″ means it takes 12 energy units to fly the 4 miles between miles 3 and 7.

Note that jet streams can overlap, but the bird cannot be on more than one jet stream at a time, and it cannot fly partial jet streams.

For simplicity, consider the end mile marker of the farthest jet stream as the end of the journey.

Write a python program that takes in an input file jetstreams.txt to plan out the optimal sequence of jet streams Mo should fly on to minimize his energy consumption throughout the entire journey. All integers in the input file are non-negative. As output, print out the mininum total energy and a list of tuples denoting the jet streams’ endpoints.

For example, given this sample jetstreams.txt, the minimum total energy needed to fly all 24 miles is 352 energy units, and the optimal sequence of jet streams is [(0,5), (6,11), (14,17), (19,24)].

Please send your finished python script to challenges@mopub.com

2. PrettyPrettyPrinting

Let’s play a game of PrettyPrettyPrinting. Given a string, you rearrange consecutive letters to form english words of length four or more. You may also skip letters between words. Valid english words are described in mowords.txt.

A properly formatted PrettyPrettyPrinting should capitalize the beginning of words and represent skipped letters with a “-”.

Your task is to write a script in python that takes a single string as an input and prints to stdout a single PrettyPrettyPrinting with the minimum number of skipped letters.

For example the input:
"cesaleomrnu" could result in:
"Scale-Mourn"

Any other PPP strings that contain one skip and would be equally valid.

For example:
"cesaleomrnu" could also result in:
"-EaselMourn"

However, the the input
"flokwnot" could not result in:
"FlowKnot" because the output uses letters that are not consecutive.

Here’s an example string to try:

"etaelehoyrnrsweeneiornvtsdelreiolrertsrhotruongpmghwsihlxtde
elaneeetldosheeralithtndareluttelderrocltaeiwrtodeoeyladfswp
sremeucraddfvrntaiansudynaeytnaidthioicheegblyoeielsvvneolii
wudveieuaoaodptetpurrdeieecnohasapiwdoehltflsbohlamthioeosistssbstwe"

The resulting PPP should contain less than 35 skips.

Send your finished python script to challenges@mopub.com