Facebook Interview Question: Formatting a collection of times for a movie show time output (using Linq is preferred)

Question

class TimeObject
{
    DateTime time;
    bool isMatinee;
}

Given: {8:00, 9:30, 11:00, 12:10, 2:00, 4:00, 5:20} -- a collection of TimeObjects

Output: (8:00AM, 9:30, 11:00, 12:10PM, 2:00), 4:00, 5:20 -- return a string, oh and AM/PM should be picked up from localization strings

Caveats: AM/PM only shown for first time, ( ) encloses those elements whose matinee bool was set to true.

Question is: I have to figure out how to output the above string.

I mentioned, I knew C#, the interviewer was adamant to know how to do this in the fewest lines of readable code, preferably using LINQ. He said, I could write it to the console, but I had to remember to localize the AM and PM.

I obviously created a bunch of temp collections, and crap, and totally botched it up. He claims that it's only a few lines of LINQ. I tried other things, though he kept steering me towards LINQ.

Help? Any body has ideas? This has really been cringing me the whole day now.

UPDATE - I GOT THE JOB! They also asked me Edit distance {HELLO} --> {HLO}, tell the min. number of edits/updates it'll take to get to the final string. And there are Bees, And Honey in the world, there is 1 queen bee, the only way the honey can be accessed is through the Queen. Construct a make belief computer world that can support this, and tell if the world is in violation or not -- Graph, Root node is Queen Bee, Nodes are Honey and Bee, Run BiPartite test to see if world is in violation.

Answer 1

[edit]
I'm sure there's a cleaner way to do this but here's what I have. A simple grouping would make it easier if it weren't for the time formatting restrictions. I'll try to come up with another version.

var amTimes = times.Where(to => to.time.Hour < 12)
                   .Select((to, i) => new
                   {
                       to.isMatinee,
                       repr = i == 0 ? to.time.ToString("h:mmtt")
                                     : to.time.ToString("h:mm")
                   });
var pmTimes = times.Where(to => to.time.Hour >= 12)
                   .Select((to, i) => new
                   {
                       to.isMatinee,
                       repr = i == 0 ? to.time.ToString("h:mmtt")
                                     : to.time.ToString("h:mm")
                   });
var stimes = amTimes.Concat(pmTimes);
var mats = String.Join(", ", stimes.Where(t => t.isMatinee).Select(t => t.repr));
var nonmats = String.Join(", ", stimes.Where(t => !t.isMatinee).Select(t => t.repr));

var output = string.Format("({0}), {1}", mats, nonmats);

---

[edit2]
Ok, so this is very likely THE kind of answer the interviewer was looking for.

var output = String.Join(", ",
    times.Select(to => new
    {
        prefix = to == times.First(t => t.isMatinee) ? "(" : "",
        time = to.time,
        fmt = to.time.Hour < 12
            ? (to == times.First(t => t.time.Hour < 12) ? "h:mmtt" : "h:mm")
            : (to == times.First(t => t.time.Hour >= 12) ? "h:mmtt" : "h:mm"),
        suffix = to == times.Last(t => t.isMatinee) ? ")" : "",
    })
    .Select(x => String.Format("{0}{1}{2}", x.prefix, x.time.ToString(x.fmt), x.suffix)));

Normally when I write LINQ expressions, I always try to consider the performance. Since performance wasn't a factor here. This should be the easiest to write and follow (but with horrible performance).

The approach, consider the time, how it's formatted, and any prefix (an open paren) or suffix (a closing paren) when printed. As long as the isMatinee grouping is contiguous (which I had always assumed) with times sorted, this should always work.

It only has a prefix if it is the first time that is a matinee. A suffix if it is the last time that is a matinee. It should be formatted with AM/PM if it is the first time in its respective group. It should be very easy to understand.

---

If it were only the matinee grouping involved, I'd probably do this:

