Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

$1000 coding challenge from E la Carte (YC S10)

elacarte.com

Post reply on HN
Print view View original

31–40 of 47 posts

Re: $1000 coding challenge from E la Carte (YC S10)

#31

Post by mherdeg »

#2 has me puzzled.

The problem statement (paragraphed): Chef Claudio loves to have food specials but likes knowing what each day's specials are to be a challenge.

So, he assigns a random 3-digit alphanumeric code to each of the 250 items he might make and publishes this list. [1] [2] [3]

Each day, he chooses a set of five items to make and uses a grid with a square for each of the 36 letters/numbers to let guests know if a particular item they want is a special that day. [4]

To do this, for each of the digits of each item, he crosses out that square on the grid (if the square is already crossed out, he makes no change). [5]

What is the probability (to the ten-thousandths place) that a guest chooses an item and the grid makes it appear to be today's special when in fact it is not? [6] [7]

What is the probability (to the ten-thousandths place) that a guest chooses an item and the grid makes it appear to be unavailable as today's special when in fact it is available? [8]

---------------------------------------------------------------

[1] There's a list of 250 items.

[2] Each item has a "code" consisting of three alphanumeric characters. Each character was randomly chosen -- so "AA0" is a possible item name.

[3] No two items have the same code. (NB: This is not explicitly stated and does affect the outcome.)

[4] Five randomly chosen items are "specials" today.

[5] Everyone can see "today's codes": a list of all the characters that are in at least one "special". So for example if the specials are "AA1", "AA2", "AA3", "AA4", and "AA5", everyone can see that "today's codes" are the characters "A12345".

[6] We say an item "appears to be a special" if all the characters in its code are in "today's codes".

[7] We want to know:

What is the probability that,

  if I pick an item from the list which appears to be a special, 

  it actually is not a special?
A quick & dirty Monte Carlo simulation proceeds as follows:

[A] This is how to generate the probability that this happens in a single trial.

(1) Store a list of 250 distinct three-character alphanumeric strings, chosen from the alphabet 0...9A...Z. This is "the list".

(2) Randomly choose five items from "the list". Record the five items as "today's specials". For each letter in each item, record the fact that "this letter is one of today's codes."

(3) Compute the denominator: how many items on "the list" contain today's codes.

(4) Compute the numerator: how many items on "the list" contain today's codes and are not one of "today's specials".

(5) Return the numerator divided by the denominator as the probability, in this trial, that you picked an apparent special which was not actually a special.

[B] Perform [A] a lot of times and average the probability returned in each trial.

This is not amenable to a quick Monte Carlo simulation. But after 100k trials it does seem to stabilize into one approximate region.

The actual answer that the system apparently wants (via brute force & curl) I do not understand at all. Seems like it's off by an order of magnitude. I must have messed up an assumption.

---------------------------------------------------------------

[8] This never happens - it's zero.

Re: $1000 coding challenge from E la Carte (YC S10)

#33

Post by oleg_kikin »

rajatsuri wrote: post #32
oleg_kikin wrote: post #27

I answered all questions correctly. At the end they ask you for your name and your email. > We have received your submission and will be responding shortly

nice work!

The first question needs a much larger matrix. I started writing the code, but then looked at the letters and saw the solution.

Re: $1000 coding challenge from E la Carte (YC S10)

#34

Post by mherdeg »

mherdeg wrote: post #31

#2 has me puzzled. The problem statement (paragraphed): Chef Claudio loves to have food specials but likes knowing what each day's specials are to be a challenge. So, he assigns a random 3-digit alphanumeric code to each of the 250 items he might make and publishes this list. [1] [2] [3] Each day, he chooses a set of five items to make and uses a grid with a square for each of the 36 letters/numbers to let guests kno…

Just to quickly follow up: the answer that the system accepts as correct is roughly the answer I get when I compute the answer to the question "if I pick an item at random from the list of 250 items, what is the probability that that item appears to be a special and actually is not a special"?

