Linkedin Interview Question for Software Engineer / Developers

Team: Tools
Country: United States

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

``````def findRange(l):
newL = sorted(l, key = lambda x: (x[0], x[1]))
print newL
lower_bound = 0
upper_bound = 0
result = 0
for i in newL:
if i[0] < upper_bound:
# find lap here!
if i[1] < upper_bound:
continue
else:
result += i[1] - upper_bound
else:
lower_bound = i[0]
upper_bound = i[1]
result += upper_bound - lower_bound
return result``````

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

print ( findRange([(1, 2), (1, 3), (1, 4), (1, 5)]) )
Result is 7.

Maybe it's better to extend upper_bound in this manner?

``````def findRange(l):
newL = sorted(l, key = lambda x: (x[0], x[1]))
print (newL)
lower_bound = 0
upper_bound = 0
result = 0
for i in newL:
if i[0] < upper_bound:
# find lap here!
if i[1] < upper_bound:
continue
else:
result += i[1] - upper_bound
# upper_bound = i[1]
else:
lower_bound = i[0]
upper_bound = i[1]
result += upper_bound - lower_bound
print(lower_bound, upper_bound)
return result``````

print ( findRange([(1, 2), (1, 3), (1, 4), (1, 5)]) )
Result is: 5

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

Sorry, gere is the code without commented line:

``````def findRange(l):
newL = sorted(l, key = lambda x: (x[0], x[1]))
print (newL)
lower_bound = 0
upper_bound = 0
result = 0
for i in newL:
if i[0] < upper_bound:
# find lap here!
if i[1] < upper_bound:
continue
else:
result += i[1] - upper_bound
upper_bound = i[1]
else:
lower_bound = i[0]
upper_bound = i[1]
result += upper_bound - lower_bound
print(lower_bound, upper_bound)
return result``````

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

``````public static int findRange(ArrayList<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if (o1.start > o2.start) {
return 1;
} else if (o1.start > o2.start) {
return -1;
} else if (o1.end > o2.end){
return 1;
} else if (o1.end > o2.end) {
return -1;
} else {
return 0;
}
}
});

int range = 0;
int s = 0;
int i = 0;
while (i < intervals.size()) {
int j = i + 1;
int e = intervals.get(i).end;
while (j < intervals.size() && e >= intervals.get(j).start) {
e = Math.max(e, intervals.get(j).end);
j++;

}
range += e - intervals.get(s).start;
i = j;
s = j;
}
return range;
}``````

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

``````if (o1.start > o2.start) {
return 1;
} else if (o1.start > o2.start) {
return -1;
} else if (o1.end > o2.end){
return 1;
} else if (o1.end > o2.end) {
return -1;
} else {
return 0;
}``````

did you mean in the else condition o2.start > o1.start
and o2.end > o2.end ?

because in the 4 conditions in your comparator 2 of the conditions are exactly same as the previous statement.

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

i meant o2.end > o1.end

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

I am using a LinkedHashSet. Everything else takes O(n). Can any of you review this ?

``````import java.util.Iterator;
import java.util.Set;

public class Intervals{

static int findRange(Interval[] data){
for(int i=0;i<data.length;i++){
for(int j=data[i].start;j<=data[i].end;j++){
}
}

Iterator<Integer> it = res.iterator();
int start = it.next(), last = start, tmp = start, result = 0;
while(it.hasNext()){
tmp = it.next();
if(tmp-last == 1){
last = tmp;
}else{
result += (last-start);
start = tmp;
last = start;
}
}
result += (tmp-start);
return result;
}

static class Interval{
int start, end;
Interval(int x, int y){
this.start = x;
this.end = y;
}
}

public static void main(String[] args){
Interval[] data = {new Interval(1,3), new Interval(2,5), new Interval(8,9)};
System.out.println(findRange(data));

}
}``````

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

Your code gives output as 7 for the intervals:

``[{1 , 3}, {2 , 5}, {8 , 10}, {4 , 9}]``

I think the output should be 10 for this case.

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

Can you count big O for your solution, or try to start your solution with int[,] tuples = new int[,] {{0,int.MaxValue}};

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

Can someone please explain the questions? How is the answer for [(1,3), (2,5),(8,9)] is 5? What exactly are we supposed to find out?

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

Yes can somebody explain this question please? i dont know what's it's asking for

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

the person failed to mention UNIQUE intervals

[(1,3), (2,5),(8,9)] should return 5

a) 1 2 3 = 2 unique intervals (1 to 2, 2 to 3)
b) 2 3 4 5 = 2 unique intervals ( 3 to 4, 4 to 5) We did not count 2 - 3 since it was already counted.
c) 8 9 = 1 unique interval
result = 2 + 2 + 1 = 5

hope this clarified the question.

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

1,3 and 2,5 overlap in the same interval.

