Enter – the Facebook call
Me – Software Engineer with 15 years of experience in anything from AT&T / C++ to iOs development ( last 8 years ). Had my own startup, worked with Kardashians on their mobile app, married + 2 and a dog, mortgage and everything around it.
One sunny / cloudy April day, I got an email and later a phone call from Facebook ( Yes, the last company I ever thought I would be a part of, yeah, I have Facebook account and use it sometimes and I have done some Facebook integrations here and there but nothing serious or deep )
Well, one April morning I took a call from a very nice person at Facebook who explained to me what are they doing, who are they looking for, what is their hiring process and what are my options to work on if and when I get accepted. She also tested me on 5 questions about Obj-C which I got 4 out of 5 correctly which got me into the next round ( 3 total ).
10 minutes after we’ve finished our phone conversation I got an email from her with the process of hiring and what I should be preparing for as well as resources for learning the material.
What to expect on the day:
The interview will be approximately 45min long.
Be prepared for technical questions involving coding algorithms and data structures, design patterns in Objective-C, runtime complexity and iOS API’s.
It may also help to review core CS concepts as well as subjects pertaining to the scale of our environment.
For coding questions, you will be asked to produce clean, compilable, efficient code in a reasonable amount of time.
A few helpful hints:
Think out loud if you are working through a solution you are presented with as the engineer will want to know how you approach and troubleshoot problems.
If the interviewer gives you hints to improve your code, take them and run with them. It is good to adjust and work through the problems with the interviewer to show your thought process and problem solving ability.
The engineer will also want to ascertain your level of interest in the role. Have some questions prepared, for example, what is involved in the role, day to day tasks, what is the most exciting project they have worked on in Facebook etc.
Please research recent news online for talking points and more information about Facebook.
Be able to articulate a deep, thorough understanding of iOS memory management, ARC, etc.
Some Topics & things to Consider:
Data Structures: Arrays and lists (critical), Binary trees (critical), Hash tables (critical), Stacks and queues (critical), Graphs (critical), Trie (nice to have), Heap (nice to have), Set (nice to have), Red-black trees (nice to have).
Algorithms/CS Concepts: Search (iterator, binary, hash – all critical), Sort (merge, quick, bucket – all critical), Graph traversals (BFS, DFS – all critical), Complexity and big O notation (critical), Recursion (critical), Randomized quicksort (nice to have), Heap sort (nice to have), Radix sort (nice to have), Spanning tree and minimum cut (nice to have).
Objective-C Knowledge: Look through Mike Ash’s blog and NSHipster. Additionally, make sure you can explain memory management (different types), usage of different Foundation collections, threading and Thread safety.
Don’t worry about rote memorization such as runtimes or API/native calls. It’s always good to know how to figure out approximate runtimes on the fly but the code you write is more important.
Generally avoid solutions that would have lots of edge cases or huge if/elseif/… blocks. Most coding interview questions at most places are designed with semi-elegant solutions so try to identify patterns. Deciding between iteration and recursion is always an important step.
You may be asked in the interview to explain a technically challenging problem you have worked on in the past. Think about and explain how the problem was technically challenging.
Facebook preparation links:
• What to Expect During the Recruiting Process
• How to Crush Your Coding Interview
• Facebook Mobile Engineer blog post on his process
• Algorithm Tutorials
• Glassdoor Interview Questions
A few coding samples:
• Cracking the Coding Interview
• Big O Cheat Sheet
• Career Cup
• Code Chef
• Project Euler
• Geeks for Geeks
A few Facebook Links:
• Facebook on iOS: Inside the “Big Blue App”
• Timed releases for mobile apps
• Get that job at Facebook
• Facebook Bootcamp
• Engineering notes
• Facebook News Room
15 minutes after our phone call while reading all the material she sent, I came to realize just how much preparation will I have to do if I want to get anywhere near the second interview.
Before I spend time / money and energy I wanted to see what’s all the fuss was about so I went and watched Building Paper video ( an hour and a half long ). That was the first time EVER I’ve gotten through tech video without getting up from my chair, this was by far illuminating, innovating, inspiring and all other fancy words that I could think of at that moment. in hour and a half I learned about 5 brand new to me open source libraries for iOs, I learned that people in Facebook can move from any team to any team even if you spent your whole life doing backend, you can get into Mobile UI team and vice versa.
So, about half way through a video, I hit a pause button and wrote the following email back to the Facebook recruiter:
Hi <Awesome Facebook recruiter>,
thank you so much for all the information, that was literally a “Red Bull” of conversations / interviews and I’m very excited about this opportunity!
I would like to take time to prepare by taking Gayle’s classes and going over all the material that you’ve sent me.
Would that be ok if I gave you my availability dates for the next interview round after I’ve done my “homework”?
Facebook policy allows scheduling interviews anywhere between 2 days and 2 months so I figured it should give me some time to get ready.
Next thing I’ve done is :
And so the preparations begin…
As I started going over the basics, I gradually ended up doing some basic math, remembering what log(n) means, what is Big-O, and what the hell is “Red-Black Trees” ( I know, I wasn’t even aware of such trees.
I’ll try to state ALL the resources that I’ve found useful in my prep in this post.
- Trie ( not a typo ) “thanks” to Edward Fredkin
- Basic Illustration I found to be VERY useful
- Big-O ( big what now?! )
Divide and conquer algorithms usually have a
log n component to the running time. This comes from the repeated halving of the input.In the case of
binary search, every
iteration you throw away half of the input. It should be noted that in
Big-O notation, log is log base
Basically it’s a fancy way of saying that any search algorithm that splits by half every search iteration will have a time complexity of O(log n)
Example ( obj-c) :
AKA Fibonacci series
return [self fibo:n-1] + [self fibo:n-1];
What would be the runtime complexity here?
Obvious ( to some people ) answer would be O(n²) = WRONG
lets plant a tree, shall we...
few things here...
a) we do not go down the tree from both leaves simultaneously,
rather we go down on one branch-> then go back up and then go
down the second branch.
b) the bigger the input number N the deeper the tree is.
Which brings us to the time complexity ( the Big-O ).
we are going to run as many as the number of nodes in the tree
which we can set as 'A'. Each level doubles the number of
leaves ( nodes ) on the branch => 2ª => O(2ª) is the runtime
of the fibonacci series.
Basically – any search algorithm that divides
Upper and lower bounds on the complexity of problems
T(n) = Upper bound. For example assume the following algorithm, T(n) = 7n2 + 15n + 40, in big O notation one would write T(n) = O(n2) because by definition in Big-O notation we hide constant factors and smaller terms such as O(7n) becomes O(n).
Analysis of algorithms
Data Structure and other animals…
- Graphs – A graph is a structure consisting of a set of arrays (also called dimensions) and a set of edges
- Graphs memory optimization take O(n2) space.
- Graphs search time complexity is also O(n2)
- Graphs types are :
- Directed – UniDirectional, connecting 2 vertices ( nodes ) where the flow direction travels only one way.
- Undirected – well, the exact opposite of “Directed” , flow travels both ways between each vertical ( node )
- Question : given a set of n nodes and m edges where the graph was represented by an adjacency list, why insertVertex would take O(1) and deleteVertex would take O(m).
- Solution: It takes O(1) time to append a node to a linked list. And it takes O(n) time to delete an item.a) Why insertVertex is O(1)?Inserting a vertex is just appending a node to a linked list (O(1)) or 2 if the graph is undirected.b) Why deleteVertex is O(m)?Deleting a vertex means:1) Delete a linked list (O(1))2) In the worst case you will have to remove the vertex from all the linked lists: O(m). It’s O(m) cause the number of nodes in all the linked lists is m, or 2*m if the graph is undirected.
- Following up on that question I had to look up terms “adjacency list” & “adjacency matrix”.
- Adjacency list – is a collection of unordered lists used to represent a finite graph.
|The graph pictured above has this adjacency list representation:
Example of graph usage ( Facebook of course what else… )
This social network is a graph. The names are the vertices of the graph. (If you’re talking about just one of the vertices, it’s a vertex.) Each line is an edge, connecting two vertices. We denote an edge connecting vertices
vv by the pair
(u,v)(u,v). Because the “know each other” relationship goes both ways, this graph is undirected. An undirected edge
(u,v)(u,v) is the same as
(v,u)(v,u) (Directed graphs, in which relationships between vertices don’t necessarily go both ways. ) In an undirected graph, an edge between two vertices, such as the edge between Audrey and Gayle, is incident on the two vertices, and we say that the vertices connected by an edge are adjacent orneighbors. The number of edges incident on a vertex is the degree of the vertex. ( source – Khan Academy )
- Assign, weak, strong, unsafe_unretained etc….
Strong reference (which you will use in most cases) means that you want to “own” the object you are referencing with this property/variable. The compiler will take care that any object that you assign to this property will not be destroyed as long as you point to it with a strong reference. Only once you set the property to
nil will the object get destroyed (unless one or more other objects also hold a strong reference to it).
Weak reference you signify that you don’t want to have control over the object’s lifetime. The object you are referencing weakly only lives on because at least one other object holds a strong reference to it. Once that is no longer the case, the object gets destroyed and your weak property will automatically get set to
nil. The most frequent use cases of weak references in iOS are:
- delegate properties, which are often referenced weakly to avoid retain cycles, and
- subviews/controls of a view controller’s main view because those views are already strongly held by the main view.
atomic vs. nonatomic refers to the thread safety of the getter and setter methods that the compiler synthesizes for the property.
Atomic (the default) tells the compiler to make the accessor methods thread-safe (by adding a lock before an ivar is accessed).
Nonatomic does the opposite. The advantage of nonatomic is slightly higher performance.
On iOS, Apple uses nonatomic for almost all their properties so the general advice is for you to do the same
- Ok, listened for 2 hours for Gayle Mcdowell talking about how to prepare for Facebook interview. She had a lot of good pointers and raised a few questions:
- I for one, take time to develop any algorithm or to solve the problem, why they expect me to do so in under 10 minutes?
- After 15 years of software engineering, I went over the material she was presenting and I figured I used about 5% of it to develop real life solutions, systems, applications etc…
- Here is the Power Point from the lecture about Facebook for you to decide guys
Ok, Facebook or not, a week and a half later I can definitely say that I’m smarter than I used to be a week ago which only comes to show how much work one needs to be doing to stay no top of things without letting the “experience” to get in the way. I still have long way to go but at least I’m there and hopefully regardless if this Facebook position happens or not I’ll make sure from now on to keep going back to basics and practicing practicing practicing!
I’m going to publish a list of puzzles that I’m solving at least once a day which are programming language agnostic and are good practice for any level of software engineer.
Gayle Laakmann McDowell’s
Cracking the Coding Interview Challenges is now available to all at the following link: