4 ms·

Wouldn't that be a "mirror" operation, while inversion would be (I dunno) swapping the direction of the edges? I went out of my way to avoid homebrew (still do

by dekhn 4y ago

Wouldn't that be a "mirror" operation, while inversion would be (I dunno) swapping the direction of the edges? I went out of my way to avoid homebrew (still do) when I worked at google because it would reliably fail to complete some key operations in a dag, hence the interest in ensuring developers know how to do CS things.

sophonX 4y ago
There you go ! This comment should be highlighted.
- devnullbrain 4y ago
  It doesn't matter, the candidate should ask for clarification if the question is ambiguous.
  - sophonX 4y ago
    I was referring to second para or statement. (-_-)
howling 4y ago
Yeah it's not clear what he was asked. Swapping the direction of every edge of a binary tree would result in a DAG that is likely no longer a binary tree though.
- gifnamething 4y ago
  Are you confusing a binary tree with something else? Here's an example: https://leetcode.com/problems/invert-binary-tree/ https://leetcode.com/problems/invert-binary-tree/ It's an 'easy' question. The solution is <10 lines.
  - zeroonetwothree 4y ago
    Yeah it's really easy. I wrote a correct solution in about 30 seconds on my first try. And I haven't actually practiced these problems for 10+ years.
virtuous_signal 4y ago
"Mirror" is what this question is generally understood to be asking. I don't think swapping the direction of the edges produces a tree in general although it would produce a DAG. I think "invert" could mean "mirror" or turn upside-down depending on the context.
- dekhn 4y ago
  Personally, if I were asked this, I would just say "convert the graph to a matrix, invert the matrix, and then convert the resulting inverted matrix back to a graph", and let them try to figure out if that would work for a bit before joking "oh come on, preorder traversal with a temp var, do you have a more interesting question?"
- karmakaze 4y ago
  It would be more leetcode to be given an ordered binary tree and asked to reverse it O(N). It's a lot more fair to the interviewee to be given the explicit task without knowing 'the trick' unless one considers knowing recursive functions to be a trick.

by dekhn 4y ago

sophonX 4y ago

There you go ! This comment should be highlighted.

devnullbrain 4y ago
It doesn't matter, the candidate should ask for clarification if the question is ambiguous.
- sophonX 4y ago
  I was referring to second para or statement. (-_-)

howling 4y ago

Yeah it's not clear what he was asked. Swapping the direction of every edge of a binary tree would result in a DAG that is likely no longer a binary tree though.

gifnamething 4y ago
Are you confusing a binary tree with something else? Here's an example: https://leetcode.com/problems/invert-binary-tree/ https://leetcode.com/problems/invert-binary-tree/ It's an 'easy' question. The solution is <10 lines.
- zeroonetwothree 4y ago
  Yeah it's really easy. I wrote a correct solution in about 30 seconds on my first try. And I haven't actually practiced these problems for 10+ years.

virtuous_signal 4y ago

"Mirror" is what this question is generally understood to be asking. I don't think swapping the direction of the edges produces a tree in general although it would produce a DAG. I think "invert" could mean "mirror" or turn upside-down depending on the context.

dekhn 4y ago
Personally, if I were asked this, I would just say "convert the graph to a matrix, invert the matrix, and then convert the resulting inverted matrix back to a graph", and let them try to figure out if that would work for a bit before joking "oh come on, preorder traversal with a temp var, do you have a more interesting question?"
karmakaze 4y ago
It would be more leetcode to be given an ordered binary tree and asked to reverse it O(N). It's a lot more fair to the interviewee to be given the explicit task without knowing 'the trick' unless one considers knowing recursive functions to be a trick.