Alphabetic Phone Number Generator SOLVED [Problem of the Week]

It’s been a while, huh? Well, for the second time, my apologies!

Anyway, the past problem was of medium difficulty, but there’s a trick that could make your life much easier. Do you know what a permutation is? This is a permutation problem. A definition of permutation is that a permutation of [ABC] is simply [ABC – ACB – BAC – BCA – CAB – CBA] .. all possible arrangements of the three letters. Think of our problem the same way, you just need all possible arrangements for the three characters corresponding to each number. Easier? Thanks to Abdalla Gamal for making our lives easier.

So, similar to the ACM problems, we’ll solve the standard permutation problem, where we get to print all possible arrangements of a set of digits. Then, we transform that to our problem.

Alphabetic Phone Number Generator [Problem of the Week]

Mmm, not quite problem of the “week” since it has been a while since I last posted a problem – I had a busy few weeks, my apologies!

Anyway, let’s move to the problem – another Microsoft interview problem. Sure you’ve all seen how phone pads hold three letters of the alphabet for every number you can press (except for 1 and 0). Check the photo below to know what I mean …

The problem is simple. The input is a distinct, seven-digit number. The required output is all seven-character strings that could be generated from this number.

The acmASCIS 2008-Online-Contest [acmASCIS, FCIS]

Update: The contest has begun already. Deadline for submissions is 17th of Sept, 2008, at 10:00 pm.

---

An announcement to current FCISians only …

Link-the-Tree SOLVED [Problem of the Week]

This week’s problem was was pretty easy – obviously for ACMers only!!

Anyway, here’s the solution. You were given a binary tree, not necessarily complete (most people overlooked this point, and hence they didn’t handle having nodes with only left or only right nodes – they just assumed that every node either has both or not!). The task was transforming that tree into a linked list by adding a Next pointer to the struct. Here’s a diagram that would make explaining such story much easier (my diagram, that’s why it sure looks better .. LOL):

On the left, you’ll find the original binary tree, along with two pointers, R and C, that I’ll use to solve the problem as you’ll see in a moment. On the right, this is the required output.

Link-the-Tree [Problem of the Week]

Seems that last week’s problem was a bit difficult as Fouad stated in his last problem, so this weeks it’s an easier one .. not that easy though. It should be easy for all ACMers .. we’ll see!
I first met this problem in a physical Microsoft technical interview (and solved it a7l), which stresses how being an ACMer helped me a lot in passing interviews. Actually, that Microsoft interview is broken into four interviews: three in problem solving (= ACM) and one in System Architecture, Analysis and Design.

Anyway, here’s how this problem goes ..

You have a binary tree, not necessarily complete, where each Node holds two pointers (left and right) and a character as an identifier.