181–190 of 409 posts
Earlier quoted context omitted.
All great until you come across someone with a permanent poker face. During my last interview, the interviewer was frowning the whole time.
As someone with a default poker face I am so sorry, I swear I smile, just on the inside mostly.
I bombed an interview at a game company because I gave a right answer that I couldn't get them to understand. I don't remember the exact problem they wanted me to solve, but the answer involved a dynamic collection and they wanted it to grow with constant time complexity. They were probably looking for a linked list. But I said I'd use a dynamic array because those have constant time when averaged over a series of ap…
Interestingly, you can use scheduling to make a non-amortized dynamic array. Your probably know this, but for other commenters who do not— Keep two arrays, of size n and 2n. Initially the first has capacity c = n/2 and the second has capacity 0. Reads go to the first array. When you append, append one element to the first array, and copy two elements to the second array. By the time the first array is full, it has be…
Earlier quoted context omitted.
If I remember correctly, that question likely refers to some argument in the driving manual about speeding. Something along the lines of "speeding in most urban areas doesn't actually help get someone to their destination faster. There are always multiple traffic lights and other cars to contend with, so it's not helpful to go over the speed limit and it increases the risk and severity of an accident." It's perfectly…
it isn't true though. suppose there are n lanes and more than n cars, which is almost always the case in the city. if you pass someone, even just to end up stopped at the same light, you are still ahead of them in line. moving ahead by one slot is a very marginal gain, but it does add up if you pass many cars on your journey. in addition to being ahead by however many slots, eventually you will encounter step-wise ju…
Keep in mind that driving manuals are deliberately written at a 6th to 9th grade reading level depending on the state.
Yes, you're right that the gains from speeding are marginal compared to the risk, cost, and stress. But it's hard to communicate that kind of nuance. If the manual just says lead-foots aren't going to get somewhere faster by speeding to each intersection that's "good enough" and very close to reality for the purpose of the manual. National merit semifinalists can get the queue-theory version from their high-school math/driving instructor during driver's ed.
I bombed an interview at a game company because I gave a right answer that I couldn't get them to understand. I don't remember the exact problem they wanted me to solve, but the answer involved a dynamic collection and they wanted it to grow with constant time complexity. They were probably looking for a linked list. But I said I'd use a dynamic array because those have constant time when averaged over a series of ap…
For games, it absolutely does matter that only some appends trigger latency, because that causes stuttering in the game play. A linked list may be slower in most use cases...but the performance cost is fixed and can be easily designed around.
In one case I argued for a while until we moved on. In the other, I was able to show the interviewer why I was right and they eventually saw my side. I'm not sure if this was poor communication on my part (definitely possible!) but I felt helpless. Still, I don't think I'd be able to intentionally say an incorrect answer just to get the job.
Can't really comment on whether that was the correct way to handle the situation, given that passing the interview was the goal. However, I would have a hard time giving an incorrect answer on purpose. I also consider an interview as an opportunity to learn about the company I'm going to work for, and especially my future colleagues. I would probably try to give a full answer, such as "there's a widely-held concept X…
The goal of the interview shouldn't always be to get the job. If you have any length of career, you are interviewing the company as much (or more) than they are interviewing you. My approach would have been to go with the new idea and see what discussion can come out of it. If they don't have time to get into it, that's one thing but if they are simply not open-minded to new ideas, I don't want to work there.
I bombed an interview at a game company because I gave a right answer that I couldn't get them to understand. I don't remember the exact problem they wanted me to solve, but the answer involved a dynamic collection and they wanted it to grow with constant time complexity. They were probably looking for a linked list. But I said I'd use a dynamic array because those have constant time when averaged over a series of ap…
It's not great to have to double your memory usage while you reallocate your array. On more limited devices (see games consoles or mobile devices) you'll end up fragmenting your memory pretty quickly if you do that too often and the next time you try to increase your array you may not have a contiguous enough block to allocate the larger array. There's also the cost of copying objects especially if you don't know if…
You don't have to use a growth factor of 2. Any constant multiple of the current size will give you amortized constant complexity.
> On more limited devices (see games consoles or mobile devices) you'll end up fragmenting your memory pretty quickly if you do that too often and the next time you try to increase your array you may not have a contiguous enough block to allocate the larger array.
If fragmentation is a concern, you can pre-allocate a fixed capacity. Or you can use a small-block allocator that avoids arbitrary fragmentation at some relatively minor cost in wasted space.
> Why copy these objects and incur that cost if you can choose a datastructure that meets their requirements without this behaviour.
We have an intuition that moving stuff around in memory is slow, but copying a big contiguous block of memory is quite faster on most CPUs. The cost of doing that is likely to be lower than the cost of cache misses by using some non-contiguous collection like a linked list.
> as its really not suited to the constraints of games and the systems they run on.
For what it's worth, I was a senior software engineer at EA and shipped games on the DS, NGC, PS2, Xbox, X360, and PC.
Earlier quoted context omitted.
Interestingly, you can use scheduling to make a non-amortized dynamic array. Your probably know this, but for other commenters who do not— Keep two arrays, of size n and 2n. Initially the first has capacity c = n/2 and the second has capacity 0. Reads go to the first array. When you append, append one element to the first array, and copy two elements to the second array. By the time the first array is full, it has be…
One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?
The source array might be considered to have even offsets (0, 2, 4, etc, index left shift 1 bit) relative to the double-sized array.
Addition operations past the halfway value of the smaller array have a relation to values in the second by (Index When a removal operation, like pop(), selects a victim in the source array the corresponding operations must also apply in sync to the values in the larger array.
I bombed an interview at a game company because I gave a right answer that I couldn't get them to understand. I don't remember the exact problem they wanted me to solve, but the answer involved a dynamic collection and they wanted it to grow with constant time complexity. They were probably looking for a linked list. But I said I'd use a dynamic array because those have constant time when averaged over a series of ap…
In game dev, that one copy might cause a frame drop. Even if amortized over time the frame rate would be slightly higher, the occasional dip might make it unplayable. Of course, arrays have better cache locality, but they didn't ask about that. They were probably looking for a linked list with a small array in each node, which gives more constant write performance and less cache misses on read.