A question to IT KBers, part III

[Street Gerbil]

Guys and gals, you are fantastic!
You have been very helpful so far. I haven't got any viable leads yet, but at least, thanks to you people, I have made up my mind and have firm idea as to how to proceed. I am going to treat myself to a boot-camp style C++ refresher, and at the same time (thank you Microsoft for a fresh and shiny copy of VS 08 development environment) undergo a crash course in C#.

Before I proceed one step further, I would like to ask you my fellow bikers for some intelligence (in both senses of the word).
What was your experience at job hunting?
Is it best to apply via a headhunter or directly to the company?
From your experience, what are the things interviewers seem to focus on?
What are your favorite questions or puzzles that you remember?
Do you know of any programming brainteasers I can practice on?
Bring it on! Throw it at me!
It is a brainstorm, people. Speak up, everything goes!
Thanks!
SG

[Street Gerbil]

The silence is deafening...
Ok, let me start.
1) This one had me puzzled. I could not solve it on a whiteboard. Certainly not in allotted time. "Write a program that prints all permutations of characters in a string". If interviewers ask this kind of questions, I'd better apply for a McJob...

2) Figured out this one :-) How to write a function that swaps two variables without using a temporary variable?

[jrandom]

1) This one had me puzzled. I could not solve it on a whiteboard. Certainly not in allotted time. "Write a program that prints all permutations of characters in a string".

Um. Well, start by thinking about how many different permutations there are of a string of length n.

Then think, what's the simplest element that forms the difference between similar permutations, and how would you step through those differences?

You should be able to arrive at decent implementation of a solution to that problem within twenty minutes or so of whiteboard blathering. Problem-solving is about reducing things to their essences.

One test I like to use when interviewing programmers is "write a program that reverses a singly-linked list in place" ("yes, that's right, 'in place' means without allocating any new memory").

Any solution with computational complexity worse than O(n) (or, in fact, a nonfunctional solution, or a complete failure to find a solution at all) is a fairly good indication that they aren't very good at writing computer programs.



It's amazing, the number of guys who think they're competent programmers who choke when given a genuine problem to solve. They're so used to just copying ideas from cookbooks that they've forgotten how to think...

If interviewers ask this kind of questions

If they don't, you can assume that it's going to be a horrid place to work, because they don't know what they're doing.

[jrandom]

How to write a function that swaps two variables without using a temporary variable?

For an interesting application of a side effect of the standard answer to this question, see the 2007 winner of the Underhanded C Contest (underhanded, not obfuscated).

[xwhatsit]

One test I like to use when interviewing programmers is "write a program that reverses a singly-linked list in place" ("yes, that's right, 'in place' means without allocating any new memory").

Er... just reverse all the links?

A->B becomes A<-B.

prev = null;
curr = link.getFirst();
while(curr != null) {
    next = curr.getLink();
    curr.setLink(prev);
    prev = curr;
    curr = next;
}

Does that work? Or should I go to bed. I'm using temporary pointers, does that count?

As for swapping two variables without using temporary variable,

a = a + b;
b = a - b;
a = a - b;

[Street Gerbil]

One test I like to use when interviewing programmers is "write a program that reverses a singly-linked list in place" ("yes, that's right, 'in place' means without allocating any new memory").

Any solution with computational complexity worse than O(n) (or, in fact, a nonfunctional solution, or a complete failure to find a solution at all) is a fairly good indication that they aren't very good at writing computer programs.

It's amazing, the number of guys who think they're competent programmers who choke when given a genuine problem to solve. They're so used to just copying ideas from cookbooks that they've forgotten how to think...

I must be one of them. I do not see how you can reverse a linked list without using at least three extra pointers to hold the elements in place while you are reshuffling the links.

For me, unfortunately, for the last ten years a criteria of a well-written program meant, that a supporter in Puna can understand and modify the code as expected without spending 12 hours on the phone... That's what OGSing large business applications does to you :-((((. You get fancy with a code, you are being asked to rewrite it for clarity. You are being asked too often, it gets recalled on a performance review.

[xwhatsit]

Actually, why not treat it like a stack?

You could pull nodes off the list and put them into a new list -- backwards -- but don't create a copy. Actually delete them and move them to the new list.

Rewritten after looking at the most basic style of linked list functions on wikipedia:

List newlist;

