undefined | Better HN

0 pointsXcelerate1y ago0 comments

Yeah, I thought of that actually, but the interviewer said “very little memory” at one point which gave me the impression that perhaps I only had some registers available to work with. Was this an algorithm for an embedded system?

The whole problem was kind of miscommunicated, because the interviewer showed up 10 minutes late, picked a problem from a list, and the requirements for the problem were only revealed when I started going a direction the interviewer wasn’t looking for (“Oh, the file is actually read-only.” “Oh, each number in the file is an integer, not a float.”)

0 comments

jagged-chisel1y ago

That “miscommunication” you mention has been used against me in several interviews, because I was expected to ask questions (and sometimes a specific question they had in mind) before making assumptions. Well, then the 30min becomes an exercise in requirements gathering and not algorithmic implementation.

NoToP1y ago

Which in fairness, is a reasonable competency to test for in an interview

jagged-chisel1y ago

Indeed. But I need clarity on which skill they want to test in thirty minutes.

1 more reply

creata1y ago

With 256 counters, you could use the same approach with four passes: pass i bins the numbers by byte i (0 = most sig., 3 = least sig.) and then identifies the bin that contains the median.

I really want to know what a one-pass, low-memory solution looks like, lol.

pfdietz1y ago

Perhaps the interviewer was looking for an argument that no such solution can exist? The counterargument would look like this: divide the N numbers into two halves, each N/2 numbers. Now, suppose you don't have enough memory to represent the first N/2 numbers (ignoring changes in ordering); in that case, two different bags of numbers will have the same representation in memory. One can now construct a second half of numbers for which the algorithm will get the wrong answer for at least one of the two colliding cases.

This is assuming a deterministic algorithm; maybe a random algorithm could work with high probability and less memory?

j / k navigate · click thread line to collapse

0 pointsXcelerate1y ago0 comments

0 comments

jagged-chisel1y ago

NoToP1y ago

Which in fairness, is a reasonable competency to test for in an interview

jagged-chisel1y ago

Indeed. But I need clarity on which skill they want to test in thirty minutes.

1 more reply

creata1y ago

With 256 counters, you could use the same approach with four passes: pass i bins the numbers by byte i (0 = most sig., 3 = least sig.) and then identifies the bin that contains the median.

I really want to know what a one-pass, low-memory solution looks like, lol.

pfdietz1y ago

This is assuming a deterministic algorithm; maybe a random algorithm could work with high probability and less memory?

j / k navigate · click thread line to collapse