I say "roughly" because they're almost the same order of magnitude, but still off by a few insignificant digits.

I wonder whether that has something to do with either of these assumptions I made:

[3] No two items have the same code.

[4] Five DISTINCT randomly chosen items are "specials" (it is not possible for today's specials to be the first item on the list five times).

Re: $1000 coding challenge from E la Carte (YC S10)

#35

Post by anonymoushn »

mherdeg wrote: post #34
mherdeg wrote: post #31

#2 has me puzzled. The problem statement (paragraphed): Chef Claudio loves to have food specials but likes knowing what each day's specials are to be a challenge. So, he assigns a random 3-digit alphanumeric code to each of the 250 items he might make and publishes this list. [1] [2] [3] Each day, he chooses a set of five items to make and uses a grid with a square for each of the 36 letters/numbers to let guests kno…

Just to quickly follow up: the answer that the system accepts as correct is roughly the answer I get when I compute the answer to the question "if I pick an item at random from the list of 250 items, what is the probability that that item appears to be a special and actually is not a special"? I say "roughly" because they're almost the same order of magnitude, but still off by a few insignificant digits. I wonder whe…

That's curious. I initially tried a solution like this and got a result that differed from the expected result by a small amount. I discarded this solution and looked for others when rajatsuri said the first part of q2 assumes that the customer has already picked items that appear to be available.

Edit: By turning the 2 assumptions you mentioned on or off, I am only able to produce answers that are slightly too large or slightly too small. I wonder what the correct question is...

Re: $1000 coding challenge from E la Carte (YC S10)

#36

Post by thedufer »

o1iver wrote: post #29
thedufer wrote: post #28

The second problem is not well-defined, so how long it takes has considerably more to do with how many possible interpretations you have to try before you get it right and how long it takes you to grok the grid scheme than how long it actually takes you to solve problems of that nature. You may want to consider rewriting it. As it is, I've lost any interest I initially had in your company as a whole. You need to stan…

Please elaborate... I don't understand the criticism. I find the question quite interesting. What is ambiguous about it?

It does not state whether all 250 items must have unique codes. It also is not clear whether, in the questions, the guest chooses a random code (unlikely), a known item, or an item that is marked as being on the menu.

The second question is very misleading, because the answer is obvious without any math at all, which led me to believe I had misinterpreted the problem completely.

Finally, when you call something a grid, I expect it to be 2-dimensional, and without a picture this is the image that stuck. It took me longer than it should have just to grok this basic premise of the problem.

Addendum: it is also not clear whether the five items must be five distinct items, i.e. drawing with vs. without replacement.

On a related note, pages with no title and no favicon give a feeling of illegitimacy. This also added to my overall poor impression of this startup.

Re: $1000 coding challenge from E la Carte (YC S10)

#38

Post by theycallhimtom »

oleg_kikin wrote: post #27

I answered all questions correctly. At the end they ask you for your name and your email. > We have received your submission and will be responding shortly

Mind explaining what question 2 is actually asking? (Not the solution just the question)

Re: $1000 coding challenge from E la Carte (YC S10)

#40

Post by oleg_kikin »

theycallhimtom wrote: post #38
oleg_kikin wrote: post #27

I answered all questions correctly. At the end they ask you for your name and your email. > We have received your submission and will be responding shortly

Mind explaining what question 2 is actually asking? (Not the solution just the question)

1) Chef has a list of 250 3-letter codes

2) He randomly picks 5 of them as "special"

3) He makes a list X of all unique letters in the codes of these 5 dishes

4) Guest picks a random dish. There are a few things that can happen:

   A) The code of that dish has a letter that's not on the list X. Ignore.

   B) All letters of that dish are on the list X. Two options:

      B1) The dish the guest picked is one of the 5 special.

      B2) The dish the guest picked is not one of the 5 special.
The first question is - how often does B2 happen?

The answer to the second question of that problem is obvious, you don't need to write any code.

Post reply on HN