Sith Interviewing Tactics [modified]

[Fatbuddha 1]

:laugh: 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 ). :laugh: 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)

[Distind]

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.

[supercat9]

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.

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