Expedia questions

I'm making this blog just to remember all the questions that I had during different interviews.
I'm like a collector - I'll post not only my questions but also my friends ones and I believe that if you just sit down and solve some of the problems that I published here you'll be prepared for a software interview.
Questions from Expedia:
On the phone - describe how are you going to design a system that serves 2 elevators (elevator algorithm). Basically you have 2 elevators in an 18 floor building and you need some program that manages them - how will this program look like, describe in details all the classes and objects that you are going to use or implement. Smart question - capture all your OOP skills + the way you are thinking.
The real interview:
First guy asked me to implement a routine that has 2 parameters - string base and string needle and returns the index of the last appearance of the needle in the base:
Int32 LastIndexOf(String base, String needle)
And because we had some time he asked me to solve the riddle about 2 dice and presenting the days of a month with them - basically you have 2 six side dice and you need to put on every side just one number (numbers are 0-9) in such an order that you can represent every day of a month - 01, 02...31. It has a trick in it that I couldn't think of at the time:) But he was happy with my prove that is not possible:) Don't be mislead - it's possible it's just require some unusual glimpse at the problem.
The second one presented me with a binary unordered tree and asked me to find the closest number to a given one in that tree.
Afterwards he asked what if it wasn't a tree but an array or list - how can I change my routine - he basically force me to implement everything with collection and Iterator/Enumerator.
The third one was a sql guy and he asked me to write a store procedure. You have a self reference table - EmployerId, Name, ManagerId where the managerId is pointing to the employerId and he wanted the store procedure to print the name of the employer and the name of the manager.
He asked me about transactions, what is primary key, foreign key in the database, how they are implemented, what is the 3 normal form, is it always useful and why not, etc - all database stuff.
The fourth one asked me to print all the substring of a given string (combinatorial question). For example if you have the string "abc" you need to print "", "a", "b', "c", "ab", "ac", "bc", "abc". I ended up writing an iteratively solution.
The fifth one was a web developer and basically draw me a web site on the board and asked me to write the html and java script for it. It was funny - to write html on the white board:) So basically the web page has 2 edit boxes - hours and minutes where you can input numbers between 1 and 12 and a button . When you click the button next to it he wanted to see a number. This number represents the angle between the hands in the clock that you just inputted:)
He wanted to see how I'll do the javascript and if I can write the html from scratch.
The end.