Interviewcake - HiCal Solution in Golang

Your company built an in-house calendar tool called HiCal. You want to add a feature to see the times in a day when everyone is available.

To do this, you’ll need to know when any team is having a meeting. In HiCal, a meeting is stored as an object of a Meeting class with integer variables startTime and endTime. These integers represent the number of 30-minute blocks past 9:00am.

Breakdown

What if we only had two ranges? Let's take:

  [Meeting(1, 3), Meeting(2, 4)]

These meetings clearly overlap, so we should merge them to give:

  [Meeting(1, 4)]

But how did we know that these meetings overlap?

We could tell the meetings overlapped because the end time of the first one was after the start time of the second one! But our ideas of "first" and "second" are important here—this only works after we ensure that we treat the meeting that starts earlier as the "first" one.

How would we formalize this as an algorithm? Be sure to consider these edge cases:

The end time of the first meeting and the start time of the second meeting are equal. For example: [Meeting(1, 2), Meeting(2, 3)]
The second meeting ends before the first meeting ends. For example: [Meeting(1, 5), Meeting(2, 3)]

Here is my solution in Go

	package main
	import (
	"fmt"
	"sort"
	)
	type Meeting struct {
	StartTime int
	EndTime int
	}
	func MergeRanges(meetings []Meeting) []Meeting {
	sort.SliceStable(meetings, func(i, j int) bool {
	return meetings[i].StartTime < meetings[j].StartTime
	})
	var sortedMeetings []Meeting
	for _, m := range meetings {
	sortedMeetings = append(sortedMeetings, m)
	}
	var mergedMeetings []Meeting
	// initialize mergedMeetings with the earliest meeting
	mergedMeetings = append(mergedMeetings, sortedMeetings[0])
	for i := 1; i < len(sortedMeetings); i++ {
	currentMeeting := sortedMeetings[i]
	lastMergedMeeting := mergedMeetings[len(mergedMeetings)-1]
	if currentMeeting.StartTime <= lastMergedMeeting.EndTime {
	lastMergedMeeting.EndTime = Max(lastMergedMeeting.EndTime, currentMeeting.EndTime)
	lastMergedMeeting.StartTime = Min(lastMergedMeeting.StartTime, currentMeeting.StartTime)
	mergedMeetings[len(mergedMeetings)-1] = Meeting{
	StartTime: lastMergedMeeting.StartTime,
	EndTime: lastMergedMeeting.EndTime,
	}
	} else {
	mergedMeetings = append(mergedMeetings, currentMeeting)
	}
	}
	return mergedMeetings
	}
	func Max(x, y int) int {
	if x > y {
	return x
	}
	return y
	}
	func Min(x, y int) int {
	if x < y {
	return x
	}
	return y
	}
	func main() {
	meetings := []Meeting{
	{0, 1},
	{3, 5},
	{4, 8},
	{10, 12},
	{9, 10},
	}
	mergedMeetings := MergeRanges(meetings)
	fmt.Println(mergedMeetings) // [{0, 1} {3, 8} {9, 12}]
	}

view raw InterviewCake-HiCal hosted with ❤ by GitHub