Programming Puzzle

[Trimbo]

Got this many years ago in an interview:

http://digg.com/programming/Array_Reordering_Programming_Puzzle

Not too hard, but hard to do in < 30 minutes under pressure.

 

[Cowboy Bob]

Completely useless waste of time to set that in an interview. If I needed to do something like that and didn't know immediately off the top of my head how to do it, I'd just Google it. Simple algorithmics are no indicator of a decent developer.

To be honest, I'd have probably just got up and walked out. I'm a professional contractor and the only kind of tests that may be acceptable are ones directly related to the project being discussed - and even then I see them as a kind of insult.

 

[Trimbo]

Completely useless waste of time to set that in an interview. If I needed to do something like that and didn't know immediately off the top of my head how to do it, I'd just Google it. Simple algorithmics are no indicator of a decent developer.

To be honest, I'd have probably just got up and walked out. I'm a professional contractor and the only kind of tests that may be acceptable are ones directly related to the project being discussed - and even then I see them as a kind of insult.

I agree - totally useless. It was many years ago (I was still a student!) and they offered me £50 a week!

 

[MarillionFan]

tulipe. Next!

 

[_V_]

As a professional business man, I'd offer the following solution.

1. Stick the algorithm requirement on RentACoder.
2. Pay the $10 required for the solution
3. Bill the client £500

HTH

 

[scotspine]

don't let a certain russian see that temp var for goodness sake!

 

[VectraMan]

Maybe I'm being thick, but isn't that just a bubble sort?

 

[scotspine]

depends how the swap function is called

 

[AtW]

don't let a certain russian see that temp var for goodness sake!

too late... use assembly's command: xchg

Just sort the array (in place using QuickSort, supported by any good library) but use reversed key values, thus: it will sort as:

1a, 1b, 2a, 2b etc - of course reverse order only to be used for key comparison purposes, it won't be changed in the array: there job done in less than few minutes.

Of course in reality the solution should be more effective - you don't really need to swap them and trash processor cache - you need to think what you will do with the data later, say if its saving in such a state on disk then you can just do it in simple loop with counter plus fixed offset thus merging two sorted streams on the fly.

And if you need array with changed places for some later processing then you can do similar merging on the fly.

All in all stupid task that is only excusable by separating pros (who will solve it in 1 minute using existing tools) from amateurs who will actually be stupid enough to follow artificial rules instead of just bending the spoon.

If they don't like it then I'd walk out.

 

[Trimbo]

I obviously didn't make it clear, you are rearranging the array, not sorting it. To put it another way, you are not allowed to look at the contents of the array items to help you. So any kind of sort function is right out. Anyway who cares its old news now..! (somebody pasted a good solution on the digg page).

too late... use assembly's command: xchg

Just sort the array (in place using QuickSort, supported by any good library) but use reversed key values, thus: it will sort as:

1a, 1b, 2a, 2b etc - of course reverse order only to be used for key comparison purposes, it won't be changed in the array: there job done in less than few minutes.

Of course in reality the solution should be more effective - you don't really need to swap them and trash processor cache - you need to think what you will do with the data later, say if its saving in such a state on disk then you can just do it in simple loop with counter plus fixed offset thus merging two sorted streams on the fly.

And if you need array with changed places for some later processing then you can do similar merging on the fly.

All in all stupid task that is only excusable by separating pros (who will solve it in 1 minute using existing tools) from amateurs who will actually be stupid enough to follow artificial rules instead of just bending the spoon.

If they don't like it then I'd walk out.