Friday, December 6, 2019

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







Wednesday, July 24, 2019

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.







Monday, July 8, 2019

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








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

Test Implementation








Monday, June 17, 2019

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

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)}$.






Friday, May 17, 2019

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.

Mock Private Static Method

For mocking private static method we need to use

Mock Public Static Method

When mocking public static method we could use either of following:
OR
Here is the implementation

BE CAREFUL NOT USE FOLLOWING WITH PUBLIC STATIC METHOD

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.