The Reverse Words problem in the qualification round of Google Code Jam Africa 2010 is trivial. You are given a bunch of space separated words that you need to re-order (just the words, not the characters within the words). The number of words is, at most, 1000 so doing everything in memory is entirely feasible on a modern computer. Just be sure to watch out for the separating spaces in the result. You don't want any leading/training spaces.

Here's some simple C# code that solves it [running time is O(n) for n words. Space required is solely to hold the input values plus a small constant overhead to build the result]:

using System;

using System.IO;

using System.Text;


namespace GoogleCodeJam.Africa2010.ReverseWords


    class Program


        static void Main()


            const string basePath = @"C:\";

            var infile = new StreamReader(basePath + "");

            var outfile = new StreamWriter(basePath + "output.txt");


            int n = Int32.Parse(infile.ReadLine());

            for (int caseNo = 1; caseNo <= n; caseNo++)


                var words = infile.ReadLine().Trim().Split(new []{' '});

                var answer = new StringBuilder();

                for (int i = words.Length-1; i >= 0; i--)

                    answer.Append(" " + words[i]);


                outfile.WriteLine("Case #{0}: {1}",

                                    caseNo, answer.ToString().Trim());







Bookmark and Share