Sith Interviewing Tactics [modified]

[Lost User]

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();
    }

[Lost User]

Okay after much testing I have a non recursive version:

using System;

namespace Test
{
class fib
{
double n = 0;
public double next
{
get
{
return n;
}

        set
        {
            n = Math.Round(((Math.Pow(fib.golden(),value)) - Math.Pow((1-fib.golden()),value)) / Math.Sqrt(5));
        }
    }

    private static double golden()
    {
        return (1 + Math.Sqrt(5)) / 2;

    }
}

}

    public static double MyFib(int n)
    {
        fib f = new fib();
        f.next = n;
        return f.next;
    }

Like I said, 'recursive algroythms are a bad idea.' GoodFib(6000) -1142292160 MyFib(6000) Infinity GoodFib(1000) 1556111435 MyFib(1000) 4.3466557686938915E+208 If you change GoodFib to return a double: GoodFib(6000) Infinity GoodFib(1000) 4.3466557686937428E+208 MyFib looses precision (I think):

    public static double NotEqual()
    {
        double count;
        double result1 = 0;
        double result2 = 0;
        for (count = 1;; count++)
        {
            result1 = GoodFib(count);
            result2 = MyFib(count);
            if (result1 != Math.Floor(result2))
                break;
        }
        Console.WriteLine("Result1: \[" + result1.ToString() + "\]");
        Console.WriteLine("Result2: \[" + result2.ToString() + "\]");
        return count;
    }

NotEqual() 71.0 Result1: [308061521170129] Result2: [308061521170130] ?!?! Not really sure which is correct. The online sources say GoodFib is right. If I was really to do something like this I would use Math Lab C# extensions. Guarinteed precision.

modified on Wednesday, July 8, 2009 2:42 AM

[Lost User]

'Maybe the SS uses this formula...' :laugh:

[Vozzie2]

Very nice, But i have visual studio 2003, :laugh: 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 . X|

It feels good to learn and achieve

[_Erik_]

I think you have not got the point. What I mean is that when an intervewer asks you to solve a problem within some kind of restrictions, as "recursive way" to do "whatever", the really important thing here is not the problem itself, but the way you can solve it applying those restrictions. That is why I have showed two possible ways to solve Fibonacci sequence in a recursive way. The first one is horrible because it has an exponential complexity, while the second one is linear. Sure, using golden proportion in this concrete case comes with a constant complexity algorithm, but you have not folowed the instructions. So, the problem here is not finding a Fibonacci number. The problem is to do it in a recursive way with a good performance. If the interviewer had asked you, for example, to find an iterative way to solve Hanoi's Tower problem, golden proportion would not be there to help you. On the other hand, when you say recursion is bad, sorry, but you are absolutely wrong. Many abstract data types are recursive by definition, like trees or graphs. Just implement a non recursive way to find a file within a tree of folders. When you get it, do it recursive. When finished, analyze both of them, how they work and what they do under the covers. When you get finished, I think you will really appreciate the real value of recursion.

[Viral Upadhyay]

i agree with you. Some time interviewer make matter worst. I also cant code when some one watching me. Its really confuse me. :^)

Viral My Site Tips & Tracks

[_Erik_]

That is exactly the point I wanted to reach.

[Lost User]

Yes I understand your point is valid. However, if the candidate tells the interviewer he understands recrusion and gives the text book definition and tells the interviewer that the problem is better solved using non-recrusive methods... If the interviewer does not trust the candidate it speaks bad for the company they represent. Why are recursive algrythms bad: IEEE Abstract - Recursive algorithms in computer science courses: Fibonacci numbersand binomial coefficients[^] I did some BigO testing of the various algorithms, here are the results: BadFib(40) LoopCount: [204668309] - SplitTimeMicro: [15042441.7069767] GoodFib(40) LoopCount: [38] - SplitTimeMicro: [1171.09856140934] MyFib(40) LoopCount: [1] - SplitTimeMicro: [6122.8452219486] - 'can be improved using the correct math lib.' LinerFib(40) LoopCount: [41] - SplitTimeMicro: [652.317543151434] Liner Fib:

    public static double LinerFib(double n)
    {
        double previous = -1;
        double result = 1;
        double sum = 0;
        for (double i = 0; i <= n; ++i)
        {
            sum = result + previous;
            previous = result;
            result = sum;
        }
        return result;
    }

'Most solutions to problems which are inherintly recrusive in nature can be solved using liner proofs...'

[Lost User]

_Erik_ wrote:

The problem is to do it in a recursive way with a good performance. If the interviewer had asked you, for example, to find an iterative way to solve Hanoi's Tower problem, golden proportion would not be there to help you.

This can be solved in linear time using a Hamiltonian Path: Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs [^]

[Lost User]

Using infinite asymptotics... MyFib(1477) Loops: [1477] Steps: [Approx:25109] GoodFib(1477) Loops: [1088552] Steps: [6537220] LinearFib(1477) Loops: [1092980] Steps: [8752702] Even though Linerfib takes more steps, it out performs GoodFib in a clock test. In engineering we call this the 'Proof from the pudding...' LinerFib(1477) LoopCount: [1478] - SplitTimeMicro: [44.6984183744023] MyFib(1477) LoopCount: [1] - SplitTimeMicro: [48.8888950970026] GoodFib(1477) LoopCount: [1475] - SplitTimeMicro: [507.047683434626]

modified on Wednesday, July 8, 2009 2:35 PM

[Lutoslaw]

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

[_Erik_]

Ok, guy. Which part of "the really important thing here is not the problem itself, but the way you can solve it applying those restrictions" is the one you have not understood?

[Lost User]

:~

_Erik_ wrote:

Ok, guy. Which part of "the really important thing here is not the problem itself, but the way you can solve it applying those restrictions" is the one you have not understood?

I have all ready admited your point is valid! My problem with the interviewer was that I had expalined the problems with recrusion and how it causes bad things to happen like: heap pile up, stack overflow, huge thread stacks, and object over load due to the problem with not being able box objects for reuse. I also told the interviewer that I only had a basic understanding of the problem and that I knew it would be better solved with out using recursion. I did explain what recursion was and such. My biggest mistake was not asking the interviewer for a diffrent problem using the same constraints for which I completly undestood. We are human Eric, a knowlegable man learns from his own mistakes, a wise man learns from others. I was not trying to bash you in this thread, my honest appoligies if you though as much. My intent was to show how I arrived at my conclusions about the problem algroythm during the interview. Perhaps others reading this thread could gain wisdom from my mistake. ~TheArch :cool:

[S Senthil Kumar]

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.

Regards Senthil _____________________________ My Home Page |My Blog | My Articles | My Flickr | WinMacro

[Lost User]

Doh! :sigh: You are correct! If you want all the files in all the directories you have to add: "*", SearchOption.AllDirectories

[Chris Losinger]

$10 says thisDir.GetDirectories is recursive

image processing toolkits | batch image processing

[Lost User]

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.

[Lost User]

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 :cool:

modified on Wednesday, July 15, 2009 8:27 AM

[Chris Losinger]

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

image processing toolkits | batch image processing

[Lost User]

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.