Facebook Interview Question SDE1s
Country: United States
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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
My solution in C++:
- DaveRoox November 20, 2017class 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; }