My favourite fiz-buzz problem for Senior Programmers

This post, I will be discussing one of my favourite fiz-buzz problems for senior programmers/engineers. 

Find Kth largest element from a list of 1 million integers. 

Or

Find Kth largest element at any given point of time from a stream of integers, count is not known. 

This problem is interesting as it has multiple approaches to solve and it checks the fundamentals of algorithms and data structure. Quite often, candidate start with asking questions like is the list sorted? Or can I sort the list ? In such case, I go and check on which sorting algorithm the candidate proposes. This gives me an opportunity to start conversation around complexity of the approach (particularly, time complexity). Most of the candidates are quick to point out algorithms (like Quick Sort , Merge Sort) which take O(NlogN) for sorting a list. This is right time to point out that why do you need to sort the complete array/list if you just need to find out 100th or kth largest/smallest element. Now the conversation usually go in either of the direction - 

1. Candidate sometime suggest that, sorting is more quicker way to solve this problem - missing altogether the complexity aspect. If someone doesn't even realize that sorting is not the right way to handle this problem, then it kind of red signal for me. 
2. At times candidates acknowledge the in-efficiency of sorting approach and then start looking for better approach. I suggest, candidates to think out loud which will give me insight about their thought process and how are they approaching it. When I see them not moving ahead; I suggest them on optimizing Quick sort approach ? Is there any way to cut down the problem size in half in every iteration ? Can you use divide and concur to improve on your O(NlogN) complexity ?   

This problem can be solved by Quick Select as well as using Heap data structure. This problem also has a brute force approach (i.e. run loop for k time; in each iteration find the maximum number lower than the last one). 

If the candidate doesn't make much progress then I try to simplify the problem by saying - find 3rd or 2nd largest element. I have seen some of the senior programmers failing to solve this trivial version as well. This is clear Reject sign for me.

Also, sometime I don't even ask candidate to code. I use this problem to just get an idea and skip the coding part if i see a programmer sitting right across me :)

-Happy problem solving !

Count number of different bits in two Numbers

Problem:
Given two numbers, find how many bits are different in two numbers.
Or, another way to look at problem is - Determine number of bits required to convert num_1 to num_2.

num_1 = 1
num_2 = 0
Number of different bits = 1

num_1 = 11111
num_2 = 01110
Number of different bits = 2

Solution:
Basically we need to find at each position if the value of bit in two number is same or different. If they are different then increase the counter and do the same for all subsequent bits.

It might not be very obvious from the problem but there is a bit operator which exactly finds out how different two inputs are. Let's apply XOR operator and see how it behaves:

1 ^ 0 = 1
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 1 = 0

So notice that, when bits are same output is always 0. And when both bits are different then output is 1.

    11111
^  01110
-------------
    10001

So after taking XOR, we just need to count the number of 1's in the result.


Java Implementation

public static int countNumberOfDifferentBits(int a, int b){
       int xor = a ^ b;
       int count = 0;
       for(int i= xor; i!=0;){
            count += i & 1;
            i = i >> 1;
       }
}

Binary Tree Level Order Traversal

Pre-order, In-order and Post-order traversal of tree use Depth First Search (DFS). These are called DFS since these techniques visit the tree deeper and deeper until it reaches the leaf node. Level-order traversal (as the name suggest) visits the nodes level by level. Level Order Traversal is Breadth First Search(BFS). Below diagram shows Level Order traversal of a binary tree. 

Let's see implementation techniques:

Without Using External Storage

Applying recursion in BFS traversal is non-trivial. So in this case, the most obvious approach could be to print the nodes at each level iteratively. Above tree has three level, which equals the height of the tree. Now, how do we print all nodes at a given level?

To print nodes at level 2(i.e. 2 and 3), we need to start at the root and keep traversing down the tree recursively. Each time we go one level down the level value needs to be reduced by 1. This way both left and right subtree will keep going down the tree independently until the level becomes 1.

   public void levelOrderIteratively(){

    int height = this.getHeight(root);

    for(int i=1; i<= height; i++){

    printNodesAtGivenLevel(root, i);

    }

    }

