Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
In the third case "in between" , shouldn't it be
totalLen += point.y - lastPoint.x;
instead of
totalLen += point.y - lastPoint.y;
To ps:
no, since you are adding the additional length to it. the original post is right I think.
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;
}
}
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());
}
}
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());
}
}
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;
}
}
//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);
}
}
}
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..
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..
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));
}
}
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)
Sort the list based on x cordinate and keep recording the point which is of interest.
- Anonymous February 05, 2014