Two interviews with Google

As I have already said, I had two interviews with Google. Both of the interviews were conducted over the phone (they called me both times). The first interview was with the recruiter and was mostly about my resume and possibilities of me moving to Dublin, Ireland. There was a small technical test too. The second interview was fully technical and lasted for about 45 minutes.

Since many of you asked for details and since I didn’t sign or promise any confidentiality to Google over these and since I don’t think there was anything that shouldn’t be released to the public, I am posting more details about both of the interviews below.

First interview.

As I said, the first interview was with the recruiter. She was mostly clearing up a few points of my resume. For instance, I am still doing my Bachelor in Computer Science and I am short of three courses to finish it. The soonest I can take these courses is the semester of Fall 2006. The recruiter was wondering what would happen if I would be hired by Google earlier than I could finish my degree. I said that it would bother me at all. I can always postpone the study (as I am already doing for the last few years), or take the courses in another college or university or do something else. My options are open. That seemed like a satisfying answer. And I don’t think there were any interesting non-technical parts in that interview.

The technical test included just a few questions. Here they are (quoted from memory) with the answers. I appologize in advance for messing up with the order and forgetting and misquoting things.

Q: In native UNIX file system, what are the three timestamps associated with every file?
A: That’s an easy one. The three timestamps are access time (atime), modification time (mtime), and change time (ctime).

Q: Could you, please, explain in more detail what are access time, modification time, and change time?
A: That’s another easy one. Access time shows when the file was last accessed, or read. Modification time shows when was the file last modified (written to or created), and change time shows when was the last time file properties were changed, including the modification and access time (like it can be done by touch utility or backup/restore software).

Q: Could you rate the speed of these three operations: read from register, read from RAM, and disk seek operation? Which one is the fastest and which one is the slowest?
A: Reading from the register is the fastest and disk seek operation is the slowest.

Q: Here is a question from the networking area. How many hosts can be in /19 network?
A: Ouch. That hurts. I am not that good with networks in general, with subnet masks in particular, and with calculating odd numbers in my head in a very particular. Let’s see… (Here I started to talk numbers, count my fingers and let a lot of non-sense out of my mouth)
Q: Let me rephrase this. You don’t have to give an exact number. Just the formula would be good enough. How would you go about solving this problem?
A: Well, the network mask is a 32 bit number. /19 means that the first 19 bits of the network mask are set, which means that the rest of the bits are left for the host addressing. Since the the bits can have only two values (true and false), the formula would go something like: 2 to the power of 32 minus two to the power of 19…
Q: OK, good. Do you have to subtract anything from this?
A: Oh, yeah, sure. I forgot. There are two addresses that go for network address and for broadcast. So the final formula would be: 2^32 – 2^19 – 2 = number of hosts in /19 network.

As far as I remember, these are all. I have to say that the lady was very helpful and understanding. It was obvious that she wasn’t a technical person herself, but she had a good set of answers and helping questions in front of her and was matching my answers onto the predefined ones pretty easily.

She also asked me to do self-evaluation. Basically, I had to grade myself in a few areas, like shell programming, perl programming, pythong programming, UNIX system administration, Linux system administration, TCP/IP networking, SQL, and some others. I could use any grade from 0 to 10. She also explained that 0 meant no experience or knowledge what-so-ever, while 10 was for reserved for those who wrote a book on the subject.

After I did the evalution, she explained that she will send my resume, my answers, and my self-evaluation to the technical department and that if they will be interested, I will hear from them within a week. She also told me that I could be asked in-depth questions in areas like TCP/IP networking, UNIX and Linux system administration, shell and perl programming, SQL databases, algorithms (quicksort), etc. She gave me a broad list of topics that pretty much covers everything in Computer Science.

Three or four days later I received an email that asked me if I was comfortable with suggested date and time for the technical interview. I confirmed.

Second interview

If I’d been any smarter, I would have prepared myself for the second interview. There are plenty of resource on the web, as well as on my bookshelves that I could use to refresh my memory. But I didn’t. It could have helped or it couldn’t have helped. I don’t know.

