The Attic

Oh, great. Yesterday I flattened a bush; today you want me to un-flatten it?

This is going to require a bit of recursion, I can just tell. That's fine, I love recursion.

I kept all the child pointers when I flattened the bush, so that will tell me where the children start. I'll just traverse the list, and anytime I find a child pointer, I'll disconnect the child and all its siblings, reconnecting them as the child of the parent.

Hmmm. Only one small problem: how will I know when to stop disconnecting the child? The first parent that I encounter will get the child, and the remainder of the list afterwards, as its children.

Maybe I'd better rewrite Flatten to use a different algorithm. Certainly the interviewer would have steered me toward a solution with recognizable ends. Wouldn't he?

Yesterday I made a linked list, in Java. Yeah, that's right.

Today I'm taking on a programming problem: given a doubly-linked list (with head and tail), where any element may have a child doubly-linked list (without head and tail), flatten the structure into a doubly-linked list.

That sounds vaguely tree-like, but trees don't usually have linked siblings. It's all just parents and children. I'm calling this a bush.

Let's look at the structure.

head->A<=>D<=>E<=>F<-tail
      |           |
      B<=>C       G
                  |
                  H

Without being told where to put stuff, I could just tack it all on the tail. But I think tacking it on after its parent is more elegant, if it can be implemented in similar complexity and space. In the bush I drew, I'd like the nodes to end up in alphabetical order.

I might even be able to do this without recursion.

I started my studying today by looking at Programming Interviews Exposed. The author indicates that linked-list problems are common in coding interviews, because they can be solved relatively quickly, but they still expose the coder's thought processes.

As a Java programmer, I don't have much use for linked lists. Java includes a LinkedList class that takes care of all the operations for me. But according to the book, I might still be asked to implement a linked list of my own and solve some linked list problems... because it will expose my thought process.

Okay, I remember linked lists from back when I was a hot-shot C programmer. (I used to think Java was a flash in a pan. With the recent security vulnerabilities, it may turn out that way after all.) I can do this. But perhaps I should pass on the brain teaser for today. The list problems can be my brain teaser.

Implement a singly-linked list. Given a doubly-linked list (with tail pointer) where each node may have a doubly-linked list (without head or tail pointers) as a child, and the children may have their own children, flatten it to a plain doubly-linked list. Now put it back.

Today's studying involved "Dynamic Programming" and "Backtracking", which really turned out to be different names for little tricks I've used before in recursion. I'm going to have to look at them again, just to make sure I've got it straight, in case I get asked. I don't want to look like an idiot because I don't know something's name.

Especially if I use it all the time.

Anyway. I know why you're really here: today I tried a brainteaser from techinterview about pirates. It ARRRR-ta be a lot of fun.

Five pirates have captured a booty of 100 gold pieces. As you know, pirates use a seniority system when it comes to making decisions; in this case, the most senior pirate is pirate #5 and the least senior is pirate #1 (n00b).

You also know, of course, that pirates are greedy. And bloodthirsty. What sets this group of pirates apart, though, is how intelligent they are.

By which I mean that they're really smart (not noteworthy in the opposite direction).

Their method of dividing the 100 coins will be in keeping with pirate greed, violence, and seniority. The most senior pirate will propose a division of booty. All the pirates will vote to accept or reject the proposal. If at least 50% approve, the booty is divided according to the proposal. Otherwise, the propose-er walks the plank, and the new most senior pirate makes a new proposal.

Of course, having such massive brainpower, the most senior pirate makes a proposal that is automatically accepted. What was it?

Today I only studied a little bit. I had too much other stuff to do. But I did manage to find a nice brain teaser from GeeksForGeeks.org.

Imagine a champagne pyramid, but in only two dimensions. Like this:

Level 1:    1
Level 2:   1 2
Level 3:  1 2 3

Of course, we could have as many levels of this "pyramid" as we liked.

All the glasses are the same. When you overfill Level 1 glass 1, the overflow goes half to the left (Level 2 glass 1) and half to the right (Level 2 glass 2). Every time a glass is overfilled, half the overflow goes to the left and half to the right.

Find a method to tell me how much champagne is in any glass, when I tell you how much I poured into the top glass.

For instance, if I say I poured 4 glassfuls, and I want to know about Level 3 glass 3, you'd tell me it had 0.25 glassfuls.