its not whether they lack the right skills or not. Its whether its worth it for them to use the skills. If this guy earns more than $400 in the time it takes for him to reformat and reinstall his computer, he should buy a new computer.
"Depth is, for any non-trivial, non-binary tree, less than breadth. Therefore a strict breadth-first ordering in a FIFO involves FAR MORE data movement (copying) and function calling (enqueue+CTOR and DeQueue+assign etc) than the recursive solution."
in this case, you are required to visit the nodes across the breadth to visit nodes of a certain depth. going all the way down will involve unnecessary node traversion
So the recursive function is _more_ efficent and is _more_ elegant and robust and involves less memory (and so less vm interraction and higher degree of locality and probably less cache contention on modern hardware) because you don't have to look-aside from your active data to do queue management and your active dataset is constrained by your depth parameter.
cant argue with better cache behavior, but passing around a depth variable like that is definitely not more elegant. Theres a difference between elegance and efficiency. in your case, your function is horrendously inefficient, but it is possible to code up a recursive function similar to yours. however, the FIFO solution is still more elegant due to its robustness with traversing more general graph structures.
For instance, at any given time, your complete active dataset is the current path from root to current node. So lets say this routine was traversing a slow-stroage tree (e.g. a database) or shared data structure, the total number of records that would have to be read-locked to acheive a consistent (safe) pass is CURRENT_DEPTH (a scalar quantity from 1 to X) while doing a breadth-first traversal with consistent (safe) read using a FIFO would require locking the current node plus all nodes who's depth is less than the depth of the current node. Not terribly elegent nor efficent.
incorrect. you would need to read lock some nodes at the current depth and the current depth-1.
Look it up.
For "a constrained operation on a tree" where the nature and order of the tree are unknown (e.g. as a generic operation) queue-based operations are "always" inferrior.
And as for graph traversals, if there are "cycles" then you don't have "a tree" you have "a graph" which is a completely different problem set. If the tree is immutable (constant or logically constant, or expensive to mark, or subject to multiple concurrent traversals) then you need to be able to construct a coresident data structure (typically a visitation set) to act as a dynamic boundary case and to prevent a traversal that looks artificially "leggy" you would want to use a FIFO.
But again, that's a GRAPH and not a TREE.
Look that up too
if you read my original post, i did distinguish between an arbitrary graph and a tree. the point is that the fifo solution is more robust: it can handle more problems while having the same running time. If your code, in a later phase, turns out it needs to be modified so that the structure is no longer a tree, you would need less effort to modify your algorithms that traverse the structure.
Now if you _know_ youre data set is likely to produce a leggy tree, or degenerate into a linked list or something, you would want a FIFO; just as if you know your tree is artificially broad (say that each node can have hundreds of direct children) you would want to avoid the FIFO as if your life depended on it.
that doesnt make sense. it doesn't matter either way.
Being "Completely Breadth First" in no way equates to "More Elegant" unless you are only interested in the breadth-first-i-ness for its own sake.
it is more elegant because of its robustness when traversing non-tree structures
[BEGIN OLD GEEZER ASIDE]
When I was in my B.S.C.S. program back in 1982 I took this course called "The calculus of computer programming"; the course was terribly boring but the lab sessions were outstanding. We had a pascal compiler
Your function is going to traverse the entire tree, obviously that is not very efficient. You only want to traverse the nodes above that level.
the classic FIFO solution is recursive too.
You have to note that it is not necessarily a binary tree. the interviewer is testing the classic solution of a tree traversal where you put visited nodes in a queue or stack. In this case, it doesn't matter whether it is a queue or a stack.
The FIFO solution can be considered more elegant because it is completely breadth first. If you try to adapt your algorithm to a graph traversal where there may be cycles, but you also want to list the nodes of a distance from the beginning node, it will still work.
tree traversal is easy. all you want to make sure for efficiency is not to go beyond the depth needed. However, i think the intereviewer was looking for the elegance and robustness of using a global queue or stack. (if the interviewer asks: what if we relax the assumption that the structure we are traversing is a tree, the solution need not be modified)
Im interested in what your solution to that toy problem is.
The FIFO queue solution is quite obvious and runs in linear time. I don't see how you can get better than that.
then why are they waiters? usually they know how to groom themslves well to become hookers or gigolos. Let the homeless people work below minimum wage.
Eh.. in Taiwan we don't tip and the service is a lot better than in USA. The food is too.. for about $5 you can get equivalent of a $100 meal in USA and the service is better too.
mod the parent up, its true. No one tips other than the USA. Also, USA things are so expensive and sucky, US dollar is still overvalued. sell your $$$ folks
Um.. he's only 5 years old, just let him play. It will help his mental development. Its not like school work at 5 years old matters all that much Put yourself in his shoes. He wants to play games. He enjoys it better than other activities. Why stop him? When he wants to do other activities, he will. Its just a phase.
It is obvious that Tom Lin has very little to do with luxpro. hotels.com.tw is a web hosting company that luxpro uses, hence, the whois info is under hotels.com.tw
Actually, it is not known whether true pseudo-random generators exist either.
It is well known that if pseudo-random generators exist, P != NP
All available "pseudo-random generators" are called pseudo-random because they satisfy some ad-hoc statistical test, not that they are really pseudo-random in any way.
It is not just broadband internet. The overall quality of life in America is a lot worse than other countries. Many Americans are ignorant how far other countries have advanced. Living in America feels like living in 1980's taiwan.
Slashdot Mirror
stop turniing his readable code into your unreadable code. he should use strcat() end of discussion.
Mod parent up!
lol at worrying about the efficient of strcat()
thats why you eat it with slices of rabbit liver
this shit happens in taiwan too.. very frequently. i dont see why people die..
no
they suck
for a long time, they were the only monitors with a maximum refresh rate of 75Hz
it strains the eye really badly
I fail to see how "logically solving problems" is not math
cable is better than dsl? are you kidding me slow dsl is way better than cable just because telco providers have better access to the backbones
its not whether they lack the right skills or not. Its whether its worth it for them to use the skills. If this guy earns more than $400 in the time it takes for him to reformat and reinstall his computer, he should buy a new computer.
in this case, you are required to visit the nodes across the breadth to visit nodes of a certain depth. going all the way down will involve unnecessary node traversion
cant argue with better cache behavior, but passing around a depth variable like that is definitely not more elegant. Theres a difference between elegance and efficiency. in your case, your function is horrendously inefficient, but it is possible to code up a recursive function similar to yours. however, the FIFO solution is still more elegant due to its robustness with traversing more general graph structures.
incorrect. you would need to read lock some nodes at the current depth and the current depth-1.
if you read my original post, i did distinguish between an arbitrary graph and a tree. the point is that the fifo solution is more robust: it can handle more problems while having the same running time. If your code, in a later phase, turns out it needs to be modified so that the structure is no longer a tree, you would need less effort to modify your algorithms that traverse the structure.
that doesnt make sense. it doesn't matter either way.
it is more elegant because of its robustness when traversing non-tree structures
Your function is going to traverse the entire tree, obviously that is not very efficient. You only want to traverse the nodes above that level. the classic FIFO solution is recursive too. You have to note that it is not necessarily a binary tree. the interviewer is testing the classic solution of a tree traversal where you put visited nodes in a queue or stack. In this case, it doesn't matter whether it is a queue or a stack. The FIFO solution can be considered more elegant because it is completely breadth first. If you try to adapt your algorithm to a graph traversal where there may be cycles, but you also want to list the nodes of a distance from the beginning node, it will still work. tree traversal is easy. all you want to make sure for efficiency is not to go beyond the depth needed. However, i think the intereviewer was looking for the elegance and robustness of using a global queue or stack. (if the interviewer asks: what if we relax the assumption that the structure we are traversing is a tree, the solution need not be modified)
Im interested in what your solution to that toy problem is. The FIFO queue solution is quite obvious and runs in linear time. I don't see how you can get better than that.
Why dont' they just rent a bunch of apartments and houses, should be cheaper that way.
1st post
then why are they waiters? usually they know how to groom themslves well to become hookers or gigolos. Let the homeless people work below minimum wage.
Eh.. in Taiwan we don't tip and the service is a lot better than in USA. The food is too.. for about $5 you can get equivalent of a $100 meal in USA and the service is better too.
mod the parent up, its true. No one tips other than the USA. Also, USA things are so expensive and sucky, US dollar is still overvalued. sell your $$$ folks
Um.. he's only 5 years old, just let him play. It will help his mental development. Its not like school work at 5 years old matters all that much Put yourself in his shoes. He wants to play games. He enjoys it better than other activities. Why stop him? When he wants to do other activities, he will. Its just a phase.
It is obvious that Tom Lin has very little to do with luxpro. hotels.com.tw is a web hosting company that luxpro uses, hence, the whois info is under hotels.com.tw
lol if the shuffle can be charged while be used for female masturbation it would probably generate a lot of elextricity
great... i guess they solved P!=NP then.
Actually, it is not known whether true pseudo-random generators exist either.
It is well known that if pseudo-random generators exist, P != NP
All available "pseudo-random generators" are called pseudo-random because they satisfy some ad-hoc statistical test, not that they are really pseudo-random in any way.
eh of course it can be solved. there are a finite number of states.
I am Taiwanese, and I have to say that Far Eastern Asians like us, are far dumber than Indians.
Actually, the best food is found in Asia. (even western cuisine)
It is not just broadband internet. The overall quality of life in America is a lot worse than other countries. Many Americans are ignorant how far other countries have advanced. Living in America feels like living in 1980's taiwan.