# FB Interview Experience Part 3: On-Site Interviews

This is my final post in my facebook interview series. This comes after:

My final on-site interviews were scheduled on the 9th October in the London Office on something people at facebook call “University Day”. Its mostly a day for interviewing undergrads or people who have just finished their undergrad.

**Disclaimer:** I’m not sure if I’m allowed to reveal the interview questions but I
will put them here and remove them later on if necessary.

# Preparation

From what I had read online, I knew that the Software Developer Role had 3 on-site interviews of 45 minutes each:

- Behavioural
- Algorithmic
- System Design

I hadn’t prepared anything specific for the behavioural interview.

I spent the majority of the time preparing for the algorithmic interview as it is by far my weakest point. I’m a developer who likes to develop things and I do have knowledge of data structures and algorithms but I usually look them up when needed and sometimes even solutions to simple algorithmic problems don’t come easily to me. (I practised from leetcode, hackerrank and Elements of Programming Interviews)

For the system design interview, I had taken a look at some sample problems online and had decided that I would take a closer look at them at a later stage as they seemed to be the kind of problems I enjoy solving and would be able to grasp the idea easily.

Later on (I don’t remember exactly when), I took a closer look at my interview confirmation mail and got to know that since I’m an undergrad, instead of the system design interview I would have another algorithmic interview (bummer!).

# On-Site

I reached the venue at the specified time and there were a total of 7 people who were interviewing that day. There were people who were still doing their undergraduate (like me) and others who had just finished in May and had recently joined some other company. We were welcomed by the wonderful recruiting team and then after a few introductions, were given a schedule of the interviews. I had the interviews in the following order:

- Behavioural
- Algorithmic 1
- Algorithmic 2

## Behavioural Interview

The initial 20-30 minutes were discussions on my past experience - stuff like explaining any project I had done, my particular role, why I chose to explain that particular project now, issues I might have faced while working under someone, while mentoring someone and so on. Some examples of the type of questions asked are available at the following link.

After that, we had time for a simple algorithmic problem as well which I was supposed to solve on a whiteboard. The problem was as follows:

```
You have a svn repository and are writing a tool. What algorithm would you use to
implement svn bisect. svn bisect works as follows:
Suppose we know for a fact that there was no bug at commit A but there is a bug
in the current Head of the repository. Given a test command (which checks if the
bug is present or not), svn bisect should be able to report the exact commit
where the bug was introduced.
Assume you have a function test(commit) which returns whether the bug is present
or not in a commit. You are supposed to implement:
bisect(start_commit, end_commit)
```

This was a pretty simple problem (hint: binary search) and I was able to solve it quickly. First I verbally explained my solution and then implemented it on the whiteboard.

## Algorithmic Interview 1

This was one of the interviews I think I messed up in. Usually in 45 minute interviews, you have 2 problems which are usually solved in the timeframe and then if there is extra time remaining, you get another question on which usually a discussion is just started. I solved the first (easy) question and then got stuck on the 2nd one. Even when I managed to solve it, the solution wasn’t optimal. But, somehow, even though very little time was left, I managed to atleast verbally/diagrammatically on the whiteboard, solve the last one.

The first question was the following:

```
Given two strings A and B. You have to report whether B only uses at max as many
alphabets as those present in A (No. of occurrences of character x in A >= No.
of occurrences of character x in B). For example:
A: abracadabra
B: caadab
Valid
A: abracadabra
B caaddab
Invalid
```

This was a pretty simple problem and I solved it nearly immediately. The code for it also did not take too much time.

The second question was the following:

```
You are given a calendar having `n` days. Entry corresponding to each day is
either 0 or 1. 1 represents a holiday while 0 represents a working day. You also
have `k` vacation days available from the company. What is the maximum possible
length of a vacation you can go on?
Example:
n=15, k=3
001001010001011
Answer = 6
Either
001111110001011
^^^^^^
or
001001010111111
^^^^^^
```

I initially wasn’t able to think of any solution and ended up explaining the brute force
solution (my fallback when I’m unable to think of anything). Even after further discussions
and hints from my interviewer, I arrived at a `O(nk)`

solution even though the optimal
solution would be `O(n)`

. I ultimately wrote this non-optimal solution on the whiteboard.

The third question was the following:

```
Suppose there is a 2D world. The buildings in this world can be represented by a
histogram:
__
| | __
__ | | | |
| | | |__| |
| | | | | |
| |__| | | |
___|__|__|__|__|__|___
You are provided an array of (width,height) tuple for each building:
[(1,4), (1,1), (1,6), (1,3), (1,5)] in the case above.
Suppose it is raining in this 2D world. Naturally, water will accumulate as follows:
Rain
||||||||||||||||||||||
vvvvvvvvvvvvvvvvvvvvvv
__
| | __
__ | |░░| |
| |░░| |░░| |
| |░░| | | |
| |░░| | | |
___|__|__|__|__|__|___
Area collected in this case = 5
Given an array of (width,height) tuple for each building, calculate the area of
water which would accumulate
```

This is a pretty nice question and I managed a `O(n)`

solution using just stacks.
We ran out of time before I could write down the whole solution but I managed to
logically explain my idea.

## Algorithmic Interview 2

This third interview also went pretty well. We managed to finish 10 minutes before time.
After I solved each question, the interviewer asked what test cases would you pass to
make this program break and also while solving he asked me to do proper edge case handling
via `throw`

s.

The first question was pretty simple:

```
Given a pattern of open/closed parentheses, find the maximum open depth reached
at any instance.
For example:
((()())) - 3
()()()() - 1
(((()))) - 4
(())()() - 2
```

I also had to handle the edge case where there was an illegal sequence of balanced parentheses. Once I was done with the above (explaining idea + code), the question was modified to:

```
Given a pattern of open/closed brackets - any one of `(`, `)`, `{`, `}`, `[`, ']',
find the maximum open depth reached at any instance.
```

Similarly, I had to solve for this as well. I was able to explain the idea for both variants as soon as the question was posed.

The 2nd question was the following:

```
Given any integer value, you have to report the next lowest value possible by
permuting its constituent digits.
Example:
4231 -> 4213 -> 4132 -> 4123 -> 3421 -> 3412 -> 3241 -> 3214 -> 3142 -> 3124 ->
2431 -> 2413 -> 2341 -> 2314 -> 2143 -> 2134 -> 1432 -> 1423 -> 1342 -> 1324 ->
1243 -> 1234 -> Not Possible
```

For this question, I was stuck for some time but once I was given a hint - to think on what algorithm I was mentally applying to achieve this series, I managed to solve it and write a pretty elegant solution, if I might say so. Again, I had to handle the edge case where there was no next permutation possible.

Later on, when I was asked for test cases, I had to mention the test case corresponding
to `0`

occurring. For example, the code I had written would behave like this `1023 -> 321`

.
But as per my interviewer, this shouldn’t be allowed. My code was structured good
enough for me to make a single line change and add a `throw`

at some spot to handle this.

## Post Interview

After the interviews, we were given an explaination of how the interviews were reviewed and then we were taken on the tour of the office (spoiler alert: its awesome!!) and that was it. The whole interview process was now done.

I was eventually contacted and informed that I would be extended a full-time offer at the London Office. Right now, I have accepted the offer and am really looking forward to joining there in August this year. Its going to be an amazing experience and I really hope I’ll learn a lot from it.