|
Hmm, it is a small world. While researching ML on another thread I found three F# implimentations:
<br />
(* Fibonacci Number formula *)<br />
let rec fib n =<br />
match n with<br />
| 0 | 1 -> n<br />
| _ -> fib (n - 1) + fib (n - 2)<br />
<br />
(* An alternative approach - a lazy recursive sequence of Fibonacci numbers *)<br />
let rec fibs = seq {<br />
yield! [1; 1];<br />
for (x, y) in Seq.zip fibs (Seq.skip 1 fibs) -> x + y }<br />
<br />
(* Print even fibs *)<br />
[1 .. 10]<br />
|> List.map fib<br />
|> List.filter (fun n -> (n mod 2) = 0)<br />
|> printlist<br />
<br />
(* Same thing, using Comprehension syntax *)<br />
[ for i in 1..10 do<br />
let r = fib i<br />
if r % 2 = 0 then yield r ] br />
|> printlist<br />
It's also recursive...
|
|
|
|
|
If you want a terrifying interview question try this beast on for size
From the command line take in two numeric strings, determine how you would have to create an equation out of the numbers given in the first string to result in the second or display that it is impossible.
Sample input: 12 3
1+2 = 3
34 12
3*4 = 12
Only, there was one of these samples roughly 20 characters long. You either had the four typical operators or perhaps just addition and multiplication to cover.
Do this in C, with no libraries, in under 6 hours, time also split doing a sodoku solver(which is a pain for those of us who'd never done one of the puzzles before, did it in two hours including learning the game).
That said, if this is some how as easy as a Fibonacci sequence I would love to be proven an idiot, this thing has been bugging me for a while now. And I may have finally figured the thing out writing this, I'll have to see if my idea works once I'm out of work.
|
|
|
|
|
I have no idea, in a simular post I offered the use of lambda functions and red black trees to solve the problem.
'I am a mathimatician suffering from Pseudo-Intellectual Academia.'
modified on Monday, July 6, 2009 1:41 PM
|
|
|
|
|
For me it would depend on the circumstances.
This is an easy bit of code just a few lines long.
Sitting here under no pressure I had it working in a couple of minutes. I would be happy to tackle it using pencil and paper.
In a interview, if they said go sit in the corner for 10 minutes and see what you can come up with, I'd likely be OK. But if the interviewer sat close and watched every move of the pencil then I might go blank if I was not previously at ease. Then it becomes as much about self-confidence and ability to think under pressure as it does about coding.
|
|
|
|
|
i agree with you. Some time interviewer make matter worst. I also cant code when some one watching me. Its really confuse me.
|
|
|
|
|
I wonder,
if recursion = spogitta then how do you enumerate directories?
It feels good to learn and achieve
|
|
|
|
|
I would use LINQ to Objects:
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Linq
{
class Program
{
static void Main(string[] args)
{
ListFiles(new DirectoryInfo("c:\\"));
}
static void ListFiles(DirectoryInfo dir)
{
var Directories = from dirs in dir.GetDirectories()
orderby dirs.FullName
select dirs;
foreach(DirectoryInfo directory in Directories)
{
Console.WriteLine("Directory: <" + directory.FullName + "> contains the following files:");
var Files = from file in directory.GetFiles()
orderby file.FullName
select file;
foreach (FileInfo file in Files)
{
Console.WriteLine("---" + file.FullName);
}
}
}
}
}
If the system had multi core I would use PLINQ to Objects...
modified on Saturday, July 18, 2009 11:12 AM
|
|
|
|
|
Umm, this goes only two levels down. If you have
C:\
A
A1
A11
File1
File2
your code will stop with A1 - it will not print A1.
|
|
|
|
|
Doh!
You are correct!
If you want all the files in all the directories you have to add:
"*", SearchOption.AllDirectories
|
|
|
|
|
If you just want the directories:
static void ListDirectories(DirectoryInfo dir)
{
var BaseDir = from dirs in dir.GetDirectories()
orderby dirs.FullName
select dirs;
foreach (DirectoryInfo thisDir in BaseDir)
{
var TheDirectory = from dirs in thisDir.GetDirectories("*", SearchOption.AllDirectories)
orderby dirs.FullName
select dirs;
Console.WriteLine("Directory: <" + thisDir.FullName + "> contains the following directories:");
foreach (DirectoryInfo directory in TheDirectory)
{
Console.WriteLine(" --[" + directory.FullName + "]");
}
}
}
modified on Saturday, July 18, 2009 11:14 AM
|
|
|
|
|
Okay make it better:
static void ListDirectories(DirectoryInfo dir)
{
var BaseDir = from dirs in dir.GetDirectories()
orderby dirs.FullName
select dirs;
Thread.BeginCriticalRegion();
foreach (DirectoryInfo thisDir in BaseDir)
{
try
{
var TheDirectory = from dirs in thisDir.GetDirectories("*", SearchOption.AllDirectories)
orderby dirs.FullName
select dirs;
Console.WriteLine("Directory: <" + thisDir.FullName + "> contains the following directories:");
foreach (DirectoryInfo directory in TheDirectory)
{
Console.WriteLine(" --[" + directory.FullName + "]");
}
}
catch (AccessViolationException ave)
{
Console.WriteLine("Access Violation for: [" + thisDir.FullName + "] ave:" + ave.Message);
}
catch (UnauthorizedAccessException uave)
{
Console.WriteLine("Unathorized Access Violation for: [" + thisDir.FullName + "] uave:" + uave.Message);
}
}
Thread.EndCriticalRegion();
}
|
|
|
|
|
Very nice,
But i have visual studio 2003,
I always liked the elegance of recursion...
I never understood why i learned this technique on fobenuca and not on directories,...
That was the point i wanted to make
.
It feels good to learn and achieve
|
|
|
|
|
$10 says thisDir.GetDirectories is recursive
|
|
|
|
|
Hmm I did have that thought. But the foundation of systems objects is actually exposed as database objects. So I wasn't sure. If the system uses a db, it totaly aviaods recursion.
|
|
|
|
|
Chris Losinger wrote: $10 says thisDir.GetDirectories is recursive
Okay I think you owe me $10! We can arrange for a friendly transfer thru paypal. LOL!
"If there are no subdirectories, this method returns an empty array. This method is not recursive."
MSDN: GetDirectories Method[^]
'If these guys don't use recursion here, I kinda wonder if they think recursion is a bad idea also.'
...And here at The Code Project...
'Hooray! No more memory exhaustive manual recursion for my disk traversals!'
Use LINQ to Create Music Playlists – Revisited[^]
~TheArch
modified on Wednesday, July 15, 2009 8:27 AM
|
|
|
|
|
so you only get immediate subdirs of the target dir ?
i thought the whole reason people were talking about directories here was that recursion is the natural way to get all subdirs, not just the immediate children. if you're not getting the full tree, what's the point of talking about it here ?
or am i misunderstanding something... ?
|
|
|
|
|
Chris Losinger wrote: so you only get immediate subdirs of the target dir ?
it is the full tree, if target dir = @"c:\"
The call to BaseDir is really unnecessary, if:
var TheDirectory = from dirs in thisDir.GetDirectories("*",SearchOption.AllDirectories)
orderby dirs.FullName
select dirs;
\\Where thisDir = new DirectoryInfo(@"C:\");
\\This gets the whole tree. No recursion.
I would decompile the System.IO class but microsoft doesn't really like it when you do that. I will take thier word that the method is not recursive.
If perhaps using the search option, does make the methods recursive (don't really understand MSDN on this) they do not have the same remark for this method using this option. But it would still be possible if you used the base method which states not recursive, then used a lambda to get all the childern. I would guess this is what the search option does.
My point is yes, recursion is a natural for humans and nature. However it's not natural for computers. We simply make computers do the things we think is natural because it describs our domain.
What is natural to humans is not necessarly natural to computers. Thinking like the computer using it's imposed domain, is how 99% of performance enhancments are made.
The interviwer imposed a domain on the problem which introduces the human factor. Adding the human factor to the problem causes bad things to happen. My point to the interviewer was this is not how to do things, esp. if performance is in question. Which performance was a big factor as I was to build a server application. I thought that it was a trick question. I thought the interviewer was testing my knowlege of how to correctly design server software. I didn't want the interviewer to think I was going to do a poor design. The interviewer did give me one thing to aid the problem. I was aloud to use a prototype language of my own design to solve the problem. So I designed a language which did allow for recursive logic, but I place a constraint on the language factored out the real recursion, so the expression of recursion was removed from the compiled code.
It's weird the prototype I designed, looks alot like F#. The prototype predated F#.
The interviewer's last comment to me was that there could be no justification to hire a lead engineer who didn't not understand recursion.
|
|
|
|
|
hmm. right you are.
cool.
|
|
|
|
|
Thanks Chris!
This thread has really helped my human factors. I didn't really know I had an unresolved resentment againts this interviewer.
It also helped me to lear something new: Big O Notation. This was another factor which came up in the interview. I did not go to an ivy leage college to study Computer Science, in fact I never went to college to learn computer science. I did study engineering and electronics in college at a technical college. The interviewer told me this would not be a factor in his assessment of my skill. However he did give me a problem first year Computer Science engineers study.
I sometimes wonder if the interviewer was really trying to factor me out of the equation.
|
|
|
|
|
Big O is cool. i learned it in college, but it was a decade before i really found a practical use for it (when i got into graphics programming).
|
|
|
|
|
Well, I think this is really a great question for an interview, becouse you can get a lot of conclusions depending on the answer.
If the answer was:
int BadFib(int n)
{
if (n == 1 || n == 2)
return 1;
else
return BadFib(n - 1) + BadFib(n - 2);
}
This answer means that the guy knows what recursion is, but he has no idea about algorithm complexity, and he does not mind performance at all. So, my next question would be: Can you do it better?
But now, if somebody came up with this solution:
public int GoodFib(int n)
{
return Fib(n, 1, 1);
}
private int Fib(int n, int n1, int n2)
{
if (n == 1 || n == 2)
return 1;
else if (n == 3)
return n1 + n2;
else
return Fib(n - 1, n1 + n2, n1);
}
This means that the guy knows what recursion is, he knows what algorithm complexity is, and he is worried about the performance of his code. So, my next question would be: When would yo be able to start with the job?
I guess the interviewer just wanted to know how skilled you were about programming.
modified on Tuesday, July 7, 2009 11:30 AM
|
|
|
|
|
In one of my interviews, I was asked to code a function to convert an string (char *, it was as C interview) into an int.
Considering that there are already a lot of functions that do it already, it looks stupid. Considering it was an way to know if I know how to solve problems, I did it.
Later, the interviewer was surprised, because I was the only one of the candidates to answer such question.
|
|
|
|
|
Paulo Zemek wrote: Later, the interviewer was surprised, because I was the only one of the candidates to answer such question.
That's sad. I wrote the pascal equivalent after roughly half a year of programming in high school, and then wrote the equivalent to convert a string into a float.
I was writing custom numeric input handlers that rejected garbage keystrokes; offhand I don't recall why I didn't want to use the standard library validation/conversion functions.
The European Way of War: Blow your own continent up.
The American Way of War: Go over and help them.
|
|
|
|
|
That is exactly the point I wanted to reach.
|
|
|
|
|
Paulo Zemek wrote: In one of my interviews, I was asked to code a function to convert an string (char *, it was as C interview) into an int.
Considering that there are already a lot of functions that do it already, it looks stupid. Considering it was an way to know if I know how to solve problems, I did it.
Cool!
But how did you do it?
|
|
|
|