//other methods are given in full implementation

The below implementation prints all nodes in the same line. In above method, we are calling a separate method to print for each level so we can format it the way we want (something like below can be easily done by tweaking above for loop. 

Nodes at level 1 = 1 
Nodes at level 2 = 2 3 
Nodes at level 3 = 4 5 6 

Using external storage / Using Queue

One of the de-facto approaches to implementing any breadth-first traversal is using Queue (First in First out data structure). BFS enables to visit nodes of the tree level by level. 

Java Implementation

Below java implementation provides level order traversal using an iterative technique which doesn't require extra storage as well as using Queue. 

package algo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Generic Binary Tree Implementation
 * @author Siddheshwar
 *
 * @param <E>
 */
public class BinaryTree<E> {
 /**
  * Root node of the tree
  */
 Node<E> root;

 /**
  * Node class to represent each node of the tree
  */
 static class Node<E> {
  E data;
  Node<E> left;
  Node<E> right;

  Node(E d) {
   this.data = d;
   this.left = null;
   this.right = null;
  }
 }

 /**
  * Get height of the tree
  * 
  * @param node
  *            root node
  * @return height of the tree which is max of left subtree height or right
  *         subtree height + 1 (for root)
  */
 public int getHeight(Node<E> node) {
  if (node == null) {
   return 0;
  }

  return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
 }

 /**
  * Print binary tree in level-order
  */
 public void levelOrderIteratively() {
  int height = this.getHeight(root);
  for (int i = 1; i <= height; i++) {
   printNodesAtGivenLevel(root, i);
  }
 }

 /**
  * Print nodes at the given level
  * 
  * @param node
  *            first call with root node
  * @param level
  *            first call with the level for which we need to print
  */
 private void printNodesAtGivenLevel(Node<E> node, int level) {
  if (node == null)
   return;

  if (level == 1) {
   System.out.print(node.data + " ");
   return;
  }

  printNodesAtGivenLevel(node.left, level - 1);
  printNodesAtGivenLevel(node.right, level - 1);

 }

 /**
  * Prints level order traversal using Queue
  */
 public void levelOrderQueue() {
  if (root == null) {
   return;
  }

  Queue<Node<E>> queue = new LinkedList<>();
  queue.add(root);

  while (!queue.isEmpty()) {
   Node<E> node = queue.poll();
   System.out.print(node.data + " ");

   if (node.left != null) {
    queue.add(node.left);
   }
   if (node.right != null) {
    queue.add(node.right);
   }
  }
 }

 /**
  * Method to test the tree construction
  */
 public static void main(String[] args) {
  BinaryTree<Integer> bt = new BinaryTree<Integer>();
  bt.root = new Node<>(1);
  bt.root.left = new Node<>(2);
  bt.root.right = new Node<>(3);
  bt.root.left.left = new Node<>(4);
  bt.root.right.left = new Node<>(5);
  bt.root.right.right = new Node<>(6);

  System.out.println(" height =" + bt.getHeight(bt.root));
  bt.levelOrderIteratively();
  System.out.println();
  bt.levelOrderQueue();
 }
}

--
keep coding !!!

Find if a word exists in a 2D grid

This problem is also known as Word Search Problem, found this on leetcode.

Problem:

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from the sequentially adjacent cell, where adjacent cells are those horizontally or vertically neighboring. The same letter may not be used more than once. 

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word : ABCCED -> true

              ABCB   -> false

Approach:

An initial glance at the 2D array confirms that at a given position there is more than one option to select next character. And if a given selected path fails to find the word then the search needs to backtrack and try out other options.  Below diagram illustrates this point - At S (row:1, col:3), we can start with either of E (up or down). But If we are looking for SEE, then choosing upper E will fail. 

We can apply Graph, depth-first traversal to check if the given input word exists in the 2D array. So we can start with the first character of the word and keep on checking if the next character of the input word is one of the neighbors of that character. Also, note that, if a neighbor is already considered then we need to discard that. 

Note: Characters can repeat in the 2D array. We need to abstract individual entries in the Node class which will keep row and column value along with the character. 

Implementation

Java implementation:

package backtracking;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;

/**
 * Searches for a word in a 2-D character array. Same character can be present at two different locations in the array.
 * Uses DFS to search the input array in the board.
 */
public class WordSearch {
 private char[][] board;
 private int ROW, COL;
 
 public WordSearch(char[][] board) {
  super();
  this.board = board;
  this.ROW = board.length;
  this.COL = board[0].length;
 }

 /**
  * DFS search.
  * 
  * @param yetToBeSearchedInputStr
  *            string which is yet to get searched in the 2-D array
  * @param currPos
  *            abstracts the character and it's row, col in the 2-D board
  * @param alreadyTravelled
  *            stores nodes which are already covered/travelled
  * @return true if the word was found in the board; false otherwise
  */
 private boolean search(String yetToBeSearchedInputStr, Node currPos,
   Set<Node> alreadyTravelled) {
  if (Objects.isNull(yetToBeSearchedInputStr)
    || yetToBeSearchedInputStr.length() == 0) {
   return true;
  }

  alreadyTravelled.add(currPos);
  List<Node> neighbors = getNeighbors(currPos);
  for (Node node : neighbors) {
   if (!alreadyTravelled.contains(node)
     && node.ch == yetToBeSearchedInputStr.charAt(0)) {
    return search(yetToBeSearchedInputStr.substring(1), node,
      alreadyTravelled);
   }
  }
  return false;
 }

 /**
  * Returns all valid neighbors (left, right, up, down) of the given node
  * @param currPos node for which all neighbors needs to be found
  * @return list of neighbors
  */
 private List<Node> getNeighbors(Node currPos) {
  int row = currPos.row;
  int col = currPos.col;

  List<Node> neighbors = new ArrayList<>();
  if (col - 1 >= 0) {
   neighbors.add(new Node(board[row][col - 1], row, col - 1));
  }
  if (col + 1 < COL) {
   neighbors.add(new Node(board[row][col + 1], row, col + 1));
  }
  if (row - 1 >= 0) {
   neighbors.add(new Node(board[row - 1][col], row - 1, col));
  }
  if (row + 1 < ROW) {
   neighbors.add(new Node(board[row + 1][col], row + 1, col));
  }
  return neighbors;
 }

 @Override
 public String toString() {
  for (int i = 0; i < ROW; i++) {
   System.out.println();
   for (int j = 0; j < COL; j++) {
    System.out.print(board[i][j] + " ");
   }
  }
  return "\n ROW=" + ROW + ", COL=" + COL;
 }

 /**
  * Abstracts the character and it's position (row and col) in the board.
  * This is required as same character can be present at two different
  * locations.
  */
 private class Node {
  char ch;
  int row;
  int col;

  public Node(int r, int c) {
   this.row = r;
   this.col = c;
  }

  public Node(char ch, int r, int c) {
   this(r, c);
   this.ch = ch;
  }
  
  @Override
  public int hashCode() {
   final int prime = 31;
   int result = 1;
   result = prime * result + getOuterType().hashCode();
   result = prime * result + ch;
   result = prime * result + col;
   result = prime * result + row;
   return result;
  }

  @Override
  public boolean equals(Object obj) {
   if (this == obj)
    return true;
   if (obj == null)
    return false;
   if (getClass() != obj.getClass())
    return false;
   Node other = (Node) obj;
   if (!getOuterType().equals(other.getOuterType()))
    return false;
   if (ch != other.ch)
    return false;
   if (col != other.col)
    return false;
   if (row != other.row)
    return false;
   return true;
  }

  @Override
  public String toString() {
   return "Node [ch=" + ch + ", row=" + row + ", col=" + col + "]";
  }

  private WordSearch getOuterType() {
   return WordSearch.this;
  }
 }

 /**
  * Test method
  */
 public static void main(String[] args) {
  char[][] board = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' },
    { 'A', 'D', 'E', 'E' } };
  WordSearch wordSearch = new WordSearch(board);
  System.out.println(wordSearch);
  Set<Node> alreadyTravelled = new HashSet<>();
  String inputString = "ABCCED";

  //first find if the first character exists in the board. Start below search for all the positions where it could be found
  //Not given logic to find the first character in the board.
  boolean f = wordSearch.search(inputString.substring(1),
    wordSearch.new Node('A', 0, 0), alreadyTravelled);
  System.out.println("Input String, "+ inputString +" exists in the 2-D character array? " + f);
 }
}

