3 ms·

couldn't you just use "sort" to sort the file on disk and then offset into the file to find the answer? i would expect sort to work fine for files larger than

couldn't you just use "sort" to sort the file on disk and then offset into the file to find the answer? i would expect sort to work fine for files larger than memory (and if it doesn't i bet there is some tool that does - merge sort with tapes is not so old...) [edit: you'd need to add, then strip, carriage returns between numbers, i guess]

lurker14 15y ago
You could, but that's incredibly slow.
- andrewcooke 15y ago
  really? for what value of incredibly? i bet it's way faster than writing all that code. [edit: to save people reading below i missed the sum requirement, which this wouldn't do, and a rough back of the envelope calculations suggests it would take about the same length of time as the code took. so i was wrong, sorry...]
  - gujk 15y ago
    Print "e" is even faster, but also missed the point.
    - andrewcooke 15y ago
      well, before i realised i had missed the sum part (which i suspect was added to foil lazy people like me) i would have argued that perhaps they are looking for someone who knows enough about the tools already available to find the fastest solution. not that i have anything against the approaches here - the dynamic programming approach over trees is really cool and i probably wouldn't have thought of it myself. i just thought it amusing that there seemed to be a simpler way.
  - NathanWong 15y ago
    I didn't have 70 GB of disk space free (two small SSDs in my laptop), but I just started running it on my old machine and will let you know the results. The grammar, parser, and traversal functions took me somewhere between two and three hours in total to think up and write; my gut feeling is that writing and sorting 70 GB of data on a spinning disk would be slower, though I may be wrong. Another issue with using sort that you still need the sum of the numbers. You could store this as "wordnum;realnum", but now you've got over 100 GB of data to sort, and you still need to parse this out when you do your single pass after to get to the correct byte count. You could spend some time optimizing the sorting format (again using tokens), but now you're spending time doing work that's getting you even closer to an actual solution in code. The coded solution is also scalable, although you could argue the necessity of scaling in this context. If a company were to introduce this puzzle looking for some byte in the first trillion numbers sorted (instead of billion), you'd be looking to sort several terabytes of data on disk; the constant memory solution, once tweaked to include the billions case in the same way the millions case is handled, would take roughly 15 minutes to run.
    - andrewcooke 15y ago
      ah, sorry - i had missed the sum of numbers. also, after reading the sort man page, for fast sorting you may need to write out the data in a set of files (each of which fits in memory), sort each separately (well, sort before writing), and then use sort --merge to join them. i'm impressed at how quickly you wrote the code. i guess it would have been better to say "i bet it would be quicker for me...". [edit] actually, you can probably work it out. say you get 10MB/s to a disc. you need to write 10 files (each 7GB) which takes 700s or about 10 minutes each. so it's about 100 minutes for writing them (sorted in memory first) and then about 100 minutes reading them in the merge (i'm thinking you can filter the output to find the answer without writing again). so you'd expect around 3 hours, or about the time the code took to write. [edit 2 to avoid yet more posts] thanks + good luck with the job application (i did one of their questions a year or two back and, while it was really interesting, all i got as a reply was "we've finished hiring this year"... although in their defense - and perhaps like you - i was doing it more for fun anyway)]
      - 15y ago

lurker14 15y ago

You could, but that's incredibly slow.

andrewcooke 15y ago
really? for what value of incredibly? i bet it's way faster than writing all that code. [edit: to save people reading below i missed the sum requirement, which this wouldn't do, and a rough back of the envelope calculations suggests it would take about the same length of time as the code took. so i was wrong, sorry...]
- gujk 15y ago
  Print "e" is even faster, but also missed the point.
  - andrewcooke 15y ago
    well, before i realised i had missed the sum part (which i suspect was added to foil lazy people like me) i would have argued that perhaps they are looking for someone who knows enough about the tools already available to find the fastest solution. not that i have anything against the approaches here - the dynamic programming approach over trees is really cool and i probably wouldn't have thought of it myself. i just thought it amusing that there seemed to be a simpler way.
- NathanWong 15y ago
  I didn't have 70 GB of disk space free (two small SSDs in my laptop), but I just started running it on my old machine and will let you know the results. The grammar, parser, and traversal functions took me somewhere between two and three hours in total to think up and write; my gut feeling is that writing and sorting 70 GB of data on a spinning disk would be slower, though I may be wrong. Another issue with using sort that you still need the sum of the numbers. You could store this as "wordnum;realnum", but now you've got over 100 GB of data to sort, and you still need to parse this out when you do your single pass after to get to the correct byte count. You could spend some time optimizing the sorting format (again using tokens), but now you're spending time doing work that's getting you even closer to an actual solution in code. The coded solution is also scalable, although you could argue the necessity of scaling in this context. If a company were to introduce this puzzle looking for some byte in the first trillion numbers sorted (instead of billion), you'd be looking to sort several terabytes of data on disk; the constant memory solution, once tweaked to include the billions case in the same way the millions case is handled, would take roughly 15 minutes to run.
  - andrewcooke 15y ago
    ah, sorry - i had missed the sum of numbers. also, after reading the sort man page, for fast sorting you may need to write out the data in a set of files (each of which fits in memory), sort each separately (well, sort before writing), and then use sort --merge to join them. i'm impressed at how quickly you wrote the code. i guess it would have been better to say "i bet it would be quicker for me...". [edit] actually, you can probably work it out. say you get 10MB/s to a disc. you need to write 10 files (each 7GB) which takes 700s or about 10 minutes each. so it's about 100 minutes for writing them (sorted in memory first) and then about 100 minutes reading them in the merge (i'm thinking you can filter the output to find the answer without writing again). so you'd expect around 3 hours, or about the time the code took to write. [edit 2 to avoid yet more posts] thanks + good luck with the job application (i did one of their questions a year or two back and, while it was really interesting, all i got as a reply was "we've finished hiring this year"... although in their defense - and perhaps like you - i was doing it more for fun anyway)]
    - 15y ago