An Interview Question

Once upon a time my favorite technical interview to conduct went something like the following. It consisted of me writing some really broken multi-threaded code and using that as a conversation starter. Candidates would drive me through discussing everything from cpu architectures, caches / cache coherency, compilers, threading, concurrency / parallelism, schedulers, and all sorts of related topics.

Below is a high level sample of how a conversation might go.

Note: Merged many of the various directions candidates would take the interview, no one hit all these points, and I am sure all these years later I am missing some neat ideas candidates brought up. Conversations were obviously more deep than what is recorded here. Also slightly modernized my broken code and made it c++ instead of c.

I: Given the following code:

ce

#include <iostream>
#include <thread>

int g = 0;

void f1() {
	for(int i = 0; i < 100 ; i++) {
		g += 1;
	}
}

void f2() {
	for(int i = 0; i < 200 ; i++) {
		g += 1;
	}
}

int main(int argc, char **argv) {
	std::thread t1(f1);
	std::thread t2(f2);
	
	t1.join();
	t2.join();
	
	std::cout << "g is now " << g << std::endl;
	
}

I: What is output at the end of execution?

C: Umm, well, it is non-deterministic.

I: Sure, but it is constrained, what possible values do you think could be output?

C: Maybe 100 or 200 or 300?

I: What the psudo-assembly look like for those functions?

C: … something something, hmm well, maybe the compiler optimized the loop away. It may recognize that loop is just an ld ; add 200 ; write instead of a loop.

I: Interesting, what would change if I marked g as volitile? Would that change the possible answers?

C: I think anything in the range 2-300

I: Great! Walk me through a possible scheduling of the two threads to get 2?

C:

I: Noice! Assuming the intent was to output 300, how would you fix the code?

C: Something something mutex! Either in the loop or outside the loop in f1/f2 Outside the loop would probably be more efficient, but in that case may as well just increment g by 200 or 100 like the optimizing compiler ;)

I: Great. What if the code is part of an RTOS system, and now I want to add the following ISR. How could we fix the code knowing the ISR code could be triggered at any time?

void ISR() {
	g += 1;
}

C: I don’t know, maybe just replace the mutex by disabling interrupts for the critical sections? Or maybe if the architecture has some sort of atomic instructions, Compare and Swap instructions?

I: Excellent! You’re hired; I quit. 😆

Where would you take the conversation? What did I miss? Ping me on twitter and let me know.