Tough Interview Questions

This thread got me worrying. I have an interview coming up with a software company notorious for tough interviews with questions such as the linked thread.

What kinds of tough thought problems have been thrown at you?

well if it is the same company, as i said in that thread, a lot of groups really downplay the “wacky” questions now.

You have two files:

array.c:


char hello[] = "Hello, world!
";

ptr.c:


#include <stdio.h>
extern char *hello;

main()
{
  printf(hello);
}

You try to compile and run them. Explain what happens and why.

I know there must be a trick, just can’t figure out what it is.

The answer to the first part is that each file will compile just fine, and the linker will create an executable just fine. But the resultant executable will generate indeterminate results, probably a core dump.

As for why, it’s because in C and C++, pointers and arrays linguistically look very similar, but internally they’re quite different animals. At the memory location where a given array exists, there will be the explicit array. At the memory location where a given pointer exists, there will be an address.

Here’s another one: you have two rectangles, a and b. Each has an x,y origin coordinate, a length l (in the x direction), and a height h (in the y direction). L and h for each of them are guaranteed to not be negative. Write some pseudocode to detect if the two rectangles intersect.

You know, at first that question looked easy. Then I though about it and it seemed pretty difficult. Then I though about it some more and decided that it’s not difficult at all - just tedious.

Without actually writing any pseudocode, you can tell if two rectangles intersect if they meet one of two criteria. One: one of the corners of either rectangle lies inside (or on the boundary of) the other rectangle. That’s pretty easy to figure out. The only other case is when the rectangles form a “plus-sign” configuration, where every edge overlaps two other edges, but none of the corners are within the other rectangle.

None of that would be difficult to code, but I can’t think of an easy way to make it look nice. It’s going to be some messy code.

Let me be a little more specific. Use no more than 4 comparisons.

I’ll take a stab at it out of boredom.


Function Intersect(ax, ay, al, ah, bx, by, bl, bh) As Boolean
  Intersect = Not ((ax+al < bx Or ax > bx+bl) And (ay+ah < by Or ay > by+bh))
End function

General Questions is for questions with factual answers. IMHO is for polls.

Off to IMHO.

DrMatrix - GQ Moderator

I could be wrong, I believe

(A x B)\intersect (C x D) = (A\intersect C) x (B\intersect D)

So you can just check for the intersection of the intervals that are the projections of the rectangles onto the x-axis and y-axis. I believe this can be done with two comparisons each. For [a,b] and [c,d], you need to compare a with c and b with d.

Oops, that should be, b with c and a with d.

bitwise has the right answer.

Here’s one I like.


class D
{
    public:
        D() { n = 0; };
        ~D() {};

       int foo() { return 0; };
       int bar() { return n; };

    private:
        int n;
};

int main()
{
    D* badPointer = 0;

    if ( badPointer )
        badPointer->foo();
    else
        badPointer->bar();

    return 0;
}

What happens when that code is compiled? What about when it’s executed? And most importantly, why?

Compiled? I think it will compile fine.
Running? A segmentation fault when you try to dereference this->n.

What line does it choke on, and why?

You might want to compile and run this to be sure.

Really? Reading the requirements, I think he was looking for my answer. (“No more than 4 comparisons”…)

But I agree with Joe Random that it is more tedious than complex.

It chokes in bar(). It tries to put this->n on the top of the stack. When it tries to do so, it’ll get a segmentation fault.

As far as the rectangle question, there were quite a few people who would try do do point-in-rectangle tests and line-cross-rectangle tests that went out so far they’d hit the back of your head. You both got the answer right, though in different forms.

Of course, if you have the compiler optimize the code, it might be smart enough to inline bar(), at which point it would realize the return value is being ignored, and would then just do nothing. Then it wouldn’t crash at all.

I was trying to show how one would approach the problem. I put down the first thing that came into my head. “A rectangle is a Cartesian product of intervals. Can I solve the problem with intervals first, and then work my way back up?” etc.

Shhh, I’m trying desperately to avoid admitting that I don’t even understand your solution.

Ah, crap, I went and did it. In the interest of fighting my ignorance, could you elaborate your answer?

For example, my thinking was “no edges can overlap”, and thus my answer.

My questions:

“” is integer division?

What are you referring to when you say “intersect”?

Sorry, it was sort of a LaTeX-ish notation without resorting to full LaTeX; perhaps, I should have gone with full LaTeX to be less confusing. That would be

(A imes B)\cap (C imes D) = (A\cap C) imes (B\cap D)

Here imes denotes Cartesian product and \cap denotes intersection; in my original post, \intersect denotes intersection and x denotes Cartesian product.