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();
        obj.addIntervals(3, 6);
        obj.addIntervals(8, 9);
        obj.addIntervals(1, 5);
        obj.addIntervals(1, 3);
        obj.addIntervals(1, 8);
        obj.addIntervals(3, 10);
        obj.addIntervals(15, 25);


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


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


        list.add(new Point(x, 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;
            }


        }

        return totalLen;
    }


}

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

- Anonymous February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

totalLen += point.y - lastPoint.x;

instead of

totalLen += point.y - lastPoint.y;

- ps October 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- JS March 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sca May 04, 2015 | Flag
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.

- glebstepanov1992 February 04, 2014 | Flag Reply
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;
        }
        
        
    }

- saumya.tyagi6 February 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity o(n)

- saumya.tyagi6 February 04, 2014 | Flag
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

- glebstepanov1992 February 04, 2014 | Flag Reply
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;
		}
	}
	
	List<Node> nodes = new LinkedList<Node>();
	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;
			}
		}
		nodes.add(obj);
		len += obj.getLen();
	}

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

	public static void main(String... args){
		IntervalImpl obj = new IntervalImpl();
		obj.addInterval(3, 6);
		obj.addInterval(8, 9);
		obj.addInterval(1, 5);
		System.out.println(obj.getTotalCoveredLength());
	}
}

- gokul February 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this : www_geeksforgeeks_org/merging-intervals/

- Coder February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Better February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import com.google.common.base.*;
import com.google.common.base.Objects;
import com.google.common.collect.Lists;

import java.util.*;

interface Intervals {

    /**
     * Adds an interval [from, to] into internal structure.
     */
    void addInterval(int from, int to);


    /**
     * Returns a total length covered by intervals.
     * If several intervals intersect, intersection should be counted only once.
     * Example:
     *
     * addInterval(3, 6)
     * addInterval(8, 9)
     * addInterval(1, 5)
     *
     * 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)
                    .add("x", x)
                    .add("y", y)
                    .toString();
        }
    }

    @Override
    public void addInterval(int from, int to) {
        intervals.add(new Interval(from, 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) {
                ranges.add(new Interval(stack.firstElement().x, stack.lastElement().y));
                stack = new Stack<>();
                stack.push(interval);
                continue;
            }

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

        if (!stack.isEmpty())
            ranges.add(new Interval(stack.firstElement().x, stack.lastElement().y));

        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();

        t.addInterval(3, 6);
        t.addInterval(8, 9);
        t.addInterval(1, 5);

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

- Test February 26, 2014 | Flag Reply
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;
		}
	}

- sLion August 30, 2014 | Flag Reply
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);
        return 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);
        }
    }
}

- wjian@yahoo-inc.com September 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nope, doesn't work correctly

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

- vv April 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

add(1,5);
add(1,1);
add(2,3);
add(3,5);
add(3,4);

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

- VV April 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

add(1,5);
add(1,1);
add(2,3);
add(3,5);
add(3,4);

int tot = getTotalCoveredLength();

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

- vv April 03, 2015 | Flag
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.LinkedHashSet;
import java.util.Set;

public class Intervals{
	
	static int findRange(Interval[] data){
		Set<Integer> res = new LinkedHashSet<Integer>();
		for(int i=0;i<data.length;i++){
			for(int j=data[i].start;j<=data[i].end;j++){
				res.add(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));
		
	}
}

- Byll October 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vv April 03, 2015 | Flag
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(logn) add interval
O(n) in order traversal
O(n) merging overlapping intervals
O(n) iterate through to count cover length

total = O(n)

- shic September 20, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More