I have implemented a simple LRU Cache. The code is far from production use. First of all it is not thread safe and I have not used template programming to make it generic. The code is just to illustrate one of the possible ways of implementing an LRU Cache.

The implementation is inspired from Sun Java LinkedHashMap implementation. For serious production use one should use the LinkedHashMap implementation. The code here is just to illustrate the data structure used.

I have used a doubly-linked list and a hashmap. All the key-value pairs are saved in a node of doubly-linked list and these nodes are hashed on the key in the hashmap. This allows for O(1) time access. The node corresponding to the most recently used key-value pair is always at the head of the linked list and the node corresponding to the least recently used key-value pair is always at the tail of the linked list. Time complexity for ‘get’ and ‘put’ operation is O(1) and the space complexity is O(n), where n is the maximum capacity of cache.

Here goes the code -

public class Node {

  public Node prev;
  public Node next;
  public String key;
  public String data;

  public Node()
  {
  }

  public Node(String key, String data)
  {
    this.key = key;
    this.data = data;
  }
}

import java.util.*;

public class LRUCache {

  private Node head;
  private Node tail;
  private int maxSize;
  private HashMap<String, Node> m = new HashMap<String, Node>();

  // Constructor - maxSize is the maximum capacity of the cache
  public LRUCache(int maxSize)
  {
    this.maxSize = maxSize;
    head = new Node(null, null);
    tail = new Node(null, null);
    head.next = tail;
    tail.prev = head;
  }

  private void addElementToListAtHead(Node node)
  {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
  }

