## Thumbtack Interview Question

SDE-3s**Country:**United States

**Interview Type:**Phone Interview

```
class NotGreatMath {
constructor() {
this.amount = 0;
this.sum = 0;
this.median = null;
this.left = null;
this.right = null;
}
insert(x) {
this.sum += x;
this.amount++;
if (this.amount == 1) {
this.median = x;
return;
}
const isLeft = x < this.median;
let next = isLeft ? this.left : this.right;
const nearest = (isLeft ? x > next : x < next) ? x : next;
if (this.amount % 2 == 0) {
this.median = next;
next = nearest;
} else {
this.median = (this.median + next) / 2;
}
if (isLeft) {
this.left = next;
} {
this.right = next;
}
}
getMean() {
return this.sum / this.amount;
}
getMedian() {
return this.median;
}
}
```

```
class NotGreatMath {
constructor() {
this.amount = 0;
this.sum = 0;
this.median = null;
this.left = null;
this.right = null;
}
insert(x) {
this.sum += x;
this.amount++;
if (this.amount == 1) {
this.median = x;
return;
}
const isLeft = x < this.median;
let next = isLeft ? this.left : this.right;
const nearest = (isLeft ? x > next : x < next) ? x : next;
if (this.amount % 2 == 0) {
this.median = next;
next = nearest;
} else {
this.median = (this.median + next) / 2;
}
if (isLeft) {
this.left = next;
} {
this.right = next;
}
}
getMean() {
return this.sum / this.amount;
}
getMedian() {
return this.median;
}
}
```

Even better. Spacetime is o(1) too, but insert is not so fast.

```
class NotGreatMath {
constructor() {
this.amount = 0;
this.sum = 0;
this.median = null;
this.left = null;
this.right = null;
}
insert(x) {
this.sum += x;
this.amount++;
if (this.amount == 1) {
this.median = x;
return;
}
const isLeft = x < this.median;
let next = isLeft ? this.left : this.right;
const nearest = (!next || (isLeft ? x > next : x < next)) ? x : null;
this.median = (this.amount % 2 == 0) ? next : (this.median + next) / 2;
if (nearest) {
if (isLeft) {
this.left = next;
} else {
this.right = next;
}
}
}
getMean() {
return this.sum / this.amount;
}
getMedian() {
return this.median;
}
}
```

The mean should be easy to track by keeping track of count .

While inserting nth number

new_mean =((current_mean)*(count-1) + new_number)/count

Or

we can keep track of the total

.

For median, we can have two heaps, one max-heap and one min-heap. Make sure the difference in the numbers in the 2 heaps is at most one at any point.

For getMedian() - if the difference between the numbers in the 2 heaps is 1, pick up the number on top of the bigger heap

If difference is 0, median is the average of the top of the 2 heaps.

My solution:

Time: O(1)

Space: O(1)

- techinterviewquestion.com February 16, 2016