GoLang: Map Values retrieved as Reference or by Value ?

GoLang Map Value : By Value or Reference ?

Map data structure in GoLang is to map keys to values.

Value Retrieval

If we have a map say objects with keys as string, then we retrieve a value for any key as

objects["key"]

is Value a reference or new value?

Having come from Java background, my idea was the value retrieved from map was going to be by reference. This was not true. Value retrieved from map by above fashion actually returns new object.

So if the value in the map is some struct, then any updated on the extracted value is not reflected.

Example

In this example,

1. we retrieve a value from a map
2. We update the value
3. retrieve the same value from map again

Here we can see the update is not reflected into the map. RUN THE CODE

package main

import (
  "fmt"
)

type Person struct {
  Name string
  Address string
}

func main() {
  persons := map[string]Person {
    "ginny" : Person {
      Name : "ginny",
      Address: "Hogwart",
    },
  }
  
  person := persons["ginny"]
  fmt.Println(person) // will print ginny and Hogwart as expected
  
  person.Address = "Three Brooms"
  fmt.Println(person) // will print ginny and Three Brooms as expected. But this is not updated into Map
  
  person = persons["ginny"]
  fmt.Println(person) // will print ginny and Hogwart not the updated values
}

What to do for reflecting the update into map?

If you want the update in value to be reflected into the map, then the mapping in map should be pointer.

persons := map[string]*Person

This is same example as above. Only we are using pointer values in the map. Here we are able to see that the update is reflected into the map. RUN THE CODE

package main

import (
  "fmt"
)

type Person struct {
  Name string
  Address string
}

func main() {
  persons := map[string]*Person {
    "ginny" : &Person {
      Name : "ginny",
      Address: "Hogwart",
    },
  }
  
  person := persons["ginny"]
  fmt.Println(*person) // will print ginny and Hogwart as expected
  
  person.Address = "Three Brooms"
  fmt.Println(*person) // will print ginny and Three Brooms as expected. But this is not updated into Map
  
  person = persons["ginny"]
  fmt.Println(*person) // will print ginny and Three Brooms as expected
}

Similar Other Cases

1. Method Receiver : If a method updates the receiver, then receiver should be pointer in order to reflect the updates. RUN Example
2. Slice : When objects from slices are retrieved and updated, update is not reflected in slice itself. Pointer should be used to reflect the update. RUN Example

---

---

---

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

---

---

---

Daily Coding Problem #332: Relationship between SUM, XOR and AND of Two Numbers

Problem Definition

Given integers $M$ and $N$, write a program that counts how many positive integer pairs $(a, b)$ satisfy the following conditions:

1. $a + b = M$
2. $a\ XOR\ b = N$

Solution

$\mathtt{Solution\ REFERENCE}$ @ StackOverflow

Implementation

	import java.io.*;
	import java.util.Scanner;
	class Solution {
	public static void main (String[] args) {
	Scanner sc = new Scanner(System.in);
	long X = sc.nextLong();
	long S = sc.nextLong();
	long A = (S-X);
	if (A%2 == 1) {
	System.out.println("none");
	return;
	}
	A = A >> 1;
	int answers = 1;
	for(int i = 1; i <= 64; i++) {
	int xi =(int) (X & 1); // obtain LSB of XOR
	int ai = (int) (A & 1); // obtain LSB of AND
	// XOR bit is 1, AND bit is 0 which means two number bits can be either 0 and 1 OR 1 and 0
	if (xi == 1 && ai == 0) answers *= 2;
	// XOR bit is 1, AND bit is 1 , which means there can't be such numbers
	else if (xi == 1 && ai == 1) {
	System.out.println("none");
	return;
	}
	// XOR bit is 0, AND bit is 0, there can be only one choice: 0 and 0,
	// XOR bit is 0, AND bit is 1, there can be only one choice: 1 and 1
	X = X >> 1;
	A = A >> 1;
	}
	System.out.println(answers + " Pairs");
	}
	}

view raw Solution.java hosted with ❤ by GitHub

Complexity

This implementation iterates through all the bits in $XOR$ and $AND$. If $N$ be the number of bits, then the time complexity is $\cal{O(N)}$.

---

---

---

PowerMockito: Mocking Private and Public Static Methods

Assume following class with private and public static methods and we want to write junit test which access those methods. We are mocking these static methods.

	//=================================================================================================
	class MockStaticMethod {
	public int getResult(int a, int b, boolean sum) {
	if (sum) {
	return sum(a, b);
	} else {
	return diff(a, b);
	}
	} // getResult
	//-----------------------------------------------------------------------------------------------
	public static int sum(int a, int b) {
	return a + b;
	} // sum
	//-----------------------------------------------------------------------------------------------
	private static int diff(int a, int b) {
	return a - b;
	} // diff
	} // MockStaticMethod

view raw MockStaticMethodTest.java hosted with ❤ by GitHub

Mock Private Static Method

	@Test
	public void testDiff() throws Exception {
	PowerMockito.mockStatic(MockStaticMethod.class);
	PowerMockito.doReturn(3).when(MockStaticMethod.class, "diff", Mockito.anyInt(), Mockito.anyInt());
	MockStaticMethod obj = new MockStaticMethod();
	Assert.assertEquals(3, obj.getResult(0, 0, false));
	Assert.assertEquals(3, obj.getResult(1, 2, false));
	} // testDiff

view raw MockStaticMethodTest.java hosted with ❤ by GitHub

For mocking private static method we need to use

	PowerMockito.mockStatic(MockStaticMethod.class);
	PowerMockito.doReturn(3).when(MockStaticMethod.class, "diff", Mockito.anyInt(), Mockito.anyInt());

view raw MockStaticMethodTest.java hosted with ❤ by GitHub

Mock Public Static Method

When mocking public static method we could use either of following:

	PowerMockito.mockStatic(MockStaticMethod.class);
	PowerMockito.when(MockStaticMethod.sum(Mockito.anyInt(), Mockito.anyInt())).thenReturn(100);

view raw MockStaticMethodTest.java hosted with ❤ by GitHub

OR

	PowerMockito.mockStatic(MockStaticMethod.class);
	PowerMockito.doReturn(100).when(MockStaticMethod.class, "sum", Mockito.anyInt(), Mockito.anyInt());

view raw MockStaticMethodTest.java hosted with ❤ by GitHub

Here is the implementation

	@Test
	public void testSumRight() throws Exception {
	PowerMockito.mockStatic(MockStaticMethod.class);
	PowerMockito.when(MockStaticMethod.sum(Mockito.anyInt(), Mockito.anyInt())).thenReturn(100);
	MockStaticMethod obj = new MockStaticMethod();
	Assert.assertEquals(100, obj.getResult(0, 0, true));
	Assert.assertEquals(100, obj.getResult(1, 2, true));
	} // testSumRight
	//-----------------------------------------------------------------------------------------------
	@Test
	public void testSumRight2() throws Exception {
	PowerMockito.mockStatic(MockStaticMethod.class);
	PowerMockito.doReturn(100).when(MockStaticMethod.class, "sum", Mockito.anyInt(), Mockito.anyInt());
	MockStaticMethod obj = new MockStaticMethod();
	Assert.assertEquals(100, obj.getResult(0, 0, true));
	Assert.assertEquals(100, obj.getResult(1, 2, true));
	} // testSumRight2

view raw MockStaticMethodTest.java hosted with ❤ by GitHub

BE CAREFUL NOT USE FOLLOWING WITH PUBLIC STATIC METHOD

	@Test
	public void testSumWrong() throws Exception {
	PowerMockito.mockStatic(MockStaticMethod.class);
	PowerMockito.doReturn(100).when(MockStaticMethod.sum(Mockito.anyInt(), Mockito.anyInt()));
	MockStaticMethod obj = new MockStaticMethod();
	Assert.assertEquals(100, obj.getResult(0, 0, true));
	Assert.assertEquals(100, obj.getResult(1, 2, true));
	} // testSumWrong

view raw MockStaticMethodTest.java hosted with ❤ by GitHub

This will give ERROR

  org.mockito.exceptions.misusing.UnfinishedStubbingException: 
  Unfinished stubbing detected here:
  -> at org.powermock.api.mockito.internal.PowerMockitoCore.doAnswer(PowerMockitoCore.java:36)

  E.g. thenReturn() may be missing.
  Examples of correct stubbing:
      when(mock.isOk()).thenReturn(true);
      when(mock.isOk()).thenThrow(exception);
      doThrow(exception).when(mock).someVoidMethod();
  Hints:
   1. missing thenReturn()
   2. you are trying to stub a final method, you naughty developer!
   3: you are stubbing the behaviour of another mock inside before 'thenReturn' instruction if completed      
      

---

---

---

DeRegistration of a service removed health checks on other services?

$\mathtt{REFERENCE}$ @ GitHub Issue

Problem

I had been tyring to integrate Consul and Fabio.

I was able to run both these servers. Also I was able to register services to consul. That was reflected in Fabio as well. I was able to access the registered services through Fabio.

The problem I stuck into was when I tried to Deregister a service from consul, it did deregister but all the Checks from all other services were also gone. Because of the Fabio stopped accessing other services as well.

Solution

Well I really didn't find what was going on with Consul or Fabio.

All I did to fix this issue was Update the Consul version.

I had been using Consul Linux version 1.4.3.

I updated the consul to 1.5.0 and BOOM!! it fixed the issue.

---

---

---

Daily Coding Problem #294: Smallest Weight Strictly Ascending Then Descending Path

Problem Definition

This problem was asked by Square.

A competitive runner would like to create a route that starts and ends at his house, with the condition that the route goes entirely uphill at first, and then entirely downhill.

Given a dictionary of places of the form {location: elevation}, and a dictionary mapping paths between some of these locations to their corresponding distances, find the length of the shortest route satisfying the condition above. Assume the runner's home is location 0.

For example, suppose you are given the following input:

  elevations = {0: 5, 1: 25, 2: 15, 3: 20, 4: 10}
  paths = {
      (0, 1): 10,
      (0, 2): 8,
      (0, 3): 15,
      (1, 3): 12,
      (2, 4): 10,
      (3, 4): 5,
      (3, 0): 17,
      (4, 0): 10
  }
  

In this case, the shortest valid path would be 0 -> 2 -> 4 -> 0, with a distance of 28.

Solution using BackTracking

To solve this problem we need to go through all possible valid paths and determine the minimum weight path.

It can be solved easily with Back Tracking using recursive method.

Solution Overview

• Start from the starting node which is 0.
• For each of the path that can be explored from current node, travel along that path if it is valid i.e. Elevation must be valid since we must travel strictly uphill and then downhill only. Anytime we encounter invalid node, we back track and follow different path. Also if node which has already been visited in given path is encountered we should back track since it will give cycle.
• If we can safely reach final destination node which is 0 again, we store the path summation in a list (OR update miniumum weight)
• After we have found a path, we need to back track again since there may be many possible paths and we need to find the optimal path.

Java Implementation

Following is implementation in Java. This prints lightest weight and the path. (GoLang version solution, below prints all valid paths with their weights.)

	/* File: ShortestPath294.java
	* Created: 2019-05-08
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2019 Hogwart Inc.
	*/
	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	//=================================================================================================
	public class ShortestPath294 {
	public static void main(String[] args) {
	Map<Integer, Integer> elevations = new HashMap<>();
	elevations.put(0, 5);
	elevations.put(1, 25);
	elevations.put(2, 15);
	elevations.put(3, 20);
	elevations.put(4, 10);
	int[][] weights = {
	{0, 1, 10},
	{0, 2, 8},
	{0, 3, 15},
	{1, 3, 12},
	{2, 4, 10},
	{3, 4, 5},
	{3, 0, 17},
	{4, 0, 10},
	{4, 2, 1}
	};
	findPath(elevations, weights);
	elevations.clear();
	elevations.put(0, 5);
	elevations.put(1, 15);
	elevations.put(2, 10);
	elevations.put(3, 25);
	elevations.put(4, 10);
	elevations.put(5, 20);
	elevations.put(6, 0);
	int[][] weights2 = {
	{0, 1, 3},
	{0, 2, 1},
	{1, 5, 5},
	{2, 4, 1},
	{2, 6, 1},
	{4, 0, 0},
	{4, 5, 1},
	{5, 0, 5},
	{5, 4, 1},
	{6, 0, 2},
	};
	findPath(elevations, weights2);
	} // main
	/**
	* Finds smallest weight path that ascends and then descends
	* @param elevations
	* @param weights
	*/
	public static void findPath(Map<Integer, Integer> elevations, int[][] weights) {
	Map<String, Integer> pathsWeight = new HashMap<>();
	Map<Integer, List<Integer>> neighbors = new HashMap<>();
	for(int[] path : weights) {
	pathsWeight.put(path[0] + "-" + path[1], path[2]);
	if(!neighbors.containsKey(path[0])) {
	neighbors.put(path[0], new ArrayList<>());
	}
	neighbors.get(path[0]).add(path[1]);
	}
	List<Integer> bestPath = new ArrayList<>();
	List<Integer> currentPath = new ArrayList<>();
	currentPath.add(0);
	int bestWeight = findPathHelper(elevations, pathsWeight, neighbors, new HashSet<Integer>(), false, 0, currentPath, 0, bestPath, Integer.MAX_VALUE);
	System.out.println(bestWeight);
	System.out.println(bestPath);
	} // findPath
	//---------------------------------------------------------------------------------------------
	/**
	* Helper method that recursively traverses all valid paths and identifies the lightest path.
	*
	* @param elevations node to elevation map
	* @param pathsWeight path to path weight map
	* @param neighbors node to neighbors map
	* @param visited visited nodes in a path
	* @param descending are we currently descending
	* @param current current node being explored
	* @param currentPath nodes in current path so far
	* @param currentPathSum current path sum so far
	* @param bestPath best path so far
	* @param bestWeight best weight so far
	* @return best weight along current node
	*/
	public static int findPathHelper(Map<Integer, Integer> elevations, Map<String, Integer> pathsWeight, Map<Integer, List<Integer>> neighbors,
	Set<Integer> visited, boolean descending, int current, List<Integer> currentPath, int currentPathSum, List<Integer> bestPath, int bestWeight) {
	int currentBestWeight = bestWeight; // multiple path can exist from a node. So we cannot return as soon as we find a path.
	// explore current node
	for(int neighbor : neighbors.get(current)) {
	String weightKey = current + "-" + neighbor;
	if(neighbor == 0) { // we are back to source i.e Destination
	if(elevations.get(neighbor) < elevations.get(current)) { // path should descend at end
	if(currentPathSum + pathsWeight.get(weightKey) < currentBestWeight) { // is the path best path than already found?
	bestPath.clear();
	bestPath.addAll(currentPath);
	bestPath.add(neighbor);
	currentBestWeight = currentPathSum + pathsWeight.get(weightKey);
	}
	}
	} else {
	boolean isPathValid = elevations.get(neighbor) != elevations.get(current); // Path should ascend or descend
	boolean expectDescend = elevations.get(neighbor) < elevations.get(current);
	isPathValid = isPathValid && (!descending || descending && expectDescend); // If we are ascending next can be either ascend or descend.
	// But if we are descending, it must not ascend again.
	if (isPathValid) {
	visited.add(neighbor);
	currentPath.add(neighbor);
	currentBestWeight = findPathHelper(elevations, pathsWeight, neighbors, visited, expectDescend, neighbor, currentPath, currentPathSum + pathsWeight.get(weightKey), bestPath, currentBestWeight);
	currentPath.remove(currentPath.size() - 1);
	visited.remove(neighbor);
	} else {
	// Path is not valid. IGNORE
	}
	}
	}
	return currentBestWeight;
	} // findPathHelper
	} // ShortestPath294

view raw ShortestPath294.java hosted with ❤ by GitHub

GoLang Implementation

