## Linkedin Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

Sort the list based on x cordinate and keep recording the point which is of interest.

``````import java.util.*;

/**
* Created by PrabhParmeet on 2/5/14.
*/
public class IntervalsImpl implements Intervals {

List<Point> list = new ArrayList<Point>();

public static void main(String... args) {
IntervalsImpl obj = new IntervalsImpl();

System.out.println(obj.getTotalCoveredLength());
}

@Override
public void addIntervals(int x, int y) {

}

@Override
public int getTotalCoveredLength() {
Collections.sort(list);

int totalLen = 0;
Point lastPoint = new Point(0, 0);

for (Point point : list) {

if (point.x > lastPoint.y) {   //located apart
totalLen += point.y - point.x;
lastPoint = point;

} else if (point.x == lastPoint.x && lastPoint.y < point.y) { //start from same origin

totalLen += point.y - lastPoint.y;

lastPoint = point;

} else if (point.x < lastPoint.y && point.y > lastPoint.y) { //in between
totalLen += point.y - lastPoint.y;
lastPoint = point;
}

}

}

}

class Point implements Comparable<Point> {

public int x, y;

Point(int x, int y) {
if (x > y)
throw new IllegalArgumentException("x can't be greater than y");

this.x = x;
this.y = y;
}

@Override
public int compareTo(Point o) {
return o == null ? 0 : (this.x - o.x);
}
}``````

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

In the third case "in between" , shouldn't it be

totalLen += point.y - lastPoint.x;

totalLen += point.y - lastPoint.y;

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

To ps:
no, since you are adding the additional length to it. the original post is right I think.

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

This fails for (1,2)(2,3)(3,4). I think the "located apart" scenario should be greater than or equal to.

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

We can place all starts and ends of intervals on X-axis, beg is 1 and end is -1. Sort them and find lenght of interval where sum of ends and begs bigger than 0.
But it is not and incremental solution.

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

1. use divide and conquer like this
2. x is array of lower bounds and y is of upper bounds
3. and function is returning array of two elements

4.Divide array in two parts
5. calculate max interval from both side in bottom up manner.
6. If two intervals are overlapping return the lower bound of first one and upper bound of second one as result.
7. If they are not overlapping return the interval with most elements.

``````public  static int [] maxInterval(int []x,int[] y,int start,int end)
{
if(start==end)
return new int []{x[start],y[start]};
int mid=(start+end)/2;
int a1[]=maxInterval(x, y, start, mid);
int a2[]=maxInterval(x, y, mid+1, end);
if(a1[0]<a2[0]&&a1[1]>=a2[0])
return new int[]{a1[0],a2[1]};
else if(a2[0]<a1[0]&&a2[1]>=a1[0])
return new int[]{a2[0],a1[1]};
else
{
if(a1[1]-a1[0]>a2[1]-a2[0])
return a1;
else return a2;
}

}``````

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

Complexity o(n)

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

Let assume that we have sort all intervals and build covered intervals. Addition is simple.

find all intervals which parts lying between this interval begin and end. And join them

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

Not the best efficient approach but the below code should work, even the bounds of interval from and to are not known

``````public class IntervalImpl implements Intervals{

static class Node implements Comparable<Node>{
int f;
int t;

Node(int _f, int _t){
this.f = _f;
this.t = _t;
}

@Override
public int compareTo(Node o) {
return this.f -o.f; // order by from
}

public boolean checkAndUpdateIfIntersects(Node o){
if(o.f < this.t && o.t > this.t ){
this.t = o.t;
return true;
}
else if(o.f < this.f && o.t > this.f){
this.f=o.f;
return true;
}
else if(o.f < this.f && o.t < this.t)  return true;
else return false;

}

public int getLen(){
return this.t - this.f;
}
}

int len = 0;
@Override
public void addInterval(int from, int to) {
boolean flag = false;
Node obj = new Node(from,to);
for(Node n : nodes){
int oldLen = n.getLen();
flag = n.checkAndUpdateIfIntersects(obj);
if(flag){
len += n.getLen() - oldLen;
return;
}
}
len += obj.getLen();
}

@Override
public int getTotalCoveredLength() {
return len;
}

public static void main(String... args){
IntervalImpl obj = new IntervalImpl();
System.out.println(obj.getTotalCoveredLength());
}
}``````

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

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

This works : effprog_wordpress_com/2013/03/22/merge-overlapping-intervals/

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

``````import com.google.common.base.*;

import java.util.*;

interface Intervals {

/**
* Adds an interval [from, to] into internal structure.
*/

/**
* Returns a total length covered by intervals.
* If several intervals intersect, intersection should be counted only once.
* Example:
*
*
* getTotalCoveredLength() -> 6
* i.e. [1,5] and [3,6] intersect and give a total covered interval [1,6]
* [1,6] and [8,9] don't intersect so total covered length is a sum for both intervals, that is 6.
*
*                   _________
*                                               ___
*     ____________
*
* 0  1    2    3    4    5   6   7    8    9    10
*
*/
int getTotalCoveredLength();
}

public class Test implements Intervals {

List<Interval> intervals = new ArrayList<>();

static class Interval implements Comparable<Interval> {
int x, y;

public Interval(int a, int b) {
x = a;
y = b;
}

@Override
public int compareTo(Interval o) {
if (o.x != x)
return new Integer(x).compareTo(o.x);
else
return new Integer(y).compareTo(o.y);
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Interval)) return false;

Interval interval = (Interval) o;

if (x != interval.x) return false;
if (y != interval.y) return false;

return true;
}