  private void removeElementFromList(Node node)
  {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  // Function to access data from the cache
  public String get(String key)
  {
    Node node = m.get(key);
    if(node == null)
      return null;

    if(m.size() == 1)
      return node.data;

    removeElementFromList(node);
    addElementToListAtHead(node);
    return node.data;
  }

  // Function to add new data or modify existing data in the cache
  public void put (String key, String data)
  {
    if(maxSize <= 0)
      return;

    Node node = m.get(key);
    if (node != null)
    {
      removeElementFromList(node);
      addElementToListAtHead(node);
      node.data = data;
    } else {
      node = new Node(key, data);
      m.put(key, node);
      addElementToListAtHead(node);
      if(m.size() > maxSize)
      {
        m.remove(tail.prev.key);
        removeElementFromList(tail.prev);
      }
    }
    return;
  }
}

Please point out the obvious/non-obvious bugs in the code. And also provide suggestions for better implementation.

After the recent India-SA test series, the big question is which is the better test team. Obviously, if we go by test rankings India is currently the number 1 test team and the mighty SA the second in the list. But ICC decided to organize a three match series between the two sides to decide the ultimate team. They propose to Indian cricket team – if they can win at least two consecutive matches they will be declared the number 1 team of all times. The three matches will be played alternatively in India and South Africa. The Indian team can decide the order, either they can choose to play in India-SA-India or SA-India-SA. The ICC also lifted up the 5 day constraint – which means each match will end up with a result for sure, no draw. For quite obvious reasons the probability of India winning a match in India is more than India winning a match in SA.

Now the question in front of BCCI is to select the order of venues to maximize the probability of India becoming the best test team of all times.

BCCI first came up with the order – India-SA-India, which also sounds obvious. But, when they later realized that India has to win at least two consecutive matches to prove their supremacy, they changed the order to SA-India-SA which is not so obvious but of course the correct strategy (at least probabilistically).

Do some calculations yourself to appreciate the BCCI’s final decision.

int binary_search(int *a, int len, int key)
{
int low = 0;
int high = len-1;

while (low <= high)
{
int mid = (low+high)/2;
int val = a[mid];

if (val < key)
{
low = mid + 1;
} else if (val > key)
{
high = mid - 1;
} else
{
return mid;
}
}
return -1;
}

Now, try to find the bug in the above code. The bug surfaces if the array is too large. If the length of the array is too large, line number 8 in the above code would cause the variable “mid” to overflow and hence will have a negative number and the code breaks. A very simple solution would be to replace line 8 in the above code with -

mid = low + (high-low)/2;

So, you see how bugs could creep in your code. To see more detailed discussion on how the bug was discovered and a couple of more elegant, efficient solutions check out this Google Research blog – http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

• Page Replacement Algorithms – I have been digging into various page/memory replacement algorithms. For the uninitiated ones here is the wikipedia page which explains various of those algorithms in short – http://en.wikipedia.org/wiki/Page_replacement_algorithm . I explored the memcached cache replacement policy and its implementation. I will write more about my reading on this subject in my later posts. I will also try to attach implementations of few of the algorithms.
• OpenStack – Openstack is an IaaS Cloud Computing open source project started by Rackspace and NASA. There are basically two sub projects of Openstack – Nova and Swift. I have read the overview of both the sub projects and I am trying to dig more into Nova. I would love to contribute to this awesome project and will start off soon by accomplishing some low hanging fruits of Nova. Will write more about my experience and technical insights I gain in my later posts.
• Art of Trading – I have been looking into various articles related to algorithmic trading. I started off with Optimal Stopping Theorem. Depth first search of the wikipedia article led me to Search Theory, Odds Algorithm, the interesting “The Marriage Problem” . But things start getting mathematically complex once I start digging into Automated Trading Algorithms. ATQs use techniques from signal processing, game theory, gambling Kelly Criterion and time series analysis. Miles to go. Phew!

And yeah, I have also been listening to two songs continuously (read frequently) these days – Madno Re from Lamhaa (2010) and Naam Adaa Likhna from Yahaan (2005).

Today I added a new feature to the “IITG webmail chrome extension” – Auto Login feature. Now you can save your username and password in the options page of the extension and enable auto-login. After enabling auto-login feature, whenever you open http://webmail.iitg.ernet.in, the extension will automatically redirect you to your inbox.

Check out the screenshots at the extension page: https://chrome.google.com/extensions/detail/ljfkohgffehmmfnmghdlbceidmddgdob?hl=en-us

All those who are already using this extension can update it by clicking “Update extensions now” button in chrome://extensions page. New users can directly install the extension at: https://chrome.google.com/extensions/detail/ljfkohgffehmmfnmghdlbceidmddgdob?hl=en-us

Keep pouring in your feedback by posting comments.

I wrote about a chrome extension in my yesterday’s post. 1st and 2nd year students of IITG have different mail servers than Disang. They won’t be able to use the extension. So, I updated the extension. Now one can set the default mail server and save the option. Now, the extension works for all the mail servers.

Those who have already installed the extension can update it by clicking on the button “Update Extensions Now” button in the Chrome Extension page. And those who have not yet installed the extension can install the updated version directly from : https://chrome.google.com/extensions/detail/ljfkohgffehmmfnmghdlbceidmddgdob?hl=en

Keep pouring in your feedbacks in the comments.

IITG webmail accounts are hosted on different servers for students, staff and faculty. So every time I open the page – http://webmail.iitg.ernet.in, I have to change the server to Disang. I wrote a simple chrome plugin to do this automatically, every time I visit this page.

It is simple to use. You need to have the latest version of Google chrome installed. Once you have it, just click on this link: https://chrome.google.com/extensions/detail/ljfkohgffehmmfnmghdlbceidmddgdob and then press “Install” button. And you are done. Now open the webmail page – http://webmail.iitg.ernet.in and check out the selected server.

Send me feedback by commenting to this blog or at the plugin page.

One can download the script from here: http://www.spsneo.com/scripts/poststatus.tar.gz

How to use it -

1) Change the permission of the file to make it executable: chmod +x poststatus

2) Then execute the file with the status message as the argument: ./poststatus "Status Message goes here in quotes"

3) The script will first post the status message in your pidgin and will then ask whether you want to post it on twitter.  If you say yes, the script asks you for your twitter username and password.

Start using the script and send me feedback to improve it.

According to bash manual page -

History  expansions introduce words from the history list into the input stream, making it easy to repeat commands, insert the arguments to a previous command into the current input line, or fix errors in previous commands quickly.

History expansion is composed of three parts -

