Wednesday, November 09, 2011

Puzzle: Finding if a linked list has a loop

Puzzle statement:
You are given the reference to the head of a singly linked list. Come up with an algorithm to find out if the linked list has a loop. 
Credit:  I believe I read this problem in Sedgewick's Algorithms in C book first.

Puzzle: First common parent

I love to come up with elegant and simple algorithms for hard problems. Recently one thought came to my mind: why don't I create a catalog of interesting puzzles that I come across. I am sure it will be useful to some people. At least to those who are preparing for an interview. So here is my first in the series.

Disclaimer: I do not claim ownership of any of these puzzles that you will see in this series, unless explicitly noted. If I know the source, I give credit to the source. If I don't know the source and you do, please drop a comment pointing me to the original source of the puzzle.

Here is the problem:
You are given a binary search tree. For the sake of simplicity, assume that each node in the binary search tree holds an integer value and all the values are unique. Each node in the binary search tree has a reference to its right child and left child, but not to its parent. Given root, and two random nodes, find the first common parent of these two nodes. In case one of them is the ancestor of the other, return the ancestor node as the common parent.
Please note that you can only perform downward traversal, as none of the nodes have a reference to its parent.

Saturday, October 22, 2011

Loading Lisp file from URL in Emacs

On a given day, I have to login and work from multiple Linux boxes. One thing I find annoying is that every time I make a change to my .emacs file, I have to copy the changes to all the hosts.

There are multiple ways to circumvent this issue. One way I find useful is to maintain my custom file as a gist in github (or any where you can host your .emacs file) and use the following code snippet in the .emacs to load the file from the URL.

  (shell-command "curl -Ls" (current-buffer))
Let me explain what this code snippet does:
  1. It creates a temporary buffer.
  2. With the temporary buffer as the current buffer, it fetches the contents of the URL into the current buffer.
  3. It evaluates the current buffer.
  4. Remove the temporary buffer.

If the sample code above works for you, if you eval the "(hello-world)", it will say "hello world" in the mini buffer.

Monday, October 17, 2011

Fastest way to switch between buffers in Emacs

In any given Emacs session, I have at least 5 buffers open. One of the pains of using C-x b to switch between buffers is that after typing every few characters, you have to type tab to perform completion. It is a waste of time.

iswitchb is a much more efficient alternative to the default switch-to-buffer that is invoked while you type C-x b. It is time saving in two ways: (1) there is no need to type tab for completion and (2) you can give any part of the buffer name in the minibuffer prompt and jump to that buffer.

To enable this mode, add the following line in your .emacs file.
(iswitchb-mode 1) 
Thats it. You are ready to rock-n-roll.

More info at:

Font face customization in Emacs - an easy way

I usually edit source code using Emacs running inside a PuTTY session. One of the struggles I often run into is how to customize different elements I see on the screen. For e.g. the prompt in the shell-mode, previously executed command line, shell input, etc.

While I googled around a bit, I came across this incredibly useful key binding: C-u C-x =. It runs the command "what-cursor-position". Here is how you can use this: You position the cursor on the element you would like to customize, and type C-u C-x =. You will be presented with the properties of the character at point, including links to customize the character.

I find this extremely useful and hope sharing this information will help others as well.


Friday, October 14, 2011

Perlbrew saved the day

After an insanely long period of silence, I am writing another blog entry. I couldn't contain my excitement with what I learnt today and hence this post.

I had to upgrade Perl installation in my Linux host and I visited to download and install Perl. It was suggested to make use of the perlbrew to install and manage different versions of Perl under your home directory. I gave it a try and it was incredibly simple to upgrade the Perl installation in my box, without screwing up the old installation (which I still need for some of the old scripts I have).

If you haven't tried it yet, I would strongly recommend.

Monday, February 21, 2011

Two cookie attributes you MUST be aware to secure your web app

There are two attributes of cookies that every web developer must be aware of to secure your web application. These two attributes doesn't save your application from all attacks, but at least they reduce the vulnerability to a great extent. These two attributes are:

  • HttpOnly
  • Secure
The first attribute HttpOnly says that the cookie is intended to be passed only as a part of HTTP communication. Hence it must not be available to the application (like JavaScripts running in the browser). So once you load a page, if you type "javascript:alert(document.cookie)" in the URL bar, you will not those cookies that have the HttpOnly flag set.

The second attribute Secure tells that the cookie should be sent as a part of the request if and only if the communication happens over a HTTPS channel. Typically login requests are sent over HTTPS channels. (If you are using a web app that is using HTTP for login page, its time you stop using it!). Typically, as a part of the login response, there will be two sets of cookies set. One that can be sent over both HTTP and HTTPS and another set that can be sent only over HTTPS. It is the cookies that are to be sent over HTTPS that serious parts of your web application should depend on. For e.g. check out of your shopping cart.

You can learn more about HttpOnly flag here and here.Also you can learn more about Secure flag in the wiki page.

Saturday, February 19, 2011

Cygwin and irb

If you had tried to start irb in Windows that has cygwin installed, you might have got the following exception trace:

C:/Ruby192/lib/ruby/site_ruby/1.9.1/rbreadline.rb:2095:in `expand_path': non-absolute home (ArgumentError)
        from C:/Ruby192/lib/ruby/site_ruby/1.9.1/rbreadline.rb:2095:in `_rl_read_init_file'
        from C:/Ruby192/lib/ruby/site_ruby/1.9.1/rbreadline.rb:2078:in `rl_read_init_file'
        from C:/Ruby192/lib/ruby/site_ruby/1.9.1/rbreadline.rb:2499:in `readline_initialize_everything'
        from C:/Ruby192/lib/ruby/site_ruby/1.9.1/rbreadline.rb:3730:in `rl_initialize'
        from C:/Ruby192/lib/ruby/site_ruby/1.9.1/rbreadline.rb:4737:in `readline'
        from C:/Ruby192/lib/ruby/site_ruby/1.9.1/readline.rb:40:in `readline'
        from C:/Ruby192/lib/ruby/1.9.1/irb/input-method.rb:115:in `gets'
        from C:/Ruby192/lib/ruby/1.9.1/irb.rb:139:in `block (2 levels) in eval_input'
        from C:/Ruby192/lib/ruby/1.9.1/irb.rb:273:in `signal_status'
        from C:/Ruby192/lib/ruby/1.9.1/irb.rb:138:in `block in eval_input'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:188:in `call'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:188:in `buf_input'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:103:in `getc'
        from C:/Ruby192/lib/ruby/1.9.1/irb/slex.rb:205:in `match_io'
        from C:/Ruby192/lib/ruby/1.9.1/irb/slex.rb:75:in `match'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:286:in `token'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:262:in `lex'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:233:in `block (2 levels) in each_top_level_statement'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:229:in `loop'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:229:in `block in each_top_level_statement'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:228:in `catch'
        from C:/Ruby192/lib/ruby/1.9.1/irb/ruby-lex.rb:228:in `each_top_level_statement'
        from C:/Ruby192/lib/ruby/1.9.1/irb.rb:155:in `eval_input'
        from C:/Ruby192/lib/ruby/1.9.1/irb.rb:70:in `block in start'
        from C:/Ruby192/lib/ruby/1.9.1/irb.rb:69:in `catch'
        from C:/Ruby192/lib/ruby/1.9.1/irb.rb:69:in `start'
        from C:/Ruby192/bin/irb:12:in `
The solution to this problem is very simple. Just unset the HOME environment variable and start irb again.
set HOME=
Some of them are not directly related to Cygwin. But resetting will help you in avoiding issues while running gems.