var output = String.Join(", ",
    times.GroupBy(to => to.isMatinee, to => to.time.ToString("h:mm"))
         .Select(g => g.Key ? "(" + String.Join(", ", g) + ")"
                            : String.Join(", ", g)));

Answer 2

How about this?

var output =
    String.Join(", ",
        from g in given
        orderby g.time
        group g by g.time.Hour < 12 into ggs
        select
            String.Join(", ", ggs.Select((x, n) =>
            {
                var template = n == 0 ? "{0:h:mmtt}" : "{0:h:mm}";
                template = x.isMatinee ? String.Format("({0})", template) : template;
                return String.Format(template, x.time);
            }).ToArray())
    ).Replace("), (", ", ");

(The assumption here is that the times are only for a single day.)

---

@halivingston

To answer your questions:

Q1. How the query works.

• The outer String.Join is used, as you rightly say, to join together all of the individual formatted times into a single string.

• Since Linq is functional in nature it is easier to compute each element independently from the rest so I bracket every matinee time. This introduces redundant bracketing around the formatted times which are removed by the Replace function.

• The Linq query orders the TimeObject instances by time (as we don't know if they are necessarily in order when we get the collection) and then it groups them by a boolean value where true is "AM" and false is "PM". The variable ggs is the group that gets created and is named as such by my convention of calling it a "group of g's".

• Each group contains an IEnumerable<TimeObject> which needs to be iterated over to build each formatted string. However we need to differentiate between the first element and the remaining elements so we need to use the Select overload that provides the element and the index of the element. Once we have that we can build up a String.Format template that will correctly add AM/PM to the first element and also add brackets to each matinee element.

• String.Join is again used to concatenate the individual elements into a single string. The result is that the Linq query returns an IEnumerable<string> with two elements. (The outer String.Join turns these into the final single string.)

Q2. To allow for times to span multiple days I would make the following change:

group g by g.time.Date.AddHours(g.time.Hour < 12 ? 0.0 : 12:00) into ggs

This will allow any number of days to be grouped together while still separating AM and PM.

I hope that this helps.

Answer 3

bool AMShown = false;
bool PMShown = false;
StringBuilder sb = new StringBuilder();

//assuming it groups with false first:
foreach(var timeObjGrp in collection.GroupBy(p=>p.isMatinee))
{
    if (grpTimeObj.Key) StringBuilder.Append("(");
    foreach (var timeObjItem in timeObjGrp)
    {
        StringBuilder.Append(timeObjItem.time.ToString("h:m"));
        //IsAM should be something like Hours < 12
        if (!AMShown && timeObjItem.time.IsAM)
        {
            StringBuilder.Append("AM");
            AMShown = true;
        }
        if (!PMShown && timeObjItem.time.IsPM)
        {
            StringBuilder.Append("PM");
            PMShown = true;
        }
        StringBuilder.Append(",");
    }
    //here put something to remove last comma
    if (grpTimeObj.Key) StringBuilder.Append(")");
    StringBuilder.Append(",");
}
//here put something to remove last comma

I'm not sure it's LINQ-ish enough but it's readable

Answer 4

I'd hardly call this short (and readable), but it's almost all LINQ at least:

            var outputGroups =
                from item in given
                let needSuffix =
                    object.ReferenceEquals(item, given.FirstOrDefault(to => to.Time.Hour < 12)) ||
                    object.ReferenceEquals(item, given.FirstOrDefault(to => to.Time.Hour >= 12))
                let suffix = needSuffix ? "tt" : string.Empty // could use AM/PM from resources instead of DateTime format string
                let timeFormat = string.Format("H:mm{0}", suffix)
                group item.Time.ToString(timeFormat) by item.IsMatinee into matineeGroup
                orderby matineeGroup.Key descending
                let items = string.Join(", ", matineeGroup.ToArray())
                let format = matineeGroup.Key ? "({0})" : "{0}"
                select string.Format(format, items);

            var result = string.Join(", ", outputGroups.ToArray());