Following is implementation in GoLang. This solution actually prints all valid paths with their path weight. It can be easily modified to return the minimum weight path.

	package main
	import "fmt"
	// TestShortestPath solves sample examples
	func TestShortestPath() {
	elevations := map[int]int{
	0: 5,
	1: 25,
	2: 15,
	3: 20,
	4: 10,
	}
	paths := [][3]int{
	{0, 1, 10},
	{0, 2, 8},
	{0, 3, 15},
	{1, 3, 12},
	{2, 4, 10},
	{3, 4, 5},
	{3, 0, 17},
	{4, 0, 10},
	{4, 2, 1},
	}
	findPath(elevations, paths)
	elevations = map[int]int{
	0: 5,
	1: 15,
	2: 10,
	3: 25,
	4: 10,
	5: 20,
	6: 0,
	}
	paths = [][3]int{
	{0, 1, 3},
	{0, 2, 1},
	{1, 5, 5},
	{2, 4, 1},
	{2, 6, 1},
	{4, 0, 0},
	{4, 5, 1},
	{5, 0, 5},
	{5, 4, 1},
	{6, 0, 2},
	}
	findPath(elevations, paths)
	} // TestShortestPath
	//-------------------------------------------------------------------------------------------------
	type path struct {
	weight int
	path []int
	}
	func (p *path) String() string {
	return fmt.Sprintf("Weight: %d Path: %v\n", p.weight, p.path)
	}
	//-------------------------------------------------------------------------------------------------
	// findPath initializes necessary data structures to call findPathHelper
	func findPath(elevations map[int]int, paths [][3]int) {
	neighborsMap := make(map[int]*[]int)
	weights := make(map[string]int)
	for _, path := range paths {
	neighbors, ok := neighborsMap[path[0]]
	if !ok {
	newNeighbors := make([]int, 0)
	neighbors = &newNeighbors
	neighborsMap[path[0]] = neighbors
	}
	*neighbors = append(*neighbors, path[1])
	weightKey := fmt.Sprintf("%d-%d", path[0], path[1])
	weights[weightKey] = path[2]
	}
	var resultPaths = make([]*path, 0)
	var currentPath = make([]int, 0, 1)
	currentPath = append(currentPath, 0) // 0 is starting node of path
	var visited = make(map[int]bool)
	findPathHelper(elevations, neighborsMap, weights, visited, &resultPaths, &currentPath, 0, 0, false)
	fmt.Println(resultPaths)
	} // findPath
	//-------------------------------------------------------------------------------------------------
	// findPathHelper recursively finds all the paths and their sum
	func findPathHelper(elevations map[int]int, neighbors map[int]*[]int, weights map[string]int, visited map[int]bool, paths *[]*path, currentPath *[]int, current int, pathSum int, descending bool) {
	for _, neighbor := range *neighbors[current] {
	weightKey := fmt.Sprintf("%d-%d", current, neighbor)
	if neighbor == 0 {
	if elevations[current] > elevations[neighbor] {
	cpath := make([]int, len(*currentPath), len(*currentPath)+1)
	copy(cpath, *currentPath)
	cpath = append(cpath, neighbor)
	*paths = append(*paths, &path{
	weight: pathSum + weights[weightKey],
	path: cpath})
	} else {
	// Path didn't descend. Path is not valid. Do nothing
	}
	} else { // THIS BLOCK HAS REAPEATED CODE BLOCK. CAN BE MERGED AS IN JAVA VERSION. BUT THIG MIGHT CLARIFY THE SOLUTION.
	if !descending {
	if elevations[current] < elevations[neighbor] {
	visited[neighbor] = true
	*currentPath = append(*currentPath, neighbor) // add neighbor to current path
	findPathHelper(elevations, neighbors, weights, visited, paths, currentPath, neighbor, pathSum+weights[weightKey], false)
	*currentPath = (*currentPath)[:len(*currentPath)-1] // remove neighbor from current path
	visited[neighbor] = false
	} else if elevations[current] > elevations[neighbor] {
	visited[neighbor] = true
	*currentPath = append(*currentPath, neighbor) // add neighbor to current path
	findPathHelper(elevations, neighbors, weights, visited, paths, currentPath, neighbor, pathSum+weights[weightKey], true)
	*currentPath = (*currentPath)[:len(*currentPath)-1] // remove neighbor from current path
	visited[neighbor] = false
	} else {
	// Path didn't strictly = ascend or descend. Path not valid. ignore this neighbor
	}
	} else { // descending
	if elevations[current] > elevations[neighbor] {
	visited[neighbor] = true
	*currentPath = append(*currentPath, neighbor) // add neighbor to current path
	findPathHelper(elevations, neighbors, weights, visited, paths, currentPath, neighbor, pathSum+weights[weightKey], true)
	*currentPath = (*currentPath)[:len(*currentPath)-1] // remove neighbor from current path
	visited[neighbor] = false
	} else {
	// Path didn't descend. Path is not valid. Ignore this neighbor
	}
	}
	}
	}
	} // findPathHelper

view raw shortest_path.go hosted with ❤ by GitHub

Complexity

This solves the problem by traversing every possible paths. So the theoretical time complexity is $O(2^n)$.

However since the question has restriction that the path has to strictly ascend and then descend, we are returning path as invalid as soon as we encounter invalid path. Because of this restriction, in practice the time complexity will be $O(n).$

Alternative Solution with Memoization

In the previous solution, we start from first node 0 and keep on exploring all possible paths all the way to destination. During the exploration we keep updating track of path sum for all paths and update the best path.

In this solution, we compute the best path and best path weight that can be attained from given node. We cache this result and use it later when we encounter the same node in other path.

This solution does not require to pass currentPath, currentPathSum, bestPath and bestWeight to findPathHelper()

Computation is done from the end. Idea is lightest tail path will be part of the solution path.

Following in implementation.

	/* File: ShortestPath294.java
	* Created: 2019-05-08
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2019 Hogwart Inc.
	*/
	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	//=================================================================================================
	/**
	* Daily coding problem #294
	*
	* Computes shortest path that starts from 0 and ends in 0 again, strictly ascends and then descends.
	*
	*/
	public class ShortestPath294 {
	public static void main(String[] args) {
	Map<Integer, Integer> elevations = new HashMap<>();
	elevations.put(0, 5);
	elevations.put(1, 25);
	elevations.put(2, 15);
	elevations.put(3, 20);
	elevations.put(4, 10);
	int[][] weights = {
	{0, 1, 10},
	{0, 2, 8},
	{0, 3, 15},
	{1, 3, 12},
	{2, 4, 10},
	{3, 4, 5},
	{3, 0, 17},
	{4, 0, 10},
	{4, 2, 1}
	};
	findPath(elevations, weights);
	elevations.clear();
	elevations.put(0, 5);
	elevations.put(1, 15);
	elevations.put(2, 10);
	elevations.put(3, 25);
	elevations.put(4, 10);
	elevations.put(5, 20);
	elevations.put(6, 0);
	int[][] weights2 = {
	{0, 1, 3},
	{0, 2, 1},
	{1, 5, 5},
	{2, 4, 1},
	{2, 6, 1},
	{4, 0, 0},
	{4, 5, 1},
	{5, 0, 5},
	{5, 4, 1},
	{6, 0, 2},
	};
	findPath(elevations, weights2);
	} // main
	/**
	* Finds smallest weight path that ascends and then descends
	* @param elevations
	* @param weights
	*/
	public static void findPath(Map<Integer, Integer> elevations, int[][] weights) {
	Map<String, Integer> pathsWeight = new HashMap<>();
	Map<Integer, List<Integer>> neighbors = new HashMap<>();
	for(int[] path : weights) {
	pathsWeight.put(path[0] + "-" + path[1], path[2]);
	if(!neighbors.containsKey(path[0])) {
	neighbors.put(path[0], new ArrayList<>());
	}
	neighbors.get(path[0]).add(path[1]);
	}
	Object[] best = findPathHelper(elevations, pathsWeight, neighbors, new HashSet<Integer>(), false, 0, new HashMap<>(), new HashMap<>());
	System.out.println(best[0]);
	System.out.println(best[1]);
	} // findPath
	//---------------------------------------------------------------------------------------------
	/**
	* Helper method that recursively traverses all valid paths and identifies the lightest path. It computes from the end and uses memoization.
	*
	* @param elevations node to elevation map
	* @param pathsWeight path to path weight map
	* @param neighbors node to neighbors map
	* @param visited visited nodes in a path
	* @param descending are we currently descending
	* @param current current node being explored
	* @param weightCache cache for weights holding best weight that can be achieved from a node
	* @param pathCache cache for paths holding best weight that can be achieved from a node
	* @return array of best weight and best path from current node
	*/
	public static Object[] findPathHelper(Map<Integer, Integer> elevations, Map<String, Integer> pathsWeight, Map<Integer, List<Integer>> neighbors,
	Set<Integer> visited, boolean descending, int current, Map<Integer, Integer> weightCache, Map<Integer, List<Integer>> pathCache) {
	if (weightCache.containsKey(current)) {
	return new Object[]{weightCache.get(current), pathCache.get(current)};
	}
	int bestWeightFromCurrent = Integer.MAX_VALUE;
	List<Integer> bestPathFromCurrent = new ArrayList<>();
	// explore current node
	for(int neighbor : neighbors.get(current)) {
	String weightKey = current + "-" + neighbor;
	if(neighbor == 0) { // we are back to source i.e Destination
	if(elevations.get(neighbor) < elevations.get(current)) { // path should descend at end
	if (bestWeightFromCurrent > pathsWeight.get(weightKey)) {
	bestWeightFromCurrent = pathsWeight.get(weightKey);
	bestPathFromCurrent.add(neighbor);
	}
	}
	} else {
	boolean isPathValid = elevations.get(neighbor) != elevations.get(current); // Path should ascend or descend
	boolean expectDescend = elevations.get(neighbor) < elevations.get(current);
	isPathValid = isPathValid && (!descending || descending && expectDescend); // If we are ascending next can be either ascend or descend.
	// But if we are descending, it must not ascend again.
	if (isPathValid) {
	visited.add(neighbor);
	Object[] pathDetails = findPathHelper(elevations, pathsWeight, neighbors, visited, expectDescend, neighbor, weightCache, pathCache);
	int pathWeightFromNeighbor = (int) pathDetails[0];
	if(pathWeightFromNeighbor != Integer.MAX_VALUE) {
	int weightWithNeighbor = pathsWeight.get(weightKey) + pathWeightFromNeighbor;
	if (bestWeightFromCurrent > weightWithNeighbor) {
	bestWeightFromCurrent = weightWithNeighbor;
	bestPathFromCurrent.clear();
	bestPathFromCurrent.addAll((List)pathDetails[1]);
	}
	}
	visited.remove(neighbor);
	} else {
	// Path is not valid. IGNORE
	}
	}
	}
	weightCache.put(current, bestWeightFromCurrent);
	bestPathFromCurrent.add(0, current);
	pathCache.put(current, bestPathFromCurrent);
	return new Object[]{bestWeightFromCurrent, bestPathFromCurrent};
	} // findPathHelper
	} // ShortestPath294

view raw ShortestPath294.java hosted with ❤ by GitHub

Complexity

The time complexity will be $O(n).$

---

---

---

Daily Coding Problem #291: Minimum Number of Boats to save population

Problem Definition

An imminent hurricane threatens the coastal town of Codeville. If at most two people can fit in a rescue boat, and the maximum weight limit for a given boat is k, determine how many boats will be needed to save everyone.

For example, given a population with weights [100, 200, 150, 80] and a boat limit of 200, the smallest number of boats required will be 3.

Solution

To be able to determine the smallest number of boats, we need to maximize the number of pairing. To maximize the number of pairing, for given weight we must pair with the maximum value possible. If we pair we smaller weight we may not get the minimum number.

For example, given a population with weights [30, 150, 170, 50] and a boat limit of 200. Here if we pair 30 with 50, then 150 and 170 are left alone hence resulting into the result 3. However, it is possible to pair 30 with 170 and 50 with 150 satisfying the constraint. This pairing will give the result 2.

Therefore, for each weight, we must pair it with the maximum weight possible. We might be tempted to use following solution:

1. For each weight, iterate through rest of the weights to find the maximum weight with which it can be paired. Make sure to avoid already used weight.

This solution will work, but it will have time complexity $O(n^2)$

Solution Using Sorting

Following is implementation is using sorting. This method is still $O(n^2)$. It takes $O(n)$ time find pair. I am trying to figure out if the pair could be found in $O(logn)$ time instead so that the overall time complexity will be $O(nlogn)$

