Algorithms and Data Structures Interview Preparation & Walkthrough — Part 1
Many of new graduates want to knock on the doors of big companies in Silicon Valley such as Facebook, Amazon, Apple, Netflix, Google and Microsoft. However, preparing for a technical interview is a long and tiresome process. I, myself is also a SW engineer, been there, done that, but still, at some days I will need to face the process again. So I decided to write some articles to remind myself (and you) to get through the process as smooth as possible.
Useful Resources
Algorithms, Part 1 and Algorithms, Part 2 are two of the most famous free online courses for Algorithms in case you want to refresh your memory.
There are two other books I would recommend anyone who is preparing technical interviews to read:
- Elements Programming Interviews, by Adnan Aziz which has 300+ programming questions and solutions, and it comes with a CD for electronic copy of questions and solutions you can practice with your IDE.
- Cracking The Code Interview, by Gayle Laakmann McDowell which also has plenty of programming questions and solutions.
Prereq — Complexity Time and Space
Before we dive into some basic data structures, I want to talk about another basic prerequisite —Complexity Analysis.
It’s important to understand the time complexity of method calls, especially ones that perform operations with data structures. But why do we care? When you start to work in Industry, complexity analysis would help you solve scalability issue beforehand, make better decisions, figure out efficiency & tradeoffs, choose which data structure(s) to use for your project, then find the optimal solutions. Most of all, it’s a common interview topic.
When it comes to Space Complexity, we are talking about Auxiliary Space vs Space Complexity. Auxiliary Space is the extra memory required to perform an algorithm. Space complexity is the memory required to execute an algorithm which includes both input size as well as auxiliary space. When you are asked to do space complexity analysis, usually people are asking about Auxiliary Space (without taking the input size into account). However, it’s your responsibility to ask if the interviewer is interested in the input size as well.
A quick example to discuss Time Complexity and Space Complexity:
function printAndSaveAllNames(array) { // Input size n
// instantiate an empty array, constant space size
var result = [];
// instantiate a counter, constant space size
for(var i =0; i < array.length; i++) {
// push n items into the array, linear space size, linear time
result.push("Name: " + array[i]);
}
}
// Time: n * 1 = n, Linear time complexity: O(n)
// Auxiliary space : n + 2,
// Space complexity = input + auxiliary space = n + n + 2 = 2n + 2
// Drop coefficients and lower order terms ...
// Linear space complexity: O(n)Common Big-O Orders (and examples)
For Asymptotic Notations, we use Big-O as upper bound, Big-Ω (omega) as lower bound, and Big-Θ (theta) as tight bound.
● Constant O(1) — Independent to input size
○ Lookup a key in a hash
○ Arithmetic calculation
○ Assigning a value
○ Updating the value of an existing element in an array
● Linear O(n) — Grows proportional to input size
○ Finding an item in the linked list or array
○ Looping through a collection of elements (for loop, while loop …etc)
● Quadratic O(n^2) — Grows proportional to the square of the input size
○ A nested loop
○ Iterating through a 2-dimensional array
○ Insertion sort
● Logarithmic O(logn) — Grows logarithmically to input size
○ Binary search for a value in a sorted array
○ Inserting a value in a binary search tree
● Quasilinear O(nlogn) — Common for comparison sorting algorithms
○ Quicksort
○ Mergesort
○ Heap Sort
● Polynomial O(n^c) — c is a constant power
○ Deeply nested loops
● Exponential O(c^n) — c is a constant base
○ Multiple recursion algorithms
● Factorial O(n!) — Grows proportional to the factorial of the input size
○ Finding permutations
In my next post (I didn’t expect to spend 2 hours writing this post already…), I will start talking about Data Structures for Array and String, and hopefully covering some of the common interview questions.
Before You Go —
There’s no better way to support me than to give me a follow on Medium (Victor Lin). Let me know that I should write more!
Did you know that you can give up to 50 👏’s by pressing down on the 👏 button? Give it a try if you reeeeeeally liked this article!
