Thumbtack Interview Question for SDE-3s

• 0

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

My solution:
Time: O(1)
Space: O(1)

``````public class Statistics {
private int[] counter;
private long sum;
private int n;

public Statistics() {
// initial an array for counter number of
// existed of each value in [0-999]
counter = new int[1000];

// sum all insert value
sum = 0;

// n is number of value
n = 0;
}

public void insert(int value) {
// if insert value not in range [0-999], return
if (value >= 1000 || value < 0) {
return;
}

// increase counter in this value
counter[value]++;

// calculate sum
sum += value;

// increase number of value
n++;
}

public double getMean() {
return (double)sum / n;
}

// examples we have:
// value:    3   9   11
// counter:  1   3   20
// n = 1 + 3 + 20 = 24
// so median will be value at position 24 / 2 = 12
// we will count until meet value at position 12
// result is 11
public int getMedian() {
int medianIndex = (n + 1) / 2;
// counter variable
int idx = 0;
for (int value = 0; value < 1000; value++) {
idx += counter[value];
if (idx >= medianIndex) {
return value;
}
}
return -1;
}
}``````

Comment hidden because of low score. Click to expand.
0

About median, isn't it supposed to be different for even and odd numbers. You are doing n+1/2 always

Comment hidden because of low score. Click to expand.
0
of 0 vote

You are not allowed to store the numbers themselves

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0

Nah, it doesnt work

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

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.

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.