Microsoft Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
1.
O(n)
public static void main(String[] args){
SegT root = null;
root = add(root, 2, 10, 5);
add(root, 5, 7, 2);
add(root, 12, 15, 4);
add(root, 6, 10, 12);
int n = getMax(root, Integer.MIN_VALUE);
System.out.println(n);
}
public static int getMax(SegT node, int max){
if(node == null)
return max;
max = Math.max(max, node.bwidth);
max = getMax(node.left, max);
max = getMax(node.right, max);
return max;
}
public static SegT add(SegT node, int start, int end, int bwidth){
if(node == null){
node = new SegT(start, end, bwidth);
return node;
}
merge(node, start, end, bwidth);
return null;
}
public static void merge(SegT node, int start, int end, int bwidth){
if(node == null)
return;
if(start >= node.start && end <= node.end){
node.bwidth += bwidth;
return;
}else if(start > node.start && start < node.end && end > node.end){
node.end = end;
node.bwidth += bwidth;
return;
}else if(start < node.start && end < node.end && end > node.start){
node.start = start;
node.bwidth += bwidth;
return;
}else if(start < node.start && node.left == null){
SegT n = new SegT(start, end, bwidth);
node.left = n;
return;
}else if(start > node.start && node.left == null){
SegT n = new SegT(start, end, bwidth);
node.right = n;
return;
}else if(start > node.end){
merge(node.right, start, end, bwidth);
}else{
merge(node.left, start, end, bwidth);
}
}
static class SegT{
int start;
int end;
int bwidth;
SegT left;
SegT right;
public SegT(int start, int end, int bwidth){
this.start = start;
this.end = end;
this.bwidth = bwidth;
}
}
2.
public static void main(String[] args){
int N = 3;
Map<Integer, List<List<Integer>>> sch = new TreeMap<Integer, List<List<Integer>>>();
int[][] teams = new int[N][N];
int[] tn = new int[N];
schedule(sch, 0, 0, 0, teams, tn);
for(Map.Entry entry: sch.entrySet()){
System.out.println("Day-"+entry.getKey() + " " + entry.getValue());
}
}
public static int schedule(Map<Integer, List<List<Integer>>> sch, int day, int p, int q, int[][] teams, int[] tn){
int n = teams.length;
if(p != q){
int dtext = day;
List<List<Integer>> games = sch.get(dtext);
List<Integer> game = new ArrayList<Integer>();
game.add(p);
game.add(q);
if(games == null){
games = new ArrayList<List<Integer>>();
}
games.add(game);
sch.put(dtext, games);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j || teams[i][j] == 1 || tn[i] == 1 || tn[j] == 1)
continue;
teams[i][j] = 1;
teams[j][i] = 1;
tn[i] = 1;
tn[j] = 1;
day = schedule(sch, day, i, j, teams, tn);
tn[i] = 0;
tn[j] = 0;
}
}
return day+1;
}
/* when processes run in parallel - their
bandwidth requirements add up */
List all start times and end times
Sort the list
Scan from left to right
maxBandwidth = 0
currentBandwidth =0
if start time
currentBandwidth += bandWidth for this interval
if ( maxBandwidth < currentBandwidth )
maxBandwidth = currentBandwidth
if end time
currentBandwidth -= bandWidth for this interval
if ( maxBandwidth < currentBandwidth )
maxBandwidth = currentBandwidth
print maxBandwidth
end
2. in ruby
- ryangurney October 23, 2017