Dolphin, the GameCube and Wii emulator - Forums

Alright, the final regret in the job interview that completely blew it for me. So to recap I spent roughly 40 minutes on the previous problems getting increasingly nervous and frustrated during the entire thing. My brain as basically gone at this point, and I was working with binary trees which I don't have any direct experience with dealing with. So all around this last question was going to be a good time. So here it is , the final function that had to be implemented


That's it. That's all it was, a simple delete tree function. It iterates through all the elements of the tree and deletes them. So having a mental breakdown at this moment in time it takes me a few minutes to pump out some terrible code that uses recursion.

Still not told if we we need to allocate and destroy the C string at this point. Still doesn't really matter, since it's just a minor implementation detail. Note to those reading is that my solution at that time was not this clean and I messed it up severely multiple times before getting to that solution. But alright, that code works. The interviewer wants a non-recursive version of it. Because like we said earlier, we don't want the overhead of a bunch of recursive calls.
This bent me over and did my raw, at that moment I knew I was screwed, I had struggled with the recursive version and I'll completely blow this one. At this point I may as well as have been a stump, I was a fool, a mess, I was on the outside looking in. Screaming to myself mentally to calm down and think it through logically.
I couldn't, I was done. Ten minutes of me mumbling to myself and stuttering I hadn't had anything to show. The interviewer pitied me and gave me the answer instead. It's incredibly simple and clean, it hurt me more than any words could.

It made complete sense, the interviewer asked me if I understood how it worked. I cringed, I understood it completely. I fumbled out a few words saying I did plus some other unintelligible nonsense at the time. I had lost completely, there was nothing I could do. This is my regret, and it is one of the largest in my collection. If I redid the interview now I would still be a nervous mess just because of the companies reputation and have had wanting to work there since I was a child. I completely blew it with this company, and for that I regret.

So the non-recursive version thrashes the heap (with a bunch of vector resizing) instead of the stack. It might even run slower...

There is no vector resizing going on here - using a vector to implement a stack is efficient. After the first pop_back the vector will not immediately release the reserved memory, so the next push_back will be free until you hit the next realloc threshold.

In general using a stack you manage yourself for recursive algorithms is objectively superior - the behavior in case of very deep structures is easier to understand (at worst you run out of RAM, which is usually better than running out of stack space and happens at way larger scales).

Also, another unrelated random note. In part 1, your vector based solution is more terrible than you realized. On top of being O(N) memory, it's also O(N²) time since adding an element to the start of a vector requires moving all the other elements back. In an interview, I would think negatively of someone who would write this and not notice this problem (if he does notice the problem, that's fine, it's part of the thought process).

Last thing, you never really "completely blew it" with a company. Most companies understand that people can be stressed and not perform well during an interview and will gladly let you try again ~1y from now.

(What happened to your job in that english company that does ARM consulting stuff?)

For the feeling nervous part having the mentality that you have nothing to lose and only to gain helps me a bit here. I also have a problem of nervousness in many exams and interviews that i took so i feel you a bit there, hope this tip helps.

(11-04-2014, 09:56 PM)delroth Wrote: [ -> ]There is no vector resizing going on here - using a vector to implement a stack is efficient. After the first pop_back the vector will not immediately release the reserved memory, so the next push_back will be free until you hit the next realloc threshold.

That's a contradictory statement, you say there's no resizing until the theshold is reached whereupon the vector is resized. Realloc can quite happily turn the heap into swiss cheese if it's poorly implemented.

std::vector does exponential resizes, so the push_back complexity is an amortized O(1). Using a vector here is definitely appropriate in terms of speed - and definitely more safe than using the call stack to store state.

That's not guaranteed though. The std::vector documentation is as follows:

Quote:Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity (see push_back).

may != will
can != will
should != will
Rule #1 of using the STL: don't assume anything about the underlying implementation (unless you like nasty surprises). Only the interface definition is binding.

Yes, that's the difference between theory and practice. In practice, all STL implementations I care about have amortized O(1) push_back complexity. And when in the context of a job interview, you're definitely right to assume this as long as you explain it.

I agree that making these assumptions is sometimes dodgy, but I'd rather work with some assumptions than avoid the STL altogether. Maybe that's because I got used to working in a very homogeneous environment where I can check these assumptions "once and for all".

Unfortunately these sorts of problems aren't limited to the STL...
I've recently been working on an android app that uses depth textures to render 10-bit RGB images. Some devices work fine, others are horribly slow. It turns out the PowerVR OpenGLES library was compiled using software floating point (why....) and each pixel is converted from short to float by the cpu, meaning each conversion is done using a call to libc's __aeabi_i2f(). The libc on the device is from plain old gcc which only implements that function using integer math (again why....) so if I want decent performance I have to build and bundle my own libc.so with my app, with the aeabi floating point helpers implemented to actually use floating point hardware. All because someone at Imagination didn't use the right compiler switch.