Sith Interviewing Tactics [modified]

[Lost User]

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

[Lost User]

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

[Ian_Sharpe]

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.

[Vozzie2]

I wonder, if recursion = spogitta then how do you enumerate directories?

It feels good to learn and achieve

[_Erik_]

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

[Paulo Zemek]

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.

[Dan Neely]

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.

[Lost User]

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

[Lost User]

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

[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