Learning Revisited: April 2015

Thursday, April 30, 2015

Java Collections Cheat Sheet

Source: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgFLPosNUOWvHe2Ah2DMKkQJrVGThQgpdPixuChwCAtaCS9i50Ipy7gklwR3Eima3xe-gdsplRdGFY0zZ8tlboe8ZgFnQaSiZvGgcywojwQ1wdaAf8g2smM6XkNVffoa8oqSvXG-ECrFg/s1600/Java+collection+cheat+sheet.PNG

HashMap internal implementation in Java

Below link provides good explanation about this topic.

http://javarevisited.blogspot.in/2011/02/how-hashmap-works-in-java.html

http://javahungry.blogspot.com/2013/08/hashing-how-hash-map-works-in-java-or.html

HashSet internal implementation in Java

HashMap.put method will return

oldValue: if key is already present, then it will overwrite the value and returns old value
null: if key is not present, then it will add this key,value pair and then returns null.

In case of HashSet, internally it has a hashmap. When we call add method it will call 'put' method of the hashmap and if put method returns null means new entry is added into hashmap and hashset

more at: http://javahungry.blogspot.com/2013/08/how-sets-are-implemented-internally-in.html

Java example of impementing equals, hashCode, compareTo, toString methods

Source: Java Official website

import java.util.*;

public class Name implements Comparable {
    private final String firstName, lastName;

    public Name(String firstName, String lastName) {
        if (firstName == null || lastName == null)
            throw new NullPointerException();
        this.firstName = firstName;
        this.lastName = lastName;
    }

    public String firstName() { return firstName; }
    public String lastName()  { return lastName;  }

    public boolean equals(Object o) {
        if (!(o instanceof Name))
            return false;
        Name n = (Name) o;
        return n.firstName.equals(firstName) && n.lastName.equals(lastName);
    }

    public int hashCode() {
        return 31*firstName.hashCode() + lastName.hashCode();
    }

    public String toString() {
 return firstName + " " + lastName;
    }

    public int compareTo(Name n) {
        int lastCmp = lastName.compareTo(n.lastName);
        return (lastCmp != 0 ? lastCmp : firstName.compareTo(n.firstName));
    }
}

Java purpose of AtomicInteger

We can use AtomicInteger to avoid count++ issue in mutli-threading environment.

AtomicInteger provides incrementAndGet() and decrementAndGet() methods which are thread safe.

With use of AtomicInteger, we can solve this problem without using synchronized keyword

more: https://docs.oracle.com/javase/tutorial/essential/concurrency/atomicvars.html

http://javarevisited.blogspot.in/2012/01/how-to-write-thread-safe-code-in-java.html

Friday, April 24, 2015

Find the smallest positive integer value that cannot be represented as sum of any subset of a given array

Question Details:

Given a sorted array (sorted in non-decreasing order) of positive numbers, find the smallest positive integer value that cannot be represented as sum of elements of any subset of given set.
Expected time complexity is O(n).

Examples:

Input:  arr[] = {1, 3, 6, 10, 11, 15};
Output: 2

Input:  arr[] = {1, 1, 1, 1};
Output: 5

Input:  arr[] = {1, 1, 3, 4};
Output: 10

Input:  arr[] = {1, 2, 5, 10, 20, 40};
Output: 4

Input:  arr[] = {1, 2, 3, 4, 5, 6};
Output: 22

more: http://www.geeksforgeeks.org/find-smallest-value-represented-sum-subset-given-array/

Solution Explanation:
http://stackoverflow.com/a/21078133/4507251