Interview Questions Received, Reviewed

Prior to going indie, I was often an interviewee or an interviewer for a number of game studios. I thought it’d be fun to share some of the questions I’ve received over the years and discuss my responses at the time, and how I might respond now in hindsight. Out of respect for the studios and interviewers, I won’t specify where I received these interview questions (or who interviewed me). I may also slightly alter some of these questions at my discretion to add some information entropy, but the main idea of the question will remain intact.

Blast from the past

So without further ado, let’s look at 4 random interview questions I can recall. The newest of the questions presented here are still from a decade ago, so I think I’m within my rights to share them with impunity.

Reversing a linked list

In C, write a routine that reverses a linked list.

This was one of the first software interview question I ever got in the industry, and I remember being extremely confused as to why I was asked this. IIRC, I asked whether we should just save ourselves the trouble and construct the list as a doubly-linked list instead (at the time, I didn’t quite understand the “spirit” of interview questions which are intentionally contrived to create a problem-solving scenario).

Eventually, I stumbled on a solution like the following: 

struct node_t
{
    node_t* next;
};

void reverse(node_t* n)
{
    node_t* last;
    node_t* temp;

    // Base case: No-op if list is empty or contains one element.
    if (!n || !n->next)
    {
        return;
    }
    
    last = n;
    n = n->next;
    last->next = NULL;

    while (n)
    {
        // We want n to point to last.
        // Store the next iterate in a temporary first.
        temp = n->next;

        // Redirect the current node to point to the previous one.
        n->next = last;
        
        // Update the previous node.
        last = n;

        // Advance the iterate.
        n = temp;
    }
}

Overall, not a bad warmup question in my opinion. Even if it’s fairly contrived, solving it on the spot is pretty doable for engineers across the seniority spectrum, and demonstrates that the engineer understands basic pointer manipulation and can reason through a basic control structure. One nice thing about this question is that compared to other questions like finding the midpoint of a linked list, there aren’t really any “tricks” to uncover in this question. The solution is about as O(N) as they come (I was asked the standard questions about space and time complexity also).

Write malloc and free

In C, write an implementation of the malloc and free interface.

This was another question I got early in my career. My response was pretty unsophisticated at the time:

  • First, I presumed that I had some way of reserving a block of memory from the OS (the interviewer conceded this).
  • Then, I basically implemented a free-list approach using a first-fit linear scan to locate a sufficiently large block to subdivide.
  • I used the first 8 bytes to store the start of the free list, and initially, the rest of the memory range was occupied with a single free list node.

I was fortunate to have read K&R’s C book only a few months prior to that interview, so the ideas in the chapter about memory suballocation were relatively fresh – otherwise, I’m sure I would have struggled a good deal more.

Overall, the interview was gentle in that I wasn’t asked to really optimize my solution more beyond getting it “correct.” Since that point though, I’ve had the opportunity to both write and use more “industrial strength” allocators, so my approach to writing malloc and free now would be a lot more nuanced.

Some ideas that come to mind:

  • Reserving memory from the OS (with VirtualAlloc or mmap) is a slow operation. In the context of a game, you really want to do only a couple upfront reservations where possible and suballocate within that, especially on console, since you can’t really afford a multi-ms intra-frame hitch.
  • The simplest “allocation” strategy is honestly a fixed static array of N objects of a specific type. This type of thing is compatible with multiple strategies for leasing/returning objects to the pool depending on usage, but works particularly well in the context of games where you want a well-defined budget for various object types anyways.
  • Most modern allocators are built with thread-local heaps that avoid the type of contention heap allocators used to really struggle with. For the most part, it’s no longer the allocation itself that’s slow, but moreso the memory access latency hit afterwards. For many types of objects that are “one off” objects or objects that aren’t processed in bulk, an allocation isn’t really as catastrophic as “hardcore” low-level programmers might make them out to be. IMO, you’re better off focusing your attention on proper memory management for the specific objects where this type of thing really matters (as opposed to trying to “ECS all the things”).
  • If console is a target, your allocator must be NUMA aware to some degree. Atomic contention on the same address across the CCX boundary is far too expensive to ignore. This is one of the main ways console development (on the CPU) still differs a fair bit from PC development, despite consoles now being “just x86”.

Another personal preference that’s developed is that I prefer bit-set hierarchies over free lists in many scenarios. Free lists are nice in that they are super easy to get up and running, but eventually, the disadvantages start to show:

  • Free-lists appear to be easy to leverage in a lock-free manner, but the ABA problem makes it so that you end up needing to shard free-lists across threads anyways (or leverage some other serialization mechanism or do sentinel value shenanigans). Point being that free-lists are easy until thread-safety is involved, at which point they suddenly become quite tricky.
  • Free-lists will naturally fragment over time, and merging adjacent free list nodes isn’t cheap.
  • Free-list nodes are temporally sequenced as opposed to spatially sequenced, so over time, allocations performed close together in time may be far apart in address space.

Allocators like mimalloc manage to solve all the problems above to varying degrees by doing various heroics. In the case of mimalloc, a non-deterministic GC is needed to handle cases where allocations are freed on a different thread than the original allocating thread. However, I honestly think a bit-set is likely good enough for many scenarios:

  • A compare-exchange on a bit-set entry doesn’t suffer from the same ABA problem that a free-list node exchange does.
  • Bit-sets are naturally coalescing, and neighboring unset bits constitute larger block ranges. This can permit some operations like extending an existing allocation that a free-list would struggle with.

