Please enable JavaScript.
Coggle requires JavaScript to display documents.
Master the Coding Interview - Coggle Diagram
Master the Coding Interview
:two_hearts:
Non-Technical
:selfie:
Getting the interview
Resume
Personalized on the position
One page
relevant skills
show exactly what you did and possibly the results
make it measurable (add numbers, e.g. I improved speed by 20%)
Online link
use this checklist:
https://www.notion.so/Master-coding-interview-f392e912e18c44c8aaef74a269541866#47e09ae50cb24aaf88792de9a2506b52
LinkedIn
Better then resumes
update frequently to show up in recruiters' searches
Email
For companies best way to get candidates is through referral
Cover letter: specific and personalized
Send requests to people working at a company of interest (not asking for a job!)
use
email extractor tools
to get email addresses
Portfolio
Lack of experience on a topic
GitHub
Website
1-2 Big projects
Blog (e.g. Medium)
it's a numbers' game: we want to increase our success rate
:sparkles:
Mindset
DON'T
walk into an interview like it's your one and only chance - it's not do or die
DO
treat the interview as a learning experience, a way to check how good you are
enter the interview with energy and a big smile
show yourself excited and make the interviewers excited to interview you
What an interviewer wants to find out:
Can you do the job?
Can I work with you?
Are you going to improve?
:fire: The Four Heroes
two to four stories you should have prepared and will help you standout
Technical
Episode of your career demonstrating your technical skills
Success
Episode in which you were successful (e.g. receiving a promotion for something you did)
Leadership
demonstrate you're taking ownership and feel yourself accountable, not just sitting idle waiting for inputs
Challenge
Talk about a difficult moment/task in your career and how you overcame it
:grey_question:
The always asked
:speaking_head_in_silhouette::
Tell me about yourself
tell them about your hero journey: from unskilled to someone they want to hire - stand out
mention skills relevant to the job (see job description)
mention things you want to get asked
answer in about a minute: don't bore them!
:silhouettes:
Why us
research about the company and understand the problems they are trying to solve
show you want to grow with the company
make the interviewer feel special - make it seem that the company is your top choice
Why are you leaving your current job?
no negativity, no complaining - tell them you want to grow
:!?:
Tell me about a problem + how you solved it
SAR
S
ituation
briefly explain the problem (no complaining)
A
ction
explain the action(s) you took to solve it
R
esult
explain what happened after applying the actions
answer using numbers and metrics (e.g. increased performance/users base/etc. by 10%)
Variation: Tell me about an interesting project
show how you are different
relate it to the job you applied for
:chains:
What is your biggest weakness
give a real answer and show what you did/are doing to improve yourself
example: "When I have to solve something I tend to jump straight into code but sometimes I should stop a moment before moving to the coding part. Lately I started to impose myself that I annotate the steps and I spend 30-60 minutes before coding a non-trivial problem"
don't brag and say things like "I work too hard"
:question:
Any questions for us
focust on the interviewer, not the company (use YOU) - mention something they mentioned in order to tailor the qwuestions on them
examples
what you wish somebody told you when you started?
where do you see the company going in the next 3-5 years? This demonstates you want to grow with the company and you care about company's plans
have you seen your skills grow during the past year?
Reverse Interview Questions
:gun:
Secret Weapons
: try to fit those in a conversation
never give up: it's very rare that you have a perfect interview
Simplicity over Complexity
Code is about solving problem for others - make sure you value simplicity (e.g. readable code)
Premature optimization is the root of all evil
you don't have infinite time and resources to solve a problem - make sure you let interviewers know that you value effort/resul ratio
Overall goal, not narrowed on smaller activities
don't ignore the business context and customers' requests
No complaining
- about client/code/colleagues/etc.
NO EGO
don't feel hurt when receiving feedbacks
the overall goal is what matters
feedback culture
:coffee:
Offer + Negotiation
:unamused:
Handling rejection
don't get depressed - it's ok to fail
ask for feedback
ask when it will be a right time to re-apply
:moneybag:
Negotiation 101
salary expectations: give average salary based on the region and use it as a starting point
Always negotiate
even if uncomfortable
the larger the company, the more room of negotiation
don't appear greedy, give reasons for everything
e.g. if needing more time tell is is a big family decision and you'd need to discuss this with your partner
Be positive
don't think you're mean just because you're negotiating - negotiation is finding a balance between what two parties want
Have stakes
companies need an incentive to offer you more
show them you're able to walk away because you have other options
:money_mouth_face:
Handling an offer
don't end the conversation: be positive and tell them you are very happy but also need time to evaluate all of your options because it is an important decision (again, not greedy)
if you get an offer let other companies you're interviewing with know
it creates social proof that you are in demand
What to do
find exact salary >= avg salary (Salary.com or glassdoor)
what value do you provide? you can use it as a negotiation argument
go higher than what you wish to earn - you will meet somewhere in the middle
if declining always be polite and don't burn bridges
Handling multiple offers
decision checklist (1-5 most to least important)
is there an offer you feel underqualified for? Then you should take it as it will let you grow the most
Long-term growth potential
Will you respect people around you? You shouldn't be the smartest guy in the room
Salary and benefits. Think also of long-term gratification
Is your decision based on desperation? Think of long-term implications and make sure it is worth the change, choosing a job with purpose and that makes you happy
:chocolate_bar:
Getting a raise
Ask for a raise
if you don't ask, the answer will always be no
ask more than what you wish for
Show don't tell
show why you're valuable making a powerpoint or a one page summary on how you're contributing
keep a folder of all the good things you did and skills you learned
:microscope:
Technical
:lock:
Foundations
Big O
Good code
Scalabe
Time Complexity (Speed)
Rules
Each input gets its variable
Always consider worst case
Drop constants
drop non-dominant Big Os
O(1): n. of operations independent from the size of the input
O(n): n. of operations scales linearly with the size of the input
O(n^2): n. of operations grows quadratically with the size of the input
O(n!): like adding a loop for every element in the input
Space Complexity (Memory)
It is always a balance (and tradeoffs) between readable code, fast code, memory-efficient code
Readable
Notation to measure the scalability of our code: how much the code slows down as the size of the input increases
How to solve Coding Problems
Step by step
1
2
3
4
5
3 more items...
Don't be annoying asking too many questions about too small details
Find out the main goal: what is the most important value of the problem? Ask about size of the input and whether we have time and/or memory
Verify the contraints: e.g. can number be positive? sorted? duplicates?
write test cases matching contraints
Will there always be a solution available? What to return if no solution?
What are the inputs? What are the outputs?
Write down the keypoints of the problem at the top with expected output
What interviewers look for
Analytic skills and thought process
Coding skills
Technical skills (know the foundations)
Communication skills
:house:
Data Structures
way to organize data in a collection of values with a specific relationship between the elements + possible operations on them
each DS is best suitable based on the problem to solve: trade-offs among DSs
Operations
Access
Insertion
Deletion
Traversal
Search
Sort
How computer stores data
CPU: the actual executor of operations
sometime couple with a near cache, an access RAM fast
programs are likely to access nearby data (locality principle)
RAM: fast, volatile memory
stores program data under execution
organized in registries of 1 byte of data
if data cannot fit in memory, then overflows
data structures are basically "how data is arranged in RAM"
Storage: slow, persistent
holds data/programs not being processed/executed
:house:
Array
Static
fixed in size
Dynamic
need to recreate the array in order to adapt to new size: move to new contiguous soace in memory where the array fits
CONs: slow insert/delete because need to shift array if not at end, fixed size with static array
PROs: fast look-ups (indexed), fast push/pop, ordered
append operation can be O(n) - overhead of managing the memory re-allocation
String questions? Turn the string into an array!
:red_flag:
Interview Techniques
Two-pointers
e.g. nested for loops
usually used for brute force solution
Shifting pointers
change pointers based on the values encountered in the array
usually initialized with first and last indexes
useful to find max/min in a solution space
:house:
Hash Table
key-value pair data structure
key is hashed through a hash function to get the address where the value is stored
Hash function
idempotent: given the same input will always return the same output
one-way: given an output cannot get to the corresponding input (non-invertible function)
function that generates an output of fixed length for each input
if hash calculation is slow - accesses to hash tables will be slow
PROs: fast look-ups (good collision detection needed), fast inserts, flexible keys
CONs: unordered, slow key iteration
in case of collisions, access can be O(n/k), where k is the size of the table => O(n)
Collisions
there is limited space in memory for the hash table, therefore it will happen to get the same hash for 2 divverent keys
values colliding on a specific hashed key will be stored as a list
Linked List
can be used to reduce time complexity (trade-off with memory)
:house:
Linked List
set of items loosely linked together through pointers.
head
: pointer to the first element of the list.
tail
: pointer to the last element of the list, which is null-terminated (tail points to null)
Singly Linked List
: each item has one pointer referencing to the next item
PROs: fast insertion, fast deletion, ordered, flexible size
CONs: slow lookup, more memory (to store pointers). In addition principle of locality cannot be leveraged like for array, since elements in linked lists aren't generally stored contiguously in memory
uses less memory and it's easier to implement but cannot traverse backwards
Doubly Linked List
: each items has a pointer referencing the next item and another referencing the previous item
allows to traverse backwards and search is O(n/2) but it requirtes more memory and more complex implementation to handle the extra reference
Pointer
: reference to a place in memory - most programming languages autmatically free unreferenced memory (garbage collection)
:red_flag:
Interview Techniques
slow & fast pointers
example: find the mid point: for every step of iteration we will advance the slow pointer of 1 and the fast pointer will advance by 2
:house:
Stack
PROs: fast operations, fast peek, ordered
CONs: slow lookup
LIFO: last-in, first-out (think of plates)
Can be implemented with arrays or linked list
Linear data structure: traversed sequentially with only one element which can be directly reached
:warning: it limits the operation which can be performed compared to a lower-level data structure
:house:
Queue
PROs: fast operations, fast peek, ordered
CONs: slow lookup
:warning: it limits the operation which can be performed compared to a lower-level data structure
Linear data structure: traversed sequentially with only one element which can be directly reached
:forbidden: Do not implement a queue with an array: each dequeue will cause the array to shift entirely because the first element is removed
:evergreen_tree:
Tree
Hierarchical data structure
one root node, every node not root has one parent, leaf nodes do not have children, sibling nodes have the same parent
linked list is a particular type of tree, where nodes point to max 1 child
a tree contains subtrees
:deciduous_tree:
Binary Tree
each parent node has at max 2 children each child 1 parent
Perfect BT
every node has exactly 2 children
number of nodes doubles at each level, number of nodes at one level equals to all of the nodes at previous levels + 1
half of the nodes are at the bottom, leading to more efficiency when performing a choice on which node to pick
O(log(n))
has to do with how many possible choices are available while exploring a tree: choose to explore a subset (subtree) excluding another. If there's an order relationship, is like looking in a phone book
each level "l" has 2^l nodes
1 more item...
Full BT
: every node with children has exactly 2 children
Binary Search Tree (BST)
each vertex has only up to 2 children that satisfies BST property
All vertices in the left subtree of a vertex must hold a value smaller than its own and all vertices in the right subtree of a vertex must hold a value larger than its own
Balanced
AVL Trees
Red/Black Trees
Unbalanced
can degenerate in being a linked list: O(n) performances
there are algorithms to keep the tree balanced (see AVL & R/B Trees)
PROs: operation are less than O(n) for a balanced BST, ordered, flexible sizing with nodes
CONS: No O(1) operation
:!:
Heap
each node mantains a strong order over its children (e.g. max/min of all the children, max/min is at root)
Binary Heap
a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
PROs: Better than O(n), Priority, Fexible size, Fast insert
CONs: Slow lookup
Priority Queue
each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority
Heap with array
:speech_balloon:
Trie
specialized tree used in prefixed search (mainly text) - also called "Prefix Tree"
because of prefixes lots of space is saved - we don't to store multiple times words which start with the same prefix
BigO = O (length of the word)
:ideograph_advantage:
Graph
Basics
composed of
nodes
or
vertexes
connected through
edges
Tree is a type of graph
set of values related to each other in a pair-wise fashion
Types of Graph
Directed
Undirected
Cyclic
Acyclic
Weighted
Unweighted
Very popular: Directed Acyclic Graph (DAG)
useful to represent relationships, but hard to scale
How to build a graph
Edge lists
Adiacency Matrix
Adiacency List
:computer:
Algorithms
:recycle:
Recursion
function refering to itself within its body
Recursion costs memory: function calls are kept being added to the call (memory) stack. If not popped => Stack Overflow
:crossed_swords:
Divide and Conquer
tasks that have repeated subtasks (subproblems) which are smaller instances of the main problem and the combined results of the subproblems solve the main problem
PROs: code is more dry, readability
every problem which can be solved recursively can also be solved iteratively: but some problems are more suitable to recursion (e.g. traversing data structures with unkown depth like trees and graphs)
CONs: large stack
mitigated with tail call optimization: programming languages optimize the call stack allocation if the recursive call is the last returned statement - instead of keeping the stack active just to return the return value to the caller, this ret. value is written directly in the memory space where the caller expects it to be
:warning:
Mind the BigO
recurs. algorithms which solve a problem of size N have a compl. of O(2`N)!
The three laws of recursion
Anatomy of recursion
1) A recursive algorithm must have a
base case
, which makes the recursion stop
2) A recursive algorithm must call itself, recursively - identify the repeated subtasks to be solved through the recursive case
3) A recursive algorithm must change its state and move toward the base case - solving each subtask the alg. get closer and closer to the base case and then returns
:straight_ruler:
Sorting
Animations
Comparison Sort
Elementary Sorting
Bubble Sort
least efficient, but easy to understand
Time Complexity: O(n^2), Space Complexity: O(1)
at each iteration the largest item bubbles up to the end
Selection Sort
at each iteration the smallest item is selected and it's swapped to the index according to the current iteration (at the first iteration is swapped with the first element, at the second iteration with the second and so on
Time Complexity: O(n^2), Space Complexity: O(1)
Insertion sort
it keeps two subarrays: one sorted and one unsorted. At each iteration an element is taken from the unsorted subarray and inserted at the right position in the sorted subarray
worst case is still O(n^2) - but if array is nearly sorted then it is O(n)
performs well on small and/or nearly sorted dataset
Divide & Conquer Sorting
Merge Sort
Divide dataset in halves until there's only one item (base case). Then all of the subarrays are recursivles merged (smallest item to largest, comparisons happen on smaller data sets)
time: O(n*logn), space O(n)
Stable: keep orginal order for equivalent items
Quick sort
Partition the dataset then recursively quicksort sub-datasets at the left and at the right of the pivot.
the partition step selects a pivot (e.g. always last item) and re-arrange dataset so that items at the left of pivot are smaller than pivot and items at right of it are larger
average time complexity O(n*logn), space complexity O(logn), memory used for the recursive calls
:warning: Worst case time complexity is O(n^2) and happens when the chosen pivot is either the smallest or largest element in the dataset. Pivot choice is important!
Heapsort
O(n*logn), O(1)
The heapsort algorithm has two main parts (that will be broken down further below): building a max-heap and then sorting it
1) Build max heap, max element will be at index zero 2) swap first and last element and decrement heap size 3) run heapify step to ensure heap's property is respected 4) repeat step 2 until dataset is fully sorted
Sorting is based on comparisons between elements: mathematically cannot beat O(n*logn)
Dancing Algorithms
Choosing a sorting algorithm
Few items and/or nearly-sorted datasets => Insertion Sort
Never use bubble sort or selection sort, useful only for educational purposes
Worried about worst-case scenario and space complexity of O(n) not a problem => Merge sort (it's always O(nlogn) and stable
not worried about worst case and need smaller space => Quick sort (be careful on choosing the pivot as it could go to O(n^2)
Worried about worst-case and need extra space: Heapsort
though having same complexitx quicksort, merge sort, heap sort, quicksort is generally faster because doesn't do unnecessary swaps
Non-Comparison Sort
take advantage of howe data is sotred in memory in terms of zeroes and ones to do the sorting - only works with numbers in a specific range
Radix-Sort
Counting Sort
:mag:
Searching
Searching in a list
Linear search
O(n)
: good for limited datasets
finding item within an list (no matter if sorted or not)
Binary Search
only if data is sorted
O(logn)
Searching with strings? Try a Trie!
:walking: Traversal
more general than search indicating visiting of every node in a tree or vertex in a graph
for indirected graph, it might be an idea to keep a list of the visited vertexes in order to not incurr in infinite loops over the same nodes
Breadth First Search (BFS)
start with a node an proceed traversing left to right level by level
PROs: Shortest path to a node, closer nodes
CONs: needs additional memory to track the children of a node at a specifil level
Which one to use?
If you know a solution is not far from the root of the tree: BFS
If the tree is very deep and solutions are rare: BFS - (DFS will take long time)
If the tree is very wide: DFS - (BFS is going to need more memory to track nodes in current level)
If solutions are frequent but located deep in the tree: DFS
Determining whether a path exists between two nodes: DFS
Finding the shortest path: BFS
Shortest Path Problem
Graphs with weighted edges
Dijkstra
CONs :works only with positive weights
PROs: runs faster than Bellman-Ford
Bellman - Ford
PROs: can accomodate negative weights
CONs: can take a long time to run O(n^2)
BFS assumes all edges have the same weight
used for recommendation engines, peer-to-peer networks, maps
Depth First Search (DFS)
each branch is explored at its deepest before moving to the next one
PROs: less memory (no need to store anything to do the traversal), finds whether a path exists
CONs: can get slow if depth is high
Tree
maze-solving: used to find a solution path and backtrack if one path is not leading to a solution
:explode:
Dynamic Programming
It basically is an optimization technique according to which a problem is solved by breaking it down into a collection of subproblems
each subproblem is solved once and its solution is stored (cached) in case next time the same subproblem occurs
DP = Divide and Conquer + Memoization
:memo:
Memoization
specific form of caching where the return value of a function is cached based on its input
the first time a memoized function is executed with a specific input, it is calculated and then the association input-output is stored in a cache. If same input occurs a second time, it will be used to fetch from the cache (usually a hash table w/ O(1))
Should DP be considered?
Can problem be divided in subproblems?
Recursive solution?
Repetitive subproblems (same calculation over and over)?
Memoize subproblems
Increased space complexity to improve time complexity
Fibonacci example
:triangular_ruler:
System Design
There is no right answer
every interviewer will expect a different answer
ask about the area to be focused on
focusing on the data model is usually a good place to start
don't mention specific technologies
draw! it will keep you on track on talking about the design
talk! Should be a conversation with back and forwards
General strategy
:silhouettes:
Scaling for Users
Caching
Deployment Options