Note:

• search method performs the DFS search until the word becomes empty or the search fails. It takes the substring of the word which is yet to be verified.
• If you understand DFS properly, then this approach is quite straightforward. 

---
keep coding !!!

Integer to Binary Using Recursion

Problem:
Get binary equivalent of a number using Recursion.
getBinary(2)       = 10
getBinary(5)       = 101
getBinary(1024) = 10000000000

Iterative implementation of this problem is quite trivial. But here it's expected to be done recursively!

Approach 1

The approach is quite simple -  Divide the decimal value by 2 and write down the remainder. Repeat this process until you can't divide anymore. 

Calculate for 13,

 13/2 = 6 and remainder = 1

 6/2   = 3 and remainder = 0

 3/2   = 1 and remainder = 1

 1/2   = 0 and remainder = 1        

To get binary, we write down the value of reminder from bottom to top. So it gives 1101. Let's apply recursive thinking to solve this problem. 

Subproblem will be dividing the number by 2 in each iteration. 

Base Case - binary of 1 is 1 (or 0 is 0) . 

Combining subproblem result might be tricky as it needs to be done in a reverse way. This can be achieved if the method is called first (and then the remainder operation is performed). This will ensure that the remainder is performed only when base case is reached.

public static String getBinary(int num) {
 if (num < 2) {
  return "" + num;
 }

 return getBinary(num / 2) + num % 2;
}

