Created
February 21, 2019 06:11
-
-
Save TomaQ/5884e4c2e27f344d03de6561f39f5fca to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// This one seems pretty abstract and probably depends a lot from interview to interview | |
// but here's my interpretation without any feedback from the interviewer | |
// and trying to do it in 15 mins | |
public class Firework | |
{ | |
public int StartTime {get;set;} | |
public int Duration {get;set;} | |
} | |
public bool WereFireworksAlwaysPresent(List<Firework> fireworks) | |
{ | |
//general check stuff here | |
// sort fireworks based on start time (probably a better way) | |
fireworks = fireworks.OrderBy(x => x.StartTime).ToList(); | |
int farthestEndTime = 0; | |
// start at the second firework since the festival starts with the first one | |
for(int i = 1; i < fireworks.Length; i++) | |
{ | |
// logic here might be a little iffy | |
// we're seeing what is the latest end time for fireworks so far | |
int previousEndTime = fireworks[i-1].StartTime + Duration; | |
if(previousEndTime > farthestEndTime) | |
farthestEndTime = previousEndTime; | |
// check if by the time the firework ended if the next one started or if a previous one already went off | |
if(farthestEndTime < fireworks[i].StartTime) | |
return false; | |
} | |
return true; | |
} | |
public int MaxNumOfFireworksPresent(List<Firework> fireworks) | |
{ | |
// general check stuff here | |
//this is pretty much a "find the max number of intervals overlapping" question | |
var start = fireworks.OrderBy(x => x.StartTime).ToList(); | |
var end = fireworks.OrderBy(x => x.StartTime + Duration).ToList(); | |
int currentOverlap = 0; | |
int maxOverlap = 0; | |
int startIndex = 0; | |
int endIndex = 0; | |
while(startIndex < start.Length && endIndex < end.Length) | |
{ | |
if(start[startIndex] < end[endIndex]) | |
{ | |
currentOverlap++; | |
if(currentOverlap > maxOverlap) | |
maxOverlap = currentOverlap; | |
startIndex++; | |
} | |
else | |
{ | |
currentOverlap--; | |
endIndex++; | |
} | |
} | |
return maxOverlap; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment