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

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.

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

Complexity

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

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

---

---

---