So, 1->5 is 4 and 8->9 is 1 for a total of 5.

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

Think of it as intervals on the number line, and the problem is asking for the range that all these intervals cover.
to give you an specific example:
[(1,3)] will cover a range of 2
[(1,3), (2, 5)] will cover 4
[(1,3), (4, 5), (7,10)] will cover 6.

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

bool pair_compare(const std::pair<int,int> &a, const std::pair<int,int> &b) {
return a.first < b.first;
}

int covered_interval(std::vector<std::pair<int, int> > pairs) {
int n = pairs.size();
if (n == 0) {
return -1;
}

std::sort(pairs.begin(), pairs.end(), pair_compare);

int i = 1;
int sum = 0;
int begin = pairs[0].first;
int end = pairs[0].second;

while (i < n) {
std::pair<int, int> pair = pairs[i];
if (pair.first > end) {
sum += end - begin;
begin = pair.first;
end = pair.second;
} else {
if (end < pair.second) {
end = pair.second;
}
}
i++;
}

sum += end - begin;
return sum;
}

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

``````bool pair_compare(const std::pair<int,int> &a, const std::pair<int,int> &b) {
return a.first < b.first;
}

int covered_interval(std::vector<std::pair<int, int> > pairs) {
int n = pairs.size();
if (n == 0) {
return -1;
}

std::sort(pairs.begin(), pairs.end(), pair_compare);

int i = 1;
int sum = 0;
int begin = pairs[0].first;
int end = pairs[0].second;

while (i < n) {
std::pair<int, int> pair = pairs[i];
if (pair.first > end) {
sum += end - begin;
begin = pair.first;
end = pair.second;
} else {
if (end < pair.second) {
end = pair.second;
}
}
i++;
}

sum += end - begin;
return sum;
}``````

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

Perfect

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

``````public class Point implements Comparable<Point>{
int x;
int y;

public Point() {
this(0, 0);
}

public Point(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public int compareTo(Point other) {
if (this.y == other.y) return 0;
return this.y < other.y ? -1 : 1;
}
}

public int findRangeOfIntervals(Point[] points) {
List<Point> list = Arrays.asList(points);
Collections.sort(list);
int lowerBound = -1;
int upperBound = -1;
int result = 0;

for (int i = 0; i < list.size(); i++) {
Point p = list.get(i);
if (p.x <= upperBound) {
if (p.y > upperBound) {
upperBound = p.y;
}
} else {
lowerBound = p.x;
upperBound = p.y;
}

if (result < upperBound - lowerBound) {
result = upperBound - lowerBound;
}
}

return result;
}``````

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

This works for (1,2) (1,3) (1,4) (2,5) (6,8) (8,12) (11,19)

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

``````class Tuple
{
public:
Tuple(int a, int b):a(a), b(b){}
Tuple(const Tuple& t): a(t.a), b(t.b){}
int a;
int b;
};

bool compare(const Tuple& t1, const Tuple& t2)
{
return t1.a < t2.a;
}

Tuple findMaxRange(vector<Tuple>& V){
if(V.size() == 1)
return V[0];
//assert(V.size() > 0);

sort(V.begin(), V.end(), compare);
Tuple max(V[0]);
Tuple cur(V[0]);

for(int i=1; i<V.size(); ++i){
Tuple& tmp = V[i];
if(cur.b >= tmp.a && cur.b < tmp.b) {
cur.b = tmp.b;
if((cur.b-cur.a) > (max.b-max.a))
max = cur;
}
if(cur.b < tmp.a)
cur = tmp;
}

return max;``````

}

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

``````class Tuple
{
public:
Tuple(int a, int b):a(a), b(b){}
Tuple(const Tuple& t): a(t.a), b(t.b){}
int a;
int b;
};

bool compare(const Tuple& t1, const Tuple& t2)
{
return t1.a < t2.a;
}

Tuple findMaxRange(vector<Tuple>& V){
if(V.size() == 1)
return V[0];
//assert(V.size() > 0);

sort(V.begin(), V.end(), compare);
Tuple max(V[0]);
Tuple cur(V[0]);

for(int i=1; i<V.size(); ++i){
Tuple& tmp = V[i];
if(cur.b >= tmp.a && cur.b < tmp.b) {
cur.b = tmp.b;
if((cur.b-cur.a) > (max.b-max.a))
max = cur;
}
if(cur.b < tmp.a)
cur = tmp;
}

return max;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

I just used as hashset to store the int values in each interval and returned the hashset count.

``````protected int GetCoverageOfIntervals()
{
int[,] tuples = new int[,] {{1,3}, {2,5}, {8,9} };
HashSet<int> covered = new HashSet<int>();
int i = 0;

while (i < (int)(tuples.Length/2))
{
for (int j = tuples[i, 0]; j < tuples[i, 1]; j++)
i++;
}
return covered.Count;
}``````

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.