Power Sets

For a given set of items, power set is the set of all subsets of it. If there are $n$ items in the given set, then there are $2^n$ subsets.

Generating Power Sets

One of the way to generate Power Sets is using binary numbers. For each of the set in the power sets, we have $two$ choices for an item in the given set - include it or not include it. This can be denoted as 1 and 0. We know that, if we have $n$ bits, then we can form $2^n$ numbers using a sequence $0$ and $1$ $n$ bits. Similarly, if have $n$ items set, then each of the binary number from $0$ to $2^n - 1$ will represent a sub set. If a bit is $ith$ bit is $0$, then the $ith$ item is excluded from the subset, else we include it.

Following picture should clearly explain this concept.

Implementation

	/* File: PowerSetGenerator.java
	* Created: 9/28/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	//=======================================================================================
	import java.util.ArrayList;
	import java.util.List;
	//=======================================================================================
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class PowerSetGenerator {
	/**
	* Driver method
	* @param args
	*/
	public static void main(String[] args) {
	PowerSetGenerator generator = new PowerSetGenerator();
	for (List<Character> set : generator.generatePowerSets(new char[]{'A', 'B', 'C', 'D'})) {
	System.out.println(set.toString());
	}
	} // main
	//-------------------------------------------------------------------------------------
	/**
	* For each of the number from 0 to 2^n - 1, generate a sub set represented by the number.
	* Assemble all the subsets together to generate Power Set.
	* @param set Input Set.
	* @return Power Set of the given input set.
	*/
	public List<List<Character>> generatePowerSets(char[] set) {
	List<List<Character>> powerSets = new ArrayList<>();
	int max = 1 << set.length; // max = 2^n formed by right shifting 1 for n times
	for (int i = 0; i < max; i++) {
	powerSets.add(convertNumberToSet(set, i)); // for each binary number from 0 to 2^n - 1, generate sub set
	}
	return powerSets;
	} // generatePowerSets
	//-------------------------------------------------------------------------------------
	/**
	* Generate subset represented by given number
	* @param set Given Input set.
	* @param number Given number which represents a subset
	* @return Subset represented by given number
	*/
	private List<Character> convertNumberToSet(char[] set, int number) {
	List<Character> subset = new ArrayList<>();
	int index = 0;
	for (int i = 1; index < set.length; i = i << 1, index++) {
	if ((number & i) == i) { // determine if index th bit is 1 or 0 in the given number
	subset.add(set[index]); // include index th number if corresponding bit is 1 in the given number
	}
	}
	return subset;
	} // convertNumberToSet
	} // PowerSetGenerator

view raw PowerSetGenerator.java hosted with ❤ by GitHub

Time Complexity

There are $2^n$ subsets. We can't avoid computation of each subset. Here in this method, to determine each subset, we traverse through each of the item. $\therefore$ The complexity of this approach is $\cal{O(n2^n)}$ which is exponential with the size of the input.

---

---

---

Mockito: Mocking Final Methods With PowerMockito

Introduction

Mockito makes the testing job easier. But Mockito itself has its own limitations.

Poblem with Mocking final Method

One of such limitations is mocking of final method. When we try to mock a final method, as we normally mock other methods, it is not mocke. Real implementation of that method is executed. In fact, Mockito does not even complains about it. The real implementation is run without any Warning or Exception.

  /* File:    JobsTest.java
 * Created: 9/24/2018
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart Inc.
 */

package com.hogwart;


import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.mockito.Mockito;
import org.powermock.modules.junit4.PowerMockRunner;

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

//=======================================================================================


/**
 * @author Sabbir Manandhar
 * @version 1.0
 */
@RunWith(PowerMockRunner.class)
public class JobsTest {

  //-------------------------------------------------------------------------------------

  @Test
  public void testGetJobCount() {
    List expectedJobIds = new ArrayList();
    expectedJobIds.add("J456");
    expectedJobIds.add("J459");

    Jobs jobs = Mockito.mock(Jobs.class);
    Mockito.doReturn(expectedJobIds).when(jobs).getJobIds();

    List jobIds = jobs.getJobIds(); // Here we expect to receive mocked Job IDs
    Assert.assertEquals(expectedJobIds.size(), jobIds.size());
  } // testGetJobCount

} // JobsTest

//=======================================================================================

/**
 * Class Representing Jobs Queue
 */
