When I was interviewing for my current job I was asked to theoretically sort a list with with N elements where N >> M where M is the total number of bytes in RAM (but with infinite disk). I thought ok, easy, I basically explained every step of MergeSort except instead of doing operations in the memory, we need to some operations in the memory (i.e. merging) and then need to dump middle products to disk. You need to be a little more clever since you can't just merge in memory and save in disk (e.g. you can't perform the very last step of merging two N/2 N/2 arrays in memory since N/2>>RAM). Anyway, I was confident with my answer, and my interviewer sounded happy too. Then he asked me "but why don't you use swap?" Hmm I was very surprised. Since this wasn't a coding question (I was already asked dozens of questions involved programming) I thought this was a purely theoretical question. So, I never thought about the systems aspect. On a second glance, it indeed seemed like I just reinvented swapping.
I think CS interview questions can be hard because sometimes you don't know what sort of "model of computation" are you operating on. Am I on a totally abstract setting where all I have is an abstract machine. Or do I literally have an Intel CPU running Linux? Or am I even higher level than that and can think in terms of the abstraction of python. I think sometimes this is not clarified.
One other time in a different interview, I was asked "how does OS free memory in constant time". Having implemented malloc etc a few times I thought this was a stupid question because it depends on the C library implementation of malloc/free as one could also implement free in O(logn) using tree-like structures. Anyway, said something like "it just clears the pointer in the linked list in sbrk()'d space so that node is inaccessible" which apparently was the "correct" answer.
>"Or am I even higher level than that and can think in terms of the abstraction of python. I think sometimes this is not clarified." //
Which may be the point, they want you to ask "what am I optimising for", to be aware that there's no simple best answer without needing prompting. Also that the optimisation might be at the business level, like time critical implementation, or use of excess resources gleaned from some other part of the corporation.
So instead of telling you they want a one-liner, you saying "what are our constraints; how long have I got to implement it, ...".
I think CS interview questions can be hard because sometimes you don't know what sort of "model of computation" are you operating on. Am I on a totally abstract setting where all I have is an abstract machine. Or do I literally have an Intel CPU running Linux? Or am I even higher level than that and can think in terms of the abstraction of python. I think sometimes this is not clarified.
One other time in a different interview, I was asked "how does OS free memory in constant time". Having implemented malloc etc a few times I thought this was a stupid question because it depends on the C library implementation of malloc/free as one could also implement free in O(logn) using tree-like structures. Anyway, said something like "it just clears the pointer in the linked list in sbrk()'d space so that node is inaccessible" which apparently was the "correct" answer.