The RangeTracker class tracks ranges of numbers. Your task is to design and implement an efficient version of this module that has low space and time complexity.
There can multiple implementations of this, but we are not looking for a specific one. Make sure you choose the right data structures so that your implementation is efficient.
The RangeTracker class provides three functions:
1. addRange: Given an input range, it starts tracking the range. Eg:
addRange(10, 200) – Starts tracking range 10 – 200
addRange(150, 180) – Starts tracking range 150 – 180.
addRange(250, 500) – Starts tracking range 250 – 500.
2. queryRange: Given an input range, this returns if the range is being tracked or not. Eg:
queryRange(50, 100) – Returns true, as this is being tracked.
queryRange(180, 300) – Returns false, as only a partial of this range is being tracked.
queryRange(600, 1000) – Returns false, as this range is not tracked.
3. deleteRange: Given an input range, this range is untracked after this call has been made. If the range does not exists then it is a no-op. Eg:
deleteRange(50, 150) – Stops tracking range 50 – 150.
You do not need to make RangeTracker persistent (writable/readable on disk). An in-memory implementation is fine. You do not need to submit a test program that uses these APIs . However, feel free to create one if it would be helpful to you in designing or debugging the API. Make sure the work that you submit is syntactically correct. It is not mandatory that you implement all the interfaces, but make sure that your design and choice of data structure is good enough to implement all interfaces if you had considerably more time.
You may use the PHP standard library, but no other libraries. All source code must be your own.
Please strive for:
1. Clean design: Make your code readable and re-useable where possible; give thought to your interface.
2. Efficiency: Try to make each function as fast as possible, while still tracking overlapping ranges efficiently.
3. Robustness: Handle error sensibly; handle large or unusual sets of ranges.
Please briefly explain your design choices in your comments.
class RangeTracker
{
// Start tracking the given range
public function addRange($start, $stop) {
}
// Stop tracking the given range
public function deleteRange($start, $stop) {
}
?
// Check whether the entire given range is being tracked
public function queryRange($start, $stop) {
}
}