-1

In Missy Elliott's song Work It, she sings, "I put my thang down, flip it, and reverse it."

A lot of jokes have been made of these lyrics, including this classic xkcd: https://xkcd.com/153/

I recently saw this tweet, https://i.stack.imgur.com/mLq15.jpg , and began to wonder what data structures can be flipped AND reversed.

A linked list can be reversed, but can it be flipped?

A B tree could be 'flipped' in the sense that child nodes point to parent nodes instead of the other way around but I would probably describe this as 'inverted' not flipped.

I think an array could be flipped by swapping its indices and values. Could it then be reversed?

The written lyrics are:

I put my thang down, flip it and reverse it

Ti esrever dna ti pilf nwod gnaht ym tup i

This line is definitely reversed, but I don't think it's flipped. I think if the characters were upside down, then they would be both reversed AND flipped.

I'm looking for a serious answer as I hope this could lead to a fun interview question.

Adam
  • 959
  • 10
  • 23
  • So you don't want to ask real life questions but only tricks and games? Going into interviews is hard enough without you trying to trip us up. – Rob Apr 27 '21 at 01:07
  • Take a look at [`BitSet`](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/BitSet.html) – fps Apr 27 '21 at 01:18
  • @Rob tricking someone definitely is not the goal. I was hoping to put together a few questions that are just for fun. – Adam Apr 27 '21 at 02:06

1 Answers1

2

Not so easy, since presumably you want flipping and reversing to be distinct operations so that you don't end up with the same structure. Also you want them both to be real operations, not just drawing differently.

The only thing that comes to mind is this recent SO question, where I mention that a postorder traversal of a tree is the reverse of the preorder traversal of the reversed tree: Uniqueness of Inorder, Preorder, and Postorder traversal with null elements

So... if you want to convert a pre-order traversal function to post order or vice-versa, you can whack the tree down, flip it around and then reverse the output.

A function that converts a pre-order traversal function into a post-order traversal function would be the Missy Elliott Combinator, which is not a bad name at all.

ETA:

Also, and completely unrelated...

You can perform any rotation of an object in 2D by reflecting it across a chosen line (the flip) and then reversing it along an axis. The angle of rotation is twice the angle between the lines of reflection. It also works for pointing an object along any vector in 3D.

This operation should obviously be known as a Missy Eliott rotation.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87