Thumbtack Interview Question
SDE-3sCountry: 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