Uber Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
use min-heap to store all the intervals from both ranges N(logN) + M(logM)
Next we loop over all elements in the queue.
We sort the intervals by the starting position and the range size (end-start).
The loop is Nlog(N)
Here is the "OR" function:
void mergeOrIntervals(const std::vector<std::pair<int, int> >& v1, const std::vector<std::pair<int, int> >& v2)
{
std::priority_queue<Interval, std::vector<Interval>, std::greater<Interval> > q;
std::for_each(v1.begin(), v1.end(), [&](const std::pair<int, int>& p) {
Interval interval(p);
q.push(interval);
});
std::for_each(v2.begin(), v2.end(), [&](const std::pair<int, int>& p) {
Interval interval(p);
q.push(interval);
});
std::vector<Interval> orV;
while(!q.empty()) {
const Interval& interval = q.top();
if(orV.empty()) {
orV.push_back(interval);
} else {
Interval& lastInterval = orV.back();
if(lastInterval.contains(interval)) {
lastInterval.merge(interval);
} else {
orV.push_back(interval);
}
}
q.pop();
}
// Print the merged result
std::for_each(
orV.begin(), orV.end(), [&](const Interval& interval) { std::cout << interval.toString() << std::endl; });
}
Here is the full code (forgot to copy it entirely...):
#include "CommonHeader.h"
class Interval
{
public:
int start;
int end;
Interval()
: start(0)
, end(0)
{
}
Interval(const std::pair<int, int>& p)
: start(p.first)
, end(p.second)
{
}
bool contains(const Interval& other) const
{
return (other.start >= start && other.start <= end) || (other.end >= start && other.end <= end);
}
void merge(const Interval& other)
{
start = std::min(start, other.start);
end = std::max(end, other.end);
}
int range() const { return end - start; }
bool operator>(const Interval& other) const
{
if(start > other.start) return true;
if(start < other.start) return false;
return range() > other.range();
}
std::string toString() const { return "(" + std::to_string(start) + "," + std::to_string(end) + ")"; }
};
void mergeOrIntervals(const std::vector<std::pair<int, int> >& v1, const std::vector<std::pair<int, int> >& v2)
{
std::priority_queue<Interval, std::vector<Interval>, std::greater<Interval> > q;
std::for_each(v1.begin(), v1.end(), [&](const std::pair<int, int>& p) {
Interval interval(p);
q.push(interval);
});
std::for_each(v2.begin(), v2.end(), [&](const std::pair<int, int>& p) {
Interval interval(p);
q.push(interval);
});
std::vector<Interval> orV;
while(!q.empty()) {
const Interval& interval = q.top();
if(orV.empty()) {
orV.push_back(interval);
} else {
Interval& lastInterval = orV.back();
if(lastInterval.contains(interval)) {
lastInterval.merge(interval);
} else {
orV.push_back(interval);
}
}
q.pop();
}
// Print the merged result
std::for_each(
orV.begin(), orV.end(), [&](const Interval& interval) { std::cout << interval.toString() << std::endl; });
}
The solution I gave was to apply regular merge interval code to 2 list
1. Sort both lists by their end time
2. Run merge overlapping interval function on each list geeksforgeeks.org/merging-intervals/
3. Now add the two lists and sort by end time
4. Again apply merge overlapping interval function on this list, result will be your ans
Optimized version of above algo is to merge two list, after the step 2 in the above algo, all we need to do is extract 1 interval from each merged list and merge them and then check this merged interval with last interval in the result list to see if it can be merged too
If the interviewer tells you, “it’s not sorted” and the first step you do is “sort” or if you sort over time using a heap, you might loose him/her. At least it's a strong indication you should think as well about a solution that does not include sorting (since the sorting is very obvious).
A similar obvious alternative is finding out if you have discrete time and if you can walk through the time in, let's say, m steps, and if m << n (tie is n*log(n)) then you might use or indicate a different approach than priority queues (aka sorting, heaps):
1) run through the n intervals of the first list and put each [start time.. end time] into a hash set. Optimize it by keeping a max-end value and only put [max(max-end) .. end time]. So you end up with an O(n+m) loop
2) do the same for the second list but instead of putting into a hashset check the first hashset if at that time an interval existed and depending on or / and operation extend, end or start a new result interval.
You end up with a O(n+m) time complexity and O(m) space complexity algorithm that might over-perform or under-perform significantly compared to the heap/sorting solution depending the problem set constraints given.
Always, state your assumptions and practice by making assumptions conscious.
@ChrisK I guess that this approach would work if the intervals are small. Given the following example:
v1 = {1,1000},{1100,2000}
v2 = {600,900},{10,000-50,000}
I would rather compare each element in v1 against elements in v2 (O(2^2))
So your solution should be considered for small intervals only
- dimansp October 06, 2017std::vector<std::pair<int, int>> OrFunction(const std::vector<std::pair<int, int>>& v1, const std::vector<std::pair<int, int>>& v2) { std::vector<std::pair<int, int>> result; std::map<int, int> data; for (const auto& p : v1) { data[p.first]++; data[p.second]--; } for (const auto& p : v2) { data[p.first]++; data[p.second]--; } int i = 0; int count = 0; for (const auto& p : data) { if (count == 0) i = p.first; count += p.second; if (count == 0) result.push_back(std::make_pair(i, p.first)); } return result; } std::vector<std::pair<int, int>> AndFunction(const std::vector<std::pair<int, int>>& v1, const std::vector<std::pair<int, int>>& v2) { std::vector<std::pair<int, int>> result; std::map<int, int> data; for (const auto& p : v1) { data[p.first]++; data[p.second]--; } for (const auto& p : v2) { data[p.first]++; data[p.second]--; } int i = 0; int count = 0; for (const auto& p : data) { count += p.second; if (p.second > 0) i = p.first; if (p.second < 0 && i != 0) { result.push_back(std::make_pair(i, p.first)); i = 0; } } return result; }