Skip to content

Instantly share code, notes, and snippets.

@tsiege
Last active March 16, 2024 16:37
Star You must be signed in to star a gist
Save tsiege/cbb0507082bb18ff7e4b to your computer and use it in GitHub Desktop.
This is my technical interview cheat sheet. Feel free to fork it or do whatever you want with it. PLEASE let me know if there are any errors or if anything crucial is missing. I will add more links soon.

ANNOUNCEMENT

I have moved this over to the Tech Interview Cheat Sheet Repo and has been expanded and even has code challenges you can run and practice against!













The below is just for some preservation for those who stumble across here, but is no longer kept up to date.












\

Studying for a Tech Interview Sucks, so Here's a Cheat Sheet to Help

This list is meant to be both a quick guide and reference for further research into these topics. It's basically a summary of that comp sci course you never took or forgot about, so there's no way it can cover everything in depth.

Contributing

Please see the Tech Interview Cheat Sheet Repo

Data Structure Basics

Array

Definition:

  • Stores data elements based on an sequential, most commonly 0 based, index.
  • Based on tuples from set theory.
  • They are one of the oldest, most commonly used data structures.

What you need to know:

  • Optimal for indexing; bad at searching, inserting, and deleting (except at the end).
  • Linear arrays, or one dimensional arrays, are the most basic.
    • Are static in size, meaning that they are declared with a fixed size.
  • Dynamic arrays are like one dimensional arrays, but have reserved space for additional elements.
    • If a dynamic array is full, it copies its contents to a larger array.
  • Multi dimensional arrays nested arrays that allow for multiple dimensions such as an array of arrays providing a 2 dimensional spacial representation via x, y coordinates.

Time Complexity:

  • Indexing: Linear array: O(1), Dynamic array: O(1)
  • Search: Linear array: O(n), Dynamic array: O(n)
  • Optimized Search: Linear array: O(log n), Dynamic array: O(log n)
  • Insertion: Linear array: n/a Dynamic array: O(n)

Linked List

Definition:

  • Stores data with nodes that point to other nodes.
    • Nodes, at its most basic it has one datum and one reference (another node).
    • A linked list chains nodes together by pointing one node's reference towards another node.

What you need to know:

  • Designed to optimize insertion and deletion, slow at indexing and searching.
  • Doubly linked list has nodes that also reference the previous node.
  • Circularly linked list is simple linked list whose tail, the last node, references the head, the first node.
  • Stack, commonly implemented with linked lists but can be made from arrays too.
    • Stacks are last in, first out (LIFO) data structures.
    • Made with a linked list by having the head be the only place for insertion and removal.
  • Queues, too can be implemented with a linked list or an array.
    • Queues are a first in, first out (FIFO) data structure.
    • Made with a doubly linked list that only removes from head and adds to tail.

Time Complexity:

  • Indexing: Linked Lists: O(n)
  • Search: Linked Lists: O(n)
  • Optimized Search: Linked Lists: O(n)
  • Insertion: Linked Lists: O(1)

Hash Table or Hash Map

Definition:

  • Stores data with key value pairs.
  • Hash functions accept a key and return an output unique only to that specific key.
    • This is known as hashing, which is the concept that an input and an output have a one-to-one correspondence to map information.
    • Hash functions return a unique address in memory for that data.

What you need to know:

  • Designed to optimize searching, insertion, and deletion.
  • Hash collisions are when a hash function returns the same output for two distinct inputs.
    • All hash functions have this problem.
    • This is often accommodated for by having the hash tables be very large.
  • Hashes are important for associative arrays and database indexing.

Time Complexity:

  • Indexing: Hash Tables: O(1)
  • Search: Hash Tables: O(1)
  • Insertion: Hash Tables: O(1)

Binary Tree

Definition:

  • Is a tree like data structure where every node has at most two children.
    • There is one left and right child node.

What you need to know:

  • Designed to optimize searching and sorting.
  • A degenerate tree is an unbalanced tree, which if entirely one-sided is a essentially a linked list.
  • They are comparably simple to implement than other data structures.
  • Used to make binary search trees.
    • A binary tree that uses comparable keys to assign which direction a child is.
    • Left child has a key smaller than it's parent node.
    • Right child has a key greater than it's parent node.
    • There can be no duplicate node.
    • Because of the above it is more likely to be used as a data structure than a binary tree.

Time Complexity:

  • Indexing: Binary Search Tree: O(log n)
  • Search: Binary Search Tree: O(log n)
  • Insertion: Binary Search Tree: O(log n)

Search Basics

Breadth First Search

