On: Google interview questions - fun brain teasers

[tlrobinson]

I think questions like the golf ball and blender ones are silly, but I like questions like "How would you find out if a machine’s stack grows up or down in memory?".

Here's one way in C...

    void stacktest(void *pa) {
        int b;
        void *pb = &b;
        printf("grows %s\n", (pb < pa) ? "down" : "up");
    }

    void main() {
        int a;
        stacktest(&a);
    }

[aston → tlrobinson]

We just talked about this problem in the office yesterday. My officemate got asked this for the job he got at Google, and solved it the same way. His boss pointed out only after he accepted the offer that there's no need to make a function call--just allocate two local vars in main...

Also, the same answer basically works to implement "sizeof" for ints.

[huhtenberg → aston]

It is an obvious simplification, but his boss is wrong. The order of uninitialized variables can be changed by the compiler. For example to better package the variables due to an alignment requirements. E.g. allocating

  char a;
  long b;
  char c;
  short d;

on a RISC-style platform as "a,c,d,b" requires 8 bytes, while as a,b,c,d - 12. This may not matter in a majority of cases, but it some it does.

[aston → huhtenberg]

For homogenous variables (like two "int"s), I don't think you could make a strong argument for the compiler reordering them.

[huhtenberg → aston]

Some advanced optimization may benefit from this sort of reordering. Alternatively, a compiler that reorders all local variables for "security" purposes may mix even just two ints if it's implemented in a dumb way.

[tlrobinson → aston]

I was actually asked this problem on a job interview (not Google) and gave the answer your boss pointed out, but the interviewer then pointed out that local variables aren't necessarily laid out in memory in the order they're declared.

The function call is the only reliable way I can think of. Any others?

[huhtenberg → tlrobinson]

> Any others?

alloca()

Also, for the two-variable approach something like this should force the compiler to allocate variables in a required order:

  int main()
  {
     int foo;
     {
       int bar;
       ...
     }
     ...
  }

[utnick → tlrobinson]

would this work?

in main: int x; int *p = &x; start writing random data to p, p-1, p-2, etc etc return; if nothing bad happens the stack grows up?

[aston → utnick]

What's your definition of "nothing bad happens"? And how do you recover if it does happen?

[pfedor → aston]

Ummmm I may be way off base here but I remember hearing that some implementations (*BSD??) randomly reorder the local variables on stack to make exploiting buffer overruns more difficult. So if it's true then you do need to make a function call.

[aston → pfedor]

Not sure this is even possible with compiled code. Even so, you don't really change the buffer overrun attack vector at all by moving variables around.