Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
I think binary indexed tree should do, keep updating the intervals (each unique interval by 1) and read at the input point.( Please point out if there is any mistake or I have understood the question incorrectly.)
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 10000
int tree[MAX + 1];
void update(int idx, int val) {
while (idx <= MAX) {
tree[idx] += val;
idx += idx & -idx;
}
}
int read(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= idx & -idx;
}
return sum;
}
int main() {
memset(tree, 0, sizeof(tree));
int n, lb, ub, pt;
printf("enter no of intervals\n");
scanf("%d",&n);
for (int i=1; i<=n; i++) {
scanf("%d %d",&lb,&ub);
update(lb, 1);
update(ub+1, -1);
}
printf("enter query point\n");
scanf("%d",&pt);
printf("%d\n",read(pt));
return 0;
}
Lets say the points are (a1,b1) (a2,b2) (a3,b3) (a4,b4) (a5,b5), Construct Bindary Tree Either on min values(a1,a2,a3,a4,a5) or max values( b1,b2,b3,b4,b5), and add another field range which will be ri = bi-ai, Insert this in each tree node,
Now compare given point's min value in the Binray tree.
Complete Running code in java ::
1. Time Complexity :: O(n)
2. Space Complexity :: O(n)
class InternalNode {
int low;
int high;
int max;
InternalNode left;
InternalNode right;
@Override
public String toString() {
return "InternalNode{" +
"max=" + max +
", low=" + low +
", high=" + high +
'}';
}
}
public class IntervalTree {
public InternalNode insert(InternalNode root, int low, int high) {
if(root == null) {
InternalNode node = new InternalNode();
node.low = low;
node.high = high;
node.max = high;
return node;
}
if(low < root.low) {
root.left = insert(root.left, low, high);
} else {
root.right = insert(root.right, low, high);
}
root.max = Math.max(root.high, high);
return root;
}
public InternalNode isOverlap(InternalNode root, int low, int high) {
if(root == null) {
return null;
}
if(root.high >= low && root.low <= high) {
return root;
// return root;
}
if(root.left != null && root.left.max > low) {
return isOverlap(root.left, low, high);
} else {
return isOverlap(root.right, low, high);
}
}
public int isOverlapWithCount(InternalNode root, int low, int high , int count) {
if(root == null) {
return 0;
}
if(root.high >= low && root.low <= high) {
return 1+ (isOverlapWithCount(root.left, low, high , count) +
isOverlapWithCount(root.right, low, high, count)
);
}
if(root.left != null && root.left.max > low) {
return isOverlapWithCount(root.left, low, high , count);
} else {
return isOverlapWithCount(root.right, low, high, count);
}
}
public static void main(String args[]) {
IntervalTree it = new IntervalTree();
InternalNode root = null;
root = it.insert(root, 10, 15);
root = it.insert(root, 11, 13);
root = it.insert(root, 18, 21);
root = it.insert(root, 20, 25);
root = it.insert(root, 0, 7);
System.out.println(it.isOverlap(root, 8, 9));
System.out.println(it.isOverlap(root, 17, 17));
System.out.println(it.isOverlap(root, 21, 22));
// System.out.println(it.isOverlap(root, 21, 22));
System.out.println(it.isOverlap(root, 12, 18));
System.out.println(it.isOverlap(root, 24, 26));
System.out.println("total count = " + it.isOverlapWithCount(root, 10, 12,0));
}
}
Interval Trees implemented using red black trees.
- Anonymous January 12, 2013