Google Interview #2

It's been a few weeks since my first Google interview, and after being contacted by HR I've completed my second phone interview.

Going into the interview, I was slightly concerned that I was going to be interviewed for a different position instead of Site Reliability Engineer (SRE), as the emails from Google HR were a little misleading, having received emails with the subject: "Google: Network Engineer, Google.com"; and "Google: Software Engineer, Google.com".

Thankfully however, they were interviewing me for a SRE position (it seems). That being said, I was also anxious I'd get all the nasty and curly programming related questions about algorithms, btrees and O() notation. Secretly, I was hoping for questions like those I came across when I was first having a look online at interview questions, especially this page.

Luckily for me, the questions were along those lines (some questions almost verbatim from that page in fact). Overall, the interview ran for about 45 minutes and overall I think I fared a lot better than the screening interview.

---

Question: If you were writing a function to see if a given number was a power of two, how would you go about it?
My answer: I'd check if the square root of the number is a whole number that has no decimal component. The boolean condition would look something like:

sqrt( theNumber ) % 1 == 0

In retrospect: This is woefully wrong, I was labouring under the wrong impression as to how roots translate into powers. Having a quick look online, I probably could have mentioned as well that a number that is a power of two only has one set bit in it - so maybe this is intended to be a follow on from the first round of questions (counting the number of set bits in integers).

---

Question: You're trying to set up SSH so you can log in without a password, how do you go about this?
My answer: Run ssh-keygen to generate a keypair (if you don't already have one) and put your public key (found in ~/.ssh/id_rsa.pub or id_dsa.pub) into the target host's authorized_keys file.
In retrospect: I had to giggle when the interviewer asked me the question he asked if I knew what SSH was. I'm a little suprised that people on the second interview wouldn't know what it is, or that they wouldn't know how to do key-based auth in SSH. Oh well.

---

Question: You're trying to unmount a filesystem, but it's telling you that its still in use - what's going on?
My answer: You've still got open filehandles to something under the mounted filesystem's path. Typically (for me) my shell's working directory is still in that path and I've stupidly forgotten to change out first. In other cases, you can tell what file handles are open with the 'lsof' command.

---

Question: You want to rename all the files under the current working directory that end in '.htm' to end in '.html'.
My answer: Do it in a bash one-liner:

for i in `find . | grep ".htm$"`; do mv $i $il; done

Interviewer clarification: Can you think why that might not work?
My answer: Whoops! The shell is going to interpret $il as a variable named 'il', to fix this easily, just put quotes around it so it looks like:

for i in `find . | grep ".htm$"`; do mv $i "$i"l; done

Interviewer clarification: What happens if I have a folder under there called 'blah.htm' when you run that command?
My answer: Whoops again: it's going to rename the folder, to fix that pass an argument to the find command to only return files, and not directories. The command now looks like:

for i in `find -t f . | grep ".htm$"`; do mv $i "$i"l; done

In retrospect: I'm happy with my answer, I should have thought it out a bit before I answered, but I was able to answer all the clarifications off the cuff without thinking too much - so I don't think this was too bad.

---

Question: In Perl, you have two arrays and want to compare their values, how would you go about this?
My answer: I thought there was a builtin that provided this functionality, but couldn't think what it was called. However I said that the easiest way to do it would be to create a hash for each array with the value as the key, and some kind of dummy value. This makes for checking if destination values exist easy. The code I described would have looked like:

#!/usr/bin/perl

use strict;
use warnings;

# Who cares what the actual contents are, this is for an example
@arr1 = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
@arr2 = [ 1, 2, 3, 5, 6, 8, 10 ];

# Create a hash for the first array
$hash1 = {};
foreach( @arr1 ) {
    $hash1->{ $_ } = 1;
}


# Create a hash for the second array
$hash2 = {};
foreach( @arr2 ) {
    $hash2->{ $_ } = 1;
}

# Compare the values
foreach( keys %{ $hash1 } ) {
    if( ! defined( $hash2->{ $_ } ) ) {
        // Generate some kind of output
    }
}

In retrospect: There is no built-in, and this approach was okay. I had only mentioned comparing hash1 to hash2 (what in hash1 is not in hash2), but didn't mention checking hash2 back against hash1 - I don't know whether the interviewer presumed this or anything, but he seemed satisfied I knew what to do - maybe it doesn't matter. I'm quite happy with my answer.

---

Question: You have a script in ~/bin called cd, which outputs your current workind directory, then changes the directory. Why might this script not work?
My answer: It's not going to be in your path, or depending how you've added it to your path, it might be finding the system's cd command first.
Interviewer clarification: It's in my path already, why might it not be working as expected?
My answer: The script could be trying to reference 'cd' which would be executing itself, or maybe it doesn't have the execute bit set for the script.
Interviewer clarification: Okay, I'm running the script and it's outputting the current working directory, but hasn't changed it.
My answer: (after a bit of back and forth) The change of working directory happens in the process spawned for the script, not the parent process - so it's changing directory for the script not the shell. The way to fix this would be to use a bash alias instead.
In retrospect: Kill me now! I don't know why I was thinking why cd was a separate binary! Actually, I had already suggested that I would have done it with a BASH alias to begin with, and had mentioned it another few times - but I didn't put two and two together mentally as to why - which is what he was really looking for. I'm also unsure as to whether he was being deliberately vague so I covered all the steps, or whether I was just missing the angle he was going for.

---

At this point, the interviewer seems generally quite happy with the answers but it seems I'm getting through them too quickly. He says he'll have to ask me some harder questions...

---

Question: You try to run a command, and the shell comes back and says something along the lines of 'no more processes available'. Whats going on?
My answer: You've run out of process IDs. It would normally wrap around and give you an available one, which means you've got as many processes running as the limit - and it's probably something malicious doing this.
Interviewer clarification: How many might that be in a normal circumstance?
My answer: 65535 I think, I'm not sure.
In retrospect: I actually meant 65536 (2^16), but am used to coding where you lose a bit out of the number space for signing. It's actually 32768 (2^15) by default, and can go as high as 4194304 (2^22).

---

Question: Normally, how would you go about killing a process?
My answer: If it wasn't zombified, you could send it a SIGHUP (the default signal sent by kill). That being said, if the process is malicious or zombie'd you could send a different signal with -9 to tell the kernel to kill the process and clean up its memory.
Interviewer clarification: What's the name of that signal?
My answer: I can't remember tbh :)
Interviewer clarification: Can you name any other signals?
My answer: Off the top of my head: USER1; USER2; USER3; USER4 and yeah no I can't really think of any more at the moment.
In retrospect: SIGKILL, it's really not that hard to remember *applies forehead* Also, there are only two 'user' signals, and they're called: SIGUSR1; and SIGUSR2.

---

Question: In the circumstances above, how would you go about getting a process listing.
My answer: You wouldn't be able to spawn any new processes to run commands, so you're limited to functions that are already built into the shell. I can't think of how I'd go about it TBH. There should be an entry somewhere in /proc/ for each process, but I'm not sure where specifically as I haven't had to do that before.

At this point we have a bit of back and forth where he tries to hepl me think it through

My answer: Haha, TAB COMPLETION!!!

Interviewer clarification: Haha clever idea, but not what I'm looking for.

A bit more back and forth where he tries to lead me to a different solution that might let me see directories too.

My answer: You could use flow control with shell expansion, something like the following - however in the case above we're going to have more arguments than you can pass to a command so it's not going to be the best solution.

for i in *; do echo $i; done

In retrospect: Actually, we're not executing a command (and we can't), so this solution would be just fine. I'm a little confused as to whether this is the final answer I gave, but in retrospect its where I was headed. All the back and forth got me a little confused (and it gets better :P).