Perhaps the main drawback to a bit-set (or a hierarchy of bit-sets) is the memory overhead, since unlike free-list nodes, occupancy bits can’t be interned in blocks of free memory. BUT, I think this has other advantages nonetheless:

  • Lookups against a bit-set are cache-friendly.
  • Because a bit-set isn’t interned within the free memory blocks, you can leverage bit sets to implement virtual allocators that manage remote memory, as you would for a sysram-resident GPU allocator.

Being able to share the allocation implementation between the CPU and GPU makes for some nice affordances which I’m enjoying in the Rookery. In particular, optimizations in the allocator benefit both the CPU and the GPU, and I can use the same tooling to visualize the heap and do other debugging operations.

Point-triangle interior test

In C++, given three points in a 2D plane, determine if a fourth point on the plane lies within the interior of the triangle defined by the first three.

I was fond of this question, because it seemed fair and also more relevant to my actual graphics-programming day job. The way I approached it was in the “vector” style of constructing a vector associated with each edge, then determining if the point was on the right or left side of the edge with a cross product. If the point was on the “right” side of each edge, I declared the point in the triangle interior.

One tricky bit of this approach was also accounting for the triangle orientation, since the points as presented could have been presented in either a clockwise or counter-clockwise order. I was aware that this would be a problem, so I handwaved it away but then I forgot to circle back to this point at the end (the interviewer had to remind me, whoops!). Luckily, it’s not too hard to just take a cross product of the triangle edges and compare the test orientations with the triangle orientation instead.

If I was asked this question again today, I could take a similar approach, but have since picked up a few more ideas:

  • Aside from wanting to know if a point is in the triangle interior or not, you often want the barycentric coordinates as well, so you might as well just compute the barycentric coordinates and check if those values are in the unit interval as opposed to a dedicated interior/exterior test.
  • If I was to implement this today, I would be a lot more sensitive to matters concerning floating point precision.
  • I’d also consider singular cases more carefully:
    • What happens if the point to be tested is exactly on a triangle edge?
    • What happens if the point to be tested is exactly on a triangle vertex?

The barycentric approach is what I’d do today if I needed this routine, because it’s more flexible and just as fast (despite needing a bit more algebra).

What makes a BRDF a BRDF?

Describe for me the properties of a BRDF.

(BRDF in this case being a bi-reflectance distribution function). Now, I must confess that while I don’t think this is an objectively good interview question, I actually loved this question because how often do you get to namedrop a concept like Helmholtz Reciprocity in an interview and get away with it? When I encountered this question, it was maybe a year after the game graphics community had just underwent the physically-based rendering rennaisance, and being formerly a student of physics myself, I consumed that material voraciously. In hindsight, I technically got this question wrong since while I mentioned Helmholtz reciprocity and energy conservation, I neglected to mention the positivity requirement.

If I was asked this question again, I would give a similar response, but probably would extend my response to include optional desiderata. That is, properties of a BRDF we don’t necessarily need, but are certainly nice-to-have:

  • Small parameterization
    • At the end of the day, one of the primary customers of the BRDF are artists that need to actually author and manipulate materials, so being able to distill a large range of optical behaviors in a small parameter set is ideal, not just for ease-of-use, but also for memory (since BRDF parameters tend to wind up in texture data).
  • Easy to sample/integrate
    • Rendering BRDFs requires actually evaluating the BRDF for one or many values of the incident direction, so there is an accuracy-speed tradeoff at play.
    • Being analytically integrable is often too high a bar, so we often settle for the next-best-thing. BRDFs that are quick to sample are amenable to other quadrature methods (e.g. Monte Carlo or brute force uniform quadrature).
    • Aside from being easy to sample, an even more desirable property is a BRDF that is easy to importance sample. That is, if it’s easier to sample directions that are biased towards the dominant portions of the BRDF in a controlled manner, this can lead to a faster converging integral. Now, a fair bit of research is understandbly concerned with figuring out more efficient ways to sample predominantly used BRDFs (e.g. vNDF sampling). I suppose what I’m pondering is if it may make sense to work in the opposite direction: designing a BRDF that may sacrifice accuracy in order to permit cheaper sampling. I don’t have an answer to this question at the moment, but this is sort of where this hypothetical interview question would lead me.

I actually think this question is still quite relevant today, since I’m getting a little tired of “the look” that so many games have due to a high convergence of:

  • choice of BRDF model and parameterization
  • choice of BRDF-environment light integration approximations

I’m looking forward to implementing the material and lighting model in my engine, since it will give me a chance to make these choices from first principles (and hopefully have something interesting to share).

To be continued…

Overall, it’s been fun to reminisce a bit on past evaluations, in part because it’s fun to see ways in which my thought process has changed over the years. I think questions that allow the interviewee to explore a range of potential responses and considerations are good questions – so aside from the first warmup-style question here, I think all the other questions are vindicated as being fairly decent questions (at least, for the type of work I do).

With that, I think this is a good place to pause! I have a bunch of additional questions that I think carry interesting insights with the benefit of hindsight that I will share next time!


Discuss this post on Patreon.