• Event Designators: It is a reference to an entry in the history list.
• Word Designators: It is used to select a word from the event.
• Modifiers: Modifies the word selected by the word designator or the action of the command.

All the three parts are optional and are separated from each other by a : (colon). There can be multiple modifiers each separated by a : (colon).

Now I will explain each part one by one.

Event Designators:

1. ! Start a history substitution, except when followed by a blank, newline, carriage return,  = or (
2. !n It refers to n’th command in the history. So if you just type in
   !68 at the command prompt, 68th command in your history list will be executed.
3. !-n It refers to n’th command in the history from last. So if you just type in !-1 at the command prompt, last command will be executed.
4. !! is an alias for !-1. Example:
   $apt-get install gnome-ppp    //Permission Denied. You need to be sudo to do this!
$sudo !!                      // This is equivalent to sudo apt-get install gnome-ppp
5. !string It refers to the most recent command in the history starting with string. It is again an useful expansion when you don’t remember the arguments to a command which you have executed earlier.
6. !?string[?] It refers to the most recent command containing string. The trailing ? may be omitted if string is immediately followed by a newline.

Word Designators:

1. n The nth word, count starting from 0. 0th word normally refers to the command. Example:
   $sudo cat /etc/resolv.conf     //Instead you want to edit the resolv.conf file
$sudo vi !!:2                       //This is equivalent to sudo vi /etc/resolv.conf
2. ^ This refers to 1st word. This is equivalent to :1 as refered above. The only .advantage is that you can omit : (colon) when you use ^. Example:
   $cat ~/.bashrc
$vi !!^        //This is equivalent to "vi !!:1" that is vi ~/.bashrc

3. $ This refers to the last word.
4. x-y This refers to a range of words; ‘-y‘ is equivalent to ’0-y’.
5. * This refers to all the words except the 0th one. This is helpful when you have to execute a command with all the arguments passed to the last command.
6. x* This is an alias for x-$ .

Note: If a word designator is used without an event specification, the last command in the history is used as the event. Example -
$cat ~/.bashrc
$vi !:1 // This is equivalent to vi !!:1 or vi ~/.bashrc

Modifiers:

1. h This removes the trailing file name component, leaving the head. Example:
   $cat /home/spsneo/.bashrc
$ls !!:1:h //This expands to ls /home/spsneoExplanation: !! refers to the last command and then :1 refers to the 1st word of the last command and then :h removes the trailing file name component i.e., .bashrc . Hence the expansion.
2. t This removes all leading file name components, leaving the tail.
3. r This removes the trailing suffix of the form .xxx , leaving the basename.
4. p Print the new command but do not execute it.
5. s/old/new This substitutes the first occurrence of old with new. Example:
   $cat /etc/resolv.conf
$!!:s/resolv/yum //This expands to cat /etc/yum.conf

6. g This is used in conjunction with “:s” modifier. This causes changes to be applied over the entire event line rather than just the first occurrence. Example:
   $cat test.cpp test.h
$!!:gs/test/source/ //This expands to cat source.cpp source.hh

This is all I have to share about bash history expansion.

Do post comments if you find any mistake or if you want any further clarifications. One can also go through the bash manual pages for more options.

I wrote a script which when executed automatically sets the GNOME wallpaper as BING background of the day. This is a PHP script. To execute this script you need to have php installed on your system. You can install php in Ubuntu as

sudo apt-get install php5 php5-cli

Now you are all set to download this script. Download Link: http://www.spsneo.com/scripts/bing_wallpaper.tar.gz

Download this file, extract the script file. Now you can run the script from terminal :
php bing_wallpaper.php

And your wallpaper is set. You can run this script daily from your terminal or you can set a cron job for the same or you can set up an icon in your gnome panel for this script.

I will keep updating this script. And I am also planning to write the same script in python. So check back again if you dont want to install php on your system.

Send your feedbacks and suggestions.

Update 1: I have modified the script to work with http proxy. Just assure that the environment variable http_proxy is properly set.

Update 2: Modified the script to keep the image centered on the desktop with black background. Try it out.