Stack Progress
getBinary(13)
    --> getBinary(13/2) + 13%2
             --> getBinary(6/2) + 6%2
                     -->getBinary(3/2) + 3%2
                             -->getBinary(1)    //base case, return 1
                     --> ""+ 1+ 1
             --> ""+1+1+0
     -->""+1+1+0+1   

Approach 2

Let's explore on another approach which uses bit manipulation to generate a binary equivalent. 

Binary of 5 is 101. Now let's see if we can get the bit values (1, 0 and 1) of the number by some bit manipulation technique. 

5 & 100 = 100   

5 & 010 = 000

5 & 001 = 001

Notice that, And operation (&) is performed with a number whose all values are 0 except leftmost position. And then that keeps on shifting to the right side. And the output will be 1 at that position if the bit value is 1 in the number (and 0 otherwise).

When you apply recursive thinking, it's quite clear that method needs another argument which will help in getting bit value at a given position. Integer in Java is 32 bit long, so that number will take the initial value of 1 << 31 (i.e. leftmost bit is 1 and rest all are 0). And when all bit positions (from MSB to LSB) are explored the recursion should stop. 

public static String getBinary2(int num, int and){
 if(and == 0){
      return "";   //if all bits are checked; just return
 }

 /**
  * If value at position is 1 in num; it will give and value
  */
 int t = (num & and) == and ? 1 : 0;
 
 return ""+ t + getBinary2(num, and >>> 1);
}

String binary = getBinary2(5, 1<<31);

//binary = 00000000000000000000000000000101

Can you try to come up with stack progress as shown for first approach?
Do post your feedback/doubts below!
---
keep coding !!!

Longest Substring Without Repeating Characters

Problem:
Given a string, find the longest substring without repeating characters.
"abcabcd"  --> "abcd"
"aaaaaa"    --> "a"
"abcad"     --> "bcad"

Solution

This problem might be trivial if there is no restriction on time complexity. But if the expected time complexity is linear then it becomes quite interesting. Let's see how we going to approach to solve it. 

Once you start moving from left to right in the given input string (one character each time), there will be a need to find if the character already exists before? 

if the character doesn't exist earlier - continue further.

if the character exists earlier - this substring (starting from a given index) could be a potential answer. 