class Jobs {

  //-------------------------------------------------------------------------------------

  /**
   * Retrieves List of Job IDs and return
   * @return List of Job IDs
   */
  public final List getJobIds() {
    List result = new ArrayList();

    // ...
    // Implementations to compute list of job ids
    // ...

    return result;
  } // getJobIds

  // Other Methods

} // Jobs

      

Here the test will fail because we are expecting mocked job ids of size 2, but the actual implementation is run and an empty list is returned.

Solution - PowerMockito

Even though Mockito cannot mock final methods, they can be mocked using PowerMockito.

We need to use following in our code to fix our test.

  
@RunWith(PowerMockRunner.class)
@PrepareForTest(Jobs.class)
public class JobsTest {

  ...

    Jobs jobs = PowerMockito.mock(Jobs.class);
    PowerMockito.doReturn(expectedJobIds).when(jobs).getJobIds();

      

Following is the complete working solution:

  
/* File:    JobsTest.java
 * Created: 9/24/2018
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart Inc.
 */

package com.hogwart;


import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.mockito.Mockito;
import org.powermock.api.mockito.PowerMockito;
import org.powermock.core.classloader.annotations.PrepareForTest;
import org.powermock.modules.junit4.PowerMockRunner;

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

//=======================================================================================


/**
 * @author Sabbir Manandhar
 * @version 1.0
 */
@RunWith(PowerMockRunner.class)
@PrepareForTest(Jobs.class)
public class JobsTest {

  //-------------------------------------------------------------------------------------

  @Test
  public void testGetJobCount() {
    List expectedJobIds = new ArrayList();
    expectedJobIds.add("J456");
    expectedJobIds.add("J459");

    Jobs jobs = PowerMockito.mock(Jobs.class);
    PowerMockito.doReturn(expectedJobIds).when(jobs).getJobIds();

    List jobIds = jobs.getJobIds(); // Here we expect to receive mocked Job IDs
    Assert.assertEquals(expectedJobIds.size(), jobIds.size());
  } // testGetJobCount

} // JobsTest

//=======================================================================================

/**
 * Class Representing Jobs Queue
 */
class Jobs {

  //-------------------------------------------------------------------------------------

  /**
   * Retrieves List of Job IDs and return
   * @return List of Job IDs
   */
  public final List getJobIds() {
    List result = new ArrayList();

    // ...
    // Implementations to compute list of job ids
    // ...

    return result;
  } // getJobIds

  // Other Methods

} // Jobs


      

Note

If you spy a class and mock a final method, then you might get some exception messages when you try to run the test class. One of possible exception is org.mockito.exceptions.misusing.WrongTypeOfReturnValue.

---

---

---

LeetCode: Word Search in 2D Matrix of characters

Difficulty Level: $\mathtt{MEDIUM}$
This is a LeetCode question. Find the DESCRIPTION HERE

Solution

This problem can be solved using Depth First Search (DFS) which will employ necessary Backtracking. Starting from any cell, we look for a match of characters from the beginning of input word. If there is a match, we look for the next character in the input word in the neighboring unvisited cells of the board. When the whole word is found, we return true.

Backtracking

When there is a match for a character in a word, we move to next character and also move to next neighbor. For the given cell there are Four possible neighbors. At a time, we select one neighbor and expand the search. It can happen that one neighbor might lead to a path where only some characters are matched while other neighbor can lead to the path where whole word is matched. So if we select the first neigbor, it will ultimately lead the end where we don't have any match. At such time, we should be able to backtrack and follow different path to look for possible desirable path.

Implementation

Following is the implemenation of the backtracking solution using DFS discussed above.

