Tough Interview Questions

Um, okay, sure. Thanks?

Clearly I will not comprehend what you’re talking about, as the only characters in your clarification I understand are the parentheses and the equals sign.

Here are some interesting puzzle sites.
I’m not sure if some of these would qualify as interview questions. I think some of them would take longer than the time alotted for an interview to solve. I take a stab at them every now and then. I get some ideas, but almost never a full solution; I’m not sure if they are that hard, or I just haven’t devoted enough time.
and the forum

Not all of these are invertiew questions either. They are divided into difficulty level. Some of them require mathematical sophistication; there is even a section devoted to Putnam questions.

The specific code that I wrote there will crash?

If you don’t know LaTeX (and most people here wouldn’t, so it’s generally avoided), that might be a bit tough to read.

Would it help if I said (A [symbol]Ç[/symbol] B) [symbol]´[/symbol] (C [symbol]Ç[/symbol] D) = (A [symbol]Ç[/symbol] C) [symbol]´[/symbol] (B [symbol]Ç[/symbol] D)? Those are standard set-theoretic operators.

Too lazy to log on to a box with a C++ compiler, but I’m gonna guess that it barfs at runtime in D::bar. It won’t choke earlier because it’s a non-virtual method, which means dynamic dispatch won’t be involved, which means the method will be resolved at compile time, which means the method will get invoked, but with an invalid “self” or “this” object (I forget what C++ calls it–I’m more of a CLOS guy :)). It’ll add the offset for the “n” variable (platform and compiler dependent) to 0 and try to access the memory at that location to determine the value of “n”, which will generate a segfault (if you’re on a platform where a reference to that address will generate one…)

It’s probably easier to read that code correctly if you add in the ! operator that I left out of the line that should read if ( !badPointer ). Mea culpa.

How did you know what characters to put in the symbol-tag? What is the mapping?

Windows has a utility called charmap that’s very helpful for this sort of thing.

Hmm… I seem to recall something about C++ allowing all methods that are declared within the class definition to be inlined. I don’t know if the standard requires that behaviour or merely permits it, and, frankly, I’m not about to crack open my annotated C++ reference without getting paid to do so. And even if it required it, I’d be really shocked if it required compilers to implement unused expression elimination.

Don’t worry about it, I don’t want to hijack this thread any further, as I think it’s an interesting topic.

The short answer is no. Basically, I have a 9th grade education, and am a self taught programmer by trade. I have a propensity for logic, so I’ve earned my money designing databases, and my strong suit is (no surprise) user interfaces. (Teaching myself C resulted in 3 unrelated instances of accidentally overwriting my partition table. Doh!)

I’ve never heard of LaTeX or “Cartesian product”, and I can’t fathom “intersect” in the context of bitwise’s second post. I’ve seen [symbol]Ç[/symbol] in the book Infinity and the Mind, but I didn’t really understand that book tremendously well.

Thanks for the effort, but any more would be wasted. Please resume discussion of interview puzzlers.

Oh, in that case, it’ll compile and run fine, because it’ll call D::foo, which doesn’t reference any instance variables (or whatever C++ calls them).

Here is a puzzle I find interesting. I don’t remember if this is discussed in the second site I linked; it most likely is.

You are given an array containing integers from 1 to n. One integer appears exactly twice; n-2 integers appears exactly once; and one integer does not appear at all. Find the missing integer in the most efficient way possible in terms of both time and memory.


Finding the repeated integer and finding the missing integer are the same in difficulty. Your solution will probably find both simultaneously.

I know of two ways to solve this problem.

Hint (first way)

I call this way a “math hack”. Think about solving equations. It is a clever trick with mathematics — not very advanced mathematics, I would say high-school level. Actually, I know of two math hacks with the same theme; the principle is the same.

Hint (second way)

This way is more “CS-y”. It uses general CS ideas you would learn in an undegrad curriculum. A permutation can be decomposed into disjoint cycles. The array isn’t quite a permutation, but it is “close”. Think about this and how bucket sort works.

