- Important thing to remember
- Working with this repo
- All Coding interview exercise and answers
- What to practice?
- How to Approach?
- What you should prepare?
- Computer Science Concepts
- Big O complexity
- Recursion
- Data Structures
- Algorithms
- Data Structure Q & A
- Algorithms Q&A
- Mathematics & Stats You should know
- JavaScript Fundamentals
- Difference between i++ and ++i
- Bitwise operation in JavaScript
- Mock Interview
- Mandatory Algorithms
- Coding Interview Question and Answers
- Facebook Recruiting Portal Coding Interview Questions
- Graphs
- Trees and Graphs
- Route Between Nodes: Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
- Minimal Tree: Given a sorted increasing order array with unique integer elements, write an algorithm to create a binary search tree with minimal height
- Check if a given binary tree is BST ( Binary Search Tree )
- Delete node from Binary Search Tree (BST)
- Find the In-Order successor in a given BST?
- Recursion Interview Questions
- Sorted Array Interview Coding
- Linked List
- Binary Search for competitive programming from zero to advanced
- Greedy Algorithm
- BST
- Constraints on Coding interview
- How to start DSA?
- References
Coding interview question answers in JavaScript for Facebook, Amazon, Google, Microsoft or any company. Find all notes and Coding exercises for this repo here
- Remember: Run through
your codenot through thealgorithmwhile executing test. - While
solvingproblem: give yourself difficult values like use 7-8 elements of array not just 3 elements array. [1,2,3] instead use [12,34,22,51,6,96,43,8] - While
executingyour code always start with very easy example [2,3,1]
-
Download or clone in local machine.
-
Run
npm ci -
Then run individual file to see result on console.
-
You should use
node filenamein console to see results.
Make sure you know Computer science basic data structures. Also you should be aware of fundamental algorithms.
Once they give you problem, don't start coding. Ask clarifying questions to make sure you understand the problem.
Example:
- Will there be null/empty values on input?
- Will all numbers in a binary tree integers?
- Computer Science Concepts
- DataStructure
- Algorithms
- Big O Time
- Big O Space
- Recursion
- Memoization / Dynamic Programming
Learn Big O. Make sure you give what would be the runtime complexity and memory complexity.
- Array.push() is O(1) constant time complexity
- string.indexOf() search is O(n) linear time complexity
- for loop O(n) linear time complexity
Iterative functions take no extra memory and therefore, memory complexity is constant O(1).
Recursive functions take extra on the stack therefore, memory complexity is lograrithmic O(logn)
Factorial Simple Recursion
Recursive Factorial Simulation
Recursive Factorial Time complexity O(n)
Recursive Factorial Space complexity is O(n)
- Array
- Hash Table
- Linked List
- Stack
- Queue
- Tree
- Tries
- Graphs
- Heaps
- Vectors
- Merge sort
- Quick sort
- Breadth-first search
- Depth-first search
- Binary Search
Arrays can store a fixed number of elements, whereas a collection stores object dynamically so there is no size restrictions it grows and shrinks automatically.
- Insert at the end (push) is efficient.
- Insert at in between is not efficient.
Given a sorted array of integers, return the index of the given key. Return -1 if the key is not found.
Run below script
node .\src\arrays\binary-search.js
Given a large array of integers and a window of size w, find the current maximum value in the window as the window slides through the entire array.
Linked lists are dynamic data structure and memory is allocated at run time. They don't store data contiguously rather they use link to point to other elements.
Performance wise linked lists are slower than arrays because there is no direct access to linked list elements.
Suppose we have an array that contains following five elements 1, 2, 4, 5, 6. We want to insert a new element with value “3” in between “2” and “4”.
You have to copy 1,2 in new array then insert 3 and copy rest of the values. Runtime complexity and memory complexity is very high.
Therefore, we use linked list to store 1-6 and we can easily insert 3 in between 2 and 4.
The linked list is a list of items, called nodes. Nodes have two parts, value part and link part. Value part is used to stores the data. The link part is a reference, which is used to store addresses of the next element in the list.
- Head: Head is a reference that holds the address of the first node in the linked list.
- Nodes: Items in the linked list are called nodes.
- Value: The data that is stored in each node of the linked list.
- Link: Link part of the node is used to store the reference of other node.
class LinkedListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}Below are the types of LinkedList:
-
Singly Linked List
-
Doubly Linked List
-
Circular Linked List
Implement a LinkedList:
The newly created node will become head of the linked list. · Size of the list is increased by one.
We’re given the pointer/reference to the head of a singly linked list, reverse it and return the pointer/reference to the head of the reversed linked list.
Problem Solving steps
Running program output
Depth First Search (DFS) uses a stack for storing the nodes that it is visiting.
var stack = [1, 2, 3, 4];
stack.pop(); // 4 , stack [1,2,3]
stack.pop(); // 3 , stack [1,2]
stack.pop(); // 2 , stack [1]
stack.pop(); // 1 , stack [ ]Breadth First Search (BFS) uses a queue for storing the nodes that it is visiting.
var queue = [];
queue.push(1); // queue [1]
queue.push(2); // queue [1,2]
queue.push(3); // queue [1,2,3]var queue = [1, 2, 3, 4];
queue.shift(); // 1 , queue [2,3,4]
queue.shift(); // 2 , queue [3,4]
queue.shift(); // 3 , queue [4]
queue.shift(); // 4 , queue [ ]A tree has hierarchical data and it has nodes. It is a type of graph. Each node (except root) has exactly on parent and zero or more children.
A tree is acyclic meaning it has no cycles: "a cycle is a path [AKA sequence] of edges and vertices wherein a vertex is reachable from itself".
Therefore, a tree is also called as Directed Acyclic Graph (DAG).
- Root: top node of tree is called root and has no parent and has no incoming edges.
- Node: every node has parent ( except root ) and 0 or more children's.
- Edge: used to connect two nodes.
- Path: A path is an ordered list of nodes that are connected by edges.
- Leaf: A leaf node is a node that has no children.
- Height of the tree: The height of a tree is the number of edges on the longest path between the root and a leaf.
- The level of node: The level of a node is the number of edges on the path from the root node to that node.
- Children: Nodes that have incoming edges from the same node to be said to be the children of that node.
- Parent: Node is a parent of all the child nodes that are linked by outgoing edges. - Sibling: Nodes in the tree that are children of the same parent are called siblings.
- Ancestor: A node reachable by repeated moving from child to parent.
If you want to store hierarchical data use Tree.
You should know about Binary Tree and Binary Search Tree.
In BFS algorithm, a graph is traversed in layer-by-layer fashion. point. The queue is used to implement BFS.
Example: Suppose you have given a tree structure and asked to calculate the average of numbers at each level.
-
Strategy:
Iterative -
Time Complexity:
O(n logn) -
Space Complexity:
O(n logn) -
Use
Queuewhile coding.
The DFS algorithm we start from starting point and go into depth of graph until we reach a dead end and then move up to parent node (Backtrack). The stack is used to implement DFS.
- Strategy:
Recursive - Time Complexity:
O(n logn) - Space Complexity:
O(n logn) - Use
Recursive Call Stackwhile coding.
| BFS | DFS |
|---|---|
| Search level by level | Search from root to the leaf |
| Uses Queue to sort | Uses Stack to sort |
| Time complexity: Slow | Time complexity: Fast |
| Where to use: solution is not far from the root of the tree,If the tree is very deep and solutions are rare, If solutions are frequent but located deep in the tree, | Where to use: tree is very wide |
| Time Complexity: O(V+E) | Time Complexity: O(V+E) |
A binary tree is a type of tree in which each node has at most two children (0, 1 or 2) which are referred as left child and right child.
A Minimal Binary Tree has about the same number of nodes on the left of each node as on the right.
In Binary Search Tree nodes are:
- The key in the left subtree is less than the key in its parent node.
- The key in the right subtree is greater or equal the key in its parent node.
Checkout Binary Search Tree Visualization here.
BSTs get an average case of O(log n) on gets, adds, and deletes, but they can have a worst case of O(n) if you do something like add a sorted list to a BST. Go ahead, do a BST then add [1,2,3,4,5] to it.
Below image showing how to add [3, 7, 4, 6, 5, 1, 10, 2, 9, 8] in BST.
Binary Search Algorithm
Binary Search can be done both in iterative or recursive way.
Binary Search tree has left sub tree which is less than or equal to root. And right subtree which is strictly greater than the root.
Below image is not a BST
Simulating Recursive Binary Search for an existing number in a sorted increasing order unique integer array.
Simulating Recursive Binary Search for an non-existing number in a sorted increasing order unique integer array.
Trie is a tree, in which we store only one character at each node. This final key value pair is stored in the leaves.
Trie is also suitable for solving partial match and range query problems.
Each node in the heap follows the rule that the parent value is greater than its two children are.
There are two types of the heap data structure:
- Max heap: each node should be greater than or equal to each of its children.
- Min heap: each node should be smaller than or equal to each of its children.
A heap is a useful data structure when you want to get max/min one by one from data.
It is just like a dictionary or key value pair.
Graph represents network. It has Nodes, Vertices and Edges.
Implement Graph Question Implement Graph Answer
When you want to find all possible routes between airports then you want to use BFS.
Find all possible routes from PHX to BKK. Also then you can decide which path is the shortest one.
Question Answer Source Code: Find all possible routes between 2 airports using BFS
Question Answer Source Code: Find shortest route between 2 airports using DFS
Browser's JavaScript Engine (Array.prototype.sort) uses merge sort maximum time. Runtime complexity O(n logn), Memory complexity O(n) because we have to create new list. It uses divide-and-conquer algorithm! and also it is recursive.
https://www.youtube.com/watch?v=UxnyImctVzg
Merge Sort Algorithm
Merge Sort Algorithm Simulation
Merge Sort Implementation Visualization:
See the Pen Merge Sort In-place Answer by Rupesh Tiwari (@rupeshtiwari) on CodePen.
2 sorted arrays find the median element. Median is the middle index its not an average of values in an sorted array.
So in order to find median we can use the stich algorithm since arrays are already sorted. Then we can find the middle index.
Find Median Values Question & Answer
When Browser's are not using Merge sort they most of the time use Quick sort variations. Most powerful sorting algorithm
Quick sort Algorithm
Pseudo Code for Quick Sort Algorithm
Quick Sort Algorithm Simulation
Quick Sort Partition Algorithm
Quick Sort Partition Algorithm Simulation
Implement Quick Sort Algorithm Question
Quick Sort Answer with extra Array and Space complexity is O(n)
Quick Sort Answer with in-place partition and Space complexity O(1) the most Efficient algorithm
Implement in-place algorithm for Quick Sort Answer
In Quick sort we do not create auxiliary arrays. Therefore, it is good choice for Array to use quick sort. However in merge sort we create 2 auxiliary arrays. Therefore, linked list is a good choice.
XOR represents the inequality function, i.e., the output is true if the inputs are not alike otherwise the output is false. A way to remember XOR is "must have one or the other but not both". XOR can also be viewed as addition modulo 2.
Find how many different numbers in the array.
Input =[3, 5, 6, 3, 3 , 9, 5]
answer = 4
There are 4 values 3,5, 6,9.
x = 0;
array.forEach((num) => (x ^= num));
return x;Example create an array containing numbers from 0 to 9.
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
var y = new Array.from(Array(10).keys());
Answer: 9
1,000,000,000 = 1 Billion
Answer: 6
1,000,000 = 1 Million
Divide two integers without using '/' (division) or '*' (multiplication) operators.
node .\src\math-and-stats\integer-division.js
const x = new Array(4).fill(new Array(4).fill(0));
const map = new Map();
// insert
map.set('key', 'value');
// get
map.get('key');
// remove
map.delete('key');
// check key exist
map.has('key');
// size
map.size;By default array.sort does not work you must pass delegate method.
var a = [23, 4, 2, 155, 43];
a.sort();
// output: [155, 2, 23, 4, 43] Not sorted at all.
In order to sort in ascending order you must pass delegate method.
Ascending Order Sorting
var a = [23, 4, 2, 155, 43];
a.sort((a, b) => a - b);
// output: [2, 4, 23, 43, 155]
Descending Order Sorting
var a = [23, 4, 2, 155, 43];
a.sort((a, b) => b - a);
// output: [155, 43, 23, 4, 2]
An integer is a whole number that can be either greater than 0, called positive, or less than 0, called negative. Zero is neither positive nor negative.
Letters asci code starts from 96 to 122.
charCodeAt()gives the ascii code.String.fromCharCode(code)converts code to string.
const letter = 'A';
const newKey = (letter.charCodeAt() + 3) % 122;
const result = String.fromCharCode(newKey);
console.log(result); //"D"Math.abs(-4); //4
Math.abs(2); //2Slice does not mutate the original array.
slice(index,count) : Starts taking number from
given index and go till given count.
[20,39,48,58,16,36,48].slice(0,3) = [20,39,48]
[20,39,48,58,16,36,48].slice(3,7) = [58,16,36,48]
Math.floor(2.5) = 2
Math.floor(2.8) = 2
Math.floor(2.4) = 2Math.round(2.5) = 3
Math.round(2.8) = 3
Math.round(2.4) = 2Number.MAX_SAFE_INTEGER is the largest integer which can be used safely in calculations.
For example, Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2 is true — any integer larger than MAX_SAFE_INTEGER cannot always be represented in memory accurately. All bits are used to represent the digits of the number.
It is 16 digit number.
Number.MIN_SAFE_INTEGER= -9007199254740992Number.MAX_SAFE_INTEGER= 9007199254740991
So basically ++i returns the value after it is incremented, while i++ return the value before it is incremented.
Moving bit/s towards the right side in binary number.
4>>2 = 16
x>>y means x/2^y divide x by 2 to the power of y.
Moving bit/s towards the left side in binary number.
4<<2 = 0
x<<y means x*2^y multiply x by 2 to the power of y.
Traverse by depth and collect all the numbers. And calculate average also.
Runtime Complexity O(logn) Space Complexity O(logn)
abstract data type (ADT) - ADT is defined as a user point of view of a data type and Does not talk about how exactly it will be implemented.
Trade off or invest some memory to improve run time complexity. Suppose use Has-table, set etc. to insert some of the calculations that you want to not repeat.
All Mandatory algorithm source code download here.
See the Pen Binary Search on Sorted Array Algorithm by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Merge Sort Algorithm by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Merge Sort Algorithm by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Quick Sort In-place Implementation: Answer by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Binary Tree Traversal by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Practice by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Practice by Rupesh Tiwari (@rupeshtiwari) on CodePen.
O(Log(n)) time | Space O(1)
For 1 insert operation, avg case is O(log(n)) and worst case is O(n) For n insert operations, avg case is O(n log(n)) and worst case is O(n^2)
O(log n) time | space O(1)
O(log(n)) time | O(1)
See the Pen Binary Search Tree Implementation by Rupesh Tiwari (@rupeshtiwari) on CodePen.
Download solutions to Facebook Recruiting Portal Coding Interview Questions here.
Category: Graphs Difficulty: Easy
See the Pen Graph: DFS Question (easy) by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Graph: DFS Answer (easy) by Rupesh Tiwari (@rupeshtiwari) on CodePen.
Graph Depth First Search Explanation
Route Between Nodes: Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Answer Source Code Route Between Nodes
Minimal Tree: Given a sorted increasing order array with unique integer elements, write an algorithm to create a binary search tree with minimal height
What is Minimal Tree?
Minimal Tree Simulation
Answer for Creating Minimal Tree Interview Question
Binary Search Tree (BST): is a binary tree in which for each node value of all the nodes in the left subtree is lesser or equal to the root node. And the values of all the nodes in the right subtree is greater than the root node.
In order to find a tree as BST we must define each node range that is its outer and inner bound values and iterate the tree and compare their ranges.
Is Binary Search Tree Algorithm
Is Binary Search Tree Algorithm Simulation
Is Binary Search Tree Coding Files
There are 3 conditions you should think:
Delete where there is no children
Delete node where there is 1 child
Delete node where there are 2 children
Delete 15 from BST
See the Pen Delete node in BST Question by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Delete node in BST Answer by Rupesh Tiwari (@rupeshtiwari) on CodePen.
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>
Case 1: If Node has right sub-tree. Then go deep to left-most node in right subtree or find the min in the right subtree.
Case 2: If Node has no right child then go to the nearest ancestor for which given node would be in the left tree.
Example: Find in-order successor of 12?
Example: Find in-order successor of 6?
See the Pen Find In-order Successor in BST Question by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Find In-order Successor in BST Answer by Rupesh Tiwari (@rupeshtiwari) on CodePen.
x to the power n Brute Force
x to the power n using simple recursion un-optimized
x to the power n using optimized recursion with multiple subproblems
Modular Exponentiation is the remainder dividing up on Pow(x,n) by M.
[2,4,10,10,10,18,20] find first and last occurrence of number 10.
[1,1,3,3,5,5,5,5,5,9,9,11] How many 5's here?
[11,12,15,18,2,5,6,8] how many times this sorted array is rotated?
💡 Hint: Once we find the pivot in this array then the index of the pivot will give you the rotation count.
Circularly sorted array means a rotated sorted array. Find index of 8 in [12, 14, 18, 21, 3, 6, 8, 9] array.
💡 Hint:
- Brute Force =>
O(n)search each element of an array. Don't code for it. - Optimized =>
O(logN)
Circularly sorted array will have at least one half completely sorted.
And the other half where you have the pivot element there elements will be also sorted after pivot element.
Try Binary Search.
See the Pen Reverse Linked List: Answer by Rupesh Tiwari (@rupeshtiwari) on CodePen.
See the Pen Find merge point of 2 linked list Answer by Rupesh Tiwari (@rupeshtiwari) on CodePen.
Binary Search is used to solve 2 kinds of problems: 1- Search problems, find real numbers. 2- Optimization problems. Maximize element x keeping y minimum. Or minimize element x keeping y maximum.
Next you have to solve some basic binary search problems.
- Do all basics problems related to binary search that I have given in this link
- Next do all below advanced problems
Below problems are lying under optimization problems. Just watch Book Allocation and Aggressive Cows videos (links are below) to understand optimization logic. Once you understood them after that for rest problems you need to apply same logic. Every iteration you reduce the search space by either maximizing or minimizing the solution.
It is useful for optimization problem. Below is the template for Greedy Algorithm.
- Watch this video from Love Babbar
- Watch these videos to learn greedy algorithm
- Find the solutions of the problems shared by Love Babbar here
getOptimal(items, n)
1- Initialize result as 0
2- while(all items are not considered) {
i = selectAnItem()
if(feasible(i))
result = result +1;
}
3- return result;See the Pen Min Coins by Rupesh Tiwari (@rupeshtiwari) on CodePen.
Note: Greedy Algorithms may not work always like Longest Path in Binary Tree.
Below are the standard problems solved by Greedy Algorithms. I have solved first 4 problems listed below:
https://codepen.io/collection/QWbzGB
- Activity Selection
- Fractional Knapsack
- DIEHARD
- DEFKIN
- Job Sequencing
- Huffman Coding
- Prim's Algorithm
- Kruskal's algorithm
- Dijkstra's algorithm
- Finding close to optimal solutions for
NP Hard ProblemlikeTravelling Salesman Problem
Merge 2 smallest and make one node. Next select 2 smallest and make one node. Repeat the merge process
Always select 2 minimum one is called as Greedy Algorithm. This is called as Optimal Merge Pattern Tree which is Greedy approach
- Take a LEFT then go extreme RIGHT to get predecessor of given node
- While going right update predecessor
- Take a RIGHT then go extreme LEFT to get successor of given node
- While going left update successor
Read the given constraints before coding and applying algorithm.
If N < 10^5 then you must solve the problem in run time complexity of O(N) or O(N log (n))
If constraints are given then read them and then decide complexity.
| N | RunTime Complexity |
|---|---|
| N < 4000 (10^3) | O(n^n) or O( n log(n)) |
| 10^5 | O(n) or O(n log (n)) |
| 10^9 | O(log(n)) or O(1) |
Examples:
https://www.codechef.com/problems/DECODEIT This should be done within O(n) or O(n log (n))
While learning DS solve problems for the same DS also. Example if you are learning string then solve the problems for the string.
- Number Theory
- Sorting Algorithms
- Merge
- Quick
- Searching
- Linear
- Binary
- Recursion & Backtracking
- Greedy
- Graph
Every topic finish 30 to 40 questions. For Array, String, Recursion and Graph do more than 50 questions.
Go to practice page: https://practice.geeksforgeeks.org/explore/?page=1
Every day do below:
- 3 easy questions
- 2 medium questions
- 1 hard question
- http://btholt.github.io/four-semesters-of-cs/
- https://btholt.github.io/four-semesters-of-cs-part-two/
- Binary Tree Visualization
- [Part 3] Binary Search, Competitive Programming Series | from Zero to Advanced