Solving dynamic programming interview problems

"Give all loops a fixed upper bound. It must be trivially possible for a checking tool to prove statically that the loop cannot exceed a preset upper bound on the number of iterations. If a tool cannot prove the loop bound statically, the rule is considered violated."

https://pdfs.semanticscholar.org/ad40/26510beb1a309902704583...

I agree with you quite a bit, but to me it looks like there's some assumption buried in there that the only reason to ask interview questions is to evaluate individual performance on heads-down coding problems, which is not necessarily representative of a real work environment.

The information I look for when interviewing includes: How do people behave when asked questions they don't know? How will a candidate act in meetings? How curious is the candidate when faced with a tough question? Do they verbalize their thought process? Do they start making things up and/or try to appear like they know the answer when they don't? Do they gravitate towards certain kinds of problems? Do they ask questions or try to tough it out alone?

I've never asked a DP problem in an interview, but I do like to try to get an idea of the candidate's limits and boundaries, so I try to ramp up the difficulty until we hit questions they have trouble with. (I do warn them in advance.) I don't really want to hear correct answers to simple questions, I want to see how far they can get before they get stuck. I also want to hire people smarter than me.

If you only look for coding efficiency in a candidate, then yes, your information over time ratio might be low. (And it might be surprisingly low for all your questions.) But if you expand the kinds of information you collect to include social factors, behavior, knowledge limits, and more, then it's really not that bad.

The rationale they used for these rules was written down. It has nothing to do with Fortran. I've offered links that you can read. You're making more assumptions. If there's C-to-Fortran calling at all, then recursion presents zero extra difficulty. Once you can make any function call, you can make all function calls.

> This is in addition to not using recursive functions being pretty standard in anything embedded.

It's true that for small embedded devices, recursion is not used often. It's also true that function pointers and heap allocations and unbounded loops are generally avoided too. Though, often main() in an embed is a white(true){} loop. I wouldn't be surprised to see that at NASA.

One could argue that all of these 10 NASA rules represent some standard practice in embedded code and/or some degree of common sense. They're not claiming to be new or non-standard or unintuitive or innovative; they simply wrote down what people agreed are best practices.

I'm not sure I know what you mean about stack vs heap not making sense because of Python's memory manager. Will you elaborate?

The primary issue is that the default stack limit in Python is too small for some applications of recursion, which the comment before mine illustrates. This is true not just in Python, but any language, since the stack size is generally a function of the process or OS, not a limit of the language. Heap allocated stacks are a reasonable thing to do in any language.

You're right you can solve that in Python by using a list. Python's memory management doesn't really affect one's ability to do so, right?

A secondary issue is that native recursion sometimes uses more memory than a manually heap-allocated "stack". If I make my own stack, I have complete control and complete understand of what's in memory and how much I use. With the native stack, it can be very opaque, and it's easy to chew up the already-too-small stack very quickly by accidentally having a large stack frame.

In Python everything is an object. Python gives you a reference to that object when you create it. There is no way to tell Python(CPython anyway) in which memory space you would it to create that object.