Facebook Hacker Cup: Qualification Round

Studious Student

Published Jan 11, 2011 in facebook, hackathon, journal
Scroll

You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.


Input

As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.


Output

Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.


Constraints

1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10


This challenge is kind of tricky. It’s not any sorting of words, instead it’s called Lexicographical sort order. Pretty much sorting based on the rank of the alphabets.


For example:


facebook hacker cup for studious students
cupfacebookforhackerstudentsstudious


With the above example, the input returns the following output. Where if you take a closer look, its basically the alphabets starting with A then to Z, if that is fulfilled, it moves on the next character to see if it fulfills the same requirements, else it will do a sort. Simple? But tricky.


Here is how you do it in PHP.



Source Code (PHP)

Facebook Hacker Cup: Qualification Round

Peg Game

Published Jan 11, 2011 in facebook, hackathon, journal