Facebook Interview Question for SDE1s

Country: United States

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

My solution in C++:

``````class Interval {
public:
int start;
int end;
Interval(int _start, int _end):
start(_start), end(_end) {}
};

vector<Interval> insertAndMerge(const vector<Interval> &v, int number) {

vector<Interval> toReturn;

int k = 0;
while(k < v.size() && v[k].end < number)
k++;

if(k > 0) {
for(int i = 0; i < k; i++)
toReturn.push_back(v.at(i));
if(k < v.size())
toReturn[k - 1].end = v[k].end;
else
toReturn[k - 1].end = number;
}
else
toReturn.push_back(Interval(min(number, v[0].start), v[0].end));

for(int i = k + 1; i < v.size(); i++)
toReturn.push_back(v.at(i));

return toReturn;

}

int main() {

vector<Interval> v = {
Interval(1, 4),
Interval(6, 8),
Interval(11, 13)
};

for(const auto &i : insertAndMerge(v, 9)) {
cout << "[" << i.start << ", " << i.end << "]\n";
}

return 0;
}``````

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

My solution in C++:

``````class Interval {
public:
int start;
int end;
Interval(int _start, int _end):
start(_start), end(_end) {}
};

vector<Interval> insertAndMerge(const vector<Interval> &v, int number) {

vector<Interval> toReturn;

int k = 0;
while(k < v.size() && v[k].end < number)
k++;

if(k > 0) {
for(int i = 0; i < k; i++)
toReturn.push_back(v.at(i));
if(k < v.size())
toReturn[k - 1].end = v[k].end;
else
toReturn[k - 1].end = number;
}
else
toReturn.push_back(Interval(min(number, v[0].start), v[0].end));

for(int i = k + 1; i < v.size(); i++)
toReturn.push_back(v.at(i));

return toReturn;

}

int main() {

vector<Interval> v = {
Interval(1, 4),
Interval(6, 8),
Interval(11, 13)
};

for(const auto &i : insertAndMerge(v, 9)) {
cout << "[" << i.start << ", " << i.end << "]\n";
}

return 0;
}``````

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

``````class Interval {
public:
int start;
int end;
Interval(int _start, int _end):
start(_start), end(_end) {}
};

vector<Interval> insertAndMerge(const vector<Interval> &v, int number) {

vector<Interval> toReturn;

int k = 0;
while(k < v.size() && v[k].end < number)
k++;

if(k > 0) {
for(int i = 0; i < k; i++)
toReturn.push_back(v.at(i));
if(k < v.size())
toReturn[k - 1].end = v[k].end;
else
toReturn[k - 1].end = number;
}
else
toReturn.push_back(Interval(min(number, v[0].start), v[0].end));

for(int i = k + 1; i < v.size(); i++)
toReturn.push_back(v.at(i));

return toReturn;

}

int main() {

vector<Interval> v = {
Interval(1, 4),
Interval(6, 8),
Interval(11, 13)
};

for(const auto &i : insertAndMerge(v, 9)) {
cout << "[" << i.start << ", " << i.end << "]\n";
}

return 0;
}``````

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

My solution in C++:

``````class Interval {
public:
int start;
int end;
Interval(int _start, int _end):
start(_start), end(_end) {}
};

vector<Interval> insertAndMerge(const vector<Interval> &v, int number) {

vector<Interval> toReturn;

int k = 0;
while(k < v.size() && v[k].end < number)
toReturn.push_back(v.at(k++));

if(k > 0)
toReturn[k - 1].end = k < v.size() ? v[k].end : number;
else
toReturn.push_back(Interval(min(number, v[0].start), v[0].end));

for(int i = k + 1; i < v.size(); i++)
toReturn.push_back(v.at(i));

return toReturn;

}

int main() {

vector<Interval> v = {
Interval(1, 4),
Interval(6, 8),
Interval(11, 13)
};

for(const auto &i : insertAndMerge(v, 9)) {
cout << "[" << i.start << ", " << i.end << "]\n";
}

return 0;
}``````

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

``````List<Interval> insert(List<Interval> list, int val) {
Iterator<Interval> iterator = list.iterator();
Interval prev = null;
while(iterator.hasNext()) {
Interval interval = iterator.next();
if(val - interval.end == 1) {
interval.end = val;
} else {
if(prev != null && (interval.start - prev.end == 1)) {
prev.end = interval.end;
iterator.remove();
}
}
prev = interval;
}
return list;``````

}

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

``````List<Interval> insert(List<Interval> list, int val) {
Iterator<Interval> iterator = list.iterator();
Interval prev = null;
while(iterator.hasNext()) {
Interval interval = iterator.next();
if(val - interval.end == 1) {
interval.end = val;
} else {
if(prev != null && (interval.start - prev.end == 1)) {
prev.end = interval.end;
iterator.remove();
}
}
prev = interval;
}
return list;
}``````

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

Simple Java Solution

