I was referred to Facebook by a friend who works there and was contacted by HR about a week later. We set up a 45-minute technical phone interview which was to be held a week and a half later.
For the actual interview, I was first asked a couple of generic questions about myself and Facebook before moving on to the technical questions. There were two programming questions.
For the first question, I first described what my algorithm would be, then discussed time and space complexity before finally implementing it. My interviewer didn't have anything to say about my answer and we simply moved on.
I took the same basic approach to the second question; described my algorithm, discussed space/time complexity, and then implemented it. However, after discussing the space and time complexity for my potential solution, my interviewer asked me if I saw any draw-backs to my algorithm. I told him that it used a lot of extra space, and he asked if I could think of a more efficient (space-wise) solution. I thought about it for a while but blanked out. He then suggested I just go ahead and implement my algorithm.
The last 5 or so minutes of the 45 minute interview were devoted to me asking questions. I asked a few, and the interview was over.
I received a generic rejection email 3 days later.

1. Why are you Interested in Facebook?
2. What is your favorite feature of Facebook? Then as follow ups, what would you change about this feature, and what could be a drawback of this change?
3. Given "data", "from", and "to" fields, replaces all occurrences of the characters in the "from" field in the "data" field, with their counterparts in the "to" field.
Data: "Hello World"
From: "lod"
To: "xpf"
"Hexxp Wprxf"
4. Create an iterator class for a tree. The iterator should traverse the tree using in order traversal. Implement the constructor and next functions.