Daily Coding Problem #292: Teams without Enemies

A teacher must divide a class of students into two teams to play dodgeball. Unfortunately, not all the kids get along, and several refuse to be put on the same team as that of their enemies.

Given an adjacency list of students and their enemies, write an algorithm that finds a satisfactory pair of teams, or returns False if none exists.

  For example, given the following enemy graph you should return the teams {0, 1, 4, 5} and {2, 3}.

  students = {
    0: [3],
    1: [2],
    2: [1, 4],
    3: [0, 4, 5],
    4: [2, 3],
    5: [3]
  }
  
  On the other hand, given the input below, you should return False.

  students = {
    0: [3],
    1: [2],
    2: [1, 3, 4],
    3: [0, 2, 4, 5],
    4: [2, 3],
    5: [3]
  }
      

Solution

The Solution is straight forward. We maintain Two Lists representing two teams. At the same time we also maintain Two Sets representing the enemies of the teams.

We iterate through all the members one by one. We insert the member into eligible list and update the enemies set as well. If we can successfully insert all the members, then we have our solution. If we are unbale to insert all memebers, then the two teams cannot be formed.

WARNING!!

The solution is not as straight forward as it sounds.

It may be possible that the team member inserted previously into any of the list might cause conflict and hence result might not be possible.

  For following example, if we iterate in the order 0, 1, 2, 3, 4, 5 we will enounter 4 is enemies in both the team.

  students = {
    0: [3],
    1: [5],
    2: [4],
    3: [0, 4, 5],
    4: [2, 3],
    5: [3]
  }

  But it has valid team division and that is: {0, 4, 5} and {1, 2, 3}.
      

So for some of the inputs, we might need to iterate in different permutation. For this reason, we need Back Tracking

Implementation

Following is implementation with back tracking.

	/* File: Enemies.java
	* Created: 7/24/2019
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2019 Hogwart Inc.
	*/
	import java.util.*;
	//=======================================================================================
	/**
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class Enemies {
	/**
	* Driver method
	*/
	public static void main(String[] args) {
	Map<Integer, int[]> enemyMap = new HashMap<>();
	enemyMap.put(0, new int[]{3});
	enemyMap.put(1, new int[]{2});
	enemyMap.put(2, new int[]{1, 4});
	enemyMap.put(3, new int[]{0, 4, 5});
	enemyMap.put(4, new int[]{2, 3});
	enemyMap.put(5, new int[]{3});
	System.out.println(divide(enemyMap));
	enemyMap = new HashMap<>();
	enemyMap.put(0, new int[]{3});
	enemyMap.put(1, new int[]{2});
	enemyMap.put(2, new int[]{1, 3, 4});
	enemyMap.put(3, new int[]{0, 2, 4, 5});
	enemyMap.put(4, new int[]{2, 3});
	enemyMap.put(5, new int[]{3});
	System.out.println(divide(enemyMap));
	enemyMap = new HashMap<>();
	enemyMap.put(0, new int[]{3});
	enemyMap.put(1, new int[]{5});
	enemyMap.put(2, new int[]{4});
	enemyMap.put(3, new int[]{0, 4, 5});
	enemyMap.put(4, new int[]{2, 3});
	enemyMap.put(5, new int[]{3});
	System.out.println(divide(enemyMap));
	} // main
	//-----------------------------------------------------------------------------------------------
	/**
	* Divide the team into two
	* @param enemyMap
	* @return
	*/
	private static String divide(Map<Integer, int[]> enemyMap) {
	List<Integer> first = new ArrayList<>(), second = new ArrayList<>();
	Set<Integer> firstEnemies = new HashSet<>(), secondEnemies = new HashSet<>();
	return helper(enemyMap, new ArrayList<>(enemyMap.keySet()), 0, first, second, firstEnemies, secondEnemies);
	} // divide
	//-------------------------------------------------------------------------------------
	/**
	* Helper method to divide the team using Back Tracking
	* @param enemyMap
	* @param members
	* @param cursor
	* @param first
	* @param second
	* @param firstEnemies
	* @param secondEnemies
	* @return
	*/
	private static String helper(Map<Integer, int[]> enemyMap, List<Integer> members, int cursor, List<Integer> first, List<Integer> second, Set<Integer> firstEnemies, Set<Integer> secondEnemies) {
	if (cursor == members.size()) {
	return "(" + first.toString() + ", " + second.toString() + ")";
	}
	int member = members.get(cursor);
	if (first.isEmpty() || !firstEnemies.contains(member)) {
	List<Integer> cFirst = new ArrayList<>(first);
	List<Integer> cSecond = new ArrayList<>(second);
	Set<Integer> cFirstEnemies = new HashSet<>(firstEnemies);
	Set<Integer> cSecondEnemies = new HashSet<>(secondEnemies);
	addMember(cFirst, cFirstEnemies, member, enemyMap.get(member));
	String result = helper(enemyMap, members, cursor + 1, cFirst, cSecond, cFirstEnemies, cSecondEnemies);
	if (result != null) return result;
	}
	if (second.isEmpty() || !secondEnemies.contains(member)) {
	List<Integer> cFirst = new ArrayList<>(first);
	List<Integer> cSecond = new ArrayList<>(second);
	Set<Integer> cFirstEnemies = new HashSet<>(firstEnemies);
	Set<Integer> cSecondEnemies = new HashSet<>(secondEnemies);
	addMember(cSecond, cSecondEnemies, member, enemyMap.get(member));
	String result = helper(enemyMap, members, cursor + 1, cFirst, cSecond, cFirstEnemies, cSecondEnemies);
	if (result != null) return result;
	}
	if (!first.isEmpty() && firstEnemies.contains(member) && !second.isEmpty() && secondEnemies.contains(member)) {
	return null;
	}
	return null;
	} // helper
	//-------------------------------------------------------------------------------------
	private static void addMember(List<Integer> team, Set<Integer> teamEnemies, int member, int[] enemies) {
	team.add(member);
	for (Integer enemy : enemies ) {
	teamEnemies.add(enemy);
	}
	} // addMember
	} // Enemies

view raw Enemies.java hosted with ❤ by GitHub

---

---

---

LeetCode #632: Minimum Range

$\mathtt{Solution REFERENCE}$ @ LeetCode #632

Smallest Range : Problem Definition

This is a LeetCode Problem. You can find it HERE

Given $k$ lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each the lists.

The range $[a,b]$ is smaller than the range $[c,d]$ if $b-a < d -c$ OR $a < c\ if\ b-a == d-c$

Solution

Brute Force Solution

The straight forward solution would be to consider every possible set that includes at least one element from each of the list and find the minimum range out of those all sets.

The problem is, there are exponential number of possible sets to be considered. If we consider sets with one element from each list, then we already have $k^n$ sets. So this is not practical.

Efficient Solution

If we have a list, then to minimize the range, we either need to increase the minimum value or decrease the maxmimum value in the set.

We start by considering a set of $k$ elements which will have one item from each of the given list. At each step we keep track of $MAX$ and $Min-Range$ and it can be done in constant time $O(1)$. Now at each step, we remove the minimum element from set. To maintain constraint of having at least one element from each list, to compensate the removal of minimum element, we insert the next element from the list to which the minimum element we just removed belongs.

After each step we update $MAX$ and $Min-Range$ if necessary.

Once one of the list exhausts, we can safely return the $Min-Range$ as our result because we cannot have other lists which includes at least one element from each list.

Time and Space Complexity

Talking about Time Complexity, at the worst we will need to go through all the elements in all the $k$ lists which is O(nk) assuming each list has $n$ elements. Remember that we are removing the minimum element from the set and then push new element to it. So we must be able to identify the minimum element each time. If we iterate through all elements in the set to find the minimum, it will take $O(k)$ time. Therefore the overall time complexity will be $O(nk^2)$.

We can make this better by using $Min-Heap$. Instead of using set to store $k$ elements, we use $min-heap$ where we can find minimum element in $O(1)$ time, remove and add element in $O(logk)$ time. So the overall time complexity will be $O(nklogk)$.

The Space complexity will be $O(k)$ to store $k$ elements at each step.

Min Heap

It is not enough to store only the elements from the input lists.

When we remove an element from the heap, we should be able to identify to which list this element belongs to and at which index because after its removal we need to add next item from the same list. For this reason, items pushed into the heap should have information:

1. actual element from lists
2. list to which the element belongs (index)
3. index where this element lies in the list (index)

This implies we could use array of 3 elements as an item of the heap: $[<item>, <index\ of\ list>, <index\ within\ the\ list>]$