---

Question: So how do you kill the process in the above circumstance?
My answer: I'm not sure, suprisingly I haven't had to do this before.
In retrospect:

---

Question: Okay, assume we've successfully killed all the processes, you try to run a command and it comes back with the same error as originally: 'no more processes available'. What's happened?
My answer: Whilst going through killing processes, the ones later down the queue to get killed have probably spawned their own children.
In retrospect: How would you deal with this?
My answer: I'm not really sure.
In retrospect: What happens when you background a process? Is there a mechanism for pausing a process?
My answer: Oh, duh. You can sleep it, but I don't know the mechanism for doing this - probably also via /proc.

---

Aaaaand, that's all folks. My knowledge of dealing with stuff in /proc let me down but otherwise I felt the questions were answered either adequately, or I covered all the relevant gotchas surrounding each problem - hopefully this demonstrates I understand what's going on.

The interviewer indicated as much, saying I got 99% of the questions right but anywhere I fell down I ticked all the boxes and mentioned all the critical considerations. He also said he had little doubt that I'd proceed onto the next round of interviews (though they would only get harder), and that I should hear from them within the week.

All in all, I'm happy and feeling quite a bit more confident for Round#3 - although I think I might need to study up and actually prepare for this round. Also I think this next round is where I start not being able to talk about things and have to sign an NDA - so this may be my last post on the subject.

I'll let you all know if I fail miserably :P