 |
|
|
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.
|
| Sign In·View Thread·PermaLink | 1.00/5 (4 votes) |
|
|
|
|
|
|
Well I suppose you were talking about Fibonacci...
It is just a supposition since Google doesn't know about "Fabbinicci"
...
|
| Sign In·View Thread·PermaLink | 5.00/5 (1 vote) |
|
|
|
|
|
|
Hmm, yeah! I can pass a test on code only 50% pass but but fail an english test 100% people pass.
infinate = ∞
|
| Sign In·View Thread·PermaLink | 1.00/5 (1 vote) |
|
|
|
|
|
|
I won't be really fussy for the english, since I am french, I do not master this langage
Just a little test, which sentence is correct:
"I hide behind the bar waiting for the cowboys stop shooting"
"I hide behind the bar waiting for the cowboys to stop shooting"
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Hmm, Both, Shout first ask questions later. 
The identy is related to eclidian geometry identies and 'Hilbert's Tenth Problem'.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
|
|
|
|
|
|
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!
|
| Sign In·View Thread·PermaLink | 3.00/5 (1 vote) |
|
|
|
|
|
|
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
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
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)
|
| Sign In·View Thread·PermaLink | 5.00/5 (1 vote) |
|
|
|
|
|
|
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.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
|
|
|
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. 
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Recursion is indeed dangerous, particularly in this case!
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
{
public FibonacciNumber(int i, int v) { Index = i; Value = v; }
public int Value;
public int Index;
}
class Foo
{
static List<FibonacciNumber> Decompose(int number)
{
var allf = AllFibonacciTo(number);
var result = new List<FibonacciNumber>();
for (int i = allf.Count; i-- > 0; )
{
var f = allf[i];
if (f.Value <= number)
{
result.Add(f);
number -= f.Value;
}
if (number == 0)
break;
}
result.Reverse();
return result;
}
static List<FibonacciNumber> AllFibonacciTo(int number)
{
var result = new List<FibonacciNumber>();
result.Add(new FibonacciNumber(0, 1));
result.Add(new FibonacciNumber(1, 2));
int last = 2;
while (last < number)
{
var fn = new FibonacciNumber();
int N = result.Count;
fn.Index = N;
fn.Value = result[N - 1].Value + result[N - 2].Value;
last = fn.Value;
result.Add(fn);
}
return result;
}
static void Main()
{
int N = 78;
Dump(AllFibonacciTo(N));
Dump(Decompose(N));
}
static void Dump(List<FibonacciNumber> lf)
{
foreach (var item in lf)
Console.Write("({0}, {1}) ", item.Index, item.Value);
Console.WriteLine();
}
}
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
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Maybe more in line with what they asked....
static int RFibonacci(int index)
{
if (index < 1) return 1;
if (index < 2) return 2;
return RFibonacci(index - 1) + RFibonacci(index - 2);
}
static int DFibonacci(int index)
{
if (index < 1) return 1;
if (index < 2) return 2;
int u = 1;
int v = 2;
int N = 1;
while (N < index)
{
int tmp = u + v;
u = v;
v = tmp;
N++;
}
return v;
}
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.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
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.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
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.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
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.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
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.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
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.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
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.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
|
|
|
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...
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
But RFibonnaci, the recursive version, has to perform approximately 2^(index-1) method call.
If you do it right, the number of method calls will precisely equal the result. In any case, a naive approach is going to take O(phi^n) calls to complete (since the ratio of adjacent Fibonacci numbers approaches phi, i.e. (1+sqrt(5))/2 aka the Golden Mean).
An alternate recursive approach is to write a method which returns two adjacent Fibonacci numbers (either as a structure, or using pass-by-reference). Starting with having an input with n<=1 yielding (0,1), and otherwise having the code for n read the values for (n-1) into (x,y) and return (y,x+y), the recursion runs nicely in linear time.
|
| Sign In·View Thread·PermaLink | 5.00/5 (1 vote) |
|
|
|
|
|
|
Hmm, it is a small world. While researching ML on another thread I found three F# implimentations:
(* Fibonacci Number formula *)
let rec fib n =
match n with
| 0 | 1 -> n
| _ -> fib (n - 1) + fib (n - 2)
(* An alternative approach - a lazy recursive sequence of Fibonacci numbers *)
let rec fibs = seq {
yield! [1; 1];
for (x, y) in Seq.zip fibs (Seq.skip 1 fibs) -> x + y }
(* Print even fibs *)
[1 .. 10]
|> List.map fib
|> List.filter (fun n -> (n mod 2) = 0)
|> printlist
(* Same thing, using Comprehension syntax *)
[ for i in 1..10 do
let r = fib i
if r % 2 = 0 then yield r ]
|> printlist
It's also recursive...
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
RSS feed
General 
News 
Question 
Answer 
Joke 
Rant 
Admin 
