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.

:niceone:

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...

:niceone:

[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<T>'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<T>'s reverse method works just fine.

I fully agree

And people wonder why projects never deliver on time or budget :crazy:

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. :zzzz:

[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<T>'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.

[Street Gerbil]

Don't be silly; you and xerxesdaphat came up with the same correct solution.
I knew I started this thread for a reason. Admittedly it never occurred to me that at an interview I can just write a couple of lines of pseudocode instead of tediously chasing all the pointers and making sure that the counters are not off by one or that I haven't forgot to declare a loop counter (my favorite pen-and-paper based coding bug). Thanks for the tip!





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?

On the other hand I've seen programs crashing in the production environment after a programmer has decided that an infrastructure class is not fancy enough and implemented some kind of ultra-fast search algorithm without realizing that if a user hits cancel at exactly the right time, the algorithm will be asked to search for an empty string, something that UtString.search() was perfectly capable of doing in a correct way. I've seen how the program suddenly prints (or worse, emails) a contract requiring a customer to pay by February 30th, because the programmer thought he knows better (or just was not aware that he needs to call UtDate.addMonth()).

[jrandom]

On the other hand I've seen programs crashing in the production environment after a programmer has decided that an infrastructure class is not fancy enough...

Yeah, I hate that too. Can't stand cunts who think they know it all and try to make everything as complicated as possible.

(No, I'm not one of them. At least, I try not to be.)

[imdying]

Yes, in balance the force must be.

[Ixion]

Nah, that can cause an overflow.

This one should not:


a = a ^ b;
b = a ^ b;
a = a ^ b;
Ahh the beauty of XOR...


No-one said the variables were numeric. Or even convertable to numeric. Nor was the language specified. Nor the compiler. With modern multithreading OSs and optimising compilers you cannot be sure that those three statements will be executed sequentially.

I wouldn't want to work for a company that placed such stock on conjuring tricks. Once upon a time memory and storage cost enormous sums.I worked with a system that had only 128 bytes of memory (yes, bytes) Minimising variables and such was important. 4 bytes saved was dollars save. Now, that's not true .Hardware is cheap. If an extra variable is needed declare it. The cost of the extra RAM will be saved 100 times over in the time saving the first time someone has to maintain the program.

What the expiring gentleman said. The purpose of any software development is to add to the profitability of the business (or equivalent for government departments etc). Reinventing wheels is not profit enhancing. And the most beautiful tightly coded application is useless if it doesn't arrive until three months after it was needed.

[enigma51]

Yeah, I hate that too. Can't stand cunts who think they know it all and try to make everything as complicated as possible.

(No, I'm not one of them. At least, I try not to be.)

Yet your interview question says otherwise :wacko:

[Street Gerbil]

Yet your interview question says otherwise :wacko:
Well, I think that is a bit unfair. Even if you haven't touched algorithms for 10 years, you can sketch the nodes and the pointers and figure out how it should work. The program printing permutations of a string is less obvious because there are many ways of doing it and you need to figure out the one easiest to implement.

[jrandom]

Yet your interview question says otherwise :wacko:

It's a simple question designed to figure out whether someone wanting to work for a company has a minimal level of brainpower and is familiar with certain basic computer programming concepts.

Don't read too much into it.

Fact is, all other arguments about how one should use libraries aside, if an applicant can't solve the problem as stated, they're a dumbfuck who needs to be in a different line of work.

The point is not that one shouldn't ever reinvent the wheel - the point is that one should be capable of reinventing the wheel, and then choose not to do so when it's not necessary.

No matter how fast the processor or how enormous the memory or comprehensive the class library of basic data-manipulation functions, a dumbfuck programmer can still quite happily implement, f'rinstance, a data-processing routine which uses up all that memory when it should use a tenth of it, and takes days to run when it should take minutes.

It happens all the time out there, and I've always tried to do my employers a favour by weeding those people out in interviews.

Would you mind letting your hackles back down now?

[jrandom]

4 bytes saved was dollars save. Now, that's not true .Hardware is cheap. If an extra variable is needed declare it. The cost of the extra RAM will be saved 100 times over in the time saving the first time someone has to maintain the program.

:yes:

I believe I made an identical comment earlier in this discussion.

What I like to point out to people is the difference between optimising linearly (saving a byte here or there, or taking a chunk out of the execution time of a loop) which is generally not worth bothering with, and optimising by reducing the computational complexity of your algorithm (looking at a problem in a whole new way which means you can finish processing in ten minutes instead of a week).

It's the latter that always has been and always will be important.

And that's why I like to see job applicants solving the list-reversal problem with a single pass through the list, instead of looping across it once for every node, etc. It's the latter type of thinking that leaves computers churning for weeks when they could be finished on a lunchbreak.

Fred Brooks, the author of The Mythical Man-Month (which is a great read) wrote an excellent essay a while back called 'No Silver Bullet - Essence and Accidents of Software Engineering' about these concepts and how they apply in the efficiency of the industry.

It's out there on the innuhneh, go read it y'all.

[scracha]

Reminds me of an interview I had in Edinburgh once.

Interviewer: "you have to write a program to read data from a tape drive. How would you verify the data has been written correctly?"
Moi: "I'd use a 32 bit CRC to validate the data"
Interviewer: "but what if the CRC was wrong"
Moi: "eh?"
Interviewer: "but what if the CRC doesn't detect the error"
Moi: "but the odds of that are less than 1 in 4 billion"
Interviewer: "ok but what if this happened"
Moi: "umm....I'd use a 64 bit CRC"
Interviewer: "can you think of another way"
Moi: "Oh for fucks sake"

Tosser started waffling about linked lists and reading in the data backwards or some $hite like that.

I didn't get that job.

[lager zombie]

10 Fuck Off
20 Goto 10

[avgas]

"Show me in 30 seconds how you would write a program to maintain the temperature in a room"

- heres a tip, its not a technical question, all he wants is a structure diagram showing that you consider when fans/heaters should be changed while watch a dynamic element (temperture).
- He doesn't care what variables you use, only what the structure of the code should looks like.
- He doesn't care if you f-up a loop, use a while instead of the logic....etc he just wants to see if you can consider what is involved and plan before you leap.

FYI recruitment agents are assholes, i specifically said that i was after an electronics/software job - and ended up getting into the power industry.
They get paid commission by jamming the circle into a square.

[lager zombie]

Most recruitment agencies scan CV's for keywords.

Get the tech / business / logic balance wrong and they'll wipe their arse on the cv before giving it to the hedonistic receptionist to lick off then throw in the bin.

[jrandom]

Interviewer: "can you think of another way"

"Reed-Solomon codes, motherfucker, but who could be arsed. And I'm outta here, cos you're a twat."

Edit: Agreed re. 99% of recruitment agents being scum-sucking oxygen thieves.

[enigma51]

It's a simple question designed to figure out whether someone wanting to work for a company has a minimal level of brainpower and is familiar with certain basic computer programming concepts.

Don't read too much into it.

Fact is, all other arguments about how one should use libraries aside, if an applicant can't solve the problem as stated, they're a dumbfuck who needs to be in a different line of work.

The point is not that one shouldn't ever reinvent the wheel - the point is that one should be capable of reinventing the wheel, and then choose not to do so when it's not necessary.

No matter how fast the processor or how enormous the memory or comprehensive the class library of basic data-manipulation functions, a dumbfuck programmer can still quite happily implement, f'rinstance, a data-processing routine which uses up all that memory when it should use a tenth of it, and takes days to run when it should take minutes.

It happens all the time out there, and I've always tried to do my employers a favour by weeding those people out in interviews.

Would you mind letting your hackles back down now?

Your question is hardly going to establish compentancy. What is going to do is the person on the other side is going to think what a twat.

If someone asks me shit like that in an interview i will be happy to not get the job cause clearly i am going to work with someone who thinks his a god ..... I already have that title.


if your interviewing a gradute knock your self out you will get a nice uni answer. If you interviewing someone like me .......... i will not apply for a job where the employer think your a graduate!

[jrandom]

What is going to do is the person on the other side is going to think what a twat.

Only if they can't actually answer the question, IME.


If someone asks me shit like that in an interview i will be happy to not get the job cause clearly i am going to work with someone who thinks his a god ...

Whatever works for you bro.

:sunny:

[enigma51]

Whatever works for you bro.

:sunny:

You cant tell me you believe that your question is going to establish if someone can do the job or not?

[jrandom]

You cant tell me you believe that your question is going to establish if someone can do the job or not?

I can tell you that I'm not going to have this argument with you on the forum.

:hug:

[enigma51]

I can tell you that I'm not going to have this argument with you on the forum.

:hug:

who's having a argument?

[jrandom]

who's having a argument?

If you say my question won't establish whether someone can do the job, and I say you're wrong about that, then we're having an argument.

[Street Gerbil]

Ok, here is another one:
I get more or less what the code does (although I am still amazed that this code would even compile) but what really gets to me is the second part of the question: "Why would someone want to do something like that?"
(Taken from Stroustrup's exercises)



void send (int * to , int * from , int count )
// Duff’s device. Helpful comment deliberately deleted.
{
int n = (count +7 )/8 ;
switch (count %8 )
{
case 0 :
do { *to++ = *from++;
case 7 : *to++ = *from++;
case 6 : *to++ = *from++;
case 5 : *to++ = *from++;
case 4 : *to++ = *from++;
case 3 : *to++ = *from++;
case 2 : *to++ = *from++;
case 1 : *to++ = *from++;
}while (--n>0) ;
}
}

[imdying]

I can't remember if you were looking for work in Christchurch or not, but if so, pm and I will refer you to a recruiter that has worked for myself and others in the past.

[jrandom]

"Why would someone want to do something like that?"

Loop unrolling to optimise memory-to-memory copies in embedded systems.

Edit: I'd suspect that most modern compilers would be capable of achieving the same performance out of more conventionally-written code.

[enigma51]

Loop unrolling to optimise memory-to-memory copies in embedded systems.

Edit: I'd suspect that most modern compilers would be capable of achieving the same performance out of more conventionally-written code.

Dont you think that simply asking the question how you optimize memory to memory copies do the trick?

1 It gives the person an idea of what he/she can expect from the role. IE clearly you are having memory issues
2. You dont look like a prick trying to being smart

[hdus001]

Heres one that I was asked:

You have a processor that only has one register and only supports one instruction - "DCX LABEL" - which means decrement the value in the register and jump to LABEL if new value in register is not 0. Write a loop that'll decrements any number in the register (positive or negative) to 0.

[jrandom]

Dont you think that simply asking the question how you optimize memory to memory copies do the trick?

Of course. I personally would never dump Duff's Device in front of someone and say "what's that good for then".

Edit:


You dont look like a prick trying to being smart

You have some emotional issues about 'smart' people, don't you? Give it a rest, man, just relax about the whole subject.

[Street Gerbil]

Heres one that I was asked:

You have a processor that only has one register and only supports one instruction - "DCX LABEL" - which means decrement the value in the register and jump to LABEL if new value in register is not 0. Write a loop that'll decrements any number in the register (positive or negative) to 0.

Ok, here is the opinion that would have gotten me thrown out of your interview:
you write the following line:


label1: dcx label1

If register value is positive, it will iterate until it becomes zero.
If it is zero it will exit right away.
If it is negative, it will happily decrement until the underflow, at which stage the value in the register will become positive and will keep decrementing itself to zero.
What's the right answer?

[enigma51]

Of course. I personally would never dump Duff's Device in front of someone and say "what's that good for then".

Edit:



You have some emotional issues about 'smart' people, don't you? Give it a rest, man, just relax about the whole subject.

If you refering to yourself as being smart you are sadly mistaken.
I find you arrogant and a know it all.

[jrandom]

I find you arrogant and a know it all.

Gah. I just can't win, can I?

Oh, well. The line to join the club starts over there ---------->

[nodrog]

can somebody explain how to set the clock on my microwave?

[Ixion]

That's hardware. This is a software discussion

[nodrog]

so they wont know? geez, i thought IT guys were smart?

[hdus001]

Ok, here is the opinion that would have gotten me thrown out of your interview:
you write the following line:


label1: dcx label1

If register value is positive, it will iterate until it becomes zero.
If it is zero it will exit right away.
If it is negative, it will happily decrement until the underflow, at which stage the value in the register will become positive and will keep decrementing itself to zero.
What's the right answer?


Yup that is the right answer. You are hired !!

minor nitpick: if it is 0, it wont exit rightaway..will go negative, then count down eventually to 0 and then exit.

[scracha]

"Reed-Solomon codes, motherfucker, but who could be arsed. And I'm outta here, cos you're a twat."
Edit: Agreed re. 99% of recruitment agents being scum-sucking oxygen thieves.

Bwahahah. Unfortunately this prick was the lead developer. I thought of a couple of more methods but I just blurted out "oh for fucks sake" cos I knew working with this guy was gonna be impossible. He obviously wanted to impress me with his own more efficient method and after 45 minutes of him picking holes in the code I had to handwrite I'd had enough (especially as for once it actually worked!).

Reed-Solomon codes...well I've learned something new today. Am pretty sure I'll never use it but what the hell.






Some days I really miss coding.

[avgas]

can somebody explain how to set the clock on my microwave?
Press the time button, hold down for 4 seconds, when the time displays starts flashing enter the 24hour side (eg 16:00) press time again then enter the minute side (16:34). Press start or time to allow the clock to start.

Some Microwave clocks will allow you to enter the whole time (hours:minutes) all at the same time eg 1,6,3,4 = 16:34

[enigma51]

Press the time button, hold down for 4 seconds, when the time displays starts flashing enter the 24hour side (eg 16:00) press time again then enter the minute side (16:34). Press start or time to allow the clock to start.

Some Microwave clocks will allow you to enter the whole time (hours:minutes) all at the same time eg 1,6,3,4 = 16:34

So how do you make the 6 bit of the time of your clock the 1 bit of your clock?

[Street Gerbil]

Guys, has anyone got a Stroustrup C++ 3rd edition that I can borrow?

[jrandom]

Guys, has anyone got a Stroustrup C++ 3rd edition that I can borrow?

Yup, if you don't mind coming to Newmarket to pick it up.

[scracha]

Guys, has anyone got a Stroustrup C++ 3rd edition that I can borrow?

Hell, I even took my C bibles from the UK. Borrow it....no fuckin chance. It's a classic :clap:

[Forest]

Most recruitment agencies scan CV's for keywords.

Get the tech / business / logic balance wrong and they'll wipe their arse on the cv before giving it to the hedonistic receptionist to lick off then throw in the bin.

I once got a call from a recruiter in Melbourne. They had a "hot opportunity" which was a "perfect fit" for me.

So I rocked up and was told that the job was for an experienced LISP developer to head a team that was writing code for embedded telephony hardware.

What was it that qualified me for this exciting and challenging role? My CV contained the word telephony.