JavaScript interview with a Google engineer: Meeting hour optimization

Показать описание

Рекомендации по теме

Комментарии

As a first year student, I hope I one day become good enough to solve these problems. I feel like im nowhere near this lol

jensenkhemchandani

39:26 "Now we're cooking with gas" HELL YEAH BROTHER

TheBlaCkoR

I love the hint "Enumerate", and permutations...n choose k type stuff

GKizer

Recognizing that generating combinations rusty is quite tricky, you can do it pretty simply/painlessly in JS:
function combinations([head, ...rest]) {
if (!head) return [ [ ] ]
let restCombos = combinations(rest)
let headCombos = restCombos.map(combo => [head, ...combo])
return headCombos.concat(restCombos)
}

inordirections

Assuming that the problem is equivalent to find, given an array of numbers, the largest combination of numbers such that this combination is less or equal to an another given number.

meetingList = [2, 3, 5]
duration = 8

D = np.zeros((len(meetingList), duration + 1), dtype=np.uint32)

for j in range(1, D.shape[1]):
D[0][j] = 1 if j >= meetingList[0] else 0

for i in range(1, D.shape[0]):
for j in range(1, D.shape[1]):
D[i][j] = (max(D[i - 1][j], D[i - 1][j - meetingList[i]] + 1) if j >= meetingList[i] else D[i - 1][j])

The idea is that, considering the duration of i-th meeting, if this meeting "can stay" in the total amount of hours, the best number is the maximum that you have obtained before the duration of the i-th meeting (i.e D[i - 1][j]) wrt the number of meeting that you can make with the previous meetings in the remaining time plus one.

DarioAlise

I think a sliding window with a vector to track meetings that match the input hours would work

seymour_videos

39:28 "Okay, now we're cooking with gas" love it :D Kudos to the interviewer, probably gave to much hints to pass the candidate in real interview, but I love the "let's work it out together" approach regardless of final outcome.

notMichal

Backtrack would be a good option and check for permutations

Manu-wbuv

The first one is just a combinatorics problems wherein the set of meetings that can be attended is just the set of the ways in which meetings of a set amount of hours can be taken such that the net amount of hours is always less than or equal to 8. Once that set is obtained it isn't hard to sort through the elements (each of which are a set themself) with the higher number of elements (meetings)

Dev-zrsi

(For practice I'll write some notes here as I hear the problem descriptions.)

The first task can be done in O(k log n), with n being the number of meetings and k is the number of meetings in the answer. Just use a min-heap and pop k elements.

The second task is an NP-complete problem. For not too large inputs it's pretty easy to solve though. Have an boolean array "reachable" of length hours+1. Set reachable[0] = true. For every meeting, loop through the array and for index i if reachable[i]==true then set reachable[i+meeting length]=true. After this, the largest index where the reachable is true is the number of hours you can achieve. Reconstructing the meetings requires some extra book-keeping, but that's easily added. Complexity O(hours*n).

alcesmir

First day when getting the job: "Well, uhm. My boss told me to tell you that you should please bring your own keyboards to us."

das

when *Intergalactic Avenger* meets *Stealthy Werewolf* 😂

lukkash

This is a knapsack dp problem right? Very similar to subset sum problem

VivekNayyar

This is the bin packing problem with 1 bin.

griesrt

Is this a mock interview, or just founder of this website is from Google?
Seems like every other week, some another Google fellows are inventing another kind of "interview training website" :)

reyou