Implementation

	/* File: Boats.java
	* Created: 7/24/2019
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2019 Hogwart Inc.
	*/
	import java.util.Arrays;
	import java.util.Collections;
	//=======================================================================================
	/**
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class Boats {
	/**
	* Driver method
	*/
	public static void main(String[] args) {
	System.out.println(compute(new Integer[]{100, 200, 150, 80}, 200) + " == " + 3);
	System.out.println(compute(new Integer[]{30, 40, 70, 100, 200, 150, 80}, 200) + " == " + 4);
	System.out.println(compute(new Integer[]{}, 1) + " == " + 0);
	System.out.println(compute(new Integer[]{100}, 200) + " == " + 1);
	System.out.println(compute(new Integer[]{200, 10, 200, 200}, 200) + " == " + 4);
	System.out.println(compute(new Integer[]{200, 200, 10, 200, 200}, 200) + " == " + 5);
	System.out.println(compute(new Integer[]{170, 160, 30, 90}, 200) + " == " + 3);
	System.out.println(compute(new Integer[]{150, 150, 150, 30}, 200) + " == " + 3);
	} // main
	//-----------------------------------------------------------------------------------------------
	/**
	* Computes number of boats required
	* @param weights array of weights of population
	* @param limit weight limit of each boat
	* @return number of boats needed
	*
	*/
	public static int compute(Integer[] weights, int limit) {
	if(weights.length == 0) return 0;
	Arrays.sort(weights, Collections.reverseOrder());
	boolean[] used = new boolean[weights.length];
	int boats = 0;
	for(int idx = 0; idx < weights.length; idx++) {
	if (used[idx]) continue;
	if (weights[idx] == limit) {
	boats++;
	continue;
	}
	int pair = findPair(weights, used, limit - weights[idx], idx+1, weights.length-1);
	if (pair > -1) {
	used[pair] = true;
	}
	boats++;
	}
	return boats;
	} // compute
	/**
	* Find pairing for the limit provided
	* @param weights
	* @param used
	* @param limit
	* @param lo
	* @param hi
	* @return
	*/
	private static int findPair(Integer[] weights, boolean[] used, int limit, int lo, int hi) {
	int lastValid = -1;
	for (int i = hi; i >= lo; i--) {
	if (!used[i]) {
	if (weights[i] == limit) {
	return i;
	} else if (weights[i] < limit) {
	lastValid = i;
	} else {
	return lastValid;
	}
	} else {
	continue;
	}
	}
	return lastValid;
	} // findPair
	} // Boats

view raw Boats.java hosted with ❤ by GitHub

Complexity

Sorting can be done in $O(n logn)$ time.
Finding a pair will take $O(n)$ time.

$\therefore$ The Time Complexity of this method will be $\cal{O(n^2)}$.

---

---

---

Kruskal's MST Algorithm Using Union-Find Data Structure

$\mathtt{REFERENCE}$ @ Source Class Notes

Kruskal's Algorithm

1. Like Prim's Algorithm, it is also a greedy algorithm.
2. While Prim's Algorithm starts from single node and keep growing to reach a final tree, this algorithm starts with $|V|$ trees and keep on combining to finally reach the MST.

Main Features

1. It starts with a forest of size $n = |V|$ trees.
2. At each step, it combines two trees to obtain a bigger tree and reduces the number of tress in the forest by 1.
3. When the forest has a single tree, it is a Minimum Spanning Tree (MST).

Use Union-Find data structure to make it faster.

Formal Sketch of Kruskal's MST Algorithm

1. $A = \phi$ // A is an empty forest
2. Sort the edges in the graph in increasing order of the weight.
3. for each edge $(u,v) \in G.E$ in increasing order of weight {
   1. if $u$ and $v$ are not already connected (find by using Union-Find) {
      1. $A = A \cup \{(u,v)\}$
      2. UNION(u,v) // Union-Find operation
      }
   }
4. return A

Implementation

