Polymorpher
BAN USER
Questions (1)
Comments (3)
Reputation 0
- 0of 0 votes
AnswersAssume we have n people. Each one has a starting time and ending time. For any people, set flag to true if his/her time range overlaps with anyone else's.
- Polymorpher in United States for N/A
Need O(n) solution or very simple O(nlog(n)) solution.| Report Duplicate | Flag | PURGE
Internet Question Site Reliability Engineer
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Very neat solution. I worked out an O(nlog(n)) solution using binary tree, but yours is clearly better. For O(n) I worked out a similar solution (that space complexity depends on range of time) but you reminded me that we could make a hash function and divide (min,max) time range into n buckets, so "on average" this should be roughly O(n) and certainly better than O(nlog(n))
- Polymorpher January 30, 2012Comment hidden because of low score. Click to expand.
0
of 0 vote
Could there be more than one way?
- Polymorpher January 30, 2012Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Keeping tracking maxima of ending points doesn't cover the case of disjoint intervals. For example: [-10,-9],[9,10],[-1,1]. This is actually what I did in my first attempt.
- Polymorpher January 31, 2012