5 ms·

I knew CS graduates who loved parsing theory and could implement some basic C compilers, and I knew some who didn't know what a SCSI controller was. You get out

I knew CS graduates who loved parsing theory and could implement some basic C compilers, and I knew some who didn't know what a SCSI controller was. You get out of your education what you put into it. I had someone in an interview in Berlin ask me to write a garbage collector. In CSC 202, our professor talked about using reference counts. Reference counts can get leaks if you have two objects referencing each other with to path to either, but what I didn't realize is that Java hasn't used reference counts in a really long time. It does a search from each root (typically a thread) down the object tree; and it breaks things into young/old (eden space and .. something else) so long lived objects don't get searched as often. I learned all of that during the interview lunch break when I looked it up on my phone. One of my good friends wrote a compile time GC for GO and did this PhD dissertation on it, and he probably would have got this question right. But if it's not in your field, well the problem space for problems is pretty fucking large. Cycle detection? Man I could probably tell you back when I studied minimum spanning trees and wrote this thing to implement Dijkstra's shortest path: https://penguindreams.org/projects/graphmapper/ https://penguindreams.org/projects/graphmapper/ Off the top of my head, I'd hope each node had a unique identifier and I guess I'd mark them/store the keys in a hash table. I'd move breath first and error out if I discovered the same hash/unique key .. which of course would give me a hash the size of the tree. Unless there's a way to mark the data structure, you now have a second structure the size of your key space. I'm sure there are better solutions, but I wouldn't expect a senior program to know them off the top of their head, unless you're hiring really specifically for a position writing routing algorithms or looking for a senior airport transit architect.

WalterBright 8y ago
I just set a "visited" bit in the data structure while the code walks it. There's a cycle if the bit is already set. It's the same algorithm as yours, but a lot cheaper.
- jmts 8y ago
  Perhaps cheaper in space, but you will have to do an initial pass over the entire structure to zero your visited bits first, so it may not be cheaper in time.
  - WalterBright 8y ago
    You have to walk the hash table again to free it.
  - ufo 8y ago
    The GC already needs to sweep through the whole allocated memory to find the unreacheble objects to be freed. Flipping a bit while doing this isnt a big deal.
  - stcredzero 8y ago
    Just ensure the bits are always zero on allocation, use DFS, and ensure you re-zero the bits on the way out.
    - WalterBright 8y ago
      Since the first pass quit when it finds the first marked node, the zeroing can traverse the structure, erasing marked bits, and stopping at the first 0. The entire structure doesn't have to be visited.
      - stcredzero 8y ago
        The entire structure doesn't have to be visited. We are both saying this.
stcredzero 8y ago
I had someone in an interview in Berlin ask me to write a garbage collector. In CSC 202, our professor talked about using reference counts. Jeez. I think my profs covered ref counting as an introduction, then also went on to cover mark/sweep and generational collectors. We also covered compaction, copying and bump allocation. I don't think it took that long. If I were running a shop that focused on, say Java, I would want to know if my new hires knew background information relevant to optimizing code running on the JVM. Cycle detection? Man I could probably tell you back when I studied minimum spanning trees and wrote this thing to implement Dijkstra's shortest path: Someone should have given you breadth first search and depth first search, then ran you through how those are components to other algorithms. You should have been left with those as a "toolbox" such that you automatically spend a second thinking, "what would happen to that graph if I did DFS or BFS on it." That kind of toolbox is powerful and gives you all sorts of useful insights. You are not the only one around here to say, "Man I could probably tell you back when..." What you should be thinking now is that you were not well served by some of your teachers. Fortunately, this sort of thing is easily rectifiable. Off the top of my head, I'd hope each node had a unique identifier and I guess I'd mark them/store the keys in a hash table. Well good on you. You just did better than most of my last 6 interviewees. Unless there's a way to mark the data structure, you now have a second structure the size of your key space. This is the DFS/BFS part right here. Is the 2nd part of your statement likely to be true, and how often would it be true? Good call on the marking. (EDIT: Just thought of it: Bloom filter.) I'm sure there are better solutions, but I wouldn't expect a senior program to know them off the top of their head Cripes! Freshmen used to be able to do this stuff! unless you're hiring really specifically for a position writing routing algorithms or looking for a senior airport transit architect. How about you don't want programmers who will end up debugingg an infinite loop induced by a data cycle every single time? EDIT: I actually just wrote cycle detection for my side project in golang the day before yesterday. It took me 4 additional lines of code. If you have a shop that uses gob or some kind of object serialization, this may well be very relevant!
- blub 8y ago
  You're trying really hard to find a connection between implementing a GC and debugging memory leaks... and failing. The whole freaking point of a GC like say Java's is that an average programmer can use it without having to understand how exactly it's implemented. Of course it won't hurt to know that, but it's not at all mandatory knowledge. One just has to know which situations the GC can't cope with and avoid them. For Java there's at least one open source dedicated tool for finding leaks, it nicely explains what one needs to know.
