## Microsoft Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

Interval Trees implemented using red black trees.

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

And the complexity will be O(log n+|output|) nodes encountered

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

Interval tree.

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

We can use a derivative of RMQ. There are known algos for preprocessing in O(N) and O(1) search time. Here, instead of finding the min of the given range we pre-process for finding the given number for the given range. So, overall, answer would be O(n)

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

can any one give the example with input and output

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

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 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);
return 0;
}``````

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

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.

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

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

}``````

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.