Coding Interview is ubiquitous now across most of the companies and primarily used to filter out developers for the interview process. The argument that coding interview is an ideal test to determine the quality of the developer is very much debatable. Candidates fail the coding interview not because they are necessarily bad programmers/developers but because they are not trained and prepared for competitive programming. Competitive programming techniques are rarely used in real life production code, but are vital to crack the coding interview problems. Below are some of the key points, important algorithms and vital techniques to do better in competitive programming.
Key Points to Remember
- Always check for edge cases, e.g. number is zero or negative (also one in some cases), array or string is empty or null etc.
- Always check for missing counter++ or counter-- in while loops before running code.
- Always check the index boundary first in any (if/while) condition, to avoid index out of bounds exception with other conditions in the if/while statement.
- Anytime incrementing the array index, check if it is above the array length.
- When looping a matrix, we first loop to matrix.length, then matrix[i].length. Avoid while loops for matrix. When using while loops over a matrix, don't forget to reset the outer counter to 0.
- Every iterative or recursive solution should begin with the check for the exit case.
- Avoid preemptive checks before the recursive method call, as this adds duplicate logic, complicates the code and makes it harder to debug.
- To find the smallest amount of integers from the given array which total to the target sum, avoid the misconception of selecting the largest numbers first, it doesn't work always.
- When combining two keys into a single key string for a hash map, always have a separator between the complex two keys.
- While working with linked lists and updating the Head, Tail or Current node, always remember that "tail.next = newNode" is not enough, also need to point the tail to the new node "tail = newNode".
- Always prefer HashSet instead of HashMap if logic requires to select elements matching a given criteria, ignoring the count.
- Anytime when its required to store the index of the elements then always use HashMap instead of ArrayList.
- Always strive for better performance even at the cost of extra memory, as memory is cheap today.
Recursion to Iteration
Any recursive algorithm can be rewritten as iterative and vice versa. Iterative algorithm is generally preferred over recursive algorithm as recursion consumes limited stack memory as compared to larger heap space. A Recursion can be converted into Iteration by having a while loop and a data structure which can vary from a simple string or an array, but preferably a stack. If recursion has two or more recursive calls immediately following one another, then to preserve the order of the calls, we have to add them in the reverse order to the stack. The stack contains the variable and also holds the return value. If the stop condition is reached, check whether the stack is empty. If the stack is not empty, pop() and jump to the appropriate variable (label). If the stack is empty, return the result.
class Node {
int data;
Node left, right;
}
public void preorderRecursive(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
public void preorderIterative(Node root) {
if (root == null) {
return;
}
Stack<Node> stack = new Stack();
stack.push(root);
while (!stack.empty()) {
Node current = stack.pop();
System.out.print(current.data + " ");
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
Time Complexity
While calculating the time complexity (Big-O) it is very important to not ignore the copying of array, string and other manipulations within the loops.
Below are few examples of recursive calls and their corresponding time complexity.
Time Complexity : O(n)
recursive1(int n) {
if(n <= 1)
return;
recursive1(n - 1);
}
Time Complexity : O(2^n)
recursive2(int n) {
if(n <= 1)
return;
recursive2(n - 1);
recursive2(n - 1);
}
To determine the time complexity for recursion were the size of the list is divided into smaller list by some factor, then
n / (factor pow k) = 1, which gives k = log factor (n).
Here n is size of the list, and k is the levels of recursion.
If factor is 2, then n / (2 pow k) = 1, which gives k = log2(n)
Space Complexity
Avoid including the size of the result returned in deterring the space complexity.
Space complexity of recursive function, include any of the stack space taken up by function calls.
ASCII & Unicode
ASCII defines 128 characters, which map to the numbers 0–127. Unicode defines (less than) 2 power(21) characters, which, similarly, map to numbers 0 – 2 power(21). Unicode is a superset of ASCII, and the numbers 0–127 have the same meaning in ASCII as they have in Unicode. For example, the number 65 means "Latin capital 'A'". ASCII uses an 8-bit encoding while Unicode uses a variable bit encoding i.e. 32, 16, and 8-bit encodings. Because Unicode characters don't generally fit into one 8-bit byte, there are numerous ways of storing Unicode characters in byte sequences, such as UTF-32 and UTF-8.
String
Palindrome is a sequence of characters which reads same backward as forward. If the string has odd length like "abcba" then it has a unique character at the center, otherwise for even length like "abba" all character count is even. Hence all characters should occur an even number of times, except one. If more than one characters appear an odd number of times, then the string cannot be a palindrome.
To check if the String is a palindrome: Take two pointers i pointing to the start of the string and j pointing to the end of the string. Keep incrementing i and decrementing j while i < j and at every step check whether the characters at these pointers are same or not. If not then the string is not a palindrome else it is.
Two Pointer Approach is used for the string problems such as to reverse a string/array. In such case we have one pointer at start, while another pointer at the end, each moving in opposite direction and swapping its corresponding values.
Problems which require to find a substring or subarray with certain attributes (especially repeating attributes) and x number of changes, then it's a sliding window problem. Sliding window also has two pointers, initially both are at start, then the second pointer moves forward, while first is still at start. Once the second pointer moves to position when certain attributes are not satisfied, then depending on the problem the first pointer moves by one or other location.
Arrays
Never use switch/if-else statements for long list of mappings for example character to count, number to word etc. HashMap can be used in such cases. But always prefer to use arrays such that index is the code (character or number), while element is the value.
Always try to sort the array of the options, when we get to the point that the option is greater than the required value then we can break the loop, skip rest of the higher options, since the array was sorted.
int[] result = new int[26];
for(char c: someString.toCharArray()) {
result[c-'a']++
}
Given a fixed length array which can have 2 possible values, either zero or one (vacant or empty), then total possible unique combinations is 2^ArrayLength. If 10^9 operations are performed on the array, the total combinations of values produced are within 2^ArrayLength with cycles. Hence the Nth operation value can be found by N % 2^ArrayLength, and finding the corresponding combination value.
Quick Sort Implementation: Always select the last element in the list as pivot. Swap the elements less than pivot, with the elements from the start of the list. Finally move the pivot element from the end of the list to the position after the last swapped element which was smaller than pivot. Now the list is partitioned, with all elements before pivot are smaller than the pivot, while elements after the pivot are larger than pivot. Now call sort method recursively on the two lists excluding the pivot element, to sort them. Best case performance is O(n log n), while worst case performance is O(n^2).
private int partition(int[] array, int low, int high) {
int pivot = array[high];
int i = low;
for(int j = low; j <= high - 1; j++) {
if (array[j] < pivot) {
swap(array, i, j);
i++;
}
}
swap(array, i, high);
return i;
}
private void quickSort(int[] array, int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
Number Division
If given an integer and asked to convert it to words or reverse a number or add/remove digits etc, then NEVER convert it to char array.
int reversed = 0, pop;
while(x != 0) {
pop = x % 10;
x /= 10;
reversed = (reversed * 10) + pop
}
Below is the key logic to convert number to words, refer the entire code.
int i = 0;
String words = "";
while (num > 0) {
if (num % 1000 != 0) {
words = numberToWordHelper(num % 1000) + THOUSANDS[i] + " " + words;
}
num /= 1000;
i++;
}
private String numberToWordHelper(int num) {
if (num == 0)
return "";
else if (num < 20)
return LESS_THAN_20[num] + " ";
else if (num < 100)
return TENS[num / 10] + " " + numberToWordHelper(num % 10);
else
return LESS_THAN_20[num / 100] + " Hundred " + numberToWordHelper(num % 100);
}
Binary Search
Binary Search Recrusive: O(log n)
public int binarySearchRecursive(int[] sortedArray, int key, int low, int high) {
int middle = (low + high) / 2;
if (high < low) {
return -1;
}
if (key == sortedArray[middle]) {
return middle;
} else if (key < sortedArray[middle]) {
return binarySearchRecursive(sortedArray, key, low, middle - 1);
} else {
return binarySearchRecursive(sortedArray, key, middle + 1, high);
}
}
Binary Search Iterative
public int runBinaryIterative(int[] sortedArray, int key, int low, int high) {
int index = Integer.MAX_VALUE;
while (low <= high) {
int mid = (low + high) / 2;
if (sortedArray[mid] < key) {
low = mid + 1;
} else if (sortedArray[mid] > key) {
high = mid - 1;
} else if (sortedArray[mid] == key) {
index = mid;
break;
}
}
return index;
}
Anytime in the problem it is mentioned to "Find the smallest number for ...", then start with number = 2, and use (number << 1) or (number * 2) to increment rather than number++, so that number is incremented as 2,4,8,16,32,64,128 etc. Then find the midpoint between the previous number (failing the condition) and the current number, and use binary search logic to determine the exact smallest number with some condition.
Linked List
Array element shifts are very expensive especially for sort and similar operations. Hence Linked List is preferred in such case. Rather than shifting and swapping elements, two different linked lists are created to maintain elements less than and elements greater than or equal to.
The Two pointer approach works well for LinkedList problems.
- Have one slow pointer moving by (i+1), while another fast pointer move by (i+2).
- Have one slow pointer point to the first element while the another fast pointer move over the rest of the elements.
Calculating the mid point of the list is frequently used for quick sort or similar approaches.
right - left = 2(midpoint - left) midpoint = left + (right - left)/2
Stack and Queue
- Implementing stack requires a variable to keep track the top of stack. If the top of the stack is null then the stack is empty.
- Implementing queue requires 2 variables to track the front and the end of the queue. When front (or last) is null then queue is empty, and elements are added to the end/last node of the queue.
Monotonic Stack
A monotonic stack is a stack of elements that are incremented or monotonically decremented on the stack and can only be manipulated at the top of the stack. Monotonic stack maintenance is O(n) time complexity, all elements will only enter the stack once. Before the element is added to the stack, the element that destroys the monotonicity at the top of the stack is deleted. It mainly used to solve the problems to find the Next Greater Element or range queries in an array.
Whenever we see a number x greater than stack.peek() we pop all elements less than x. For all the popped elements, their next greater element is x.
public int[] dailyTemperatures(int[] T) {
int[] ans = new int[T.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < T.length; i++) {
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
ans[stack.peek()] = i - stack.pop();
}
stack.push(i);
}
return ans;
}
public int[] nextGreaterElement(int[] findNums, int[] nums) {
Map<Integer, Integer> map = new HashMap<>(); // map from x to next greater element of x
Stack<Integer> stack = new Stack<>();
for (int num : nums) {
while (!stack.isEmpty() && stack.peek() < num)
map.put(stack.pop(), num);
stack.push(num);
}
for (int i = 0; i < findNums.length; i++)
findNums[i] = map.getOrDefault(findNums[i], -1);
return findNums;
}
Trie
Trie is a tree data structure often used for storing characters representing collection of strings. If two strings have a common prefix then they will have the same ancestor in this tree. Trie is used for word validations, find all the words, used for prefix based search.
Initially TrieNode has empty root node with empty map, which is the current node. In order to store a string into Trie, we scan each its character, check if it is present in the Map of the current node. If character is present in the map, then we jump to the node using the reference value for the character key in the map, making it the current node. If character is not present then add the character to the map of the current node, with the value being reference to the newly created instance of TrieNode, which now becomes the current node for the next character. For the last character of the string the isEndOfWord flag is true. Finally, all the leaf TrieNode have empty maps. Time complexity is O(mn), were m is average length of string and n is total strings to be added.
In prefix based search to find if the string starting with prefix exists, we check the map for prefix character, jump to next node referenced, until all prefix characters are present in corresponding node's map. The full word check also works the same, only we check if the last character's TrieNode has isEndOfWord true.
private final TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
node = new TrieNode();
current.children.put(ch, node);
}
current = node;
}
current.endOfWord = true;
}
public boolean search(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
return false;
}
current = node;
}
return current.endOfWord;
}
Disjoint Set
A disjoint set is a group of sets where no item can be in more than one set. It is also called a union–find data structure as it supports union and find operation on subsets.
Find operation returns the group the element belongs to. It determines in which subset a particular element is in and returns the representative of that particular set. An item from this set typically acts as a "representative" of the set.
Union operation merges two different subsets into a single subset, and the representative of one set becomes representative of another.
The disjoint–set also supports one other important operation called MakeSet, which creates a set containing only a given element in it.
In order to create Union Find, we first construct a bijection or a mapping between the objects and the integers in the range [0, n). We randomly assign a mapping between the objects and the integers which is stored in a HashMap. Then construct an array which has values as indexes, were each index is associated with an object using the previous HashMap mapping. Initially each object referenced by the index in the array is a root node. As union operation e.g. Union(A,J) are executed, the objects A and J would have parent-child relationship (Parent A -> Child J), such that the index which mapped to object J is now updated to index of object A in the array. Ideally either object passed in union operation can be the parent. As this process continues the size of each group increases. If a union operation has to be performed on two objects from different group, then first the root node of the smaller group is determined and then its corresponding index is updated with the index of the root node for the larger group.
In order to find which component a particular element belongs to find the root of that component by following the parent nodes until a self loop is reached. The time complexity increases to find the root node as each node points to its parent which ultimately points to the root node along the chain. To enhance the performance we use path compression were each child object in the group now points to the root node of the group.
1. The first way, called union by rank, is to always attach the smaller tree to the root of the larger tree. Since it is the depth of the tree that affects the running time, the tree with a smaller depth gets added under the root of the deeper tree, which only increases the depth of the depths were equal. Single element trees are defined to have a rank of zero, and whenever two trees of the same rank r are united, the result has the rank of r+1. The worst-case running-time improves to O(log(n)) for the Union or Find operation.
2. The second improvement, called path compression, is a way of flattening the tree’s structure whenever Find is used on it. The idea is that each node visited heading to a root node may as well be attached directly to the root node; they all share the same representative. To effect this, as Find recursively traverses up the tree, it changes each node’s parent reference to point to the root that is found. The resulting tree is much flatter, speeding up future operations not only on these elements but on those referencing them, directly or indirectly.
import java.util.HashMap;
import java.util.Map;
class DisjointSet {
private Map<Integer, Integer> parent = new HashMap();
// stores the depth of trees
private Map<Integer, Integer> rank = new HashMap();
public void makeSet(int[] universe) {
// create n disjoint sets (one for each item)
for (int i: universe) {
parent.put(i, i);
rank.put(i, 0);
}
}
// Find the root of the set in which element k belongs
public int Find(int k) {
// if k is not the root
if (parent.get(k) != k) {
// path compression
parent.put(k, Find(parent.get(k)));
}
return parent.get(k);
}
// Perform Union of two subsets
public void Union(int a, int b) {
// find the root of the sets in which elements x and y belongs
int x = Find(a);
int y = Find(b);
// if x and y are present in the same set
if (x == y) {
return;
}
// Always attach a smaller depth tree under the root of the deeper tree.
if (rank.get(x) > rank.get(y)) {
parent.put(y, x);
}
else if (rank.get(x) < rank.get(y)) {
parent.put(x, y);
}
else {
parent.put(x, y);
rank.put(y, rank.get(y) + 1);
}
}
}
Trees
A binary search tree is a binary tree in which every node fits a specific ordering property: all left descendents <= n < all the right descendents.
Graphs
Adjacency List is the most common way to represent a graph. Every vertex (or node) stores a list of adjacent vertices. In an undirected graph, an edge like (a, b) would be stored twice: once in a's adjacent vertices and once in b's adjacent vertices.
class Graph {
public Node[] node s; // HashMap<Node, LinkedList<Node>> adjacencyMap;
}
class Node {
public String name;
public Node[] children; // Not required when adjacencyMap is used in Graph
public boolean visited; // For BFS
}
Adjacency matrix is an NxN boolean matrix (where N is the number of nodes), where a true value at matrix[i][j] indicates an edge from node i to node j. (Can also use integer with Os and 1s). In an undirected graph, an adjacency matrix will be symmetric.
Topological Sorting
Topological sorting of vertices of a Directed Acyclic Graph is an ordering of the vertices v1,v2,...,vn in such a way, that if there is an edge directed from vertex vi towards vertex vj i.e. (vi -> vj), then vi comes before vj. Hence topological sort algorithm takes a directed graph and returns an array of the nodes where each node appears before all the nodes it points to. A cyclic graph do not have any valid topological orderings. Topological sort is generally used for problems involving ordering of dependent items.
We implement topological sort using a boolean array of visited nodes, and a stack to maintain all nodes in topological sorted order. To find topological sort, we start with any node. If the current node is not visited, then we add the node as visited and explore children of the node, adding them first to the visited array. If node has no children i.e. it is completely explored then the node is added to the stack and we go back to the parent node. We continue visiting all the children of current node until all of them are visited. Finally return the topological sort by popping the nodes from the stack.
public class Graph {
private int vertices;
private List<List<Integer> > adjacencyList;
Graph(int v) {
vertices = v;
adjacencyList = new ArrayList<ArrayList<Integer> >(v);
for (int i = 0; i < v; ++i) {
adjacencyList.add(new ArrayList<Integer>());
}
}
public void addEdge(int v, int w) { adjacencyList.get(v).add(w); }
private void topologicalSort(int v, boolean[] visited, Stack<Integer> stack) {
visited[v] = true;
for (Integer i : adjacencyList.get(v)) {
if (!visited[i]) {
topologicalSort(i, visited, stack);
}
}
stack.push(v);
}
public void topologicalSort() {
Stack<Integer> stack = new Stack<>();
boolean visited[] = new boolean[vertices];
for (int i = 0; i < vertices; i++) {
if (!visited[i]) {
topologicalSort(i, visited, stack);
}
}
// Print contents of stack
while (stack.empty() == false) {
System.out.print(stack.pop() + " ");
}
}
}
Depth First Search (DFS)
In Depth-first search (DFS), we start at the root (or another arbitrarily selected node) and explore each branch completely before moving on to the next branch. That is, we go deep first before we go wide. It is simpler and mostly used to visit every node in the graph.
public void dfs(int start) {
boolean[] isVisited = new boolean[adjVertices.size()];
dfsRecursive(start, isVisited);
}
private void dfsRecursive(int current, boolean[] isVisited) {
isVisited[current] = true;
visit(current);
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
dfsRecursive(dest, isVisited);
}
}
Whenever asked for permutations or combinations then typically it can be solved by DFS with recursion. Simulate taking and not taking the current element in the list.
findCombinations(int[] array, index, target, List<Int> current, List<List<Int>> combinations) {
if(target == 0) {
combinations.add(current);
return;
}
if(target < 0) {
return;
}
for(int i = index; i < array.length; i++) {
if(i == index || array[i] == array[i-1]) {
current.add(array[i])
findCombinations(array, i+1, target - array[i], current, combinations);
current.remove(array.size() - 1)
}
}
}
Breadth First Search (BFS)
In Breadth-first search (BFS), we start at the root (or another arbitrarily selected node) and explore/visit each neighbor before going on to any of their children. That is, we go wide before we go deep. It is used o find the shortest path. It is usually implemented using an iterative solution with a queue.
public void breadthFirstSearch(Node node) {
if (node == null)
return;
LinkedList<Node> queue = new LinkedList<>();
queue.add(node); // Add first Node
while (!queue.isEmpty()) {
Node currentFirst = queue.removeFirst();
// If node already visited/added to queue then skip
if (currentFirst.isVisited())
continue;
// Mark the node as visited
currentFirst.visit();
System.out.print(currentFirst.name + " ");
LinkedList<Node> allNeighbors = adjacencyMap.get(currentFirst);
if (allNeighbors == null)
continue;
for (Node neighbor : allNeighbors) {
if (!neighbor.isVisited()) {
queue.add(neighbor);
}
}
}
}
Dynamic Programming
To solve any problem using Dynamic Programming the problem should have an optimal substructure (allows recursion) and overlapping subproblems. Any combination problem can be solved by Dynamic Programming.
Dynamic programming problems can be solved by either using Recursion (Top Down) and Memoization, or Tabulation (Bottom Up). In Top-Down approach, the problem is implemented using recursion and memoization achieved by adding hash map to store the duplicate computation. In the Bottom-up approach, we start the transition from our base state i.e DP[0] and follow our state transition relation to reach our destination state DP[n].
Below are important steps in solving a dynamic programming problem.
- Identify the changing parameters and determine the number of subproblems.
- Visualize and represent the given problem with a tree like structure on a drawing board with root as the input, children as sub-problems, edges as each combination steps and the leaves the end result for selected branch combination. This gives clear insight and understanding of the problem.
- From the above dynamic programming tree, if the height of the tree is n and each node has m children then the total time complexity is O (m^n), and the space complexity is the height of the tree i.e. n. If the tree were to be a binary tree were m is 2, then time complexity becomes O(2^n).
- Clearly express the recurrence relation.
Tabulation Approach
- Create a table with the length equal to the length of the input, plus one for the base case. Hence the length of array is target input value + 1, such that array[target-input] is the last value. The input which changes throughout the problem is used to determine size of the array for tabulation. Generally based on the type of the answer to be returned, that corresponding type is used as values for the array. If there are two target inputs then its two dimensional array.
- Initialize the array to default values, for e.g. numbers are initialized to 0 while boolean to True/False.
- Decide the trivially smallest input and add the solution for this smallest subproblem. Typically base case is added for index 0 (and 1) when either the number is 0 or char is empty etc.
- Every index of the array corresponds to the subproblem input to the problem function.
- Iterate through the table and fill in further positions based on the values in the current position.
- Determine the logic for filling the positions can be based on the recursive version of function.
For example, the coin change problem requires us to determine the fewest number of coins needed to make up the required amount. First we determine the smallest number of coins to make up 0 amount, then 1 amount, then N-1 amount finally N amount. The logic can be represented by below pseudo code.
for 0 to N amount // --- i
for each coin in coins[] // --- j
if(coin value is less then amount) then we select the coin
df[i] = Math.min(dp[i], 1 + dp[i - coins[j]])
No comments:
Post a Comment