while(oldlist != null) {
    insertBeginning(newlist, oldlist.firstNode);
    removeBeginning(oldlist);
}

Of course then you've still got one extra node in memory for a bit (newlist holds a pointer for the new value (which a pointer is already held for in oldlist) until removeBeginning() is called).

[Street Gerbil]

The only way I can reverse a list is by creating 3 new pointers:
one pointing to the first element (p1), one pointing to the second (p2), and one temporary for holding the third in place while you shuffle the second (p3).
You start checking. If your root is null, you return, job done. If you have one element (i.e. root->next is NULL) - ditto.
You grab your first element, set its next pointer to zero, and make your root point at it. This is your new end of the list. Next you save p2->next in a p3, and change p2->next to point to root and root to point to p2. Job done... well almost. You set p1 to point to p3 (new root of the old list) and p2 to p1->next. You repeat that while p1->next is not null. Voila, the list has grown in the opposite direction.

Feel free to trash my solution.

[Street Gerbil]

a = a + b;
b = a - b;
a = a - b;

Nah, that can cause an overflow.

This one should not:

a = a ^ b;
b = a ^ b;
a = a ^ b;

Ahh the beauty of XOR...

[jrandom]

I must be one of them. I do not see how you can reverse a linked list without using at least three extra pointers...

That's fine; I meant allocating new list item objects, not 'you must write a function with no variables'.

The supposition is that you don't know how big the input list is going to be, and you cannot guarantee that the system will have memory space for two of it. A function using a fixed amount of memory is fine, but a function that uses additional memory in proportion to the size of its input is not.

Does that work?

Yes, that's the bugger.

And you'd be amazed at the number of folk applying for programming jobs who can't work that straightforward iterative solution out on a whiteboard, or come up with some sort of O(n^2) monstrosity that involves walking to the end of the list after examining every node, etc.

I generally took pity on them and administered a coup de grace to the interview after 20 minutes or so of um-ing and ah-ing.

Actually, why not treat it like a stack?

Like a stack? It'd be difficult to do that without allocating a new list, no?

You can write a recursive function to do the same job as your iterative function, but that requires growing your program's stack by the same number of steps as there are elements in the list, so it kinda breaks the "don't allocate" requirement.

Feel free to trash my solution.

Don't be silly; you and xerxesdaphat came up with the same correct solution. Although it's easier to read when it's written down as pseudocode rather than some sort of narrative...

Nah, that can cause an overflow... XOR...

[imdying]

And this is how we got to things like the .NET framework. I'm not (generally) paid to feck about reinventing the wheel when using the List's reverse method works just fine.

[enigma51]

And this is how we got to things like the .NET framework. I'm not (generally) paid to feck about reinventing the wheel when using the List's reverse method works just fine.

I fully agree

And people wonder why projects never deliver on time or budget

Random how many of your project are on time?

I ask a simple question in interviews

If the person over complicates i dont want him.

and yes my question is as simple as write me a hello world program!

[enigma51]

or come up with some sort of O(n^2) monstrosity that involves walking to the end of the list after examining every node, etc.

I generally took pity on them and administered a coup de grace to the interview after 20 minutes or so of um-ing and ah-ing.

I bet you people queue up to work with you.

[imdying]

Well, to be fair, I'm expected to know how to do things like that the long way, we don't always work with frameworks. However, productivity == profit, so the better the practical knowledge of the framework, the better off an employee; no point writing something to trawl an active directory (for example) when all that functionality is all built in... but if you don't know that namespace exists, then you're on the back foot immediately.

[jrandom]

And this is how we got to things like the .NET framework. I'm not (generally) paid to feck about reinventing the wheel when using the List's reverse method works just fine.

Yes, there are always guys who insist on answering like this.

And I've lost count of the number of times I've seen guys who would answer that question that way go on to write O(n ^ 2) algorithms where O(n) ones would do, and thereby slow systems written in .NET etc to a crawl when a proper understanding of the basics of computer science would have saved them and their customers.

Doing basic stuff like efficient list manipulation in an interview is just a way of showing that one knows how to approach a problem properly.

Ever sat in front of a computer running bespoke software of some sort and watched a display inexplicably crawl across the screen for no obvious reason, instead of doing stuff quickly?

99% of the time, it's due to some programmer who doesn't think that knowing the theory of data structures and algorithms is important.