Showing posts with label map. Show all posts
Showing posts with label map. Show all posts

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







Sunday, April 8, 2018

Number Pairs Whose Sum is Multiple of a Number X

$\mathtt{DOWNLOAD\ SOLUTION}$

Task Description

Kelly gives Ashley N chocolates each having a price pi, (where pi is the price of ith chocolate), and an integer X. She asks her to group the N chocolates in to pairs such that sum of prices of chocolates in each pair is a multiple of X.

Output yes if its possible to group the chocolates in to pairs and No if its not possible.

Solution 1: Considering all possible $nC2$ pairs

The first solution is to try to form pairs and satisfies our constraint. If at any point, if the constraint is not satisfied, we will need to Backtrack and try out different pairs.

For the size of array $n$, there are total of $nC2 \approx n^2$ possible combinations. So the complexity will be ${\cal O}(n^2)$.

Solution 2: Optimization of Solution 1

Consider four numbers $a,\ b,\ c,\ d$
Let,
            a + c is a multiple of X
       and, b + d is a multiple of X
    
So the numbers can be paired as $[a,\ c]$ and $[b,\ d]$

Now,what will happen if $a + b$ is also a multiple of X?

  a + c = CONST1 * X
  b + d = CONST2 * X
  a + b = CONST3 * X

  a + b + c + d = (CONST1 + CONST2) * X
  CONST3 * X + (c + d) = (CONST1 + CONST2) * X
  c + d = (CONST1 + CONST2 - CONST3) * X

This proves that (c + d) is also a multiple of X.

So in general, if
  • $a$ and $d$ pairs up,
  • $a$ pairs up with a set of numbers $S1$ and
  • $d$ pairs up with a set of numbers $S2$
Then, $a$ and $d$ can pair up with any number in the sets $S1$ and $S2$.

With this conclusion, we can optimise our Solution 1 by eliminating the Backtrack. We can keep on pairing up numbers. If all numbers have pairs, we can return True. If any number does not have a pair, we can return False.

Time Complexity

Even after the optimization, at worst case, for each element we need to go through all elements. $\therefore$ Total Time complexity is ${\cal O}(n^2)$. The space complexity is ${\cal O}(n)$ for the array paired.

Solution 3: Linear Time Solution

The problem can be solved in linear time by traversing the array only once.

Principle

If sum of two numbers a and b is multiple of a number X,

Then,
      (a % X) + (b % X) = X     if a % x > 0
                        = 0     if a % X == 0
    
So, in order for all numbers to pair up,
      number of elements in the array with modulo X value C  
          == number of elements in the array with module X value X - C
    
Following are the linear time solutions.

Solution Using Array

Solution Using Hash Map

Time Complexity

In this solution, we traverse through the input array only once. Important thing to note here is, the size of the array count is the value of input integer X. So if there is no constraint over the value of X, then the solution could be Pseudo-Polynomial. Otherwise , the overall time complexity is ${\cal O}(n)$. The Space complexity is ${\cal O}(X)$.