Google Phone Interview(2nd round)

Just finished my interview with Google. This time is an engineer, asking lots of detailed questions.

He knows a lot about lisp, so we just discuss about the issues about lisp. like
what's the difference of lisp and other languages?
which kind of lisp complier do you use? emacs lisp vs. clisp?

Then, some questions about operating system?
What's the difference between process and thread? What kind of information does thread maintain? its own stack? heap?
How and when to do a context switch? How do you handle an time slice interrupt?
What are the possible pitfalls for multi-thread programming?

How compiler works?
Can regular expression resolve the problem of nested structures?
Tell me something about grammar?
Is type check done before or after parsing?
(I did pretty bad in this session, so he finally stopped)

Familiar with TCP/IP, RPC, network programming? (NO, skipped)

Are you familiar with B-tree, red-black tree? (No, so we switch to binary search tree)
What's the time complexity of insertion or query in a binary search tree? O(lg n)
Worst case? (O (n))
How to transform a unbalanced tree into balanced tree?
Are you familiar with TreeMap in Java?

How hash table works? What if two object have the same key value? Show me one example of hash function.
What is the innate structure of a hashtable? (I said array) How do you map a key value to an index?

Finally, one technical question:
Given a source word, a target word, and a dictionary, how to transform the source word into target word by changing only one letter in each step. The word you get in each step must be in the dictionary.

Then, I asked him about some projects details.