varjag 8y ago
When people say they expect someone to implement cycle detection, they usually mean Floyd's algorithm. https://en.wikipedia.org/wiki/Cycle_detection#Floyd%27s_Tortoise_and_Hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd%27s_Tort... If you come up with something else (like tagging nodes), you get a strike for inefficiency. It looks simple enough to feel smug about once you know it, at the same time there's near zero chance the interviewers could come up with this algorithm independently without prior knowledge.
- stcredzero 8y ago
  When people say they expect someone to implement cycle detection, they usually mean Floyd's algorithm. Not necessarily. Sometimes the dataset only has on the order of 10k nodes, and you just want to warn users if they create a cycle, or keep particular routines from going into an infinite loop. If you come up with something else (like tagging nodes), you get a strike for inefficiency. A few days ago, I implemented cycle detection in an event notification system where the graph size is relatively small in just 4 lines of code, which should be immediately understandable by any competent programmer. That you should mandate Floyd's algorithm in all cases gives you a strike for pedantic design without regard to cost/benefit.
  - varjag 8y ago
    I'm not sure what are you trying to argue. I never ask obscure CS trivia, you misread my post entirely.

WalterBright 8y ago

I just set a "visited" bit in the data structure while the code walks it. There's a cycle if the bit is already set. It's the same algorithm as yours, but a lot cheaper.

jmts 8y ago
Perhaps cheaper in space, but you will have to do an initial pass over the entire structure to zero your visited bits first, so it may not be cheaper in time.
- WalterBright 8y ago
  You have to walk the hash table again to free it.
- ufo 8y ago
  The GC already needs to sweep through the whole allocated memory to find the unreacheble objects to be freed. Flipping a bit while doing this isnt a big deal.
- stcredzero 8y ago
  Just ensure the bits are always zero on allocation, use DFS, and ensure you re-zero the bits on the way out.
  - WalterBright 8y ago
    Since the first pass quit when it finds the first marked node, the zeroing can traverse the structure, erasing marked bits, and stopping at the first 0. The entire structure doesn't have to be visited.
    - stcredzero 8y ago
      The entire structure doesn't have to be visited. We are both saying this.

stcredzero 8y ago

I had someone in an interview in Berlin ask me to write a garbage collector. In CSC 202, our professor talked about using reference counts. Jeez. I think my profs covered ref counting as an introduction, then also went on to cover mark/sweep and generational collectors. We also covered compaction, copying and bump allocation. I don't think it took that long. If I were running a shop that focused on, say Java, I would want to know if my new hires knew background information relevant to optimizing code running on the JVM. Cycle detection? Man I could probably tell you back when I studied minimum spanning trees and wrote this thing to implement Dijkstra's shortest path: Someone should have given you breadth first search and depth first search, then ran you through how those are components to other algorithms. You should have been left with those as a "toolbox" such that you automatically spend a second thinking, "what would happen to that graph if I did DFS or BFS on it." That kind of toolbox is powerful and gives you all sorts of useful insights. You are not the only one around here to say, "Man I could probably tell you back when..." What you should be thinking now is that you were not well served by some of your teachers. Fortunately, this sort of thing is easily rectifiable. Off the top of my head, I'd hope each node had a unique identifier and I guess I'd mark them/store the keys in a hash table. Well good on you. You just did better than most of my last 6 interviewees. Unless there's a way to mark the data structure, you now have a second structure the size of your key space. This is the DFS/BFS part right here. Is the 2nd part of your statement likely to be true, and how often would it be true? Good call on the marking. (EDIT: Just thought of it: Bloom filter.) I'm sure there are better solutions, but I wouldn't expect a senior program to know them off the top of their head Cripes! Freshmen used to be able to do this stuff! unless you're hiring really specifically for a position writing routing algorithms or looking for a senior airport transit architect. How about you don't want programmers who will end up debugingg an infinite loop induced by a data cycle every single time? EDIT: I actually just wrote cycle detection for my side project in golang the day before yesterday. It took me 4 additional lines of code. If you have a shop that uses gob or some kind of object serialization, this may well be very relevant!

blub 8y ago
You're trying really hard to find a connection between implementing a GC and debugging memory leaks... and failing. The whole freaking point of a GC like say Java's is that an average programmer can use it without having to understand how exactly it's implemented. Of course it won't hurt to know that, but it's not at all mandatory knowledge. One just has to know which situations the GC can't cope with and avoid them. For Java there's at least one open source dedicated tool for finding leaks, it nicely explains what one needs to know.

varjag 8y ago

When people say they expect someone to implement cycle detection, they usually mean Floyd's algorithm. https://en.wikipedia.org/wiki/Cycle_detection#Floyd%27s_Tortoise_and_Hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd%27s_Tort... If you come up with something else (like tagging nodes), you get a strike for inefficiency. It looks simple enough to feel smug about once you know it, at the same time there's near zero chance the interviewers could come up with this algorithm independently without prior knowledge.

stcredzero 8y ago
When people say they expect someone to implement cycle detection, they usually mean Floyd's algorithm. Not necessarily. Sometimes the dataset only has on the order of 10k nodes, and you just want to warn users if they create a cycle, or keep particular routines from going into an infinite loop. If you come up with something else (like tagging nodes), you get a strike for inefficiency. A few days ago, I implemented cycle detection in an event notification system where the graph size is relatively small in just 4 lines of code, which should be immediately understandable by any competent programmer. That you should mandate Floyd's algorithm in all cases gives you a strike for pedantic design without regard to cost/benefit.
- varjag 8y ago
  I'm not sure what are you trying to argue. I never ask obscure CS trivia, you misread my post entirely.