Sith Interviewing Tactics [modified]

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

[Chris Losinger]

hmm. right you are. cool. :)

image processing toolkits | batch image processing

[Lost User]

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.

[Lost User]

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?

[Chris Losinger]

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

image processing toolkits | batch image processing

[Paulo Zemek]

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.

[Lost User]

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]

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.

[Lost User]

Super Lloyd wrote:

Are you one of those religious warrior?

:laugh: No! I am still investigating it. I had a mentor from Sun whom was crazy about it. I used it alot on that job. But after leaving I think I might have only used it twice.

Super Lloyd wrote:

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

Heck, I couldn't even do the easy example of getting all the widgets in the visual tree for WPF. I will do some research for you and get back to you. But I leave you with this thought. 'How did they do this before the invented recursive functions?' ~TheArch “Make love, not war” American Proverb quotes[^]

[Lost User]

Super Lloyd wrote:

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

Just getting back to you Super Lloyd. I read the Wikipedia on recusion. Seems not all problems can be solved with out recursion. Case: Ackermann function[^] A funny from the Wiki: '"In order to understand recursion, one must first understand recursion." Or perhaps more accurate is the following, from Andrew Plotkin: "If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is."' Also from the Wiki: 'In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. These functions are also important in proof theory. Most of the functions normally studied in number theory are primitive recursive. For example: addition, division, factorial, exponential and the nth prime are all primitive recursive. So are many approximations to real-valued functions. (Brainerd and Landweber, 1974) In fact, it is difficult to devise a function that is not primitive recursive, although some are known (see the section on Limitations below). The set of primitive recursive functions is known as PR in complexity theory.' 'I guess when you really get to the salt; everything is recursive.'

[Super Lloyd]

Well, mm.. You haven't told me yet why I should abstain from recursion! Further, how about more mundane cases.... Why would getting the list of all control in a hierarchy this way be any bad? pseudo C# below! IEnumerable<Control> GetUITree(Control c) { yield return c; foreach(Control c in c.Children) foreach(Control c2 in GetUITree(c)) yield return c2; } Another "theorical" question as you might seems to like. IF I can call a user (developer) defined function in a user defined function. Any function call is potentially recursive! After all when I wrote void f() { g(); } Maybe g() enumerate a list of function pointer one of them being f(), doesn't that means you should stop calling user defined function in user defined function?

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.

modified on Sunday, July 19, 2009 4:28 AM

[Daniel Grunwald]

Super Lloyd wrote:

Why would getting the list of all control in a hierarchy this way be any bad?

In this case, it's bad because for every control in the innermost layer, it has to be passed up N levels on the stack (once for each yield return). This means iterating through the tree will be O(N^2) worst-case. But this can be easily solved using CPS (continuation passing style):

void IterateUITree(Control c, Action<Control> listener)
{
listener(c);
foreach(Control child in c.Children)
IterateUITree(child, listener);
}

But if you actually need a IEnumerable<T>, you need to give up recursion and manage the stack yourself (this also means manually repeating the foreach-magic):

/// <summary>
/// Converts a recursive data structure into a flat list.
/// </summary>
/// <param name="input">The root elements of the recursive data structure.</param>
/// <param name="recursive">The function that gets the children of an element.</param>
/// <returns>Iterator that enumerates the tree structure in preorder.</returns>
public static IEnumerable<T> Flatten<T>(this IEnumerable<T> input, Func<T, IEnumerable<T>> recursion)
{
Stack<IEnumerator<T>> stack = new Stack<IEnumerator<T>>();
try {
stack.Push(input.GetEnumerator());
while (stack.Count > 0) {
while (stack.Peek().MoveNext()) {
T element = stack.Peek().Current;
yield return element;
IEnumerable<T> children = recursion(element);
if (children != null) {
stack.Push(children.GetEnumerator());
}
}
stack.Pop().Dispose();
}
} finally {
while (stack.Count > 0) {
stack.Pop().Dispose();
}
}
}

Usage:

Control[] roots = { control };
var flatList = roots.Flatten(c=>c.Children);

[Super Lloyd]

Actually there is much more simple and readable and maintainable than this complicated flatten method, and you should have thought of it. Except it's recursive of course... (meaning that you should get rid of your mind block with recursivity!) void IEnumerable<Control>IterateUITree(Control c) { var result = new List<Control>(); result.Add(c); foreach(Control child in c.Children) IterateUITree(child, result); return result; } void IterateUITree(Control c, List<Control> result) { result.Add(c); foreach(Control child in c.Children) IterateUITree(child, result); } I used that occasionally. It avoid the "performance" problem (of both my example code and your complicated flatten code) and is much easier to read / understand / maintain. And even better performant than your flatten method, although not by much (but anyway its main advantage is readability, so I would use it even if it were less performant). Anyway, I was just talking about recursion in general and this double foreach was my 1st idea. Now you replace a very simple (and presumablye costly) nested foreach with a way more complicated (hence bug prone) code. it's not obvious it's going to be more performant or efficient. It will probably depends on the shape of the data. Also it is potentially buggy (another sign that complicated code is not a good idea, even if you *think* it's more performant)(you should do performance test to check that). Anyway, if I'm not mistaken, the GetEnumerator() method sometime return IDisposable object (it's how the Finally block of enumerator are executed I believe, as well as removing some event listeneners), so you should check that the IENumerator in your code are IDisposable or not and dispose of them...

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.

[Daniel Grunwald]

Yes, often passing a list around and adding to it works fine. But it's not exactly equivalent to your nested "yield return". In my case, I really needed a enumerator that was being lazily evaluated. And yes, you need to dispose enumerators. My Flatten method does that. Of course I realize that recursion is a lot cleaner than manually messing with a stack. That was the point of my two code snippets. But unfortunately, due do the language's implementation of "yield return", it's unavoidable in this specific case. To efficiently support recursion in iterators, the language would need something like a "yield foreach" statement - see http://blogs.msdn.com/wesdyer/archive/2007/03/23/all-about-iterators.aspx[^] ("The Cost of Iterators").

[Super Lloyd]

cool link hey! And, mm.. while I wouldn't like to write the Flatten method on a daily basis (unlike the iterators) it has some merit as a library utility! :)

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.