Following is the implementation of above explanation.

	import java.util.Arrays;
	import java.util.Comparator;
	public class Kruskal {
	/**
	* Driver method
	*/
	public static void main(String[] args) {
	Graph graph = new Graph(7, 13);
	graph.addEdge(0, 1, 6);
	graph.addEdge(0, 2, 6);
	graph.addEdge(0, 3, 5);
	graph.addEdge(1, 3, 8);
	graph.addEdge(1, 4, 5);
	graph.addEdge(2, 3, 8);
	graph.addEdge(2, 5, 3);
	graph.addEdge(3, 4, 9);
	graph.addEdge(3, 5, 4);
	graph.addEdge(5, 6, 1);
	graph.addEdge(4, 6, 1);
	graph.addEdge(3, 6, 2);
	graph.addEdge(2, 6, 1);
	Kruskal k = new Kruskal();
	int[][] result = k.MST(graph);
	for(int[] res : result) {
	System.out.println(res[0] + " " + res[1] + " " + res[2]);
	}
	} // main
	//-----------------------------------------------------------------------------------------------
	/**
	* Computes the MST of given connected graph.
	* Returns array of N-1 edges that belongs to the MST.
	* Assumes that the input graph is connected.
	*
	* @param Graph graph whose MST is to be computed.
	* @return Array of edges belonging to the MST
	*
	* Algorithm:
	* 1. Create a sorted queue of Edges sorted by their weight
	* 2. Greedily Pick lightest edge and include it in the result if it does not create cycle
	* 3. When there are N-1 edges return the edges
	*
	*/
	public int[][] MST(Graph g) {
	// Initialize container to hold result edges. There will be N-1 edges
	int[][] result = new int[g.N - 1][3];
	int cursor = 0; // cursor to point to the index to insert an Edge
	// Initialize Union-Find data structure, that will assist to know
	// if two vertex are already connected or not
	WQuickUnion uf = new WQuickUnion(g.N);
	// Sort Graph Edges in non-decreasing order of the edge weight
	g.sortEdges();
	int[] edge = g.getNextEdge();
	while(edge != null) {
	if (!uf.find(edge[0], edge[1])) { // check if source and target nodes are connected or not
	result[cursor++] = edge;
	uf.union(edge[0], edge[1]);
	if (cursor == g.N) break; // we already have N-1 Tree edges
	}
	edge = g.getNextEdge();
	}
	return result;
	} // MST
	} // Kruskal
	//=================================================================================================
	/**
	* Class to represent a graph
	*/
	class Graph {
	int N; // Number of vertices. Vertices will be numbered 0, 1, 2, 3, ....
	int[][] E; // Edges in Graph. Each edge will be 3 element array representing source vertex, target vertex and the weight.
	int cursor = 0; // cursor for inserting and retrieving edges
	//-----------------------------------------------------------------------------------------------
	/**
	* Constructor
	* @param N number of vertices in the graph
	* @param E number of edges in the graph
	*
	*/
	public Graph(int N, int E) {
	this.N = N;
	this.E = new int[E][3];
	} // Graph
	//-----------------------------------------------------------------------------------------------
	/**
	* Adds an edge to the graph
	*
	* @param s source node
	* @param t target node
	* @param w weight of edge
	*
	*/
	public void addEdge(int s, int t, int w) {
	this.E[cursor++] = new int[]{s, t, w};
	} // addEdge
	//-----------------------------------------------------------------------------------------------
	/**
	* Sort the edges of the graph in increasing order of weights.
	*
	*/
	public void sortEdges() {
	Arrays.sort(this.E, new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
	return o1[2] - o2[2];
	} // compare
	});
	this.cursor = 0;
	} // sortEdges
	//-----------------------------------------------------------------------------------------------
	/**
	* Get next edge as pointed by cursor.
	* Cursor will be reset if sortEdges() is called.
	* @return returns current edge pointed by cursor
	*/
	public int[] getNextEdge() {
	if(cursor == E.length) return null;
	return E[cursor++];
	} // getNextEdge
	} // Graph
	//=================================================================================================
	/**
	* Class to represent Union-Find Data structure
	* This is Weighted Quick Union version of the data structure.
	*
	*/
	class WQuickUnion {
	private int[] id; // id[i] represent parent of the element at index i
	private int[] size; //size[i] represent number of nodes element at index has
	//-----------------------------------------------------------------------------------------------
	/**
	* Constructor to initilize the data structure.
	* @param n number of elements.
	*
	*/
	public WQuickUnion(int n) {
	id = new int[n];
	size = new int[n];
	for (int i = 0; i < n; i++) {
	id[i] = i;
	size[i] = 1;
	}
	} // WQuickUnion
	//-----------------------------------------------------------------------------------------------
	/**
	* Identifies whether two nodes p and q are connected or not
	* @param p first node
	* @param q second node
	* @return True if the two nodes are connected otherwise False
	*/
	public boolean find(int p, int q) {
	return root(p) == root(q);
	} // find
	//-----------------------------------------------------------------------------------------------
	/**
	* Connects two nodes in the network
	* @param p first node
	* @param q second node
	*/
	public void union(int p, int q) {
	int i = root(p);
	int j = root(q);
	if (size[i] < size[j]) {
	id[i] = j;
	size[j] += size[i];
	} else {
	id[j] = i;
	size[i] += size[j];
	}
	} // union
	//-----------------------------------------------------------------------------------------------
	/**
	* Finds the root of current element
	* @param p current element index
	* @return index of the root of input index
	*/
	private int root(int p) {
	while(p != id[p]) {
	id[p] = id[id[p]]; // Path Compression. Keeps tree almost completely flat. Will still work if this line is removed.
	p = id[p];
	}
	return p;
	} // root
	} // WQuickUnion

view raw Kruskal.java hosted with ❤ by GitHub

Complexity

• Sorting takes $O(|E|log|E|)$ times
• Union-Find operations can be done in $O(log|V|)$ time if properly implemented

$\therefore$ The Time Complexity of this method will be $O(|E|log|E|)$ time.

for dense graph, $|E| \approx |V|^2 \Rightarrow$ SLOW
for sparse graph, $|E| \approx |V| \Rightarrow$ FAST

---

---

---

Look And Say or Count And Say Sequence

$\mathtt{REFERENCE}$ @ LeetCode

This is a LeetCode Problem. You can find it HERE

Problem Definition

This problem is actually generation of $look-and-say\ sequence$. DESCRIPTION

The count-and-say sequence is the sequence of integers with the first five terms as following:

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221
 
 1 is read off as "one 1" or 11.
 11 is read off as "two 1s" or 21.
 21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.
  

Solution

Then $nth$ sequence is generated using $(n-1)th$ sequence. So the obvious solution would to go on generating sequences starting from $n=1$ for which the $sequence = 1$.

Algorithm to generate a sequence from previous sequence is simple.

1. Traverse through previous sequence character by character.
1. Maintian the count of repeated character.
2. When a new character is encountered, append to result the $count$ and the $character$.
2. Return result.

We will have to repeat this algorithm until the required sequence is generated.

P.S. When I was tyring to solve this problem, I was looking for more efficient solution. More specifially I was looking for a pattern so that I could directly generate the $nth$ sequence without computing the intermediate sequences. As it turns out, there is no such solution. So the process described above is the actual solution to this problem.

Implementation

Following is the implementation in $GoLang$.

Important thing to keep in mind during the implementation is the generation of intermediate strings. Be careful to generate intermediate and final sequence in $\cal{O(n)}$ time.

	func countAndSay(n int) string {
	prev := "1"
	if n == 1 {
	return prev
	}
	for i := 2; i <= n; i++ {
	prev = compute(prev)
	}
	return prev
	}
	func compute(term string) string {
	var sb strings.Builder
	prev := rune(term[0])
	var count int = 0
	for _, v := range term {
	if v == prev {
	count++
	} else {
	fmt.Fprintf(&sb, "%d", count)
	sb.WriteRune(prev)
	prev = v
	count = 1
	}
	}
	fmt.Fprintf(&sb, "%d", count)
	sb.WriteRune(prev)
	return sb.String()
	}