I know you don’t want to get into a digression, but I will make one last attempt to explain with as much English as possible.

Given two sets A and B, their intersection A[symbol]Ç[/symbol]B is the set of all elements contained in both A and B. For example, if A = {1, 2, 3, 4} and B = {2, 4, 6, 8}, then A[symbol]Ç[/symbol]B = {2, 4}. Now, suppose C = {1, 3, 5, 7}. Then, the intersection of B and C is empty, meaning they have no elements in common. This can be written B[symbol]Ç[/symbol]C = [symbol]Æ[/symbol]; the symbol [symbol]Æ[/symbol] denotes the empty set, i.e., the set containing no elements at all.

I’ve used sets of integers in the examples above, but you can have sets of points in a plane, fruits in a baskset, socks in my drawer, etc. Rectangles can be thought of as sets of points in a plane. Two rectangles intersect or “overlap” if their intersection is not empty. (Think of Venn diagrams if you know what they are; otherwise, forget it.)

Given two sets A and B, the Cartesian product A[symbol]´[/symbol]B is the set of all ordered pairs where the first coordinate is in A and the second coordinate is in B. For example, {1, 2} [symbol]´[/symbol] {3,4} = {(1,3), (1,4), (2,3), (2,4)}. If you denote the real number line by R, then the plane is the Cartesian product R[symbol]´[/symbol]R. Rectangles are then the Cartesian product of intervals of the real number line.

Above I’ve used Cartesian products of two sets, but you can have Cartesian products of more than two. A[symbol]´[/symbol]B[symbol]´[/symbol]C would be a set of order triples. In general, you can get sets of lists of any length n, or what some people call n-tuples.

Technical note: You’ll notice that I’ve used curly braces for sets and round parethenses for lists. This notational difference is important, because order and repetition do not matter for sets, but do matter for lists. For example,

{1, 2} = {2, 1} and {2, 2, 2} = {2} = {2, 2}


(1, 2) [symbol]¹[/symbol] (2, 1) and (2, 2, 2) [symbol]¹[/symbol] (2,2)

Thanks, that’s where I was intending to put it.

People that ask TRICKY technical questions during an interview should have their fingers smashed with a hammer. If they can’t just converse with you about technical issues and figure out whether you are worth your salt, or not, then THEY are the incompetent one. Just IMHO of course.

Well, how about:

The sum of integers from 1 to n is n[sup]2[/sup] + n. So, in O(n) time and O(1) space you can get the sum of the array, S. n[sup]2[/sup] + n - S will be o - t, where t is the number that appears twice and o is the number that is omitted. If that number is odd, the solution is simple – sum the even numbers and compare that number to 2 * (floor(n/2)[sup]2[/sup] + floor(n/2)). From that you can easily work out t and o. If t - o isn’t odd, you’ll have to wait until tomorrow, because I’m sleepy.

Is this the correct answer?

It crashes because your pointer = 0, no object is being pointed to. The rest is misdirecting fluff <wink>

Sometimes they’ll throw a difficult wacky question at you just to see how you would deal with a difficult wacky task. They don’t expect you to come up with the correct solution on the spot.
A clueless Candidate “A” might just shrug his shoulders and say “uh, I don’t know, we didn’t cover that in class”. But equally clueless Candidate “B” might say, “It might take me some time to come up with the solution, but if this was a real work situation I would ask around to see if this kind of thing was done here before. I’d find out who has some expertise in this area, and ask for some pointers on how to start. I’d also see if we have any documentation on this topic, and try to find ways to finish the task correctly in the least amount of time.”

It’s possible that I didn’t quite grasp what you intended, but did you mean that:

(A [symbol]´[/symbol] B) [symbol]Ç[/symbol] (C [symbol]´[/symbol] D) = (A [symbol]Ç[/symbol] C) [symbol]´[/symbol] (B [symbol]Ç[/symbol] D) ?

That obviously should have been “allowing all methods that are defined within the class declaration to be inlined.”