Anyway, for the second interview this guy called me. He said that he speaks fluent Russian, but that interview has to be conducted in English, but I could switch to Russian if I had a problem understanding the question. I promised that it would be necessary as my technical Russian is much worse than my technical English.

Than I was asked not to use any computer, mobile, or gadget to find answers for the questions. I said that it was OK with me, non-the-less it maid me a bit more worried than I was. He also said that he would be taking notes on his notebook and that the interview on his end will be over the speakerphone. He warned me that someone else might walk in and listen to the interview and ask questions and that he would let me know if that will be the case.

The interview started with a couple of general questions like “How do you understand the position that you are applying to?” and “What have you been busy with recently?”. Those were just a warm-up questions to get used to the accents and get a better understanding of my area of expertise.

Below are the tecnical questions that I could remember (not necessarily in order) and the answer to those questions. Also, I have to say that this interview more like a talk rather than like a strict question-answer dialogue. Questions were flowing out of the previous answers and so and so forth.

Q: Are you familiar with the concept of hardlinks and softlinks (symlinks)? If so, what are the major differences between them, and what are the considerations for using one over another?
A: Yes, I am familiar. Let’s see… Hmm.. The main difference between them is that hardlinks are limited to the filesystem/partition, while the symlinks are not. That would be also the main consideration for using one over another.
Q: Could you give an example of when you would use one and not the other? Or maybe some usual usage of one and another?
A: Hmm. Well, I’ve seen hardlinks mostly in the chroot environments. Symlinks are everywhere else. Also, if I remember correctly, there is a difference when backing up a filesystem. Backup of the hardlink would be the size of the file, while with the symlink only the link itself would be backed up.
Q: Good. But can you tell me a bit more specifically how they are implemented in the kernel/filesystem? Why would the link hardlinks from chroot environment not work?
A: Hmm.. nope. I didn’t dig that deep into it, and if I did, I don’t remember.

Q: Ok, no problem. And how would you see if the file is a hardlink or a softlink?
A: Well, the directory listing should show it, and probably the stat command on the file.
Q: And how would you see the links in the directory listing?
A: I would have to do a long list (ls -l) and the first letter in the permissions will be l for link. Also, the filename will have the name of the link, than the arrow and the name of the file where the link is pointing. Something like that?
Q: I believe that it would show the symlinks like this. But how would I see the hardlinks?
A: Probably there is some parameter to ls that forces it to show the hardlinks…

Here, of course, the guy was trying to help me, but I had this burried too deep in my head. All files are hardlinks. That’s it. There is no difference between a regular file and a hardlink. It’s the same thing. Linking is done directly to the inode. If you remove the original file, the symlink will get broken. The hardlink won’t. It will even have all the data. So, I blew it.

Q: Many UNIX systems have the command to kill the process. It’s kill. Are you familiar with this command? Can you tell me how it works?
A: Yes. kill is the command that sends a signal to a process. If no signal is specified, than, if I remember correctly, SIGTERM is sent by default.
Q: Ok, good. What are other signals that could be sent with kill command?
A: Well, there are a few. SIGTERM, SIGKILL, SIGHUP, SIGUSR1, SIGUSR2…

Q: What is the difference between SIGTERM and SIGKILL signals?
A: Well, the programmer while writing software can implement signal handlers. SIGTERM is usually caught by the program to shutdown correctly, closing any files and connections it might have open, saving data, etc. SIGKILL, on the other hand, cannot be handled. It is passed directly to the operating system and kills the process.

Q: Earlier you mentioned that there are several signals available. How would you see the list of available signals on the system?
A: I believe kill has a command line argument that displays the list of signals…
Q: Do you remember which one that would be?
A: I guess -l.
Q: Suppose, the kill implementation that you are dealing with does not have this option. Where would you find the list of signals?
A: In the manual (man kill).
Q: And if the machine that you are working on does not have any manuals installed. And you don’t have any other machine handy. And you don’t have internet connection. Than?
A: Info pages come to mind. Source code too.

