Time schedule intersection

Question

I had a job interview one of the questions was the following
Given an api - you submit a name of a person and it gives back a sorted list of all the free time slots this person has. the list might be very long.

List<TimePeriod> GetTimesAvail(String person)

You are given list of people and I need to implement a function which give you back a list of time periods where all the people are available at the same time.

example for simplicity all the free time slots are on the same date

• 23/3/2017 - 00:59-1:30, 2:00-2:30, 3:00-3:30 //personA
  
• 23/3/2017 - 1:00 -1:45, 3:00 -4:00 //personB
  
• 23/3/2017 1:00am - 5:00pm //personC
  

result - 1:00-1:30 , 3:00 -3:30

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JobInterviewTests
{
    [TestClass]
    public class Question
    {
        [TestMethod]
        public void TestMethod1()
        {
            List<string> people = new List<string> { "personA", "personB", "personC" };
            List<TimePeriod> result = GetTimeSlotForAll(people);
            Assert.AreEqual(1,result[0].Start.Hour);
            Assert.AreEqual(0,result[0].Start.Minute);
            Assert.AreEqual(1,result[0].End.Hour);
            Assert.AreEqual(30,result[0].End.Minute);

            Assert.AreEqual(3, result[1].Start.Hour);
            Assert.AreEqual(0, result[1].Start.Minute);
            Assert.AreEqual(3, result[1].End.Hour);
            Assert.AreEqual(30, result[1].End.Minute);
        }

        private List<TimePeriod> GetTimeSlotForAll(List<string> people)
        {
            if (people == null || people.Count == 0)
            {
                return new List<TimePeriod>();
            }
            //future improvment -- suggested
            //List<List<TimePeriod>> tempTimeList = new List<List<TimePeriod>>();
            //foreach (var person in people)
            //{
            //    var personList = Utiliies.GetTimesAvail(person);
            //    tempTimeList.Add(personList);
            //}
            //List<Dictionary<string, List<TimePeriod>>> dictionaryList = new List<Dictionary<string, List<TimePeriod>>>();
            //foreach (var list in tempTimeList)
            //{
            //    //key is the day/month/year
            //    Dictionary<string, List<TimePeriod>> personDictionary = new Dictionary<string, List<TimePeriod>>();
            //    foreach (var time in list)
            //    {
            //        if (personDictionary.ContainsKey(time.ToDateTimeDay()))
            //        {
            //            personDictionary[time.ToDateTimeDay()].Add(time);
            //        }
            //        else
            //        {
            //            personDictionary[time.ToDateTimeDay()] = new List<TimePeriod>();
            //            personDictionary[time.ToDateTimeDay()].Add(time);
            //        }
            //    }
            //    dictionaryList.Add(personDictionary);
            //}

            //place the first person meetings a the first result
            List<TimePeriod> firstPersonList = Utiliies.GetTimesAvail(people.FirstOrDefault());
            List<TimePeriod> result = new List<TimePeriod>();
            //intersect the meetings with the others
            for (int i = 1; i < people.Count; i++)
            {
                List<TimePeriod> secondPersonList = Utiliies.GetTimesAvail(people[i]);
                foreach (var secondSlot in secondPersonList)
                {
                    foreach (var firstSlot in firstPersonList)
                    {
                        if (secondSlot.SameDay(firstSlot))
                        {
                            CheckHourIntersections(firstSlot, secondSlot, result);
                        }
                    }
                }
                //copy the result into the first person
                firstPersonList.Clear();
                foreach (var timeSlot in result)
                {
                    firstPersonList.Add(new TimePeriod(timeSlot.Start, timeSlot.End));
                }
                //clear result
                result.Clear();
            }
            return firstPersonList;
        }

        private static void CheckHourIntersections(TimePeriod firstSlot, TimePeriod secondSlot, List<TimePeriod> result)
        {
            // check all the different interval intersections
            //one intersects with the start of anothesr
            //[-----] //firstSlot
            //  [------] //secondSlot
            // 00:59 -> 1:30 --- 01:00 -> 01:45
            //also cover 
            //[-----] //firstSlot
            //[------] //secondSlot
            //also cover
            //[-------] //firstSlot
            // [------] //secondSlot
            if (((firstSlot.Start.Hour < secondSlot.Start.Hour) || (firstSlot.Start.Hour == secondSlot.Start.Hour && firstSlot.Start.Minute > secondSlot.Start.Minute)) 
                && ((firstSlot.End.Hour < secondSlot.End.Hour) ||(firstSlot.End.Hour == secondSlot.End.Hour && firstSlot.End.Minute < secondSlot.End.Minute))
                && ((secondSlot.Start.Hour < firstSlot.End.Hour) || (firstSlot.End.Hour == secondSlot.End.Hour && firstSlot.End.Minute < secondSlot.End.Minute)) )
            {
                result.Add(new TimePeriod(secondSlot.Start, firstSlot.End));
                return;
            }
            // [----] //firstSlot //02:00 -> 02:30
            //[------] //secondSlot 01:00->01:45
            if (((firstSlot.Start.Hour > secondSlot.Start.Hour) ||(firstSlot.Start.Hour == secondSlot.Start.Hour && firstSlot.Start.Minute >= secondSlot.Start.Minute))
                && ((firstSlot.End.Hour < secondSlot.End.Hour)|| (firstSlot.End.Hour == secondSlot.End.Hour && firstSlot.End.Minute < secondSlot.End.Minute)))
            {
                result.Add(new TimePeriod(firstSlot.Start, firstSlot.End));
                return;
            }
            //    [----] //firstSlot
            //[------] //secondSlot
            if (((firstSlot.Start.Hour > secondSlot.Start.Hour && firstSlot.Start.Minute < secondSlot.Start.Minute) || (firstSlot.Start.Hour == secondSlot.Start.Hour && firstSlot.Start.Minute > secondSlot.Start.Minute))
                && ((firstSlot.End.Hour > secondSlot.End.Hour && firstSlot.End.Minute < secondSlot.End.Minute) || (firstSlot.End.Hour == secondSlot.End.Hour && firstSlot.End.Minute > secondSlot.End.Minute)))
            {
                result.Add(new TimePeriod(firstSlot.Start, secondSlot.End));
            }
        }
    }
    [DebuggerDisplay("{Start.Hour}:{Start.Minute}->{End.Hour}:{End.Minute}")]
    public class TimePeriod
    {
        public DateTime Start { get; set; }
        public DateTime End { get; set; }

        public TimePeriod(DateTime start, DateTime end)
        {
            Start = start;
            End = end;
        }

        public bool SameDay(TimePeriod other)
        {
            return this.Start.Year == other.Start.Year && this.Start.Month == other.Start.Month &&
            this.Start.Day == other.Start.Day;
        }
        public string ToDateTimeDay()
        {
            return Start.ToShortDateString();
        }
    }

    public static class Utiliies
    {
        public static List<TimePeriod> GetTimesAvail(String person)
        {
            var res = new List<TimePeriod>();
            if (person == "personA")
            {
                res.Add(new TimePeriod(new DateTime(2017, 3, 23, 0, 59, 00), new DateTime(2017, 3, 23, 1, 30, 00)));
                res.Add(new TimePeriod(new DateTime(2017, 3, 23, 2, 00, 00), new DateTime(2017, 3, 23, 2, 30, 00)));
                res.Add(new TimePeriod(new DateTime(2017, 3, 23, 3, 00, 00), new DateTime(2017, 3, 23, 3, 30, 00)));
            }
            if (person == "personB")
            {
                res.Add(new TimePeriod(new DateTime(2017, 3, 23, 1, 00, 00), new DateTime(2017, 3, 23, 1, 45, 00)));
                res.Add(new TimePeriod(new DateTime(2017, 3, 23, 3, 00, 00), new DateTime(2017, 3, 23, 4, 00, 00)));
            }
            if (person == "personC")
            {
                res.Add(new TimePeriod(new DateTime(2017, 3, 23, 00, 00, 00), new DateTime(2017, 3, 23, 14, 00, 00)));
            }
            return res;
        }
    }


}

