## Facebook Interview Question for SDE1s

• 1
of 1 vote

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

@xyz, he might be a Facebook employee? (maybe from HR...). Just a thought :)

- 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:

``````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)
{
}

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())) {
const Interval2& interval1 = *iter1;
const Interval2& interval2 = *iter2;
if(interval1.intersects(interval2)) {
andV.push_back(Interval2::createIntersection(interval1, interval2));
++iter1;
++iter2;
} else {
(interval1.start < interval2.start) ? ++iter1 : ++iter2;
}
}

// Print the merged result
std::for_each(
andV.begin(), andV.end(), [&](const Interval2& interval) { std::cout << interval.toString() << std::endl; });
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just checked the number of questions you have asked here, all of them from Facebook.
How is this possible. Are you posting fake questions in the name of Facebook interviews ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Checked your past records of the questions you have asked. You have asked more than 30 questions all in the name of the same company "Facebook". Aren't all of these questions fake in the name of Facebook ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

@PenChief: cool, don't forget such inputs
A: {[0, 10], [11, 13]}
B: {[2, 12]}
desired output: {[2,12]}

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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
*/
{
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));
}
(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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. For the case of A: {[0, 10], [11, 13]} and B: {[2, 12]}, the intersection should look like {[2, 10], [11, 12]}, not {[2,12]}. Am I missing anything?

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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]}

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex this is very neat code. One observation, when

``s1== s2``

it will save same interval twice. You can fix this by changing to

``s2 > s1``

in else if block

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex this is very neat code. One observation, when

``s1== s2``

it will save same interval twice. You can fix this by changing to

``s2 > s1``

in else if block

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. Yes, there are definitely things to ask the interviewer. I just thought that
if {[0, 10], [11, 13]} + {[2, 12]} = {[2,12]}
then {[1,2], [5,7]} + {[2,6]} = {[2,6]}.
But in the description, there is {[1,2], [5,7]} + {[2,6]} = {[5,6]}.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@pkr. Thank you!
I'm not sure how the same interval can be saved twice. Can you please provide me with an input to produce this?
Along with s1 == s2, there is another condition: s2 < e1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex: right, I read the post again, actually it seems they work with half open or open intervals, as the notation (a,b) suggests ... anyway, I used, wrongly, the notation for closed intervals and meant that ...

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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) {
}
if (intervalA.get(i).getEnd() < intervalB.get(j).getEnd()) {
i++;
} else {
j++;
}
}
return intersaction;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.