Adobe Interview Question
MTSsCountry: United States
Interview Type: In-Person
public static void main(String args[]) {
IT it = null;
it = add(it, new IT(15, 20));
it = add(it, new IT(10, 30));
it = add(it, new IT(17, 19));
it = add(it, new IT(5, 20));
it = add(it, new IT(12, 15));
it = add(it, new IT(30, 40));
System.out.println(getCount(it, 18, 0));
}
public static int getCount(IT it, int t, int count){
if(it == null)
return count;
if(t < it.st || t <= it.max)
count = getCount(it.left, t, count);
if(t > it.st || t >= it.max)
count = getCount(it.right, t, count);
if(t >= it.st && t <= it.en)
count += 1;
return count;
}
public static IT add(IT it, IT node){
if(it == null){
it = node;
it.max = node.en;
}
else
addIn(it, node);
update(it);
return it;
}
public static void addIn(IT it, IT node){
if(it.st > node.st && it.left == null){
it.left = node;
node.max = node.en;
}
if(it.st < node.st && it.right == null){
it.right = node;
node.max = node.en;
}
int lm = -1;
int rm = -1;
if(it.st > node.st)
addIn(it.left, node);
if(it.st < node.st)
addIn(it.right, node);
node.max = Math.max(lm, rm);
node.max = Math.max(node.max, node.en);
}
public static int update(IT it){
if(it.left == null && it.right == null)
return it.max;
if(it.left == null)
return it.right.max;
if(it.right == null)
return it.left.max;
int lm = update(it.left);
int rm = update(it.right);
it.max = Math.max(lm, rm);
it.max = Math.max(it.max, it.en);
return it.max;
}
static class IT{
int st;
int en;
int max;
IT left;
IT right;
public IT(int st, int en){
this.st = st;
this.en = en;
}
}
This question can be converted into following question:
For given time during [TS, TE], how many user user active time(Si, Ei) has overlap with the given time during. In another word, count the number of (Si, Ei) that overlapping with [TS, TE].
If (Si, Ei) NOT overlapping with [TS, TE], there are TWO scenarios:
1. (Si, Ei) is ahead of [TS,TE] as a whole. Denote: Ei > TS
2. (Si, Ei) is behind of[TS, TE] as a whole. Denote: TE > Si
If none of above two scenarios exist, we know these two duration overlapping.
Python solution:
# input is list[][]
def activeUsers(self, input, TS, TE):
count = 0
for i in range(input):
if not (input[i][0] < TE or input[i][1] > TS):
count += 1
return count
- Makarand September 04, 2017