view raw look-and-say.go hosted with ❤ by GitHub

Complexity

Method countAndSay() runs for $\cal{O(n)}$ time $n$ being the $nth$ sequence number.

Method compute() which computes current sequence using previous sequence, runs for $\cal{O(m)}$ time where $m$ is number of characters in previous sequence.

Assuming $m=n$, The Time Complexity of this solution will be $\cal{O(n^2)}$.

---

---

---

String in GoLang

$\mathtt{REFERENCE}$ @ Blog.GoLang.Org

• The BLOG explains how slices work in Go
• This post is more or less summary of Go string
• Efficient use of string requires understanding not only how they work, but also
  1. the difference between a byte, a character and a rune
  2. the difference between Unicode and UTF-8
  3. the difference between a string and a string literal
  4. and other even more subtle distinctions

"When I index a Go string at position n, why don't I get the nth character?" As you'll see, this question leads us to many details about how text works in the modern world."

An excellent introduction to some of these issues, independent of Go, is Joel Spolsky's famous blog post, The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!).

What is string?

1. In Go, a string is in effect a read-only slice of bytes.
2. It's important to state right up front that a string holds arbitrary bytes. It not required to hold Unicode text, UTF-8 text or any other predefined format. As far as the content of a string is concerned, it is exactly equivalent to a slice of bytes

Code Points, Characters and Runes

1. As mentioned above, a string holds bytes.
2. The idea of $Character$ is a little hard to define. The Unicode standard uses the term $Code Point$ to refer to the item represented by a single value. The code point U+2318, with the hexadecimal value 2318, represents the symbol ⌘. The concept of $Character$ in computing is ambiguous or at least confusing.
3. $Code Point$ is a bit of a mouthful, so Go introduces a shorter term for the concept: $rune$. It means exactly the same as $Code Point$ with one interesting addition. The Go language defines the word rune as an alias for the type int32, so programs can be clear when an integer value represents a code point. Moreover, what you might think of as a character constant is called a rune constant in Go. The type and value of the expression '⌘' is rune with integer value 0x2318.

Range Loops

1. With a regular $for$ loop, we get bytes of the string
2. A $for\ range$ loop, by contrast, decodes one UTF-8-encoded $rune$ on each iteration. Each time around the loop is the starting position of the current rune, measured in bytes and the $Code\ Point$ is its value.

---

---

---

Print given String in ZigZag Fashion

Problem Definition

Given a string and a number of lines $k$, print the string in zigzag form.

In zigzag, characters are printed out diagonally from top left to bottom right until reaching the $kth$ line, then back up to top right, and so on.

For example, given the sentence "thisisazigzag" and k = 4, you should print:

t     a     g
 h   s z   a
  i i   i z
   s     g

Solution

The solution to this problem would be to construct $k$ lines and print them.

Key Problem

Construction of each of the line is the key part of this problem. Each line would consist necessary characters from the $input\ string$ separated by required number of $spaces$. To construct each line we need to identify characters belonging to the line and number of spaces to be inserted after/before each of the characters.

Basic Algorithm

To construct each line,

1. Insert necessary number of spaces in the beginning of the line
2. Identify next character that belongs to this line and append to it
3. Append necessary number of spaces
4. Go to step 2, if there are more characters that belong to this line, otherwise print the line and move on to next line

Identify Size of spaces and Next Belonging Character

Assuming $0\ index$ based line numbers.

1. For $ith\ line$, number of spaces that starts the line $=\ i$
2. Index (say $index$) of first character that belong to $ith\ line = i$
3. Number of spaces that follows after a character depends upon whether we are moving $up\ or\ down$. For simplicity we can assume that at character on first line $i = 0$, we are always moving $down$, while for the last line $i = k-1$, we are always moving $up$. For other lines we will be alternatively moving $up$ and $down$ starting from moving down because initially we are moving down.

             If we are moving up,
                gapSize = 2 * i - 1
   
             Else if we are moving down,
                j = k - i - 1
                gapSize = 2 * j - 1
           

   
4. Index of next character will be $index = index + gapSize + 1$

Implementation

Following is the implementation as described above.

	import java.util.Scanner;
	public class ZigZag {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String input = "I am Lord Voldemort. Lord Voldemort is my past, my present and my future!!!"; //sc.next();
	System.out.print("Enter value of K: ");
	int K = sc.nextInt();
	System.out.println();
	for (int i = 0; i < K; i++) {
	StringBuilder sb = new StringBuilder();
	sb.append(new String(new char[i]).replace('\0', ' ')); // logic may be changed to create string of spaces
	int index = i;
	boolean up = i == K - 1; // for all lines except last, we start by moving down
	while(index < input.length()) {
	sb.append(input.charAt(index)); // append char
	int gapSize; // compute and append spaces
	if (up) {
	gapSize = 2 * i - 1;
	} else {
	int j = K - i - 1;
	gapSize = 2 * j - 1;
	}
	sb.append(new String(new char[gapSize]).replace('\0', ' ')); // logic may be changed to create string of spaces
	index += gapSize + 1; // index of next char for current line
	// set direction for next character
	if (i == 0) { // for top line always consider we are moving down
	up = false;
	} else if (i == K - 1) { // for last line always consider we are moving up
	up = true;
	} else { // for middle lines we alaternatively move down and up
	up = !up;
	}
	}
	System.out.println(sb.toString());
	}
	}
	}

view raw ZigZag.java hosted with ❤ by GitHub

Complexity

Ignoring the time complexity to construct string of empty spaces, the time complexity of this implementation is $O(n)$ because we go through each of the characters in the input string only once.

---

---

---