a strange but powerful interview question

I got asked this question a long time ago in a job interview and it actually sat with me for so long that I've decided to make a video about it today this is almost a couple years later the question was write a program in C that will determine if the stack grows up or down for the computer architecture you're working on I found the question so profound because it allowed the interviewer to get so much information about the candidate's knowledge with just a couple lines of code it allowed them to know if the interview even knew what a stack was if they knew how to code in C and if they knew how under the hood what the C code does and if they could produce the code to answer the question and hey guys also if you're new here my name is Ol learning we talk about all things lowlevel programming like C rust and assembly if you like that kind of stuff follow along with me and also hit the sub button so how would you tackle this problem how do we determine if the architecture we're living on has a stack that grows up or down first we have to talk about what the stack actually is and I made other videos about that but put basically when the CPU goes in between functions it creates stack frames or region of memory memory to address its local variables now on most computer architectures the stack actually grows negatively in the negative Direction it becomes more negative as it gets bigger but this may not be the case for all computer architecture some of them may actually add to the stack pointer as the stack gets bigger so we have to write a function to figure out what direction is our stack growing we'll start here with this C code and what this code does is it calls the Upp or down function if up or down returns true then it grows up if up or down returns false then it grows down I had to kind of sneak in my cheeky Turner operator in there I know how much we all love those very much the function will return up if positive down if negative I think we should probably Define also what up means so up means that the stack as it grows the address of the stack frame is increasing and as the stack grows down is becoming more negative so as it gets bigger the top of it becomes more negative this is actually how Intel behaves by default the stack grows negatively towards the Heap obviously it has 2 to the^ of 64 bytes generally to work with so it's not a big issue um but this is how it's happening under the hood but again some other architectures May behave this way so we want to figure out how to check for that now the way that you could probably check for it pretty simply the one that a lot of people go to by default and I went to by default in the interview is you on the stack you declare two variables right so here we have int X and int y they have undefined values I guess we could say zero to get rid of all the security people in the comments um and what what'll happen here is it'll allocate room first on the top of the stack for x and then under it just in our notional picture picture your stack of plates the address y so then we can say if x is greater than y and again we're not talking the values of X we're talking the addresses of x if x is greater than y then what we can do is just return true because that means that X is on top X is more negative and true is a lowercase T here otherwise we're just going to return false right so what'll happen is if x is growing up it is getting more positive but if x is growing down it's becoming more negative so let's check this out and have to also include standard bull because C by default does not know what the word true means okay so this actually worked because the stack on the architecture that I'm on the Intel assembly architecture does grow down this code does have actually a few problems first of all we are not labeling these as volatile variables so there may be a case where the compiler does some optimizations here so we do want to also throw the volatile keyword into these variables to make sure that the assembler does not try to optimize them in any fancy ways now can you think of another assumption we're making with this problem by doing it this way so again in our notional picture of the stack here I'll make another comment block to kind of describe this we are assuming that when the assembler creates the stack it creates room for X on our notional top and then underneath that we create room on beneath it for our notional Y and then we're just trying to see which one is more negative and returning that value but the Assumption we're making here is that the assembler is putting it in that order it may not it may for some other optimization reason just put X below maybe it's doing a you know a fifo versus a first in last out when it's making the assembly the the stack allocations so this is not the most efficient way to do it I want to see if you can think of another way to check if our stack is growing up or down let me know okay you ready for it the way we're going to do this is through a little bit of recursion now let me explain to you what we're going to do here when we use variables in C we do make room for them on the stack however we also use the stack to call additional functions so if I have up or down call itself that will produce a new stack frame for its variables in some location so what we can actually do is pass around a variable in between upper down to itself and then compare the address of those two variables because we do it that way we'll have knowledge about the address of one stack frame versus the other and we can return whether one is greater than the other so let me walk through how that works right now okay you ready the solution for this is really cool so we have made up or down a recursive function now I know if recursion scares you don't worry about it it's not that bad all you have to think about is a base case and a non-base case the recursive case so what we'll do is we'll start with our recursive case where we call up or down and give it a null pointer meaning I have no information about the stack at this point so we'll go into our function here and again bull upper down now takes an INT pointer we passed it null for the first one and we have an integer X on the stack if there is no other variable meaning that we have no information about the stack yet we have to generate the information ourself with X we'll just return up or down the address of X we'll return up or down with the address of X that will enter another layer of up or down where now the in other is set we'll say up or down we'll now go to the other case and all we're going to say and again we're in a new stack frame here we've created another stack frame because we called the function again and we say return if this variable the N the one that's above it in our notional directionless stack frame return if the address of that variable is greater than the other that will come back to the base case it'll return here and that'll come out our Upp or down Case by using simple recursion we can solve this problem really cleanly and have a way that can't get optimized out because we're doing recursive function so let's go ahead and compile this and see what trouble we get into and we find that the stack frame as it's supposed to still grows down so what do you think this one little question and a couple lines of C may just reveal if we know how Stacks work how C Works how calling conventions work and a lot of really interesting things underneath the hood as it relates to computer architecture and lowlevel programming so if you enjoyed this video do me a favor hit that subscribe button and if you enjoy these kinds of problems go check out my website pone bounty.com description below and if you like to solve these kinds of challenges I'll be putting up challenges like this and if you solve it and submit a write up you might even get a job we'll see how it goes all right guys thanks for watching take care see you next time

Channel: Low Level Learning

Views: 266,570

Keywords: malloc, c programming, c++, memory allocators, heap

Id: V2h_hJ5MSpY

Length: 7min 1sec (421 seconds)

Published: Sun Jan 21 2024