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);
    }
}

Equivalence Class Partitioning Examples

Example 1:
Write test-cases for testing a power function which has the following signature:
int power(int m, int n)
and returns the result of m raised to the power of n.

The Number line can be divided into sections as shown below:
1. [MIN, -k]: where k is a value which lies between MIN and MAX, but the result of k raised to the power of k can be above MAX value.
2. [-k, 0]
3. [0,k]
4. [k, MAX]
Test-cases can be formed by taking one value from each section.

Test-cases for power function:
Total number of possible values for m with the above equivalence class partitioning: 5
Total number of possible values for n with the above equivalence class partitioning: 5
Total number of test-cases: 5*5 = 25

Find the maximum possible profit in an array of share prices

Problem:
Given an array of integers which are share prices, find the maximum possible profit that can be earned by buying and selling the shares on particular dates. Also output the dates (indices) on which the buying and selling should happen in order to earn the maximum profit.


Sample Input:
15
1 3 2 4 5 3 1 0 1 -1 1 2 3 5 4


Sample Output:

Buy date: 9
Sell date: 13
Buying price: -1
Selling price: 5
Maximum possible Profit: 6

Approach 1: Time complexity: O(n²), Space complexity: O(1)
Code:

#include <iostream>
using namespace std;

int main() 
{
 int A[100];
 int n;
 cin>>n;
 for(int i=0;i<n;i++)
 {
  cin>>A[i];
 }
 int profit = 0;
 int maxProfit = 0;
 int buyDate = 0;
 int sellDate = 0;
 for(int i=0;i<n;i++)
 {
  for(int j=i+1;j<n;j++)
  {
   profit = A[j] - A[i];
   if(profit > maxProfit)
   {
    buyDate = i;
    sellDate = j;
    maxProfit = profit;
   }
  }
 }
 cout<<"Buy date: "<<buyDate<<endl;
 cout<<"Sell date: "<<sellDate<<endl;
 cout<<"Buying price: "<<A[buyDate]<<endl;
 cout<<"Selling price: "<<A[sellDate]<<endl;
 cout<<"Maximum possible Profit: "<<maxProfit<<endl;
 return 0;
}

Approach 2: Time complexity: O(n), Space complexity: O(1)
Code:

#include <iostream>
using namespace std;

int main() {
 int A[100];
 int n;
 cin>>n;
 for(int i=0;i<n;i++)
 {
  cin>>A[i];
 }
 int currMaxIndex = 0;
 int currMinIndex = 0;
 int sellDate = 0;
 int buyDate = 0;
 int profit = 0;
 int maxProfit = 0;
 int currMinPrice = 0;
 int currMaxPrice = 0;
 if(A[0] < A[1])
 {
  currMaxIndex = 1;
  currMaxPrice = A[1];
  currMinIndex = 0;
  currMinPrice = A[0];
 }
 else
 {
  currMaxIndex = 0;
  currMaxPrice = A[0];
  currMinIndex = 1;
  currMinPrice = A[1];
 }
 for(int i=0;i<n;i++)
 {
  if(A[i] <= currMinPrice)
  {
   currMinIndex = i;
   currMinPrice = A[i];
  }
  if(A[i] >= currMaxPrice)
  {
   currMaxIndex = i;
   currMaxPrice = A[i];
  }
  if(currMaxIndex > currMinIndex)
  {
   profit = A[currMaxIndex] - A[currMinIndex];
   if(profit > maxProfit)
   {
    maxProfit = profit;
    buyDate = currMinIndex;
    sellDate = currMaxIndex;
   }
  }
 }
 cout<<"Buy date: "<<buyDate<<endl;
 cout<<"Sell date: "<<sellDate<<endl;
 cout<<"Buying price: "<<A[buyDate]<<endl;
 cout<<"Selling price: "<<A[sellDate]<<endl;
 cout<<"Maximum possible Profit: "<<maxProfit<<endl;
 return 0;
}

Testing of webpages

A very common question asked in almost all software testing interviews is:

How will you test a webpage or a website?

There is no one complete and correct answer to this question as this is a highly open-ended question aimed at assessing a candidate's ability to think in different directions and find cases where a particular logic or system can break. Also this question is used to assess a candidate's systematic approach to solving an ambiguous problem.

Let us make an attempt at solving this problem:

Step-1: Gather as much minute details as possible by asking clarifying questions.
The questions that can and should be asked (unless the interviewer has already clarified) are:
1. What is the webpage or website about?
2. Who are the intended customers of the website? What all devices is the webpage supported in?
3. How will the intended customers interact with the various UI elements of the webpage?

• What all text can customers input in the text-boxes.
• Which links and images can be clicked.

4. What all UI elements are present in the webpage?
5. What all actionable elements (these are elements like buttons, links, text boxes etc. which can be clicked or edited by the user) are present in the webpage?
6. What is the result of such actions on the UI elements? Do I need to test those results also?
7. Is the webpage meant to be displayed in localized languages?
8. What is the peak load that the webpage should sustain to?
This step can itself give the direction to think in and each question can lead to a set of test-cases.

