All posts in Algorithms
Problem statement Given a matrix in which each row and each column is sorted, write a method to find an element in it. Solution Assumptions: 1. Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order. 2. Matrix is of size . . . . Read more
Problem Statement Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents Solution This is a recursive problem, so let’s figure out how to do makeChange(n) using prior solutions (i . . . Read more
Problem Statement Implement an algorithm to print all valid (e g , properly opened and closed) combinations of npairs of parentheses Example Input: 3 (e g , 3 pairs of parentheses) Output: ()()(), ()(()), (())(), ((())) Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class PrintAllValidParens { static void solve(int l, int r, int i, char[] str) { if (l == 0 && r == 0) { System.out.println(new String(str)); } else { if (l > 0) { str[i] = '('; solve(l  1, r, i + 1, str); } if (r > 0 && r > l) { str[i] = ')'; solve(l, r  1, i + 1, str); } } } public static void main(String[] args) { solve(3, 3, 0, new char[6]); } } 
Problem Statement Write a method to compute all permutations of a string Solution Let’s assume a given string represented by the letters To permute set , we can select the first character, , permute the remainder of the string to get a new list Then, with that new list, we . . . Read more
Problem statement You are given two 32bit numbers, and , and two bit positions, and . Write a method to set all bits between and in equal to (e g , becomes a substring of located at and starting at ) Example Input: , , , Output: Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class SetBits { public static int updateBits(int n, int m, int i, int j) { int max = ~0; /* All 1’s */ // 1’s through position j, then 0’s int left = max  ((1 << j)  1); System.out.println(Integer.toBinaryString(left)); // 1’s after position i int right = ((1 << i)  1); System.out.println(Integer.toBinaryString(right)); // 1’s, with 0s between i and j int mask = left  right; // Clear i through j, then put m in there return (n & mask)  (m << i); } public static void main(String[] args) { updateBits(1024, 21, 2, 6); } } 
Problem Statement Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height. Solution We will try to create a binary tree such that for each node, the number of nodes in the left subtree and the right subtree are equal, if possible Algorithm: . . . Read more
Problem statement Given an array of integers, find the second smallest integer in that array. Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

public class SecondSmallestInteger { public static int solve(int[] arr) { int smallest = Integer.MAX_VALUE; int secondSmallest = Integer.MAX_VALUE; ; for (int i = 0; i < arr.length; i++) { if (arr[i] < smallest) { secondSmallest = smallest; smallest = arr[i]; } else if (arr[i] == smallest) { secondSmallest = smallest; } else if (arr[i] < secondSmallest) { secondSmallest = arr[i]; } } return secondSmallest; } public static void main(String[] args) { int[] arr = { 1, 2, 7, 10, 100, 999, 2, 0, 34, 42 }; int ans = solve(arr); Arrays.sort(arr); if (ans == arr[1]) { System.out.println(ans); } else { System.out.println("Problem"); } } } 
Problem statement There are stairs, a person standing at the bottom wants to reach the top. The person can climb either stair or stairs at a time. Count the number of ways, the person can reach the top. Solution We can solve this problem recursively. If the person were to . . . Read more
Over the last few years I have applied and interviewed at a number of tech firms such as Google, Yelp, Microsoft, Amazon, Adobe and other big names. I have received offers from Palantir, Workday, Flixbus, etc. In order to be successful during those interviews (but also as an engineer in . . . Read more
Problem statement Given a linked list, determine if it has a cycle in it. Solution For the solution we are going to use a technique known as the twopointer technique. That is we will involve two pointers: one slowrunner and the other fastrunner. The slowrunner will move forward 1 list . . . Read more