|
Once I travled 400 miles to interview with a startup. All went well untill I was handed a pencile and a white sheet of paper and asked to write a recursive function in C# to produce a Fabbinicc sequence. Needles to say I didn't get the job. Do these people know that recursive algroythms = spigetti code?
Hey Interviewers here is an IQ test:
Penciles are for drawing as code is to?
Hmm, the only thing important about Fabbinicci numbers and programming is that 1^n + 2^n ... + x^n has infinate solutions. And I'm not writting crypto software so it doesn't really matter.
~~~~~~~~~~~~Update~~~~~~~~~~~
I have learned much from this thread. Thanks to all who gave me a hard time!
As a result of all my research and learning I created a 'Big O Analyzer'.
Hope it helps someone other than myself.
Big O Algroythm Analyzer for .NET[^]
~~~~~~~~~~~~Update~~~~~~~~~~~
'The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program.'
Reference: Wikipedia on Recursion
~~~~~~~~~~~~Update~~~~~~~~~~~
If you tried the Big O tool and were disapointed that it did not find any Big O's at all, it's been updated. At infinity point = 1000 it's about 99.9991% acurate (good as gold). You might need to use .00002% brain power to figure out what the Big O is.
~TheArch
modified on Wednesday, July 22, 2009 4:56 AM
|
|
|
|
|
Hmm, yeah! I can pass a test on code only 50% pass but but fail an english test 100% people pass.
infinate = ∞
|
|
|
|
|
Hmm, Both, Shout first ask questions later. 
The identy is related to eclidian geometry identies and 'Hilbert's Tenth Problem'.
|
|
|
|
|
Hmm your from Switzerland... Work at CERN by chance?
|
|
|
|
|
I'd say the second, but I'm not English either..
|
|
|
|
|
Second one ofc, unless you put a ',' before the 'stop shooting' in the first one, but then it would mean something else xD
WTF has that to do with the code horror btw? 
GSoC 2009 student for SMW!
---
My little forums: http://code.bn2vs.com
---
70 72 6F 67 72 61 6D 6D 69 6E 67 20 34 20 6C 69 66 65!
|
|
|
|
|
The Fibonacci sequence doesn't have that formula. It's the recurrence relationship Fn-1 + Fn-2, with seed values of F0 = 0 and F1 = 1. And it seemed to be a test of your capability to write recursive functions. You're right about one thing though - pencils and paper aren't a development environment. They might be useful for simplifying an algorithm, or brainstorming (oh, how I hate that word) ideas, but when testing how well somebody writes code, they need to be in as close to how they would develop while at the company as possible
Between the idea
And the reality
Between the motion
And the act
Falls the Shadow
|
|
|
|
|
I think pencil and paper are superb for coding and especially planing!
I use them a lot. If I have to write complexer functions I first draw or write a pseudo code on paper and see where the difficulties can appear.
Then I start coding.
My experience is that ,in the latest during testing, you will save some time.
Or if you start up with a new project and you think about the best strategy to attack the problem.
Paper and pencil (or pen) is the best to do.
Cheers
Ps.: What has this to do with Coding horrors. Was looking for a laugh, but now I am disappointed. 
You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)
|
|
|
|
|
Hmm,
Well if you want a laugh... I broke the pencile four times, lead twice and then I broke the pencil in half after erasing three holes into the paper. I am a visual type myself, I see all the code in my head orginized into simple structures of reusable logic, for complex things over ~200 lines of code, I use state diagrams and use cases. But I don't use a pencile for that. Seems like a wasted step. I can orginize my ideas using graphics tools. Me personal fav. is MS One Note.
|
|
|
|
|
I was thought that someone reply to that.
I have to say its long time ago I really used pencils, nowadays I am using a whiteboards or as well graphic tools.
However if this thing works for you its good and cool. But I think you will agree that lot of coders are thinking that they can do it as well, which then ends up with posts in the coding horrors (worst case ).
Which is good for us, but bad for the guys that have to find such bugs.
So I think to lean back and think before someone writes a function is not a wasted time. Either it be with pencil or other tools.
And I have to say, letting someone writing a small function recursive is during a job interview is not cruel.
Considering that they don't check the syntax. So would ask for a pseudo code or what ever.
Cheers
You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)
|
|
|
|
|
Hmm,
Sorry, it's an identity inthe proof of the ∞ for this sequence. It is based on Eulclidian Geometry and Hilbert's Tenth Problem. I could not find the article on it, something to the effect of:
xn+1n + xn-1n = √xnn
Seems the article was deleted. 
|
|
|
|
|
Computafreak wrote: The Fibonacci sequence doesn't have that formula.
Well it has, but it's not a point of your post I suppose. I had a task on a math exam to derive a closed form expression of a given sequence defined by a linear recursion. It's quite easy when you know something about generating functions. That task killed me, though. 
Greetings - Jacek
|
|
|
|
|
However there is nothing wrong with a little bit of algo interview I believe.
Heck you could have impressed them by doing a non recursive version!
from the top of my mind here is a decomposition of an input number in a sum of fibonnaci number (which is unique)(pseudo code,i.e. might not compile, run and/or be full of error, use at your own risks!)
public struct FibonacciNumber<br />
{<br />
public FibonacciNumber(int i, int v) { Index = i; Value = v; }<br />
public int Value;<br />
public int Index;<br />
}<br />
class Foo<br />
{<br />
static List<FibonacciNumber> Decompose(int number)<br />
{<br />
var allf = AllFibonacciTo(number);<br />
var result = new List<FibonacciNumber>();<br />
for (int i = allf.Count; i-- > 0; )<br />
{<br />
var f = allf[i];<br />
if (f.Value <= number)<br />
{<br />
result.Add(f);<br />
number -= f.Value;<br />
}<br />
if (number == 0)<br />
break;<br />
}<br />
result.Reverse();<br />
return result;<br />
}<br />
<br />
static List<FibonacciNumber> AllFibonacciTo(int number)<br />
{<br />
var result = new List<FibonacciNumber>();<br />
result.Add(new FibonacciNumber(0, 1));<br />
result.Add(new FibonacciNumber(1, 2));<br />
int last = 2;<br />
while (last < number)<br />
{<br />
var fn = new FibonacciNumber();<br />
int N = result.Count;<br />
fn.Index = N;<br />
fn.Value = result[N - 1].Value + result[N - 2].Value;<br />
last = fn.Value;<br />
result.Add(fn);<br />
}<br />
return result;<br />
}<br />
<br />
static void Main()<br />
{<br />
int N = 78;<br />
Dump(AllFibonacciTo(N));<br />
Dump(Decompose(N));<br />
}<br />
<br />
static void Dump(List<FibonacciNumber> lf)<br />
{<br />
foreach (var item in lf)<br />
Console.Write("({0}, {1}) ", item.Index, item.Value);<br />
Console.WriteLine();<br />
}<br />
}
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
modified on Monday, July 6, 2009 7:10 AM
|
|
|
|
|
Maybe more in line with what they asked....
static int RFibonacci(int index)<br />
{<br />
if (index < 1) return 1;<br />
if (index < 2) return 2;<br />
return RFibonacci(index - 1) + RFibonacci(index - 2);<br />
}<br />
static int DFibonacci(int index)<br />
{<br />
if (index < 1) return 1;<br />
if (index < 2) return 2;<br />
int u = 1;<br />
int v = 2;<br />
int N = 1;<br />
while (N < index)<br />
{<br />
int tmp = u + v;<br />
u = v;<br />
v = tmp;<br />
N++;<br />
}<br />
return v;<br />
}
But RFibonnaci, the recursive version, has to perform approximately 2^(index-1) method call.
End result, the recursive method is so ungodly slow compare to DFibonnacci that it is tearful...
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
Hmm,
Nice! I told them it was a bad idea and offered to do it no recursive. What made matters worse was the algroythm was supose to break out after finding sequence 'x'.
He told me that he thought I was the man for the job untill I couldn't complete this simple recursive routeen.
|
|
|
|
|
well, that's the thing!
if you can't write a simple recursive it's suspicious!
I hope you can, can you?
I hope your mind block was just psychological (this will perform so badly, I should not!)
I hope it's not something again recursion in general, is it?!?
The fact that recursion *might be* problematic and *might be* improved with a non recursive fashion is a completely different issue.
As a rule recursion IS NOT bad. In fact it is use very much often!
he asked you that to checked if you know and understand recursion, to check if you are really a programmer and not a bluffer.
Now if you can't write it because *insert reason here* you are a bluffer.
Next time do it.
It doesn't matter if it's a bad idea, this is not the purpose of the exercise!
However, adding some explanation on why it is bad in this case and how to improve it! Here you just gain free bonus point!
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
<chuckle>
Hmm, I have written many, many recursive functions. None that break out of recursion however. Well maybe in VB a long time ago, using goto labels. Loop: and Exit:. It was still considered bad form then. My Java mentor from Sun was crazy about recursive logic. For this problem a simple for loop would have been a much eligant solution. I good at identifying eligance and implimenting it, but it is just not logical to do otherwise. Microsoft actually considered removing recursive funcion from C# when they ported it from MS Java. I think they are about as bad as mutiple class inheritance. Powerful, easy to abuse, rairly needed.
|
|
|
|
|
No worry, just checking!
I was wondering why you could not write the recursive function he asked!
I guess now it was a psychological blockage!
Next time, don't stress too much about the purity of the algorithm. Perfectionism is over hyped!
I am not saying we should not be perfectionist, this is an important quality for an engineer.
However perfectionism often become stubbornness, which is obviously not good hey!?
To stretch it a lot, that remind me of a yahoo science / psychology article about terrorists.
They did some psychology profiling on terrorist and, to everyone surprise, terrorist are more likely to be engineer. They explored many conjecture as to why but the best candidate seems to be that the engineer doesn't think with nuance. Things work or don't. Ideas are good or not. Engineer are often less good at compromise. I found the idea interesting. Noticed myself I do tend to be stubborn sometimes on point of detail!
Hey, don't worry, I am not implying anything about you, just let my mind wander quite a lot and thought aloud!
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
Hmm,
Being a x-military anti-terrorism super freak, I understand the subject very well. My daily exersize druing my life in the millitary was to figure out how to take control of the work in 24 hours with a team of Seven. After 9/11 I was terrified at how close my anti-terrisim counter measures were to what is possible. My job, run three miles to jump on an airplane and blow up the world.
|
|
|
|
|
Fun Bio by the way!
Those evil MVP are sneaky bastard!
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
Evil MVP a.k.a DrDotNetSky
|
|
|
|
|
The point about interview questions is not to pose real world problems, but to see if candidates have the knowledge required for the job. Our interview questions can be similarly "odd", and will vary depending on the specialisation being interviewed for. What we're looking for is the ability to solve problems, and apply knowledge.
What you should have done is written the algorithm, then gone on to explain why the recursive version is not as good as the iterative one - that would probably have impressed the interviewers more than someone who just wrote the code with no further explanation.
TheArchitectualizer wrote: Microsoft actually considered removing recursive funcion from C#
I think that's a myth. There are plenty of cases where recursion is in fact the easiest and best way to implement things.
There are three kinds of people in the world - those who can count and those who can't...
|
|
|
|
|
Super Lloyd wrote: As a rule recursion IS NOT bad. In fact it is use very much often!
I am still thinking about recursion. I really don't think it's a good thing.
MSDN: Is there any situation where recursion is useful?[^]
My thought is if you can do it with out recursion, then do.
~My 2¢
|
|
|
|
|
Are you one of those religious warrior?
Maybe I should tell you that I wrote 1 or maybe 2 goto this last year!
I am not interested in religious war!
I am interested, eventually, in well explained idea.
Please do tell me why not recurse!
So I will know when I should not...
In the case of Fiboonacci it's easy, it requires "2^N" operation recursively and "N" in a non recursive fashion. But you statement was much more general, so please provide general argument against recursion.
So that I know, according to you, when to avoid it.
Well, I decided to participate in religious war after all....
And to challenge you, without waiting for your arguments, with some counter examples.
How do you write structure recognizer in a non recursive fashion?
i.e. how do you write thing such as a "Language compiler" or an "Object graph deserializer"?
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
Super Lloyd wrote: Are you one of those religious warrior?
No! I am still investigating it. I had a mentor from Sun whom was crazy about it. I used it alot on that job. But after leaving I think I might have only used it twice.
Super Lloyd wrote: How do you write structure recognizer in a non recursive fashion?
i.e. how do you write thing such as a "Language compiler" or an "Object graph deserializer"?
Heck, I couldn't even do the easy example of getting all the widgets in the visual tree for WPF. I will do some research for you and get back to you. But I leave you with this thought.
'How did they do this before the invented recursive functions?'
~TheArch
“Make love, not war”
American Proverb quotes[^]
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
