141–150 of 176 posts
And most of the interviewers asking these questions just want someone who can help develop yet another software as a service CRUD app....
Yep. We need superman, but we are a bicycle repair shop. Only superman will do, that is the only thing we know for sure.
Earlier quoted context omitted.
You might be able to trace the execution of the iterative code more easily, but in my experience it is often much less clear why that produces the correct result and how that code was written in the first place. Take a look at the wikipedia page for computing Levenshtein distance: https://en.wikipedia.org/wiki/Levenshtein_distance#Computing... The recursive version needs barely any explanation. But ask me to carry it…
Very much agree. If you are working on any kind of tree structure, graph, parse tree, etc., recursion can be really beautiful and clear. My theory: folks like iteration because 90% of the "for" loops they write are really just "foreach".
I didn't understand this comment. What do you mean by "for vs foreach."? Can you elaborate?
Earlier quoted context omitted.
Also, it depends on the interviewer. I have been on both sides of the table and I can tell that as an interviewer you need to convey these type of questions very clearly. A interview is typically 45 minutes in most companies, where about 5-10 minutes are wasted in introduction etc. You have about 35 minutes and if you waste 15-20 minutes explaining a problem to the candidate and in the end leave the candidate with 15…
> where about 5-10 minutes are wasted in introduction etc. That tells me a lot of concerning things about the organization. If you're considering that it's "wasted time." You're missing out on a lot of important information there.
Earlier quoted context omitted.
Any examples of code for this approach? From what I guess, you are implementing some kind of assembly like approach with explicit saving of stack frame, but I am having a hard time imagining it as being easier.
Not OP, but they probably mean something like the following toy problem (in C++): struct BinTree { long value; BinTree *left; BinTree *right; }; long long RecursiveDFSSum(BinTree *node) { if (NULL == node) { return 0; } return (long long)value + RecursiveDFSSum(node->left) + RecursiveDFSSum(node->right); } long long IterativeDFSSum(BinTree *tree) { std::vector custom_stack; custom_stack.push_back(tree); long long val…
If you were coding a DP problem, then custom_stack might have a fixed size you can pre-allocate, and it might also be 2 or 3-dimensional.
For some image-based recursion, your backtracking doesn’t even need to store real pointers in the stack frame. For example when I’ve written a flood fill, I can store the return pointer as a one pixel offset in as little as 2 or 3 bits, depending on whether I include diagonal pixels (4-surround vs 8-surround).
In python you often need sys.setrecursionlimit for the recursive solutions since the default is really small. I found out the hard way in a recent Google CodeJam problem[1] that even that wasn't enough and sometimes you really do need the iterative solution to not time out. (I still believe that the limits for python for this problem was set too low since even the iterative solution required hand optimizing of the me…
Yes that, or code the recursive solution in a heap-allocated space rather than on the stack. It somehow seems easier, safer, and more explicit and controllable to me to adjust the code & data to use manual recursion with backtracking than try to adjust system stack limits. Often it consumes a lot less memory too, since you have more control over what your "stack frame" looks like; you don't have to store all your loc…
Earlier quoted context omitted.
Yes that, or code the recursive solution in a heap-allocated space rather than on the stack. It somehow seems easier, safer, and more explicit and controllable to me to adjust the code & data to use manual recursion with backtracking than try to adjust system stack limits. Often it consumes a lot less memory too, since you have more control over what your "stack frame" looks like; you don't have to store all your loc…
I've tried to compare recursive tree DFS and iterative one (with stack in Python list) implemented in Python - recursive was slightly faster. I've not compared memory usage thought. Function call has overhead and theoretically recursive approach should be slower, but list manipulation (append, pop) in Python is also not fast. In compiled languages results can differ (iterative probably will be faster).
Earlier quoted context omitted.
Yes that, or code the recursive solution in a heap-allocated space rather than on the stack. It somehow seems easier, safer, and more explicit and controllable to me to adjust the code & data to use manual recursion with backtracking than try to adjust system stack limits. Often it consumes a lot less memory too, since you have more control over what your "stack frame" looks like; you don't have to store all your loc…
Any examples of code for this approach? From what I guess, you are implementing some kind of assembly like approach with explicit saving of stack frame, but I am having a hard time imagining it as being easier.
Python memory management is automatic though, discussing stack vs heap doesn't make sense in the context of Python,well for CPython at least. I'm not sure about other Python implementations.
Earlier quoted context omitted.
> Then why does NASA consider it unsafe for mission critical code? They also proscribe unbounded iterations (point 2). In any case, NASA’s guidelines for mission-critical code are not necessarily good guidelines for general software engineering, given the constraints involved. It’s also worth noting that recursive solutions are probably more amenable to static analysis and automated theorem proving. > How about unkno…
> Then why does NASA consider it unsafe for mission critical code? More like they're using an old Fortran 77 environment which doesn't support recursive functions.
NASA's rules, the ones being referenced above, are designed for safety. They require code to be easy to statically analyze and to have absolutely predictable behavior.
Also to be avoided: memory allocation, unbounded loops, function pointers, preprocessor macros.
https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev...
why are there so many companies trying to "solve hiring". i get it's a big expense to make a bad hire but how are there like 10 different companies thinking they have an edge on 1. existing practices 2. each other
It's a hard problem that requires people to approach it seriously. And it is only getting worse with a high growth in number of people getting into tech.
It's interesting to try to solve it.
Unpopular opinion, but the best way to prepare for DP problems is to solve the well known ones and memorize them and their recurrences. Only 2-3 companies like FB and Goog ask them (well they’re the only ones worth studying DP for anyway). Coming up with a recurrence on the spot is very hard. The edit-distance paper was an award winning ACM paper and expecting someone who has never seen that before to code it up (eve…
The best way to perform well in an interview is to have seen and worked on the problem at some point beforehand. When I got a job at Google (in a previous life), two of the questions in my interview loop were ones that I had seen in previous interviews. I kept my mouth shut about that and faked brilliance in the moment. That is, I pretended to be stumped for a second, then I created a narrative where I had a sequence…
Doesn't say much for the usefulness of such an interviewing paradigm but that's a whole other conversation.