``````List<Interval> insert(List<Interval> list, int val) {
Iterator<Interval> iterator = list.iterator();
Interval prev = null;
while(iterator.hasNext()) {
Interval interval = iterator.next();
if(val - interval.end == 1) {
interval.end = val;
} else {
if(prev != null && (interval.start - prev.end == 1)) {
prev.end = interval.end;
iterator.remove();
}
}
prev = interval;
}
return list;
}``````

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

``````class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end

def __eq__(self, other):
return self.start == other.start and self.end == other.end

def __str__(self):
return "%s(%d, %d)" % (Interval.__name__, self.start, self.end)

def solution(intervals, val):
# Is val left of first interval?
if val < intervals[0].start:
if val + 1 == intervals[0].start:
intervals[0].start -= 1
else:
intervals.insert(0, Interval(val, val))
return intervals

for i, left_interval, right_interval in zip(range(len(intervals) - 1), intervals[:-1], intervals[1:]):
# We're guaranteed left_interval doesn't intersect right_interval
# We're guaranteed left_interval is left of right_interval

# Is val in left_interval?
if left_interval.start <= val <= left_interval.end:
return intervals

# Is val in right_interval?
elif right_interval.start <= val <= right_interval.end:
return intervals

# Is val is between left_interval and right_interval?
elif left_interval.end < val < right_interval.start:
if left_interval.end + 1 == val == right_interval.start - 1:
right_end = right_interval.end
del intervals[i + 1]
intervals[i].end = right_end
elif left_interval.end + 1 == val and val != right_interval.start - 1:
intervals[i].end += 1
elif left_interval.end + 1 != val and val == right_interval.start - 1:
intervals[i + 1].start -= 1
else:
intervals.insert(i + 1, Interval(val, val))
return intervals

else:
# continue searching
continue

# Is val right of last interval?
if val > intervals[-1].end:
if intervals[-1].end + 1 == val:
intervals[-1].end += 1
else:
intervals.append(Interval(val, val))
return intervals

intervals = [Interval(1, 4), Interval(6, 8)]
attempt = solution(intervals, 5)
print(attempt[0], end=' ')
print()
assert len(attempt) == 1
assert attempt[0] == Interval(1, 8)

intervals = [Interval(1, 4), Interval(6, 8)]
attempt = solution(intervals, 1)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 2
assert attempt[0] == Interval(1, 4)
assert attempt[1] == Interval(6, 8)

intervals = [Interval(1, 4), Interval(6, 8)]
attempt = solution(intervals, 0)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 2
assert attempt[0] == Interval(0, 4)
assert attempt[1] == Interval(6, 8)

intervals = [Interval(1, 4), Interval(6, 8)]
attempt = solution(intervals, 10)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 3
assert attempt[0] == Interval(1, 4)
assert attempt[1] == Interval(6, 8)
assert attempt[2] == Interval(10, 10)

intervals = [Interval(1, 3), Interval(7, 8)]
attempt = solution(intervals, 5)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 3
assert attempt[0] == Interval(1, 3)
assert attempt[1] == Interval(5, 5)
assert attempt[2] == Interval(7, 8)

intervals = [Interval(1, 3), Interval(7, 8)]
attempt = solution(intervals, 4)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 2
assert attempt[0] == Interval(1, 4)
assert attempt[1] == Interval(7, 8)``````

We can slightly optimize by using binary search instead of linear search.

``````def solution2(intervals, val):
def binary_search(intervals, lo, hi, val):
if hi == lo + 1:
interval_lo, interval_hi = intervals[lo], intervals[hi]
if interval_lo.start <= val <= interval_lo.end:
return True, lo
elif interval_hi.start <= val <= interval_hi.end:
return True, hi
elif interval_lo.end < val < interval_hi.start:
return False, lo + 1
elif val < interval_lo.start:
return False, -1
elif interval_hi.end < val:
return False, hi + 1

mid = lo + ((hi - lo) >> 1)
interval_lo, interval_mid, interval_hi = intervals[lo], intervals[mid], intervals[hi]
if interval_mid.start <= val <= interval_mid.end:
return True, mid
elif val < interval_mid.start:
return binary_search(intervals, lo, mid, val)
elif val > interval_mid.end:
return binary_search(intervals, mid, hi, val)

n = len(intervals)
intersects, i = binary_search(intervals, 0, n - 1, val)
if not intersects:
if i == -1:
if val + 1 == intervals[0].start:
intervals[0].start = val
else:
intervals.insert(0, Interval(val, val))
elif i == n:
if intervals[-1].end + 1 == val:
intervals[-1].end = val
else:
intervals.append(Interval(val, val))
else:
interval_lo, interval_hi = intervals[i - 1], intervals[i]
if interval_lo.end + 1 == val and val == interval_hi.start - 1:
hi_end = interval_hi.end
del intervals[i]
intervals[i - 1].end = hi_end
elif interval_lo.end + 1 == val and val != interval_hi.start - 1:
intervals[i - 1].end += 1
elif interval_lo.end + 1 != val and val == interval_hi.start - 1:
intervals[i].start -= 1
else:
intervals.insert(i, Interval(val, val))

return intervals``````

Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More