Sith Interviewing Tactics [modified]
-
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.
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...'
-
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.
_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 [^]
-
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.
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
-
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
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
-
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
-
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?
:~
_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:
-
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
File2your code will stop with A1 - it will not print A1.
Regards Senthil _____________________________ My Home Page |My Blog | My Articles | My Flickr | WinMacro
-
Umm, this goes only two levels down. If you have
C:\
A
A1
A11
File1
File2your code will stop with A1 - it will not print A1.
Regards Senthil _____________________________ My Home Page |My Blog | My Articles | My Flickr | WinMacro
-
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(); }$10 says thisDir.GetDirectories is recursive
-
$10 says thisDir.GetDirectories is recursive
-
$10 says thisDir.GetDirectories is recursive
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 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
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... ?
-
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.
-
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. :)
-
hmm. right you are. cool. :)
Thanks Chris! :-D 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.
-
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:
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! :cool: But how did you do it?
-
Thanks Chris! :-D 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).
-
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! :cool: But how did you do it?
Initialized an int to zero. Checked if the value started with a - (setting an isNegative boolean and, at the end, multiplying the value by -1). At each char read, checked if it was an int (>= '0' && <='9'). If not, returned 0. (it was a requisite). Multiplied the result by 10. If it was zero, nothing happened. Got the real value of the char (c - '0'). Added this value to the integer result. And thats it.
-
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.
Super Lloyd wrote:
As a rule recursion IS NOT bad. In fact it is use very much often!
I am still thinking about recursion. I really don't think it's a good thing. MSDN: Is there any situation where recursion is useful?[^] My thought is if you can do it with out recursion, then do. ~My 2¢
-
Super Lloyd wrote:
As a rule recursion IS NOT bad. In fact it is use very much often!
I am still thinking about recursion. I really don't think it's a good thing. MSDN: Is there any situation where recursion is useful?[^] My thought is if you can do it with out recursion, then do. ~My 2¢
Are you one of those religious warrior? Maybe I should tell you that I wrote 1 or maybe 2 goto this last year! I am not interested in religious war! I am interested, eventually, in well explained idea. Please do tell me why not recurse! So I will know when I should not... In the case of Fiboonacci it's easy, it requires "2^N" operation recursively and "N" in a non recursive fashion. But you statement was much more general, so please provide general argument against recursion. So that I know, according to you, when to avoid it. Well, I decided to participate in religious war after all.... And to challenge you, without waiting for your arguments, with some counter examples. How do you write structure recognizer in a non recursive fashion? i.e. how do you write thing such as a "Language compiler" or an "Object graph deserializer"?
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.