Mapping numbers to letters

I had an interview question asking this:

text file has following lines>

            1: A C D
            4: A B
            5: D F
            7: A E
            9: B C  

*Every line has a unique integer followed by a colon and one or more letters. These letters are delimited spaces (one or more)>

                            #2 Write a short program in the language

of your choice that outputs a sorted list like

            A: 1 4 7
            B: 4 9
            C: 1 9
            D: 1 5
            E: 7
            F: 5

I'm not looking for someone to solve it, but I always get confused with problems like this. I'd like to do it in C# and was wondering should I store each line in a 2d array? What is the best way to handle this. After storing it how do开发者_JS百科 I relist each line with letters rather then numbers?

Just looking for pointers here.

You can solve the problem by creating a Lookup mapping letters to a collection of numbers. You can use the extension method ToLookup to create a Lookup.

Warning: Spoilers ahead

Using LINQ you can do it like this (breaks on invalid input):

var text = @"1: A C D
4: A B
5: D F
7: A E
9: B C";

var lookup = text
  .Split(new[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries)
  .Select(
    line => new {
      Number = Int32.Parse(line.Split(':').First()),
      Letters = line.Split(':').Skip(1).First().Split(
        new[] {' '}, StringSplitOptions.RemoveEmptyEntries
      )
    }
  )
  .SelectMany(x => x.Letters, (x, letter) => new { x.Number, Letter = letter })
  .OrderBy(x => x.Letter)
  .ToLookup(x => x.Letter, x => x.Number);

foreach (var item in lookup)
  Console.WriteLine(item.Key + ": " + String.Join(" ", item.ToArray()));

In case you are familiar with LINQ the below code can give you what you are looking for:

var result = File.ReadAllLines("inFile").SelectMany(line =>
                {
                    var ar = line.Split(" ".ToCharArray());
                    var num = int.Parse(ar[0].Split(":".ToCharArray())[0]);
                    return ar.Skip(1).Select(s => new Tuple<string, int>(s, num));
                }).GroupBy(t => t.Item1).OrderByDescending(g => g.Count())
                .Select(g => g.Key + ": " + g.Select(t => t.Item2.ToString()).Aggregate( (a,b) => a + " " + b));
            File.WriteAllLines("outFile", result);

I know you said you didn't want full answers, but this kind of thing is fun. It looks like others have come up with similar solutions, but here's another way to represent it - in "one line" of code (but lots of brackets!) :)

var data = @"1: A C D
4: A B
5: D F
7: A E
9: B C";

Console.WriteLine(
    String.Join(
        Environment.NewLine,
        (from line in data.Split(new[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries)
         let lineParts = line.Split(new[] { ':', ' ' }, StringSplitOptions.RemoveEmptyEntries)
         from letter in lineParts.Skip(1)
         select new { Number = lineParts[0], Letter = letter })
        .ToLookup(l => l.Letter, l => l.Number)
        .OrderBy(l => l.Key)
        .Select(l => String.Format("{0}: {1}", l.Key, String.Join(" ", l)))));

Oh, and would I write code like that in production? Probably not, but it's fun in an exercise like this!

The thing that will help you solve this

IDictionary<char, IList<int> >

Yet Another Linq Masturbatory Implementation ("Look Ma! No loops!")

using System;
using System.IO;
using System.Linq;

public static class Program
{
    public static void Main(string[] args)
    {
        File.ReadAllLines("input.txt")
            .Select(line => 
            { 
                var split = line.Split(":".ToCharArray(), 2);
                return new { digit = split[0].Trim().Substring(0,1),
                     chars = split[1]
                        .Split(" \t".ToCharArray())
                        .Select(s=>s.Trim())
                        .Where(s => !String.IsNullOrEmpty(s))
                        .Select(s => s[0])
                    };
            })
            .SelectMany(p => p.chars.Select(ch => new { p.digit, ch }))
            .GroupBy(p => p.ch, p => p.digit)
            .ToList()
            .ForEach(g => Console.WriteLine("{0}: {1}", g.Key, string.Join(" ", g)));
    }
}

Of course you can replace GroupBy with ToLookup

I will use a Dictionary<string,List<int>> I will read the input and add 1 into the list at keys A,C,D, A at keys A,B etc, so having the result is just a lookup by letter. So like this, in a non esoteric way:

 string inp = @"1: A C D
            4: A B
            5: D F
            7: A E
            9: B C";
            Dictionary<string, List<int>> res = new Dictionary<string, List<int>>();
            StringReader sr = new StringReader(inp);
            string line;
            while (null != (line = sr.ReadLine()))
            {
                if (!string.IsNullOrEmpty(line))
                {
                    string[] tokens = line.Split(": ".ToArray(),StringSplitOptions.RemoveEmptyEntries);
                    int idx = int.Parse(tokens[0]);
                    for (int i = 1; i < tokens.Length; ++i)
                    {
                        if (!res.ContainsKey(tokens[i]))
                            res[tokens[i]] = new List<int>();
                        res[tokens[i]].Add(int.Parse(tokens[0]));
                    }
                }
            }

res will contain the result of letter->list of numbers.

String parsing using Split(":") and Split(" "). Then fill

Dictionary<int, List<string>>

and translate it into

Dictionary<string, List<int>>

You could store the input in an IDictionary, and reverse it to produce your output.

Take a look at this question.

I see that multiple similar (loops) and not so similar (linq) solutions were already posted but since i've written this i thought i'd throw it in the mix.

static void Main(string[] args)
{
    var result = new SortedDictionary<char, List<int>>();
    var lines = System.IO.File.ReadAllLines(@"input.txt");
    foreach (var line in lines)
    {
        var split = line.Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
        var lineNumber = Int32.Parse(split[0].Substring(0,1));
        foreach (var letter in split.Skip(1))
        {
            var key = letter[0];
            if (!result.ContainsKey(key))
            {
                result.Add(key, new List<int> { lineNumber });
            }
            else
            {
                result[key].Add(lineNumber);
            }
        }
    }
    foreach (var item in result)
    {
        Console.WriteLine(String.Format("{0}: {1}", item.Key, String.Join(" ", item.Value)));
    }
    Console.ReadKey();
}

An important part of the interview process is asking about and verifying assumptions. Although your description states the file is structured as an integer followed by letters, the example you give shows the integers in increasing order. If that's the case, you can avoid all of the LINQ craziness and implement a much more efficient solution:

var results = new Dictionary<char, List<int>>();

foreach (var line in File.ReadAllLines(@"input.txt"))
{
    var split = line.Split(new []{' '}, StringSplitOptions.RemoveEmptyEntries);
    var num = int.Parse(split[0].TrimEnd(':'));

    for (int i = 1; i < split.Length; i++)
    {
        char letter = split[i][0];
        if (!results.ContainsKey(letter))
            results[letter] = new List<int>();

        results[letter].Add(num);
    }
}