@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}

@Override
public String toString() {
return Objects.toStringHelper(this)
.toString();
}
}

@Override
public void addInterval(int from, int to) {
}

@Override
public int getTotalCoveredLength() {
Collections.sort(intervals);

Stack<Interval> stack = new Stack<>();
List<Interval> ranges = Lists.newArrayList();
for(Interval interval: intervals) {
if (stack.empty()) {
stack.push(interval);
continue;
}

Interval top = stack.peek();
if (interval.x > top.y) {
stack = new Stack<>();
stack.push(interval);
continue;
}

if (interval.x < top.y) {
stack.push(interval);
}
}

if (!stack.isEmpty())

int sum = 0;

System.out.println(ranges);

for (Interval range : ranges)
sum += (range.y - range.x);

return sum;
}

public static void main(String... args) {
Test t = new Test();

System.out.println(t.getTotalCoveredLength());
}
}``````

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

``````private int findRangeNotSorted(ArrayList<ArrayList<Integer>> input) {
// TODO Auto-generated method stub
if (input == null)
return 0;
else {
TreeMap<Integer, ArrayList<Integer>> inputSortedMap = new TreeMap<Integer, ArrayList<Integer>>();
for (ArrayList<Integer> currentList : input) {
if (inputSortedMap.containsKey(currentList.get(0))) {
if (inputSortedMap.get(currentList.get(0)).get(1) < currentList
.get(1))
inputSortedMap.put(currentList.get(0), currentList);
} else
inputSortedMap.put(currentList.get(0), currentList);
}

int currentStart = Integer.MIN_VALUE, currentEnd = Integer.MIN_VALUE, range = 0;
boolean startFlag;
NavigableSet<Integer> sortedKeySet = inputSortedMap
.navigableKeySet();
for (Integer o : sortedKeySet) {
ArrayList<Integer> currentList = inputSortedMap.get(o);
if (currentList != null) {
startFlag = false;
for (Integer i : currentList) {
if (!startFlag) {
if (currentEnd < i) {
currentStart = i;
} else {
currentStart = currentEnd;
}
startFlag = true;
} else {
currentEnd = i;
if (currentStart < currentEnd) {
range += (currentEnd - currentStart);
}
break;
}

}
}
}
return range;
}
}``````

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

``````//edge case: [1, 5]
//edge case: [1, 1]
//edge case: [2, 3], [3, 5], [3, 4]
//edge case: [3, 3], [3, 4], [2, 4], [5, 7], [6, 8]
struct interval
{
int from;
int to;
};

struct binary_node
{
struct interval interv;
struct binary_node* left;
struct binary_node* right;
};

public Interface Intervals
{
struct binary_node* root = NULL;

int left = -1;

public void add(int from, int to)
{
struct interval i;
i.from = from;
i.to = to;
struct binary_node* new_node = new struct binary_node;
new_node->interv = i;
if (left == -1 || left > new_node->interv.from)
{
left = new_node->interv.from;
}
new_node->left = new_node->right = NULL;
if (root == NULL)
{
root = new_node;
}
else
{
struct binary_node* p = NULL;
struct binary_node* cur = root;
while (cur != NULL)
{
p = cur;
if (i.from < cur->interv.from || (i.from == cur->interv.from && i.to < cur->interv.to))
{
cur = cur->left;
}
else
{
cur = cur->right;
}
}
if (i.from <= p->interv.from)
{
p->left = new_node;
}
else
{
p->right = new_node;
}
}
}

int getTotalCoveredLength()
{
int left, right, tot;
left = right = left - 1;
tot = 0;
in_order(root, left, right, tot);
}

void in_order(struct binary_node* root, int& left, int& right, int& tot)
{
if (root != NULL)
{
in_order(root->left, left, right, tot);
int cur_left = root->interv.from;
int cur_right = root->interv.to;
//cur_left >= left
if (cur_left > right)
{
tot += cur_right - cur_left;
}
else
{
tot += (cur_right - right > 0 ? cur_right - right : 0);
}
left  = (cur_left > right ? cur_left : left);
right = (right < cur_right ? cur_right: right);
int tot_right = in_order(root->right, left, right, tot);
}
}
}``````

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

Nope, doesn't work correctly

``````add(1,5);

int tot = getTotalCoveredLength(); //returns 3 which is NOT right! 1-5 is 4..``````

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

int tot = getTotalCoveredLength(); //returns 3 which is NOT right! 1-5 is 4..

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

int tot = getTotalCoveredLength();

it returns 3 which is NOT right! 1-5 is 4..

Comment hidden because of low score. Click to expand.
0
of 0 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

if you just have 1 range from 1 to 1,000,000 you will do a crazy amount of work for nothing... it works, but not as efficient as it can be as you will end up with a hash set of a million items just for one range...

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

Keep a binary tree sorted by the starting interval position. In order traversal the tree at every request for get cover length. Recurse on sorted list in a stack-like manner, merging overlapping intervals. Iterate through to count total intervals.

O(n) in order traversal
O(n) merging overlapping intervals
O(n) iterate through to count cover length

total = O(n)

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.