Google Interview Question
Software EngineersCountry: United States
struct Interval
{
bool operator<(const Interval& in)
{
return left < in.left;
}
int left;
int right;
};
vector<Interval> UnionInverval(const vector<Interval>& A)
{
vector<Interval> ret;
if (A.size() == 0) return ret;
Interval cur(A.front());
for (int i = 1; i < A.size(); i++)
{
if (cur.right >= A[i].left)
{
if (A[i].right > cur.right)
cur.right = A[i].right;
}
else
{
ret.emplace_back(cur);
cur = A[i];
}
}
ret.emplace_back(cur);
return ret;
}
bool IsIntervalCovered(vector<Interval> A, const Interval& a)
{
sort(A.begin(), A.end());
bool ret = false;
vector<Interval> union_A = UnionInverval(A);
int left = 0, right = union_A.size() - 1;
while (left <= right)
{
int m = left + (right - left) / 2;
if (union_A[m].left == a.left) {
ret = a.right <= union_A[m].right;
break;
}
else if (union_A[m].left < a.left) {
left = m + 1;
if (m + 1 < union_A.size() && union_A[m + 1].left > a.left)
{
ret = a.right <= union_A[m].right;
break;
}
}
else
{
right = m - 1;
if (m - 1 >= 0 && union_A[m - 1].left <= a.left)
{
ret = a.right <= union_A[m - 1].right;
break;
}
}
}
return ret;
}
int main()
{
vector<Interval> A;
A.emplace_back(Interval{ 2,5 });
A.emplace_back(Interval{ 5,7 });
A.emplace_back(Interval{ 1,4 });
Interval a{ 1, 6 };
bool ret = IsIntervalCovered(A, a);
A.clear();
A.emplace_back(Interval{ 1,4 });
A.emplace_back(Interval{ 6,7 });
A.emplace_back(Interval{ 2,5 });
a = { 2, 6 };
ret = IsIntervalCovered(A, a);
a = { 0, 4 };
ret = IsIntervalCovered(A, a);
return 0;
}
Store the intervals in List<Pair<Integer, Integer>>
Sort the list on start values of interval
public static boolean isOverLapping(List<Pair<Integer, Integer>> l, int a, int b) {
if(l==null || l.size()==0) return false;
List<Pair<Integer, Integer>> ans = new ArrayList<>();
int i,j,k,n=l.size();
Value value = new Value();
Collections.sort(l, value);
for(i=0;i<n;i++) {
System.out.println(l.get(i).getKey() + " " + l.get(i).getValue());
}
i=0;
while(i<n) {
j=i+1;
//System.out.println("start = "+ l.get(j).getKey());
int start = l.get(i).getKey(); int end = l.get(i).getValue();
while(j<n && l.get(j).getKey() <=end) {
end = Math.max(l.get(j).getValue(),end);
j++;
}
System.out.println("start = "+ start + "end= " + end);
if(a>=start && b<=end) return true;
i=j;
}
return false;
}
public static boolean isOverLapping(List<Pair<Integer, Integer>> l, int a, int b) {
if(l==null || l.size()==0) return false;
List<Pair<Integer, Integer>> ans = new ArrayList<>();
int i,j,k,n=l.size();
Value value = new Value();
Collections.sort(l, value);
for(i=0;i<n;i++) {
System.out.println(l.get(i).getKey() + " " + l.get(i).getValue());
}
i=0;
while(i<n) {
j=i+1;
//System.out.println("start = "+ l.get(j).getKey());
int start = l.get(i).getKey(); int end = l.get(i).getValue();
while(j<n && l.get(j).getKey() <=end) {
end = Math.max(l.get(j).getValue(),end);
j++;
}
System.out.println("start = "+ start + "end= " + end);
if(a>=start && b<=end) return true;
i=j;
}
return false;
}
public static boolean isOverLapping(List<Pair<Integer, Integer>> l, int a, int b) {
if(l==null || l.size()==0) return false;
List<Pair<Integer, Integer>> ans = new ArrayList<>();
int i,j,k,n=l.size();
Value value = new Value();
Collections.sort(l, value);
for(i=0;i<n;i++) {
System.out.println(l.get(i).getKey() + " " + l.get(i).getValue());
}
i=0;
while(i<n) {
j=i+1;
//System.out.println("start = "+ l.get(j).getKey());
int start = l.get(i).getKey(); int end = l.get(i).getValue();
while(j<n && l.get(j).getKey() <=end) {
end = Math.max(l.get(j).getValue(),end);
j++;
}
System.out.println("start = "+ start + "end= " + end);
if(a>=start && b<=end) return true;
i=j;
}
return false;
}
Time complexity: O(NlogN)
def checkIntervals(aListOfIntervals, interval):
newList = sorted(aListOfIntervals, key= lambda x: x[1])
stack = []
stack.append(newList[0])
for i in range(1, len(newList)):
x, y = stack[-1]
a, b = newList[i]
if a <= y:
stack.pop()
temp = tuple((x,b))
stack.append(temp)
else:
stack.append(newList[i])
a, b = interval
for val in stack:
x , y = val
if a>= x and y<=b:
return True
return False
O(nlogn)
bool print_result(vector<pair<int, int > >& v, pair<int, int>& p) {
if (v.size() == 0) return false;
sort(v.begin(), v.end());
vector<pair<int, int> > x;
//print_a(v);
x.emplace_back(v[0]);
for (int i = 1; i < v.size(); i ++) {
if (x[x.size() - 1].second >= v[i].first) {
x[x.size() - 1].second = v[i].second;
}
else {
x.emplace_back(v[i]);
}
}
//print_a(x);
for (int i = 0; i < x.size(); i ++) {
if (p.first >= x[i].first && p.second <= x[i].second) return true;
}
return false;
}
What is meant by interval is covered? Are these coordinates of a triangle and they are asking if the point is inside?
- Denis July 05, 2019