Algorithms and Data Structures Interview Preparison & Questions — Part 1

Many of new graduates want to knock on the doors of big companies in Silicon Valley such as , 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. Facebook Useful Resources and are two of the most famous free online courses for Algorithms in case you want to refresh your memory. Algorithms, Part 1 Algorithms, Part 2 There are two other books I would recommend anyone who is preparing technical interviews to read: , by Adnan Aziz which has 300+ questions and solutions, and it comes with a CD for electronic copy of questions and solutions you can practice with your IDE. Elements Programming Interviews programming which also has plenty of programming questions and solutions. Cracking The Code Interview , by Gayle Laakmann McDowell 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: (array) { // Input size n// instantiate an empty array, constant space sizevar result = [];// instantiate a counter, constant space size ( i =0; i < array. ; i++) {// push n items into the array, linear space size, linear timeresult.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) function printAndSaveAllNames for var length 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 (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. next post Before You Go — There’s no better way to support me than to give me a follow on Medium ( ). Let me know that I should write more! Victor Lin Did you know that you can give up to 50 👏’s by pressing down on the 👏 button? Give it a try if you liked this article! reeeeeeally https://upscri.be/hackernoon/