Ask HN: Have you ever needed to invert a binary tree at work?
21 comments
[deleted]
I've used trees for data, but never had to invert one.
TBH asking that kind of question at interview is a big red flag for me, means that they don't understand how to interview tech people and therefore probably don't understand how to manage tech people.
TBH asking that kind of question at interview is a big red flag for me, means that they don't understand how to interview tech people and therefore probably don't understand how to manage tech people.
> TBH asking that kind of question at interview is a big red flag for me, means that they don't understand how to interview tech people and therefore probably don't understand how to manage tech people.
This means Google and others don't understand how to manage tech people... which I guess it may be true.
This means Google and others don't understand how to manage tech people... which I guess it may be true.
Large organisations almost universally don't understand how to manage tech people. HR get in the way and force bad decisions onto even the good managers.
[deleted]
0, but you need it to get work.
Just be pragmatic about it. The same way you've learned a lot of crap at school for nothing, do you expect that in the job market it would be any different?
The world is fucked up, the earlier you internalise this in yourself, the less you suffer.
Just be pragmatic about it. The same way you've learned a lot of crap at school for nothing, do you expect that in the job market it would be any different?
The world is fucked up, the earlier you internalise this in yourself, the less you suffer.
I hate that you're right. But you're right.
[deleted]
As a professional developer, if I am faced with the task of dealing with binary trees at work, I would never:
- implement my own binary tree
- implement my own "invert a binary tree" algorithm
Reasons:
- my own implementation would be way worse than any other open source implementation (which has been reviewed extensively) in terms of: performance, number of bugs, correctness
- it would be a hell to maintain for future developers that have to maintain my code
- it just makes sense. Well understood algorithms do not require re-implementation
- implement my own binary tree
- implement my own "invert a binary tree" algorithm
Reasons:
- my own implementation would be way worse than any other open source implementation (which has been reviewed extensively) in terms of: performance, number of bugs, correctness
- it would be a hell to maintain for future developers that have to maintain my code
- it just makes sense. Well understood algorithms do not require re-implementation
No, however, please note the following:
Companies, like customers, have requirements for their needs. If a company needs a potential employee to know how to invert a binary tree then it's in their right to find one.
In Google's case, as you're probably alluding to[0], although I might be mistaken, they've always had the reputation for seeking the best qualified people[1] for their work. I mean look at who's working for them - there's a lot of well-known people in their respective fields that are working for them.
Moreover, I think that the point of these tests is to help assess a potential employee's abstract thinking. And, probably, to understand one's thought process behind the solution - if there's one - to the given problem. (Which, by the way, might be helpful if you're trying to solve AI - something that's right up in Google's alley ;).
Despite the backlash over this, I believe companies will keep doing these types of tests for a long, long time. I don't think this is going away that easily. And I also think that, in the future, these tests might be done in a way you won't even know you're being tested for.
[0] - https://twitter.com/mxcl/status/608682016205344768
[1] - I understand that "best qualified" here might mean different things for different people, but you should take it literally, that is, people who are above the average in terms of abstract thinking. I suggest you read How Google Works[2], they've coined the term Smart Creative which is kind of(?) related to this.
[2] - https://www.howgoogleworks.net/
Companies, like customers, have requirements for their needs. If a company needs a potential employee to know how to invert a binary tree then it's in their right to find one.
In Google's case, as you're probably alluding to[0], although I might be mistaken, they've always had the reputation for seeking the best qualified people[1] for their work. I mean look at who's working for them - there's a lot of well-known people in their respective fields that are working for them.
Moreover, I think that the point of these tests is to help assess a potential employee's abstract thinking. And, probably, to understand one's thought process behind the solution - if there's one - to the given problem. (Which, by the way, might be helpful if you're trying to solve AI - something that's right up in Google's alley ;).
Despite the backlash over this, I believe companies will keep doing these types of tests for a long, long time. I don't think this is going away that easily. And I also think that, in the future, these tests might be done in a way you won't even know you're being tested for.
[0] - https://twitter.com/mxcl/status/608682016205344768
[1] - I understand that "best qualified" here might mean different things for different people, but you should take it literally, that is, people who are above the average in terms of abstract thinking. I suggest you read How Google Works[2], they've coined the term Smart Creative which is kind of(?) related to this.
[2] - https://www.howgoogleworks.net/
Inverting a binary tree doesn't achieve anything; the organization is basically the same, being a mirror image, and so doesn't shed any new light on the data.
If you ever have to maintain a code base that happens to invert binary trees, find a way to nuke that code. Whatever needs the binary tree backwards should just process the original order backwards. Then you can say you once needed to remove a silly binary tree inversion at work.
Even reversing arrays and linked lists is suspicious.
Lisp code sometimes does a nreverse pass due to pushing items onto a stack while processing, which reverses their order.
I've never had to reverse an array in C or what have you.
I recall that the block sort algorithm does some clever things with multiple reverses of subranges of an array.
If you ever have to maintain a code base that happens to invert binary trees, find a way to nuke that code. Whatever needs the binary tree backwards should just process the original order backwards. Then you can say you once needed to remove a silly binary tree inversion at work.
Even reversing arrays and linked lists is suspicious.
Lisp code sometimes does a nreverse pass due to pushing items onto a stack while processing, which reverses their order.
I've never had to reverse an array in C or what have you.
I recall that the block sort algorithm does some clever things with multiple reverses of subranges of an array.
So I had to look up what 'invert a binary tree' meant. I was thinking make the leaves roots and the root a leaf, which made no sense.
So flipping the left and right, no I have never had to do that. I have had to write algorithms that processed the tree in infix, prefix and postfix order. And I have had to do it backwards, which is kind of the same but I never changed the tree for that.
As far as an interview question it is testing 2 things, 1) do you even know what a binary tree is, 2) are you comfortable with recursion. And in my case 3) are you willing to admit you do not understand and need an explanation.
From an interview perspective, all 3 are viable questions.
So flipping the left and right, no I have never had to do that. I have had to write algorithms that processed the tree in infix, prefix and postfix order. And I have had to do it backwards, which is kind of the same but I never changed the tree for that.
As far as an interview question it is testing 2 things, 1) do you even know what a binary tree is, 2) are you comfortable with recursion. And in my case 3) are you willing to admit you do not understand and need an explanation.
From an interview perspective, all 3 are viable questions.
No and that's not the point. The point is knowing the application of that algorithm or the other.
But I also never had the need for its application, maybe I had and missed it :)
But I also never had the need for its application, maybe I had and missed it :)
What does that even mean? Putting it upside down? But that's just the exact same graph, so a no-op operation? Come to think of it, I wrote a plenty of no-op methods in my career...
It means ordering it in reverse. Mirroring might be a better description.
How about we do that in Lisp, and then apply the invert function to its own source code?
Okay, now let's crank up the stupid knob to about 7.5.
1> (defun invert (tree)
(if (atom tree)
tree
(cons (invert (cdr tree)) (invert (car tree)))))
invert
2> (invert '(defun invert (tree)
(if (atom tree)
tree
(cons (invert (cdr tree)) (invert (car tree))))))
((((nil (((nil ((nil (nil (nil . tree) . car) . invert) (nil (nil . tree) . cdr) . invert) . cons) . tree)
(nil . tree) . atom) . if)
nil . tree) . invert) . defun)
3> (defun invert2 (tree)
(if (listp tree)
[mapcar invert2 (reverse tree)]
tree))
invert2
4> (invert2 '(defun invert (tree)
(if (atom tree)
tree
(cons (invert (cdr tree)) (invert (car tree))))))
(((((tree car) invert) ((tree cdr) invert) cons) tree (tree atom)
if)
(tree) invert defun)
Okay, now let's crank up the stupid knob to about 7.5.
5> (defun invert3 (tree)
(cond ((listp tree)
[mapcar invert3 (reverse tree)])
((symbolp tree) (intern (reverse (symbol-name tree))))
(t tree)))
invert3
6> (invert3 '(defun invert (tree)
(if (atom tree)
tree
(cons (invert (cdr tree)) (invert (car tree))))))
(((((eert rac) trevni) ((eert rdc) trevni) snoc) eert (eert mota)
fi)
(eert) trevni nufed)
12> (defun invert4 (tree)
(let ((tree-picture (with-out-strlist-stream (s)
(print tree s))))
(each ((line tree-picture))
(let* ((rl (reverse line))
(sb (mapcar (relate "()" ")(") rl)))
(put-line `@{sb -78}`)))))
invert4
13> (invert4 '(defun invert (tree)
(if (atom tree)
tree
(cons (invert (cdr tree)) (invert (car tree))))))
trevni nufed)
(eert mota) fi) (eert)
((eert rdc) trevni) snoc) eert
(((((eert rac) trevni)
nil
Never had to create one, let alone invert one.
I have inverted a binary tree out of fun. But if you are less strict about left/right, you have to do exactly nothing.
No, I did have to do depth first search with backtracking (e.g. once at node go one up and take node with lowest value).
I guess its a matter of perspective
Charles Babbage asked Ada Lovelace to invert a binary tree before he agreed to let her work on his Analytical Engine.
In his famous resume, Leonardo claimed knowledge of "efficient methods of turning a bifurcated assembly of facts upon itself, and other procedures useful in the arts of arranging and displaying facts."
It's tradition.
https://en.m.wikipedia.org/wiki/Ada_Lovelace
https://duckduckgo.com/?q=resume+of+leonardo+da+vinci&t=fpas...