Sith Interviewing Tactics [modified]
-
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.
-
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.
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[^]
-
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.
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 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.'
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
-
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