Sith Interviewing Tactics [modified]
-
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 wrotevoid 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
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 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);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.
-
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.
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").
-
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").
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.
-
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").
I just paid more attention to your flatten method as, convinced by your argument and the re-usability of this method (as opposed to its re-implementability!), I decided to put in my utility library. It's indeed cool and well implemented, and it does dispose all the enumerators, my mistake!
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:
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);Nifty! :cool: Would you mind if I added this coolness to the experimental test lib in my Big O Algroythm analyzer? If so let me know if you want your name in lights or not. I am adding the much needed Computer Science heurstics to the code base, so I would like to add a test for this as well. ~TheArch
-
Once I travled 400 miles to interview with a startup. All went well untill I was handed a pencile and a white sheet of paper and asked to write a recursive function in C# to produce a Fabbinicc sequence. Needles to say I didn't get the job. Do these people know that recursive algroythms = spigetti code? Hey Interviewers here is an IQ test: Penciles are for drawing as code is to? :confused: Hmm, the only thing important about Fabbinicci numbers and programming is that 1^n + 2^n ... + x^n has infinate solutions. And I'm not writting crypto software so it doesn't really matter. ~~
Update_I have learned much from this thread. Thanks to all who gave me a hard time!
As a result of all my research and learning I created a 'Big O Analyzer'.Hope it helps someone other than myself._
Big O Algroythm Analyzer for .NET[^] ~~
UpdateUpdatemodified on Wednesday, July 22, 2009 4:56 AM
You don't know why you didn't get the job. It could have been for many reasons. I've been turned down for jobs even AFTER I passed the technical part. A lot of who gets hired has to do with the chemistry of the group you're interviewing with. Qualifications are overrated. The second phrase is correct.
-
You don't know why you didn't get the job. It could have been for many reasons. I've been turned down for jobs even AFTER I passed the technical part. A lot of who gets hired has to do with the chemistry of the group you're interviewing with. Qualifications are overrated. The second phrase is correct.
-
You don't know why you didn't get the job. It could have been for many reasons. I've been turned down for jobs even AFTER I passed the technical part. A lot of who gets hired has to do with the chemistry of the group you're interviewing with. Qualifications are overrated. The second phrase is correct.
What would have been really funny; is if the interviewer actually hired me because I demonstrated recursion by repeatidly breaking the pencile in half. But he told me I didn't understand recursion. Hmm, strange how the subconcious mind works. :laugh: ~TheArch
-
What would have been really funny; is if the interviewer actually hired me because I demonstrated recursion by repeatidly breaking the pencile in half. But he told me I didn't understand recursion. Hmm, strange how the subconcious mind works. :laugh: ~TheArch