freenode/#lisp - IRC Chatlog
Search
14:05:51
jcowan
This SO has many links to papers on O(1) space vector merge sorts: https://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm
14:08:28
jcowan
One of my favorite interview questions is to ask people to write code for a procedure that, when passed a number, returns the median of that number and all other numbers previously passed, given that the number of inputs may exceed the capacity of memory.
14:09:54
jcowan
This tests a lot of things, including whether people will ask about constraints on the input and whether they collaborate well (essentially nobody gets the answer right off)
14:11:40
jcowan
I conjecture that the problem is insoluble if the inputs are arbitrary bignums, but very few people ask right off if there is a limit on the numbers being input.
14:12:53
beach
jcowan: Yes, there are several papers on O(1) space merge sort. However, it might be the case that space exists, say on the stack. I would like to see a very that uses O(1) space (with the time overhead that it implies) only if the space is really tight.
14:13:15
Bike
well i don't see how you can compute the median without having all the data, yeah... and if it's constrained to be finite you can just keep counts
14:14:19
Lycurgus
would it occur to you to not quiz someone who obviously didn need it or is that a bogus concept for you, just using judgement?
14:15:55
jcowan
The stats on candidates who look good on paper but fail the FizzBuzz test are a cautionary tale.
14:16:11
pfdietz
This makes me wonder... is there an online algorithm for median that takes O(1) time per input?
14:16:15
Lycurgus
all the more reason to develop powers of discernment, in general you won't be able to quiz
14:18:07
Lycurgus
i can ace ur dumb quiz and then sit on my ass thru whole gig like a lump because you tested me
14:18:40
Lycurgus
or rather because you failed to give me the respect and credit my experience warranted
14:18:49
jcowan
Oh yes. The point of interviews is to reduce the cost of churn, which is very high and especially for programmers.
14:19:14
jcowan
In the restaurant biz it's routine to hire anyone who isn't actually drooling into the food and be prepared to fire them in three days.
14:21:36
jcowan
ah, my problem asks for that then. Many people know the two-heap strategy, which is defeated by saying the stream may be longer than can be kept in memory.
14:22:12
jcowan
recently it turned out that the candidate had been asked for the two-heap solution in the phone screen before I got to him
14:22:38
pfdietz
There is a well-known O(n) algorithm for offline median; my question was whether that can be extended to an online version.
14:27:41
jcowan
however this is not true if the stream is truly unbounded in length because of the bignums in the buckets, so I give candidates that there might be as many as 2^64 inputs
15:36:25
admich
hello, I have a problem with clsql, someone of you know howto report bugs? I tried to send an email (as written on README file) on mailing list but the mailing list is down. Then I open an issue on the github repo reported on the README: https://github.com/UnwashedMeme/clsql/issues/10 but until now no feedback
17:50:16
thijso
I'm at the point of just giving up and stuffing ecl full of debug_log print statements...
17:53:17
pfdietz
When I debug lisp i use TRACE a lot. Some lisps support single stepping; I don't know if ecl does.
18:11:49
thijso
kind of a weird setup, I'm debugging an android app that is segfaulting in ecl_init_module, I don't have a repl to work with yet at that point
18:16:50
thijso
It's not gdb, it's probably me. I have a working gdb talking to my app on my phone through gdbremote.
18:17:41
thijso
I just don't know how to go about getting exactly where the segfault is happening, and what is triggering it
22:00:09
thijso
hmmm... maybe I should figure out if the random crashes running clfswm with newer quicklisp libs is solved. And if not, find out where the problem is...
22:00:49
thijso
although... maybe I should focus on the random -- well, not random, actually -- crashes of my android app...