-
Infuriating!
Your desires are not my own.
Somehow, I'm fulfilled.
Intolerable!
When I hurt you, I feel pain.
What was I thinking?
Inconceivable!
I search for twenty-three years.
I discover more.
I love you, Eri.
I strive for your happiness.
Be my valentine.
-
Sorry to make a whole article with little more than a link, but, really, my kids need to read this. And this seems like the easiest way to remember.
-
Nice break. Time to get back with it; I'm running out of time, and I'm sure there's stuff I don't remember.
I finish studying up linked lists from Programming Interviews Exposed. Everything is pretty straightforward, but this last problem gets me: you're given a linked list; either the last node points to null (the list is normal, and acyclic), or the last node points to one of the earlier nodes in the list, in which case it has no end and is cyclic. Write an algorithm to determine which.
I progressed very quickly to the obvious answer: visit each node, and check whether it points to any of the earlier nodes in the list. No extra storage required, but it's O(n^2).
The answer, it turns out, I never would have gotten by myself: visit all the nodes at different rates. Have a slow pointer advancing one node at a time, and a fast pointer advancing two nodes at a time; if the fast pointer reaches an end, you're done, and you've only visited 1.5 times the nodes, which is O(n). If the fast pointer ever reaches the slow pointer, you've discovered a cycle visiting only 3 times the nodes... which is O(n). Of course, the author made an error that could result in a null pointer exception, and might accidentally skip the slow pointer the first time around, but those were easy to identify and rectify.
The brain teaser, Crazy Guy on the Airplane from techinterview, actually hammered home a rule of problem solving.
There are 100 passengers, numbered 1 through 100, boarding an airplane with 100 seats, also numbered 1 through 100. They'll be boarding in numerical order, and they'll sit in their numbered seat if it's available; otherwise they'll sit in a random available seat.
Problem is, passenger #1 is crazy. He randomly picks a seat, regardless of whether his seat is available.
What's the probability that passenger #100 will get to sit in his own seat?
-
After so much coding, I decided to take it easy with a brain teaser. I liked this techinterview palindrome puzzle. October 21, 2001 was a palindromic date, when written in MMDDYYYY format. What was the latest palindromic date previous to that?
-
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?
(2 comments)