Step-2: Start thinking and writing functional test-cases for each of the details gathered in Step-1.
Question 1: What is the webpage or website about?
Test-cases can be:
1. Check that the title of the page depicts what the webpage is about?
2. Check that the meta tags of the page depict and contain keywords which accurately describe the content of the webpage. Titles and meta description are SEO techniques that help in improving search engine rankings.
3. Check that the content caters to what the webpage is about. Ask questions like the correctness of the content needs to be specified in the product specifications.
4. Check that the content is grammatically correct and legible.

Question 2: Who are the intended customers of the website? What all devices is the webpage supported in?
Test-cases can be:
1. Check that the layout and content is relevant for all classes of intended customers.
2. Check that the layout is responsive so that the webpage is rendered properly in various screen resolutions.
3. Check that the webpage is loading properly across browsers and OS combinations.
4. Ensure that the webpage handles errors gracefully if it is tried to load in non-supported browsers or OS combinations.

Question 3: How will the intended customers interact with the various UI elements of the webpage?
Test-cases can be:
1. Check that the links are clickable.
2. Check that the buttons are clickable.
3. Check that the images are visible and their loading does not take too much time.
4. Check that the text-boxes are clickable and text can be written into them.
5. Check that the elements are accessible using keyboard tab keys.
6. If there are JavaScript elements involved, then their rendering and loading should be checked.
7. Check that hovering on the right elements show intended messages.

Question 4, 5, 6: Functional verification of individual UI elements.
Test-cases can be:
1. Check that the buttons are rendered properly look and feel wise.
2. Check the size of the text-boxes, hint texts and color and size of the text the user types.
3. Maximum length of string that can be input in the text box.
4. What happens if empty string is passed as input.
5. If it is a password text box, then password should be hidden.
6. If there is a form, then proper input validation should be in place.
7. Links should lead to the right pages.
8. None of the links should lead to 404.

Question 7: Is the webpage meant to be displayed in localized languages?
This is called localization testing. Test-cases can be:
1. Check that the webpage is rendered in the correct language when loaded from the correct location.
This can be done using techniques like IP spoofing etc.
2. There should be an option to translate between languages.
3. Check that the translated text in each language is grammatically correct.

Question 8: What is the peak load that the webpage should sustain to?
This comes under performance testing of webpages. Things to be tested in this are:
1. Simulate multiple users hitting the website at the same time.
There are tools to do this: JMeter, Apache Bench.
In the absence of tools, this can be done using multi-threaded routines which send http requests to the server and record response times.
2. Monitor the memory consumption and CPU utilization on server side over a long time.

Security Testing:
Test-cases can be:
1. Cross-site scripting
2. SQL Injection
3. Denial of Service Attacks
4. All customer sensitive data should be transmitted over SSL channels.
5. There should be no non-secure (http) calls or content in https pages.

Value add test-cases:
1. There should be proper logging on server side, so that it can help in debugging.
2. There should be monitors on the server metrics of memory, CPU utilization, logging errors etc.

Hash Table Simplified

A very basic explanation of a Hash Table Data Structure

Let us consider the problem of storing a large number of words so that insertion and search operations can be performed in O (1) time complexity

If the words are stored in a simple array, then the operation will have time complexity of O (n) where n is the number of words.

We can solve the above problem by using a Hash Table data structure

What is a hash table?

A hash table is a set of key-value pairs where key is unique and a particular key cab hold a certain value.

A key is generated by a hash function.

For our example, let us consider that the hashing function works in the following manner:

1. The letters of the word are assigned a particular integer value. For example: a -> 1, b -> 2, c -> 3 and so on.

2. The integers corresponding to the letters present in a particular word are added.

3. This sum is taken as a key

4. Let us assume the number of keys formed in this way is k (which is constant). There is a catch* here which is discussed later. For now assume that the maximum number of possible keys is a constant k.

5. Let us also assume that the number of words corresponding to a single key is constant which equals to w on an average.

Now let us consider the following words and the corresponding sums which will be the keys.

Word	Sum which will be used as key
abc	6
ae	6
abcd	10
ade	10

  

Sample Hash Table storage:

Now to search for a word ade:

1. First the sum is determined which is O (1). Please note that the complexity of finding the sum for a given word having m letters is negligible compared to the complexity of finding a word in an array containing n such words.

2. Now this key can be searched in the key linked list in O(k) which in Big O notation boils down to O(1).

3. Once the key is determined, the word can be searched in O(w) which in Big O notation again boils down to O(1).

So the Search operation can be performed on such a data structure with time complexity of O (n).

Similarly for inserting a word acf:

1. First the sum is determined which is O (1). Please note that the complexity of finding the sum for a given word having m letters is negligible compared to the complexity of finding a word in an array containing n such words.

2. Now this key can be searched in the key linked list in O(k) which in Big O notation boils down to O(1).

3. Once the key is determined, the word can be inserted in O(w) which in Big O notation again boils down to O(1).

So the Insertion operation can be performed on such a data structure with time complexity of O (n).

*Catch: The choice of the hashing function needs to be made very carefully so as to maintain the following two criteria:

1. The number of unique keys generated by the hashing function should not become too high.

2. The number of words or entities needed to be stored in one linked list should not become too large.

Note: This is an attempt to explain the hash table data structure in a very simple terms. Actual implementations are much more complex and use details of the available memory storage.

References:
https://en.wikipedia.org/wiki/Hash_table