Sign in

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

[1] Capacity attribute is a performance hint. ArrayList will grow or shrink dynamically irrespective of what the capacity is set to.

[2] 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

[3] 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 Set interface.”

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 e1.equals(e2)

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 sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into 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 sticks into one stick in this way.

Key Idea

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…


Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store