Microsoft Interview Question for Software Engineer / Developers


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.

- Anonymous January 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vik January 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Interval tree.

- Riyad Parvez January 09, 2013 | Flag Reply
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)

- skp January 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can any one give the example with input and output

- Anonymous January 22, 2013 | Flag Reply
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 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;
}

- Anonymous October 13, 2013 | Flag Reply
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.

- ashi December 29, 2013 | Flag Reply
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));
    }

}

- codeAddict March 17, 2016 | 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