Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving dynamic programming interview problems

blog.refdash.com

Post reply on HN
Print view View original

161–170 of 176 posts

Re: Solving dynamic programming interview problems

#161

Post by BurningFrog »

x1798DE wrote: post #114
BurningFrog wrote: post #113

Earlier quoted context omitted.

When I interviewed at $BigCompany, I really enjoyed the whiteboard programming problems I got. But I noticed that 2/3 of them ended up with recursive solutions. Meanwhile, I spend less than 1% of my real professional programming time writing recursive code, and it's a bit silly that so much focus is on such relatively obscure technique.

I think it's a mistake to think of whiteboard problems as attempting to recreate a real work environment. They are a proxy for the kind of quality you are looking for that can be "measured" within the alotted time. They can show that the person is prepared (they studied), generally knowledgable (they remember obscure stuff), or just clever (they come up with interesting approaches to the problem). I'm not surprised y…

Yeah, it's philosophically valid that you'd want to measure certain critical things that are different from the everyday grind.

But I think the simpler explanation is that these interviewers mostly had picked "cool" recursion problems.

I did get the job, and seeing $BigCompany's hiring process from the inside didn't contradict this.

Re: Solving dynamic programming interview problems

#162

Post by bitL »

rsp1984 wrote: post #79

I've done a fair amount of interviews in my professional career, both as an engineer at Google as well as for my own startup. In an eng. interview you want to maximize information divided by time, i.e. you want to learn as much as possible about whether the candidate would be a good fit for the company and spend as little time as possible doing so (because you have other things to do -- such as interviewing more cand…

Most of the interviews are just technology-wrapped ways to confirm our initial biases about whether we like that person or not. One could ace an interview but if that person is not liked/relatable, they won't get the job. OTOH when we like somebody, we try to help even if the person is not up to required level. The only exception I can think of is when a team needs to hire a scapegoat before performance review to be fired when the expected axe lands on the team and somebody has to go. I've seen this played out at Google, FB, MS etc., regardless of what each company thought about its "scientific" interview process.

Next time on interview just for fun try to ace all technical questions but contradict some interviewer's notions held in high regard (those could be usually inferred pretty quickly during initial conversation); I am 99% sure you won't get the job. Then on another one make yourself just average tech performer but amplify agreeability with the interviewer's ideas. What would you guess would give you (much) better success ratio?

Re: Solving dynamic programming interview problems

#163

Post by bogomipz »

dahart wrote: post #160
bogomipz wrote: post #159

Earlier quoted context omitted.

>"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?" 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.

> There is no way to tell Python(CPython anyway) in which memory space you would it to create that object. Ah right, that's because all objects are heap-allocated. You choose heap by using an object for the stack, and rewriting your recursion to use (superficially) iterative code. You can choose stack allocation instead by using regular recursion: native function calls with local variables. What you bring up is an in…

>"You choose heap by using an object for the stack, and rewriting recursion using (superficially) iterative code.

You can choose stack allocation instead by using regular recursion: native function calls with local variables."

I'm not following you.

I believe these would both result in the same thing in Python. Python gives you a reference to an object. That object is stored in a private heap "somewhere." That reference to the object that Python gave you is stored on the stack. The object that it points to lives in the heap. This should be the same for both of your examples. I'm not sure what you mean by "native function calls." I am not familiar this this term.

Re: Solving dynamic programming interview problems

#165

Post by dahart »

bogomipz wrote: post #163
dahart wrote: post #160

Earlier quoted context omitted.

> There is no way to tell Python(CPython anyway) in which memory space you would it to create that object. Ah right, that's because all objects are heap-allocated. You choose heap by using an object for the stack, and rewriting your recursion to use (superficially) iterative code. You can choose stack allocation instead by using regular recursion: native function calls with local variables. What you bring up is an in…

>"You choose heap by using an object for the stack, and rewriting recursion using (superficially) iterative code. You can choose stack allocation instead by using regular recursion: native function calls with local variables." I'm not following you. I believe these would both result in the same thing in Python. Python gives you a reference to an object. That object is stored in a private heap "somewhere." That refere…

Sorry maybe I’m making it more confusing than it needs to be, I think you do understand the terms.

What we’re talking about is the difference between calling a function recursively (a function that calls itself) and instead simulating recursion using a data structure posing as a stack and an iterative function that doesn’t call itself but instead pushes and pops into your fake stack data structure.

You can either use the system’s built-in stack (by calling functions), or create your own fake stack (by pushing/popping, writing/reading an array, etc.).

Using sys.setrecursionlimit() as mentioned at the very top of this thread only affects the system stack. By “native function calls”, I just mean regular function calls. These are subject to the system’s stack limit.

When you allocate an object and use it as a fake stack to replace the system stack, the size of the object is not subject to the system’s stack limit (which is small — on PCs often a megabyte or two), it’s only limited by the available size of the heap (which is normally large relative to the system stack limit, often gigabytes).

When you make your own fake stack and use an iterative function, you can achieve a much greater recursion depth because your fake stack size is on the heap and not actually in the system stack.

Does that make more sense? The two cases are very different in Python, and using a fake heap-allocated stack, i.e. a Python object, is super useful.

Re: Solving dynamic programming interview problems

#166

Post by bogomipz »

dahart wrote: post #165
bogomipz wrote: post #163

Earlier quoted context omitted.

>"You choose heap by using an object for the stack, and rewriting recursion using (superficially) iterative code. You can choose stack allocation instead by using regular recursion: native function calls with local variables." I'm not following you. I believe these would both result in the same thing in Python. Python gives you a reference to an object. That object is stored in a private heap "somewhere." That refere…

Sorry maybe I’m making it more confusing than it needs to be, I think you do understand the terms. What we’re talking about is the difference between calling a function recursively (a function that calls itself) and instead simulating recursion using a data structure posing as a stack and an iterative function that doesn’t call itself but instead pushes and pops into your fake stack data structure. You can either use…

I see, yes. It sounds like we are same thing then. Cheers.

Re: Solving dynamic programming interview problems

#167

Post by monocasa »

dahart wrote: post #151
throwaway344534 wrote: post #128

Earlier quoted context omitted.

More like they were using C, saw the prospect of unbounded stack calls unreasonable with a computer with limited ram and banned recursion. Oh wait that's exactly what happened because iteration is safer than recursion.

Iteration is not inherently safer than recursion. NASA also banned while(true) iteration. The important part is "fixed upper bounds". "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.sema…

The static analysis tools have a harder time parsing the upper bounds on recursive functions, and so do the engineers doing the code reviews for similar reasons.

This isn't just a NASA thing. Pretty much any embedded coding standard says the same thing. The JSF C++ standard, and MISRA-C I know both do as well, just off the top of my head.

Re: Solving dynamic programming interview problems

#168

Post by celim307 »

I just give them a real world issue/bug/feature and ask them how they would complete it. Obviously im looking for as best an answer they can give me without knowing my whole stack, but what's even better is if they ask questions about my stack. Shows they know how to do requirements gathering and if they ask the right questions.

Re: Solving dynamic programming interview problems

#169

Post by bkdonline »

bogomipz wrote: post #142
ghettoimp wrote: post #140

Earlier quoted context omitted.

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".

>"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?

I guess the foreach is where each iteration has independent operation, vs a generic for loop where this iteration depends on result of the previous iterations.
Post reply on HN