Definition:

  • An algorithm that searches a tree (or graph) by searching levels of the tree first, starting at the root.
    • It finds every node on the same level, most often moving left to right.
    • While doing this it tracks the children nodes of the nodes on the current level.
    • When finished examining a level it moves to the left most node on the next level.
    • The bottom-right most node is evaluated last (the node that is deepest and is farthest right of it's level).

What you need to know:

  • Optimal for searching a tree that is wider than it is deep.
  • Uses a queue to store information about the tree while it traverses a tree.
    • Because it uses a queue it is more memory intensive than depth first search.
    • The queue uses more memory because it needs to stores pointers

Time Complexity:

  • Search: Breadth First Search: O(V + E)
  • E is number of edges
  • V is number of vertices

Depth First Search

Definition:

  • An algorithm that searches a tree (or graph) by searching depth of the tree first, starting at the root.
    • It traverses left down a tree until it cannot go further.
    • Once it reaches the end of a branch it traverses back up trying the right child of nodes on that branch, and if possible left from the right children.
    • When finished examining a branch it moves to the node right of the root then tries to go left on all it's children until it reaches the bottom.
    • The right most node is evaluated last (the node that is right of all it's ancestors).

What you need to know:

  • Optimal for searching a tree that is deeper than it is wide.
  • Uses a stack to push nodes onto.
    • Because a stack is LIFO it does not need to keep track of the nodes pointers and is therefore less memory intensive than breadth first search.
    • Once it cannot go further left it begins evaluating the stack.

Time Complexity:

  • Search: Depth First Search: O(|E| + |V|)
  • E is number of edges
  • V is number of vertices

Breadth First Search Vs. Depth First Search

  • The simple answer to this question is that it depends on the size and shape of the tree.
    • For wide, shallow trees use Breadth First Search
    • For deep, narrow trees use Depth First Search

Nuances:

  • Because BFS uses queues to store information about the nodes and its children, it could use more memory than is available on your computer. (But you probably won't have to worry about this.)
  • If using a DFS on a tree that is very deep you might go unnecessarily deep in the search. See xkcd for more information.
  • Breadth First Search tends to be a looping algorithm.
  • Depth First Search tends to be a recursive algorithm.

Efficient Sorting Basics

Merge Sort

Definition:

  • A comparison based sorting algorithm
    • Divides entire dataset into groups of at most two.
    • Compares each number one at a time, moving the smallest number to left of the pair.
    • Once all pairs sorted it then compares left most elements of the two leftmost pairs creating a sorted group of four with the smallest numbers on the left and the largest ones on the right.
    • This process is repeated until there is only one set.

What you need to know:

  • This is one of the most basic sorting algorithms.
  • Know that it divides all the data into as small possible sets then compares them.

Time Complexity:

  • Best Case Sort: Merge Sort: O(n)
  • Average Case Sort: Merge Sort: O(n log n)
  • Worst Case Sort: Merge Sort: O(n log n)

Quicksort

Definition:

  • A comparison based sorting algorithm
    • Divides entire dataset in half by selecting the middle element and putting all smaller elements to the left of the element and larger ones to the right.
    • It repeats this process on the left side until it is comparing only two elements at which point the left side is sorted.
    • When the left side is finished sorting it performs the same operation on the right side.
  • Computer architecture favors the quicksort process.

What you need to know:

  • While it has the same Big O as (or worse in some cases) many other sorting algorithms it is often faster in practice than many other sorting algorithms, such as merge sort.
  • Know that it halves the data set by the average continuously until all the information is sorted.

Time Complexity:

  • Best Case Sort: Merge Sort: O(n)
  • Average Case Sort: Merge Sort: O(n log n)
  • Worst Case Sort: Merge Sort: O(n^2)

Bubble Sort

Definition:

  • A comparison based sorting algorithm
    • It iterates left to right comparing every couplet, moving the smaller element to the left.
    • It repeats this process until it no longer moves an element to the left.

What you need to know:

  • While it is very simple to implement, it is the least efficient of these three sorting methods.
  • Know that it moves one space to the right comparing two elements at a time and moving the smaller on to left.

Time Complexity:

  • Best Case Sort: Merge Sort: O(n)
  • Average Case Sort: Merge Sort: O(n^2)
  • Worst Case Sort: Merge Sort: O(n^2)

Merge Sort Vs. Quicksort

  • Quicksort is likely faster in practice.
  • Merge Sort divides the set into the smallest possible groups immediately then reconstructs the incrementally as it sorts the groupings.
  • Quicksort continually divides the set by the average, until the set is recursively sorted.

Basic Types of Algorithms

Recursive Algorithms

Definition:

  • An algorithm that calls itself in its definition.
    • Recursive case a conditional statement that is used to trigger the recursion.
    • Base case a conditional statement that is used to break the recursion.

What you need to know:

  • Stack level too deep and stack overflow.
    • If you've seen either of these from a recursive algorithm, you messed up.
    • It means that your base case was never triggered because it was faulty or the problem was so massive you ran out of alloted memory.
    • Knowing whether or not you will reach a base case is integral to correctly using recursion.
    • Often used in Depth First Search

Iterative Algorithms

Definition:

  • An algorithm that is called repeatedly but for a finite number of times, each time being a single iteration.
    • Often used to move incrementally through a data set.

What you need to know:

  • Generally you will see iteration as loops, for, while, and until statements.
  • Think of iteration as moving one at a time through a set.
  • Often used to move through an array.

Recursion Vs. Iteration

  • The differences between recursion and iteration can be confusing to distinguish since both can be used to implement the other. But know that,
    • Recursion is, usually, more expressive and easier to implement.
    • Iteration uses less memory.
  • Functional languages tend to use recursion. (i.e. Haskell)
  • Imperative languages tend to use iteration. (i.e. Ruby)
  • Check out this Stack Overflow post for more info.

Pseudo Code of Moving Through an Array (this is why iteration is used for this)

Recursion                         | Iteration
----------------------------------|----------------------------------
recursive method (array, n)       | iterative method (array)
  if array[n] is not nil          |   for n from 0 to size of array
    print array[n]                |     print(array[n])
    recursive method(array, n+1)  |
  else                            |
    exit loop                     |

Greedy Algorithm

Definition:

  • An algorithm that, while executing, selects only the information that meets a certain criteria.
  • The general five components, taken from Wikipedia:
    • A candidate set, from which a solution is created.
    • A selection function, which chooses the best candidate to be added to the solution.
    • A feasibility function, that is used to determine if a candidate can be used to contribute to a solution.
    • An objective function, which assigns a value to a solution, or a partial solution.
    • A solution function, which will indicate when we have discovered a complete solution.

What you need to know:

  • Used to find the expedient, though non-optimal, solution for a given problem.
  • Generally used on sets of data where only a small proportion of the information evaluated meets the desired result.
  • Often a greedy algorithm can help reduce the Big O of an algorithm.

Pseudo Code of a Greedy Algorithm to Find Largest Difference of any Two Numbers in an Array.

greedy algorithm (array)
  var largest difference = 0
  var new difference = find next difference (array[n], array[n+1])
  largest difference = new difference if new difference is > largest difference
  repeat above two steps until all differences have been found
  return largest difference

This algorithm never needed to compare all the differences to one another, saving it an entire iteration.

@wcpines
Copy link

wcpines commented Jul 16, 2017

I just forked it and fixed the headings. You can find it here. Guessing I'm not the first nor the last to offer :P

@mega0319
Copy link

Very helpful. Thanks! Might be worth showing some of the data structures in actual code. I have started working on this in JS and so far I have completed linked lists and binary search trees. Will be working on hash tables later today. Here's a link to my repo.

https://github.com/mega0319/data-structures

@harrisonlingren
Copy link

harrisonlingren commented Aug 3, 2017

I forked this to an actual repo here. Fixed headings (again) and added a ToC. Gave you credit at the top and linked back to this Gist.

@v1v2r0b8
Copy link

Hash functions accept a key and return an output unique only to that specific key.

Please make it more precise as it might be a first place for somebody to look it up. The sentence contradicts the very idea of a hash function which is used to compress a huge key space (e.g. all strings up to certain length) via mapping it to range [0, 1, ... , n - 1]

@GraniteConsultingReviews

This algorithm is very hard to understand but i m trying please make this simple.

@omerbaldo
Copy link

at bubble sort, its big o efficiency says merge sort efficiency. the numbers are right, just not the label.

besides that its a good article. thanks

@najam2012
Copy link

its very beneficial. Good work bro.

@bhaumin
Copy link

bhaumin commented Nov 30, 2017

God bless you

@Clarkbaum
Copy link

I don't get why markdown headers are so often messed up. Why is this such a common problem its so easy to fix!

@mindy99
Copy link

mindy99 commented Jan 19, 2018

Keep up good work! Thanks!

@MuhsinFatih
Copy link

oh god, i'm blinded. fix the headers already. you just need to put a space after hashes

@AlinaWithAFace
Copy link

+1 please fix the headers, @Mohamed3on already did it and everything

@vijeetgv
Copy link

vijeetgv commented Jul 15, 2018

Fixed the 'merge sort complexity' repetitions & added the headers/formatting fixes from @Mohamed3on here https://gist.github.com/vijeetgv/debcccc49347e02ff816d158b564464f Is there a way to add any 'pull request' in GithubGists?

@akashperfect
Copy link

akashperfect commented Jul 29, 2018

Should the Quick Sort complexity change from:
Best Case Sort: Merge Sort: O(n)
Average Case Sort: Merge Sort: O(n log n)
Worst Case Sort: Merge Sort: O(n^2)

to

Best Case Sort: Quick Sort: O(n log n)
Average Case Sort: Quick Sort: O(n log n)
Worst Case Sort: Quick Sort: O(n^2)

@WHYjun
Copy link

WHYjun commented Sep 3, 2018

https://gist.github.com/WHYjun/b409436a37aff55e359a55b8c3a98f60

I updated your gist with comments. Please check mine!

@PriscillaLii
Copy link

Thx! The basic algorithm part is extremely good. Wish you posted DP and String match

@Ro-the-pro
Copy link

Summarizing from your Big O notes above:

S.No. Name Indexing Search Insertion Optimized Search
1 Linear Array O(1) O(n) N/A O(log n)
2 Dynamic Array O(1) O(n) O(n) O(log n)
3 Linked List O(n) O(n) O(1) O(n)
4 Hash Table O(1) O(1) O(1)  
5 Binary Tree O(log n) O(log n) O(log n)  
6 Breadth First Search   O(|E| + |V|) E: # of edges V: # of vertices    
7 Depth First Search   O(|E| + |V|) E: # of edges V: # of vertices    

@sivasaketh
Copy link

Can someone explain the difference between indexing and searching. I could not get the definition of indexing.

@ednihs
Copy link

ednihs commented Feb 22, 2019

Indexing is something similar to the the index page in your book, from where you get mapping of all the chapters in a single page, eg: which chapter is in which page. Now you can use this index information to find(search) a particular chapter and then dive further into that chapter to search for your respective topic. This makes your search logn . In programming world indexing is similar to hashing

@0xYasser
Copy link

This will give you a good explanation of what is indexing and why it's useful in databases https://www.youtube.com/watch?v=aZjYr87r1b8

@iamwhitebox
Copy link

I've been asked extremely nuanced algorithm questions like, "balanced delimiter" algorithms and such, I can't imagine how many false-negatives these interviews produce for companies.

@Sankalpbp
Copy link

Thank you very much.

@AbheeHub
Copy link

@tsiege You have shared a very wonderful resource. Thanks a lot for this.
Need help in one more thing if you or anyone can help me out.
HR Interviews are also equally and likely important as technical important.
So if there is any resource that you or anyone can share then please do share it.
The resource helping to crack HR interviews (or just simple interviews) are appreciated.

I'm asking for because there were many cases with me when I passed the technical or coding interview but was unable to make to the final HR interview.
So any help by anyone is appreciated.
And thanks once again @TSeige for sharing this wonderful resource.

@pnjha
Copy link

pnjha commented Jun 8, 2019

@tsiege You have shared a very wonderful resource. Thanks a lot for this.
Need help in one more thing if you or anyone can help me out.
HR Interviews are also equally and likely important as technical important.
So if there is any resource that you or anyone can share then please do share it.
The resource helping to crack HR interviews (or just simple interviews) are appreciated.

I'm asking for because there were many cases with me when I passed the technical or coding interview but was unable to make to the final HR interview.
So any help by anyone is appreciated.
And thanks once again @TSeige for sharing this wonderful resource.

You can go through this resource: http://blog.gainlo.co/index.php/2017/06/29/chapter-9-non-technical-questions-complete-guide-google-interview-preparation/

@prashant-shahi
Copy link

Github markdown isn't interpretation the subtitles well.

After #, make use of at least one space before you write subtitles.

https://gist.github.com/coolboi567/228b29f806a05c79c7d98292978add43

@theangelsofwar
Copy link

Great Content!

Cheers,
Angie Changpagne

@farslanku
Copy link

For wide, shallow trees use Breadth First Search
For deep, narrow trees use Depth First Search
Are you sure of this? For a wide tree, BFS is a bad idea since all nodes in the same level will be in the queue. For a deep tree, DFS might end up stackoverflows. I googled it, and this part needs being corrected :
https://www.techiedelight.com/depth-first-search-dfs-vs-breadth-first-search-bfs/

@erwoods89
Copy link

Should add in Randomized Skip List.

@trisha
Copy link

trisha commented May 7, 2021

"Big O Efficiency" sounds weird to me, I think it should be either "Computational Complexity" or "Time and Space Complexity".

Agreed with this, it's Big O notation for time and space complexity

@apimaker001
Copy link

Thanks for the information

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment