## Google Interview Question for Software Engineers

Country: United States

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

What is meant by interval is covered? Are these coordinates of a triangle and they are asking if the point is inside?

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

Updated the question with explanation.

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

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

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

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

``````def is_covered(i, L):
mask = [False for _ in range(0, i[1] - i[0])]
for it in L:
for j in range(it[0], it[1]):
if i[0] <= j < i[1]:
return False if [it for it in mask if not it] else True``````

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

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

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

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

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

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

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

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

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

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

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.