Friction on Inclined Plane

Collision

Elastic Collision

A collision of masses where both momentum and energy of the system is conserved before and after the collision.

Conservation of Momentum:

m₁u₁ + m₂u₂ = m₁v₁ + m₂v₂

Conservaation of Energy:

m₁u₁² + m₂u₂² = m₁v₁² + m₂v₂²

Inelastic Collision

A collision of masses where only momentum of the system is conserved before and after the collision.

Conservation of Momentum:

m₁u₁ + m₂u₂ = m₁v₁ + m₂v₂

Given a string with I and D output a sequence of numbers

Problem:
Given a string with "I" and "D" where "I" stands for Increment and "D" stands for Decrement, produce a sequence of numbers which follows the same pattern as the input string.

Sample Input:
ID
IID
IDDI

Sample Output:
2 3 1
2 3 4 1
3 4 2 1 5

C++ Program:
 

#include <iostream>
using namespace std;

void printNumbers(string input) {
    if (input.length() == 0) {
        return;
    }
    int dCount = 0;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == 'D') {
            dCount++;
        }
    }
    int numbers[100];
    for (int i = 0; i <= input.length(); i++) {
        numbers[i] = i+1;
    }
    // The starting number is at the index which equals the number of D's
    cout << endl << numbers[dCount] << " ";
    numbers[dCount] = -1;
    // Increment starts at the index next to index equal to number of D's.
    int iCount = dCount+1;
    // Next decrement starts at the index previous to index equal to number of D's.
    dCount--;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == 'I') {
            cout << numbers[iCount] << " ";
            numbers[iCount++] = -1;
        }
        else {
            cout << numbers[dCount] << " ";
            numbers[dCount--] = -1;
        }
    }
    cout << endl;
}

int main() {
 printNumbers("IDDI");
 return 0;
}

Find if a word is present in a matrix

Find if all the characters of a given word is present in a two dimensional matrix if the matrix can be traversed as described in the image below:

Java Program:

public class MatrixTraversalPrograms {
 public boolean driverForIsWordPresent(char[] in, char[][] matrix) {
  boolean wordFound = false;
  for(int i=0;i<matrix.length;i++) {
   for(int j=0;j<matrix[i].length;j++) {
    if(in[0] == matrix[i][j]) {
     wordFound = isWordPresent(in, matrix, i, j, 0);
    }
    if(wordFound) {
     break;
    }
   }
   if(wordFound) {
    break;
   }
  }
  return wordFound;
 }
 
