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.
if (...)
code not yet written is off-topic I'm afraid. \$\endgroup\$