Implementation

	/**
	* @author Sabbir Manandhar
	* ManandharSabbir@gmail.com
	*/
	class MinimumRange {
	public int[] smallestRange(List<List<Integer>> nums) {
	// Min heap to store intermediate k elements
	PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
	public int compare(int[] a, int[] b) {
	return a[0] - b[0];
	}
	});
	// keep track of max in the heap to compute range
	int maxSoFar = Integer.MIN_VALUE;
	// start with minimum elements from the lists into our heap
	for(int i = 0; i < nums.size(); i++) {
	int num = nums.get(i).get(0);
	heap.offer(new int[]{num, i, 0});
	maxSoFar = Math.max(maxSoFar, num);
	}
	// keep track of minimum range
	int rangeS = heap.peek()[0];
	int rangeE = maxSoFar;
	while(true) {
	// remove minimum element from the heap
	int[] min = heap.poll();
	int nextIdx = min[2] + 1;
	// once one of the list exhausts return
	if(nextIdx == nums.get(min[1]).size()) {
	break;
	}
	// insert next element fromt the list
	int nextNum = nums.get(min[1]).get(nextIdx);
	heap.offer(new int[]{nextNum, min[1], nextIdx});
	// update max so far and minimum range
	maxSoFar = Math.max(maxSoFar, nextNum);
	int newRangeS = heap.peek()[0];
	int newRangeE = maxSoFar;
	if (newRangeE - newRangeS < rangeE - rangeS) {
	rangeS = newRangeS;
	rangeE = newRangeE;
	}
	}
	return new int[]{rangeS, rangeE};
	}
	}

view raw MinimumRange.java hosted with ❤ by GitHub

---

---

---

GoLang: Initialization before the execution of init()

Problem Definition

I have this goLang package which reads a JSON config file and sets up a map. I didn't want to call a separate method to load the file and set up the map. I wanted this to happen in the beginning automatically.
So I created init() method which loads the file and initializes the map with required configuration.

Problem

I fell into problem when I wrote unit test.

For the test I wanted to load with mocked content, not the actual file content. I actually didn't want to load the file at all.

So I created a variable fileReader as an instance of ioutil.ReadFile() method. It allows me to inject mocked file reader as dependency and execute whatever I want.

But as I said earlier, I had implemented init() method to read the file. This init() executed in the beginning before I was able to inject my mocked file reader.

Solution

Clearly the solution was to find a way to inject the dependency before the init() method executes. Fortunately I found a way to do that. Its using the following:

        // executes becore init() method so that fileReader can be injected
        var _ = func() (_ struct{}) {
          fileReader = mockedFileReader
          return
        }()
      

Code Illustration

Packakge Implementation

	package authorization
	import (
	"encoding/json"
	"io/ioutil"
	"log"
	"path/filepath"
	)
	//---------------------------------------------------------------------------------------
	const (
	rolePermissionFile = "data/role_permission.json"
	)
	//---------------------------------------------------------------------------------------
	var (
	fileReader = ioutil.ReadFile
	)
	//---------------------------------------------------------------------------------------
	var rolePermissionMap map[string]map[Permission]bool
	//---------------------------------------------------------------------------------------
	func init() {
	log.Println("init(): initializing role permission map")
	absPath, _ := filepath.Abs(rolePermissionFile)
	// read file bytes
	bytes, err := fileReader(absPath)
	if err != nil {
	log.Fatalf("init(): Error reading role permission JSON content: %v", err)
	}
	// unmarshal bytes into map
	var result map[string][]int
	err = json.Unmarshal(bytes, &result)
	if err != nil {
	log.Fatalf("init(): Error unmarshalling role permission JSON content: %v", err)
	}
	// construct role permission map
	rolePermissionMap = make(map[string]map[Permission]bool)
	for k, v := range result {
	permissions := make(map[Permission]bool)
	for _, perm := range v {
	permissions[Permission(perm)] = true
	}
	rolePermissionMap[k] = permissions
	}
	} // init
	//---------------------------------------------------------------------------------------
	// Authorize checks if given role has the permission
	func Authorize(roleID string, perm Permission) bool {
	permissions, ok := rolePermissionMap[roleID]
	if !ok {
	return false
	}
	return permissions[perm]
	} // Authorize

view raw authorize.go hosted with ❤ by GitHub

Test Implementation

	package authorization
	import (
	"testing"
	"github.com/stretchr/testify/assert"
	)
	// executes becore init() method so that fileReader can be injected
	var _ = func() (_ struct{}) {
	fileReader = mockedFileReader
	return
	}()
	//---------------------------------------------------------------------------------------
	func mockedFileReader(filePath string) ([]byte, error) {
	return []byte("{\"2\" : [1, 2, 3]}"), nil
	} // mockedFileReader
	//---------------------------------------------------------------------------------------
	func TestAuthorize(t *testing.T) {
	assert.False(t, Authorize("1", PermissionRead))
	assert.True(t, Authorize("2", PermissionRead))
	assert.False(t, Authorize("2", PermissionUpdate))
	} // TestAuthorize

view raw authorize_test.go hosted with ❤ by GitHub

---

---

---