I had about 20 mins to write the code and talk about complexity. one suggestion I made since the list of free TimePeriod could be very long is to store a
List<Dictionary<day+month, TimePeriod>> persons

so we would only call the API in the beginning for the list of all of the names and than later on use a dictionary to fetch the TimePeriods for a certain date.

something like this:

List<List<TimePeriod>> temptimeList = new  List<List<TimePeriod>>();
    foreach(var person in people)
    {
        var personList = getTimesAvail(person);
        tempTimelist.Add(personList);
    }

    List<Dictionary<DateTime, TimePeriod>> dictionaryList = new   List<Dictionary<DateTime, TimePeriod>>();
    foreach(var list in temptimeList)
    {
        Dictionary <DateTime, TimePeriod> personDictionary = new <DateTime, TimePeriod>();
        foreach(var time in list)
        {
            personDictionary.Add(time.ToDateTimeDay(), time);
        }
    }

My question is: Can you please point out where is my code not optimal? I am talking about algorithm and time complexity. please let me know if you need more information.

Answer 1

Review

• GetTimeSlotForAll does 2 distinct things: (1) it loads time slots by people (2) it slices time slots to get shared free time. Each of these operations should have its own method. (single responsibility principle)
• GetTimeSlotForAll should return IEnumerable<TimePeriod> rather than List<TimePeriod> because it's intended to enumerate upon, not to change its content.
• Utiliies is missing his second t.

---

Reduce complexity

CheckHourIntersections is way too complex. An interval intersection with an included end date takes the max start and min end date, provided the start is smaller than or equal to the end.

private static void CheckHourIntersections(
    TimePeriod firstSlot, TimePeriod secondSlot, List<TimePeriod> result)
{
    if (/*edge case: overlap ..*/)
    {
        result.Add(new TimePeriod(secondSlot.Start, firstSlot.End));
        return; 
    }
    if (/*edge case: contains ..*/)
    {
        result.Add(new TimePeriod(firstSlot.Start, firstSlot.End));
        return; 
    }
    if (/*edge case: contained by ..*/)
    {
        result.Add(new TimePeriod(firstSlot.Start, secondSlot.End));
        return; 
    }
}

simplified:

private static void CheckHourIntersections(
    TimePeriod source, TimePeriod target, List<TimePeriod> result)
{
    // check all the different interval intersections
    var start = source.Start >= target.Start ? source.Start : target.Start;
    var end = source.End <= target.End ? source.End : target.End;

    if (end >= start)
    {
        result.Add(new TimePeriod(start, end));
    }
}

SameDay is too complex. DateTime.Date gives a DateTime instance that represents the start of that day corresponding to the specified instance.

public bool SameDay(TimePeriod other)
{
    return this.Start.Year == other.Start.Year 
        && this.Start.Month == other.Start.Month &&
    this.Start.Day == other.Start.Day;
}

simplified:

public bool SameDay(TimePeriod other)
{
    return Start.Date == other.Start.Date;
}