	/* File: WordSearch.java
	* Created: 9/19/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 WorldLingo Inc.
	*/
	//=======================================================================================
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class WordSearch {
	/**
	* Verifies if the given word can be found in the given board by moving left, right, top and bottom
	* unvisited cells of the board.
	* @param board Given board.
	* @param word Given word.
	* @return True if the word is found in the board, False otherwise.
	*/
	public boolean exist(char[][] board, String word) {
	int ROW = board.length;
	int COL = board[0].length;
	for (int row = 0; row < ROW; row++) {
	for (int col = 0; col < COL; col++) {
	if (dfs(board, new boolean[ROW][COL], word, 0, row, col, ROW, COL)) return true;
	}
	}
	return false;
	} // exist
	//-------------------------------------------------------------------------------------
	/**
	* Searches for the occurrence of characters in given word from the position <code>cursor</code>
	* in the given 2D board starting from given row and col.
	*
	* @param board Input 2D board of characters
	* @param visited Visited characters in the cell
	* @param word Given input word
	* @param cursor current location in the given word
	* @param row current row in the board
	* @param col current column in the board
	* @param ROW number of Rows in the board
	* @param COLUMN number of Columns in the board
	* @return True if the word occurs in the board, False otherwise
	*/
	public boolean dfs(char[][] board, boolean[][] visited, String word, int cursor, int row, int col, int ROW, int COLUMN) {
	if (cursor == word.length()) return true;
	if (!inBoard(row, col, ROW, COLUMN)) return false;
	if (visited[row][col]) return false;
	if (board[row][col] == word.charAt(cursor)) {
	visited[row][col] = true;
	boolean exist = dfs(board, visited, word, cursor + 1, row + 1, col, ROW, COLUMN) ||
	dfs(board, visited, word, cursor + 1, row, col + 1, ROW, COLUMN) ||
	dfs(board, visited, word, cursor + 1, row - 1, col, ROW, COLUMN) ||
	dfs(board, visited, word, cursor + 1, row, col - 1, ROW, COLUMN);
	if (exist) return true;
	visited[row][col] = false;
	} else {
	return false;
	}
	return false;
	} // dfs
	//-------------------------------------------------------------------------------------
	/**
	* Verify if given row and column are withing the limit
	* @param row given row
	* @param col given column
	* @param ROW ROW limit
	* @param COLUMN Column limit
	* @return True if the row and column are within the limit, False otherwise
	*/
	private boolean inBoard(int row, int col, int ROW, int COLUMN) {
	return row >= 0 && row < ROW && col >= 0 && col < COLUMN;
	} // inBoard
	} // WordSearch

view raw WordSearch.java hosted with ❤ by GitHub

Time Complexity

The exist() method runs two loops for $row \times column$ times and the dfs() method can also run upto $row \times column$ times.
$\therefore$ The complexity of this approach is $\cal{O(mn)^2}$ where $m\ = \ number\ of\ rows$ and $n\ = \ number\ of\ columns$.

Space Complexity

Here we are using extra 2D matrix visited to keep track of cells which are already visited.
$\therefore$The space complexity is $\cal{O(mn)}$.
This can be reduced to $\cal{O(1)}$ by modifying the input board to update each character with special character to mark that it has been visited. The modified character can be reset afterwards.

---

---

---

HackerRank - Flatland Space Stations (EASY)

Difficulty Level: $\mathtt{EASY}$
This is a HackerRank question. Find the DESCRIPTION HERE

	/* File: FlatlandSpaceStations.java
	* Created: 9/12/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	//=======================================================================================
	import java.util.Arrays;
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class FlatlandSpaceStations {
	/**
	* main method
	*
	* @param args
	*/
	public static void main(String[] args) {
	System.out.println(flatlandSpaceStations(6, new int[]{0, 1, 2, 4, 3, 5})); // expected 0
	System.out.println(flatlandSpaceStations(5, new int[]{0, 4})); // expected 2
	} // main
	//-------------------------------------------------------------------------------------
	/**
	* Computes the maximum distance among all distances from a city to nearest space station
	*
	* @param n number of cities
	* @param c array of cities with space stations
	* @return maximum distance
	*/
	static int flatlandSpaceStations(int n, int[] c) {
	Arrays.sort(c);
	int stationIndex = 0;
	int prevStation = c[stationIndex];
	int nextStation = prevStation;
	int max = -1;
	for (int i = 0; i < n; i++) {
	int cityDistance = Math.min(Math.abs(i - prevStation), Math.abs(i - nextStation));
	max = Math.max(max, cityDistance);
	if (i == nextStation) {
	stationIndex++;
	prevStation = nextStation;
	nextStation = stationIndex < c.length ? c[stationIndex] : prevStation;
	}
	}
	return max;
	} // flatlandSpaceStations
	} // FlatlandSpaceStations

view raw FlatlandSpaceStations.java hosted with ❤ by GitHub

Complexity

The time complexity is $\cal{O(nlogn)}$.

The space complexity is also $\cal{O(n)}$.

---

---

---