2
\$\begingroup\$

Time schedule intersection in my original question I gave an answer which has \$O(n^2)\$ complexity.

Here is the new version of the same problem. I'm trying to get to O(N+K). please review the code like this is a job interview the emphasis is on complexity and performance. thank you very much

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

namespace JobInterviewTests
{
    [TestClass]
    public class Tests
    {
        [TestMethod]
        public void TestMethod1()
        {
            List<string> people = new List<string> { "personA", "personB", "personC" };
            List<TimePeriod> result = GetTimeSlotsHashMap(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> GetTimeSlotsHashMap(List<string> people)
        {
            var result = new List<TimePeriod>();
            if (people == null || people.Count == 0)
            {
                return result;
            }
            List<Time> sortedListOfTimes = new List<Time>();
            foreach (var person in people)
            {
                var tempTimeList = Utiliies.GetTimesAvail(person);
                foreach (var metting in tempTimeList)
                {
                    sortedListOfTimes.Add(new Time(metting.Start, metting, person));
                    sortedListOfTimes.Add(new Time(metting.End, metting, person));
                }
            }
            sortedListOfTimes.Sort();
            //we now have a sorted list of all the start and ending of meetings
            //we push into the hash the times one by one and pop when we have the same meeting.
            Dictionary<string, TimePeriod> timeStack = new Dictionary<string, TimePeriod>();
            Dictionary<string, string> keyToPersonMap = new Dictionary<string, string>();

            foreach (var meeting in sortedListOfTimes)
            {
                string key = meeting.TimePeriod.StartAndEndDateTime();
                keyToPersonMap[key] = meeting.Name; //save the name of the person for each meeting in the map
                if (!timeStack.ContainsKey(key))
                {
                    //all the times which are already in the hash are intersecting.
                    timeStack[key] = meeting.TimePeriod; //push into the hash.

                    //need to checked that we have all the people in the list;

                    bool areAllThePeopleFree = people.Intersect(keyToPersonMap.Values).Count() == people.Count();

                    if (areAllThePeopleFree)
                    {
                        TimePeriod temp = new TimePeriod(timeStack.FirstOrDefault().Value.Start, timeStack.FirstOrDefault().Value.End);
                        foreach (var tempMeeting in timeStack)
                        {
                            if (temp.Start < tempMeeting.Value.Start)
                            {
                                temp.Start = tempMeeting.Value.Start;
                            }
                            if (temp.End > tempMeeting.Value.End)
                            {
                                temp.End = tempMeeting.Value.End;
                            }
                        }
                        result.Add(temp);
                    }
                }
                else
                {
                    timeStack.Remove(key);
                    keyToPersonMap.Remove(key);
                }
            }
            return result;

        }

        [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 string StartAndEndDateTime()
            {
                return Start.ToShortTimeString() + End.ToShortTimeString();
            }
        }

        /// <summary>
        /// this class stores a link to the begining or the end of a specific meeting
        /// </summary>
        public class Time : IComparable
        {
            public Time(DateTime time, TimePeriod timePeriod, string name)
            {
                ATime = time;
                TimePeriod = timePeriod;
                Name = name;
            }
            public DateTime ATime { get; private set; }
            public TimePeriod TimePeriod { get; private set; }

            public string Name { get; private set; }
            public int CompareTo(object obj)
            {
                Time y = obj as Time;
                if (ATime > y.ATime)
                {
                    return 1;
                }
                if (ATime == y.ATime)
                {
                    if (TimePeriod.Start == y.TimePeriod.End)
                    {
                        return 1;
                    }
                    if (TimePeriod.End == y.TimePeriod.Start)
                    {
                        return -1;
                    }
                    return 0;
                }
                else
                {
                    return -1;
                }
            }
        }



        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;
            }
        }
\$\endgroup\$
  • 1
    \$\begingroup\$ SameDay can be shortened to return Start.Date == other.Start.date; \$\endgroup\$ – Rick Davin May 28 '17 at 1:13
  • \$\begingroup\$ comment to self, maybe Time can have a boolean for start and end. and a counter instead of dictionary. \$\endgroup\$ – Gilad May 28 '17 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.