Wrote a compact LRU (Least Recently Used) cache implementation using LinkedHashMap’s access order facility. In a LRU cache eviction policy is to evict entries which have been accessed the longest time ago. LinkedHashMap maintains a doubly linked list of entries internally which is by default in insertion order but it has a constructor which allows you to specify that the list be maintained in access order. This is perfect for LRU cache since any of the methods such as get and put (and their variants) are considered access methods and will update the list. To be even one step ahead…
Just wanted to jot down some notes on Java’s ArrayList
 Capacity attribute is a performance hint. ArrayList will grow or shrink dynamically irrespective of what the capacity is set to.
 Having capacity set does not mean you can read or write to an index which has not been added.
var list = new ArrayList<Foo>(100); // initial capacity of 100
list.set(0, new Foo()); // error, index 0 was never 'added'
//java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
 Performance tip: When adding elements in tight loop, if you have an approx. idea of number of elements you…
I came across a note in TreeSet’s javadoc which intrigued me:
“Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the
What does that mean? The TreeSet doc says to read the doc for Comparable or Comparator so that’s what I did and here’s what I found:
“The natural ordering for a class
C is said to be consistent with equals if and only if
e1.compareTo(e2) == 0 has the same boolean value as
This post is one in the series of posts about Scala. My goal is to provide simple examples to illustrate important gotchas or points about the language.
Function Return Type
Return type is optional, but it’s better to declare it because compiler may not be able to infer it to the intended type.
For the sake of simplicity here’s an example in which the function returns Int or Boolean so compiler infers it to be AnyVal
scala> def func1(x: Int) = if (x > 1) x else falsefunc1: (x: Int)AnyVal
But if you declare it to be Int explicitly…
You have some
stickswith positive integer lengths.
You can connect any two sticks of lengths
Yinto one stick by paying a cost of
X + Y. You perform this action until there is one stick remaining.
Return the minimum cost of connecting all the given
sticksinto one stick in this way.
The key thing to note here is that given a bunch of sticks the cost to combine any two sticks will be minimum for the two smallest sticks. Now you may immediately think of sorting the sticks and then just run…