This was posted on reddit. I couldn't figure this out either. wanna give it a try?

this was posted on reddit. I couldn't figure this out either. wanna give it a try?

Attached: reddit.png (1208x3518, 495K)

Other urls found in this thread:

en.wikipedia.org/wiki/Maximum_flow_problem#Maximum_cardinality_bipartite_matching
pastebin.com/aqcDybH4
pastebin.com/Z9RFarkz
play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=abebc8f11d8405ec5fc4dfc8c7c3bc58
twitter.com/SFWRedditVideos

>interview
Nice bait. No one is going to finish your homework

Is a brute-force answer acceptable? In that case, I can't even see how you wouldn't be able to solve it.

>censors the reddit username
>doesn't censor the sub reddit name (leanpython)

This is just a variation of the knapsack problem. It’s even of the bounded type.

i censored it to post on another sub which has no-username rule.

explain?

>python

Solve the knapsack problem first.
then come back to this problem and see that it's just the same problem with a different input/variables/constraints.

too hard for you?

considering that this was an interview question, I don't think they would allow brute-forcing.

this better be a $100K+ position

I wouldn't bet on that, given that Fizzbuzz is also given just to weed out the absolute chaff.

>explain?
Literally, just search the internet for “knapsack problem.” It’s combinatorial optimization. You need to distribute members of a set across buckets with some constraints. I am not even a programmer, and I recognized this problem type when I posted . I used to work in a job where I was trying to implement a solution for efficient distribution of items across containers. I got no management support so I dropped the project.

>array of array mapping sport to camps
>compute another array mapping sport to (sport_slots - requests)
>sort desc
>negative values mean some kids will be left aside
>fill result and decrement second array until each value is negative or zero

you're hired

I'm not sure it works as pure knapsack since you have two objective functions (maximize # of kids attending some camp, minimize size (# of kids attending) of the largest camp).

Of course, in real life, you'd likely just throw this at an ILP solver

Looking at the code, first thing I think about is bipartite graphs. Add a source on the kids side and a sink on the camps' side. Edges from camps to sink have the same capacity as the camp's open seats. Edges from source to kids and from kids to camps have capacity of 1. Flows can only be integers.

Here:
en.wikipedia.org/wiki/Maximum_flow_problem#Maximum_cardinality_bipartite_matching

Wtf the expected answer isn't even evenly distributed

care to explain more?

This.
How are you supposed to optimize it if there are two separate factors? Which is more important?

>reddit
you need to go back

i follow your logic
close enough if i may say so myself
care to fix what's missing in my method?
those Dump() method calls are for LINQPad.
pastebin.com/aqcDybH4

Attached: Untitled.png (1125x707, 46K)

That's a heuristic approach, good luck proving it will always be balanced.

Use a greedy algorithm, no?

none of you are right. there's a straight forward and simple way to compute the result. look what's common in both data sets.

Brainlets don't know about hypergraphs. What the fuck do they teach you in your undegrad, burgers?

>8 hours
>15 posters
Jow Forums is only interested in FizzBuzz

>reddit
You have to go back.

sort kids by how many camps available for them. then for each kid take available camps and sort them by added kids and add that kid in the first camp.

This seems optimal to be. I can't think of a result that this algorithm would produce that could be improved by moving kids around, because you would always be moving around a less "picky" kid to make room for a more "picky" one, and this algorithm always fills in camps with the more "picky" kids first.

This is how I would do in Rust:
pastebin.com/Z9RFarkz
It doesn't match the expected answer but I think it's still correct according to the question criteria.

what's your result?

it's the first comment lol. did you read the paste bin?

play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=abebc8f11d8405ec5fc4dfc8c7c3bc58

Ben : Fun
John : Fun
Tom : Fun
Chris : Cool
Josh : Cool
Alan : Super
Timmy : Sporty
Greg : None

Just iterate over it?
I don't understand why this is hard

based retard

You can model this as a max flow/min cut problem and find the answer easily with Ford Fulkerson algorithm, no?

your result is better than mine i think i know what my mistake is.
i shouldn't have used for iteration when i'm processing the sports. i should use most available open spots when picking the sport to allocate.

if it's so easy, why don't you try?
come on.
2 anons (including me) have posted their code.

if its an interview question, its probably more to see how the problem is approached rather than how fast someone can get the "right" answer

redditors are fucking retarded kek.