So we need a start index which points to the beginning of the current potential answer. And another index which keeps on incrementing to find that maximum substring. 

how to check if character is already found ?

str = "abac"

Assume, startIndex = 0, currentIndex = 2

The character at currentIndex(i.e. 'a') will have to be checked if it's already there in the substring before it (i.e. "ab"). Brute force approach to check if the character exists in the substring will result in complexity O(substring.length()).

We can optimize it by using hashing mechanism, but keep in mind that hashing technique will increase the space overhead. 

Java Implementation

 public static String longestSubstringWithoutRepeatingCharars(String str) {
  if (str == null || str.length() < 2) {
   return str;
  }

  Set<Character> unique = new HashSet<>();
  int startIndex = 0, endIndex = 0;
  char ch;
  String max = " ";

  while (endIndex < str.length()) {
   ch = str.charAt(endIndex);
   if (unique.contains(ch)) {

    // check if max can be optimized
    if (str.substring(startIndex, endIndex).length() >= max
      .length()) {
     max = str.substring(startIndex, endIndex);
    }

    // reset both indexes to find the next substring
    startIndex++;
    endIndex = startIndex;

    // reset set so that it can again store all unique chars
    unique.clear();
   } else {
    endIndex++;
    unique.add(ch);
   }
  }

  // check if max can be optimized
  if (str.substring(startIndex, endIndex).length() >= max.length()) {
   max = str.substring(startIndex, endIndex);
  }
  return max;
 }

longestSubstringWithoutRepeatingCharars("abcad");

output: bcad

Reference:
http://articles.leetcode.com/2011/05/longest-substring-without-repeating-characters.html

---
keep coding !!!

Insertion Sort

Insertion sort is one of the most fundamental comparison based stable sorting algorithm. It is also known as playing card sort. It is based on a fundamental principle that a single element array is already sorted.  A two element array requires single comparison to sort it. A three element array can be visualized as two sub arrays (first with 2 elements and second with one element). So in each iteration, a new value is added to an already sorted sublist. 

a1 = {101}   // already sorted
a2 = {101, 2} // can visualize it as, add 2 to a already sorted sub-array having 101
       {2, 101} // one comparison required to put 2 in proper place
a3 = {101, 2, 5} // a new number added to a2
        {2, 101, 5}
        {2, 5, 101}  // put 5 in proper place

To visualize how it works, check out animation on wikipedia.

Java Implementation

/**
 * Insertion sort implementation
 * 
 * @author Siddheshwar
 *
 */
public class InsertionSort {
 /**
  * Insertion sort in ascending order
  * 
  * @param arr
  * @return arr
  */
 public int[] sort(int[] arr) {
  int tmp = 0;
  for (int i = 1; i < arr.length; i++) {
   for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
    tmp = arr[j];
    arr[j] = arr[j - 1];
    arr[j - 1] = tmp;
   }
   print(arr);
  }
  return arr;
 }

 // print current state of array
 private void print(int[] arr) {
  System.out.println();
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + "  ");
  }
 }

 public static void main(String[] args) {
  int[] arr = { 12, 11, 13, 5, 6 };
  InsertionSort is = new InsertionSort();
  arr = is.sort(arr);
  // is.print(arr);
 }
}

Output:

11  12  13  5  6  

11  12  13  5  6  

5  11  12  13  6  

5  6  11  12  13 

Performs ideal when array is nearly sorted or size is small. It can also be used as base sorting algorithm in recursive divide and conquer quick sort and merge sort algorithms.

Important Points

• If the array is already sorted, swapping will never be performed and hence time complexity will be O(n). Adaptive sorting algorithm. 
• Average and worst case time complexity is O(n^2). Space complexity is O(1)
• Worst performance when array is reverse sorted. 
• Not ideal approach if data is random.
• In the best case (when already sorted), all the elements are in proper place so it takes linear time. 
• In-efficient for value based data with large memory footprint as amount of memory shift/swap will be high. Performs good when sorting on pointer based data. 

References:
https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/insertion-sort

---

keep coding !