Facebook Interview Question
SDE1sCountry: United States
vector<pair<int, int>> Intersection(vector<pair<int, int>> const &a, vector<pair<int, int>> const &b)
{
vector<pair<int, int>> out;
int i = 0;
int j = 0;
while (i < a.size() &&
j < b.size())
{
int s1 = a[i].first;
int e1 = a[i].second;
int s2 = b[j].first;
int e2 = b[j].second;
if (s1 >= s2 &&
s1 < e2)
{
out.push_back(pair<int, int>(s1, min(e1, e2)));
} else if (s2 >= s1 &&
s2 < e1)
{
out.push_back(pair<int, int>(s2, min(e1, e2)));
}
if (e1 < e2) {
++i;
} else {
++j;
}
}
return out;
}
@ChrisK I fixed my code with the following logic: instead of moving one element at a time, I "merge" two intervals if they are adjacent so the comparison is done on two intervals: {0,13} and {2,12}
Here is the updated code:
class Interval2
{
public:
int start;
int end;
Interval2()
: start(0)
, end(0)
{
}
Interval2(const std::pair<int, int>& p)
: start(p.first)
, end(p.second)
{
}
/**
* @brief return true if merge took place
*/
bool mergeIfAdjacent(const Interval2& other)
{
if(isAdjacent(other)) {
this->end = other.end;
return true;
}
return false;
}
/**
* @brief adjacent means that this interval ends exactly where the "other" interval starts
*/
bool isAdjacent(const Interval2& other) const { return (this->end + 1) == other.start; }
bool intersects(const Interval2& other) const
{
return (other.start > start && other.start < end) || (other.end > start && other.end < end);
}
static Interval2 createIntersection(const Interval2& a, const Interval2& b)
{
Interval2 i;
i.start = std::max(a.start, b.start);
i.end = std::min(a.end, b.end);
return i;
}
std::string toString() const { return "(" + std::to_string(start) + "," + std::to_string(end) + ")"; }
};
void mergeAndIntervals(const std::vector<std::pair<int, int> >& v1, const std::vector<std::pair<int, int> >& v2)
{
// v1 and v2 are sorted
std::vector<Interval2> andV;
std::vector<std::pair<int, int> >::const_iterator iter1 = v1.begin();
std::vector<std::pair<int, int> >::const_iterator iter2 = v2.begin();
while((iter1 != v1.end()) && (iter2 != v2.end())) {
Interval2 interval1 = *iter1;
while((iter1 + 1) != v1.end() && interval1.mergeIfAdjacent(*(iter1 + 1))) {
++iter1;
}
Interval2 interval2 = *iter2;
while((iter2 + 1) != v2.end() && interval2.mergeIfAdjacent(*(iter2 + 1))) {
++iter2;
}
if(interval1.intersects(interval2)) {
andV.push_back(Interval2::createIntersection(interval1, interval2));
}
// Advance the lowest interval
(interval1.start < interval2.start) ? ++iter1 : ++iter2;
}
// Print the merged result
std::cout << "Intersections:" << std::endl;
std::for_each(
andV.begin(), andV.end(), [&](const Interval2& interval) { std::cout << interval.toString() << std::endl; });
std::cout << "Intersections___END:" << std::endl;
}
two ways to solve it:
1. merge two arrays, time:O(m+n)
2. binary search every element in the other array, O(n*logm)
option depends the size of two arrays
below is the 2nd implementation
class Solution {
public static void main(String[] args) {
Interval[] a = {new Interval(1,2), new Interval(5,7)};
Interval[] b = new Interval[]{new Interval(2,7)};
List<Interval> res = Intersection(a,b);
for(Interval i : res){
System.out.println(i.start);
System.out.println(i.end);
}
}
public static List<Interval> Intersection(Interval[] i1, Interval[] i2) {
if (i1 == null || i2 == null) return null;
int index1 = 0;
int index2 = 0;
List<Interval> result = new ArrayList<>();
for (Interval interval : i2) {
Integer start = search(i1, interval.start, 0);
Integer end = search(i1, interval.end, 1);
if (start == null || end == null) {
break;
}
result.add(new Interval(start, end));
}
return result;
}
public static Integer search(Interval[] i, int x, int type) {
int low = 0;
int high = i.length - 1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (i[mid].start < x && i[mid].end > x) {
return x;
} else if (i[mid].start == x && type == 0) {
return x;
} else if (i[mid].end == x && type == 1) {
return x;
} else if (i[mid].start > x) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (type == 1) {
if (high < 0) { return null;}
else return i[high].end;
} else {
if (low == i.length) return null;
else return i[low].start;
}
}
}
@Alex, that's a correct observation, your code is elegant and works correct ;-)
Depending on interval definition and whether it's closed or open and whether you want to merge those "connected" intervals, the case I mentioned is valid or not. It's more of a "think about it" and to encourage thinking of the other case, not mentioned, which is
A = {[0, 1], [3, 5]},
B = {[0, 10]},
where the result would be {[0,1], [3,5]}
public static List<Interval> Intersactions(final List<Interval> intervalA, final List<Interval> intervalB) {
int i = 0, j = 0;
final List<Interval> intersaction = new ArrayList<>();
while (i < intervalA.size() && j < intervalB.size()) {
final int start = Math.max(intervalA.get(i).getStart(), intervalB.get(j).getStart());
final int end = Math.min(intervalA.get(i).getEnd(), intervalB.get(j).getEnd());
if (end > start) {
intersaction.add(new Interval(start, end));
}
if (intervalA.get(i).getEnd() < intervalB.get(j).getEnd()) {
i++;
} else {
j++;
}
}
return intersaction;
}
@xyz, he might be a Facebook employee? (maybe from HR...). Just a thought :)
Now, about the question:
- Create a class named Interval
- Since the lists are sorted, we can start the beginning of each list.
** If we find an intersection, we add the result vector the intersection and advance both lists
** If no intersection is found, we advance the iterator of the *lower* interval (i.e. the one with the lowest "start" point)
The worst case complexity is O(N+M) (where N and M is the number of elements in the arrays)
Here is the C++ implementation:
- PenChief October 09, 2017