Facebook Hacker Cup: Studious student problem

During the qualification round, the following question was asked:

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

You开发者_运维百科r 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

Example input

5
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi

Example output

cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy

The program I wrote goes as:

chomp($numberElements=<STDIN>);  

for(my $i=0; $i < $numberElements; $i++)  
{  
   my $string;  
   chomp ($string = <STDIN>);  
   my @array=split(/\s+/,$string);  
   my $number=shift @array;  
   @sorted=sort @array;    
   $sortedStr=join("",@sorted);    
   push(@data,$sortedStr);  
}  

foreach (@data)  
{  
  print "$_\n";  
}  

The program gives the correct output for the given test cases but still facebook shows it to be incorrect. Is there something wrong with the program?

1
2 ba b

Your program outputs bba, which is incorrect. bab is lexicographically earlier.

#!/usr/bin/env perl 

while (<DATA>) {
    chomp;
    my($num_words, @words) = split /\s+/;
    my @sorted_words = sort @words;
    $" = '';
    print @sorted_words, "\n";
}

__DATA__
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi
2 ba b

Here is a ruby program. Since this was a quick 10 minute hack, I didn't compare performance.

biginput = [
  ['facebook', 'hacker', 'cup', 'for', 'studious', 'students'],
  ['k', 'duz', 'q', 'rc', 'lvraw'],
  ['mybea', 'zdr', 'yubx', 'xe', 'dyroiy'],
  ['jibw', 'ji', 'jp', 'bw', 'jibw'],
  ['uiuy', 'hopji', 'li', 'j', 'dcyi'],
  ['ba', 'b']
  ]

biginput.each do |input|
  out = ""

  input.each do |word|
    word << word[0]
  end

  input.sort!
  # puts temp.inspect
  input.each do |res|
    out << res[0..-2]
  end


  puts out
end

String [] student = {"jibw","ji","jp","bw","jibw"};
    Arrays.sort(student, new Comparator<String>(){

        @Override
        public int compare(String s1, String s2) {
            return (s1+s2).compareTo(s2+s1);
        }
    });
    for(int i=0;i<student.length;i++)
        System.out.print(student[i]+" ");

Answer is: bwjibwjibwjijp. If you only sort and concatenate the answer will be bwjijibwjibwjp which is incorrect.