 public boolean isWordPresent(char[] in, char[][] matrix, int i, int j, int index) {
  if(index == in.length - 1) {
   return true;
  }
  else {
   boolean complete = false;
   //Top Right
   if(i-1 >= 0 && j+1 < matrix[i].length && matrix[i-1][j+1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i-1, j+1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Right
   if(!complete && i >= 0 && i < matrix.length && j+1 < matrix[i].length && matrix[i][j+1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i, j+1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Bottom Right
   if(!complete && i+1 < matrix.length && j+1 < matrix[i+1].length && matrix[i+1][j+1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i+1, j+1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Bottom
   if(!complete && i+1 < matrix.length && j >= 0 && j < matrix[i+1].length && matrix[i+1][j] == in[index+1]) {
    complete = isWordPresent(in, matrix, i+1, j, index + 1);
    if(complete) {
     return true;
    }
   }
   //Bottom Left
   if(!complete && i+1 < matrix.length && j-1 >= 0 && matrix[i+1][j-1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i+1, j-1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Left
   if(!complete && i>=0 && i < matrix.length && j-1 >= 0 && matrix[i][j-1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i, j-1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Top Left
   if(!complete && i-1 >= 0 && j-1 >= 0 && matrix[i-1][j-1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i-1, j-1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Top
   if(!complete && i-1 >= 0 && j >= 0 && j < matrix[i-1].length && matrix[i-1][j] == in[index+1]) {
    complete = isWordPresent(in, matrix, i-1, j, index + 1);
    if(complete) {
     return true;
    }
   }
   return false;
  }
 }
}

Unit Tests:

import static org.junit.Assert.*;

import org.junit.Test;

import junit.framework.Assert;

public class MatrixTraversalTests {
 
 MatrixTraversalPrograms programInstance = new MatrixTraversalPrograms();
 @Test
 public void testTwoCharacterPresent() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','b'},
   {'a','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testTwoOnePresent() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','c'},
   {'a','x'}
   };
  Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testTwoBiggerMatrix() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','x','x'},
   {'x','b','x'},
   {'a','x','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testTwoRepeated() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','x','x'},
   {'x','b','x'},
   {'a','b','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testLarge() {
  char[] in = {'M','i','c','r','o','s','o','f','t'};
  char[][] matrix = new char[][]{
   {'x','x','x','x','x','x'},
   {'x','r','o','x','x','x'},
   {'x','x','c','s','x','x'},
   {'x','x','i','o','f','x'},
   {'x','M','x','x','f','x'},
   {'x','x','x','t','x','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testLargePartialPresent() {
  char[] in = {'M','i','c','r','o','s','o','f','t'};
  char[][] matrix = new char[][]{
   {'x','x','x','x','x','x'},
   {'x','r','o','x','x','x'},
   {'x','x','c','s','x','x'},
   {'x','x','i','o','f','x'},
   {'x','M','x','x','f','x'},
   {'x','x','x','x','x','x'}
   };
  Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testOneCharacterPresent() {
  char[] in = {'a'};
  char[][] matrix = new char[][]{
   {'a'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testOneCharacterAbsent() {
  char[] in = {'a'};
  char[][] matrix = new char[][]{
   {'b'}
   };
  Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix));
 }
}

Non-recursive level order traversal of a binary tree

Java Code:

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
   
    public TreeNode() {
       
    }
   
    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

//Non-recursive LevelOrder Traversal
    public String levelOrderTraversal(TreeNode node) {
        StringBuilder traversal = new StringBuilder();
        if(node == null) {
            return traversal.toString();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        int thisLevel = 1;
        int nextLevel = 0;
        while(!queue.isEmpty()) {
            for(int i=0; i<thisLevel; i++) {
                node = queue.remove();
                traversal.append(node.data);
                if(node.left != null && node.right != null) {
                    nextLevel += 2;
                    queue.add(node.left);
                    queue.add(node.right);
                }
                else if(node.left != null || node.right != null) {
                    nextLevel += 1;
                    if(node.left != null) {
                        queue.add(node.left);
                    }
                    else {
                        queue.add(node.right);
                    }
                }
            }
            thisLevel = nextLevel;
            nextLevel = 0;
        }
        return traversal.toString();
    }

Unit Tests:

public class TreeProgramsTest {

    TreeNode root;
    @Before
    public void initialize() {
        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
    }

    @Test
    public void testLevelOrderTraversal() {
        TreeTraversalPrograms treeTraversalPrograms = new TreeTraversalPrograms();
        Assert.assertTrue(treeTraversalPrograms.levelOrderTraversal(root).equals("123456"));
    }
}

Sudoku Solver using Backtracking

Java Code:

package com.sourabh.second;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SudokuSolver {
    //Brute force back-tracking based Sudoku Solver Program
    class Square {
        int startRow;
        int endRow;
        int startCol;
        int endCol;
    }
   
    public static void main(String[] args) {
        SudokuSolver solver = new SudokuSolver();
        Integer[][] matrix = new Integer[][]{
            {5,3,0,0,7,0,0,0,0},
            {6,0,0,1,9,5,0,0,0},
            {0,9,8,0,0,0,0,6,0},
            {8,0,0,0,6,0,0,0,3},
            {4,0,0,8,0,3,0,0,1},
            {7,0,0,0,2,0,0,0,6},
            {0,6,0,0,0,0,2,8,0},
            {0,0,0,4,1,9,0,0,5},
            {0,0,0,0,8,0,0,7,9}
            };
        matrix = solver.solveSudoku(matrix);
        //solver.printMatrix(matrix);
    }
   
    void printMatrix(Integer [][] matrix) {
        System.out.println();
        for(int i=0; i<matrix.length; i++) {
            for(int j=0; j<matrix.length; j++) {
                System.out.print(matrix[i][j] + ",");
            }
            System.out.println();
        }
    }
   
    public Integer[][] solveSudoku(Integer [][] matrix) {
        boolean complete = true;
        int i=0;
        int j=0;
        for(i=0;i<matrix.length;i++) {
            for(j=0;j<matrix[i].length;j++) {
                if(matrix[i][j] == 0) {
                    complete = false;
                    break;
                }
            }
            if(!complete) {
                break;
            }
        }
        if(complete) {
            printMatrix(matrix);
            return matrix;
        }
        //Find the square boundary
        Square currentSquare = getSquareBoundary(i, j);
        //Find in this row
        Integer[] possibleRowNumbers = getPossibleNumbersInRow(matrix, i);
        //Find in this column
        Integer[] possibleColNumbers = getPossibleNumbersInColumn(matrix, j);
        //Find in this square
        Integer[] possibleSquareNumbers = getPossibleNumbersInSquare(matrix,
                currentSquare.startRow, currentSquare.endRow, currentSquare.startCol, currentSquare.endCol);
        Integer[] possibleNumbers = getIntersectionOfArrays(possibleRowNumbers, possibleColNumbers, possibleSquareNumbers);
        boolean incomplete = false;
        for(int k=0;k<possibleNumbers.length;k++) {
            matrix[i][j] = possibleNumbers[k];
            matrix = solveSudoku(matrix);
            //printMatrix(matrix);
            for(int row=0;row<matrix.length;row++) {
                for(int col=0;col<matrix[row].length;col++) {
                    if(matrix[row][col] == 0) {
                        incomplete = true;
                        break;
                    }
                }
            }
            if(incomplete) {
                matrix[i][j] = 0;
            }
            else {
                break;
            }
        }
        return matrix;
    }
   
    Integer[] getPossibleNumbersInRow(Integer[][] matrix, int row) {
        List<Integer> possibleNumbers = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7,8,9));
        for(int i=0; i<matrix[row].length; i++) {
            if(matrix[row][i] != 0) {
                possibleNumbers.remove(matrix[row][i]);
            }
        }
        Integer[] array = new Integer[possibleNumbers.size()];
        return possibleNumbers.toArray(array);
    }
   
    Integer[] getPossibleNumbersInColumn(Integer[][] matrix, int col) {
        List<Integer> possibleNumbers = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7,8,9));
        for(int i=0; i<matrix.length; i++) {
            if(matrix[i][col] != 0) {
                possibleNumbers.remove(matrix[i][col]);
            }
        }
        Integer[] array = new Integer[possibleNumbers.size()];
        return possibleNumbers.toArray(array);
    }
   
    Integer[] getPossibleNumbersInSquare(Integer[][] matrix, int startRow, int endRow,
            int startCol, int endCol) {
        List<Integer> possibleNumbers = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7,8,9));
        for(int i=startRow; i<=endRow; i++) {
            for(int j=startCol; j<=endCol; j++) {
                if(matrix[i][j] != 0) {
                    possibleNumbers.remove(matrix[i][j]);
                }
            }
        }
        Integer[] array = new Integer[possibleNumbers.size()];
        return possibleNumbers.toArray(array);
    }

    Integer[] getIntersectionOfArrays(Integer[] ... arrays) {
        Integer[] intersection = getIntersectionOfTwoArrays(arrays[0], arrays[1]);
        //Arrays are already sorted, so applying merge on 2 arrays at a time.
        for(int i=2;i<arrays.length;i++) {
            intersection = getIntersectionOfTwoArrays(intersection, arrays[i]);
        }
        return intersection;
    }
   
    Integer[] getIntersectionOfTwoArrays(Integer[] array1, Integer[] array2) {
        List<Integer> intersectionList = new ArrayList<>();
        int a=0;
        int b=0;
        while(a<array1.length && b<array2.length) {
            if(array1[a] < array2[b]) {
                a++;
            }
            else if(array1[a] > array2[b]) {
                b++;
            }
            else {
                intersectionList.add(array1[a]);
                a++;
                b++;
            }
        }
        Integer[] array = new Integer[intersectionList.size()];
        return intersectionList.toArray(array);
    }

    Square getSquareBoundary(int row, int col) {
        Square square = new Square();
        if(row < 3) {
            square.startRow = 0;
            square.endRow = 2;
        }
        else if(row < 6) {
            square.startRow = 3;
            square.endRow = 5;
        }
        else if(row < 9) {
            square.startRow = 6;
            square.endRow = 8;
        }
       
        if(col < 3) {
            square.startCol = 0;
            square.endCol = 2;
        }
        else if(col < 6) {
            square.startCol = 3;
            square.endCol = 5;
        }
        else if(col < 9) {
            square.startCol = 6;
            square.endCol = 8;
        }
        return square;
    }
}

Unit Tests:

package com.sourabh.second;

import static org.junit.Assert.*;

import org.junit.Assert;
import org.junit.Test;

import com.sourabh.second.SudokuSolver.Square;

public class SudokuSolverTests {

    @Test
    public void testSolveSudoku3() {
        Integer[][] matrix = new Integer[][]{
            {0,0,0,1,0,0,0,0,7},
            {0,0,6,0,7,0,0,5,0},
            {0,9,0,0,0,3,6,0,0},
            {3,0,0,0,0,9,5,0,0},
            {0,1,0,0,2,0,0,3,0},
            {0,0,8,4,0,0,0,0,9},
            {0,0,9,7,0,0,0,4,0},
            {0,5,0,0,4,0,3,0,0},
            {2,0,0,0,0,1,0,0,0}
            };
        SudokuSolver solver = new SudokuSolver();
        solver.solveSudoku(matrix);
    }
   
    //@Test
    public void testSolveSudoku2() {
        Integer[][] matrix = new Integer[][]{
            {6,0,4,0,0,8,5,3,0},
            {9,0,0,0,3,6,1,0,0},
            {0,0,0,9,0,0,0,0,0},
            {4,9,2,0,0,0,0,0,5},
            {0,0,6,0,0,0,4,0,0},
            {8,0,0,0,0,0,9,2,7},
            {0,0,0,0,0,2,0,0,0},
            {0,0,9,8,7,0,0,0,1},
            {0,1,7,4,0,0,8,0,2}
            };
        SudokuSolver solver = new SudokuSolver();
        solver.solveSudoku(matrix);
    }
   
    //@Test
    public void testSolveSudoku() {
        Integer[][] matrix = new Integer[][]{
            {1,0,0,6,0,0,2,0,0},
            {0,2,0,0,0,0,9,0,5},
            {0,0,0,7,0,0,0,1,6},
            {0,9,4,0,7,6,0,0,0},
            {0,1,0,0,9,0,0,2,0},
            {0,0,0,3,1,0,4,9,0},
            {2,3,0,0,0,8,0,0,0},
            {4,0,6,0,0,0,0,5,0},
            {0,0,1,0,0,7,0,0,2}
            };
        SudokuSolver solver = new SudokuSolver();
        solver.solveSudoku(matrix);
    }

    @Test
    public void testAssertArrayEquals() {
        Assert.assertArrayEquals(new Integer[] {1,2,3}, new Integer[] {1,2,3});
    }
   
    @Test
    public void testGetPossibleNumbersInRow() {
        Integer[][] matrix = {{1,2,0,0,0}, {0,0,0,3,4}, {5,0,0,0,6}};
        SudokuSolver solver = new SudokuSolver();
        int row = 0;
        Integer[] result = solver.getPossibleNumbersInRow(matrix, row);
        Assert.assertArrayEquals(new Integer[] {3,4,5,6,7,8,9}, result);
        row = 1;
        result = solver.getPossibleNumbersInRow(matrix, row);
        Assert.assertArrayEquals(new Integer[] {1,2,5,6,7,8,9}, result);
        row = 2;
        result = solver.getPossibleNumbersInRow(matrix, row);
        Assert.assertArrayEquals(new Integer[] {1,2,3,4,7,8,9}, result);
    }

    @Test
    public void testGetPossibleNumbersInColumn() {
        Integer[][] matrix = {{1,1}, {0,0}, {0,2}, {3,0}};
        SudokuSolver solver = new SudokuSolver();
        int col = 0;
        Integer[] result = solver.getPossibleNumbersInColumn(matrix, col);
        Assert.assertArrayEquals(new Integer[] {2,4,5,6,7,8,9}, result);
        col = 1;
        result = solver.getPossibleNumbersInColumn(matrix, col);
        Assert.assertArrayEquals(new Integer[] {3,4,5,6,7,8,9}, result);
    }

    @Test
    public void testGetPossibleNumbersInSquare() {
        Integer[][] matrix = {{1,0,0}, {0,2,0}, {0,0,3}};
        SudokuSolver solver = new SudokuSolver();
        Integer[] result = solver.getPossibleNumbersInSquare(matrix, 0, 2, 0, 2);
        Assert.assertArrayEquals(new Integer[] {4,5,6,7,8,9}, result);
    }
   
    @Test
    public void testGetIntersectionOfArrays() {
        Integer[] array1 = new Integer[]{0,0,1};
        Integer[] array2 = new Integer[]{0,0,2};
        Integer[] array3 = new Integer[]{0,0,3};
        SudokuSolver solver = new SudokuSolver();
        Integer[] result = solver.getIntersectionOfArrays(array1, array2, array3);
        Assert.assertArrayEquals(new Integer[] {0,0}, result);
    }
   
    @Test
    public void testGetIntersectionOfTwoArrays() {
        Integer[] array1 = new Integer[]{0,0,1};
        Integer[] array2 = new Integer[]{0,0,2};
        SudokuSolver solver = new SudokuSolver();
        Integer[] result = solver.getIntersectionOfTwoArrays(array1, array2);
        Assert.assertArrayEquals(new Integer[] {0,0}, result);
    }
   
    @Test
    public void testGetSquareBoundary() {
        SudokuSolver solver = new SudokuSolver();
        Square square = solver.getSquareBoundary(1, 1);
        Assert.assertEquals(square.startRow, 0);
        Assert.assertEquals(square.endRow, 2);
        Assert.assertEquals(square.startCol, 0);
        Assert.assertEquals(square.endCol, 2);
    }
}