Q: In your self-evalution you graded yourself as pretty good with shell. And from your resume and experience I see that you are mostly familiar with Bourne shell (bash). Would you be comfortable writing a short shell script for me?
A: Yes, sure. May I use a piece of paper or something?
Q: Yes, of course. Grab the paper and the pen. Here is the task. You have a directory structure that you have to go through recursively and rename all .html files into .htm. How would you do it with shell?
A: There are several ways, of course. The one that comes to mind is this one: rename .html .htm `find . -iname *.html` (I actually dictated the code over the phone).
Q: Ok. Suppose that you have a system that does not have rename utility. How would you change your code?
A: Well, I would have to use mv to move files. There are several ways to go about obtaining the new filename from the old one. My favourite one is by using basename. The new code would something like this: find . -iname *.html -exec 'mv {} `basename {} .html`.htm \;. If there is no basename command available sed could be used alternatively or some other text preprocessor.

(Here we talked about different implementations of programs on different systems, mentioned GNU, and talked about how shell actually executes commands).

Q: Here is a scenario. You have host A with disk A and host B with disk B. You have to move data from host A disk A to host B disk B. Don’t think of this data as any filesystem, more like a dump or inactive database. How would you do it?
A: Well, if there is no filesystem, I can do a lower level dump with dd utility. Than I can use a number of protocols to move it – ftp, scp, rsync – and than I could use the same dd utility to write the data on to the disk.
Q: Ok. And how would you verify that the data was copied correctly?
A: I could use an md5 hash to generate a checksum of data on both disks. It would be obvious then if any errors were made.
Q: Imagine now that there is not enough disk space to make a dump of data. Say, there is 200 GBytes of data on a 300 GByte disk. How would you go about it?
A: Well, I could tell dd to read data from disk and copy it into a pipe, than use netcat to copy data over the network, and than netcat on another machine to write into pipe, where dd would get it from and write onto disk.
Q: Could you tell me the actual command line for this process?
A: It would be something like this: on host A dd if=diskA bs=1024000 | nc hostB 40000 (I would use bs option to get bigger blocks of data from a fast media to speed up the process) and on host B: nc -l 40000 | dd of=diskB. I don’t exactly the options of netcat utility, but with computer in my hands I could easily find out. -l forces netcat to listen, if I remember correctly. Port 40000 was chosen randomly, if it is used by another application, I could use any other.

Q: Ok. Now, I think that generating an md5 hash for all that data of 200 GBytes would take a long time. How would you propose to shorten this time?
A: Well, either do not check all data or use a simplier/faster algorithm. I could check only, say, few megabytes in the beginning, few megabytes in some random locations, and few megabytes in the end. Alternatively, I could use a CRC32 or something like that to check all the data.

(We talked here about the few algorithms and ways to verify the data.)

Q: Let’s move on to networking. The utility, I am sure, you are familiar with and use regularly – traceroute. Can you tell me what for is it used, what is its output, and how it works?
A: I mostly used it to troubleshoot network problems. The output shows a number of hops that the packet from source to destination travels through and the times it takes to travel the packet from one hop to another.
Q: OK. Can you tell me how it works?
A: Well, I never had to actually dig into it. All I know that it uses ICMP protocol.
Q: Can you tell me what request it sends and what reply does it expects?
A: No, not really.

Here I had to say a few words about echo request and echo reply and TTL, but I was too stressed to remember and few bits I didn’t know anyway (found out them later on).

Also, I forgot to mention, that somewhere in the middle another guy walked in and listened to the interview, but he didn’t ask me any questions at all.

As far as I remember, these are all. He than told me that he will write a report on this interview based on the notes on his notebook and will send it to the recruiting department. And that I should here again from the recruiter I talked to earlier within the next 7 days.

That’s about it. Even if I forgot and messed up a few things, I guess this post draws a good picture of what I went through. If I will remember anything important, I will update this post. Overall I have to say that both interviews were handled very professionally. I expected professionalism, but I received much more of what I was expecting. Both interviewers were well-spoken, polite, comforting, and understanding. They clearly explained the plan of actions before and after interviews, encouraged me while I was answering, helped a bit on the way, and thanked for interest in Google too many times.

Here you go…