Reverse a linked list

I got a phone interview with a tech company located in San Francisco Bay Area.

The interviewer questioned me about a linked list. I think that a linked list is basic but still can get really hard to answer in a short time under tremendous pressure.

The question goes:

Reverse any given linked list. For example, if a linked list A->B->C is given, return a new linked list C->B->A as an answer.

The interviewer gave me a hint that a simple loop is easier to program than recursion. After I struggled a lot, I came up with a rather clumsy solution. Probably, the interviewer wasn't very impressed.

I should have studied more about data structures...Well, "don't cry over split milk" though.

So today I have thought about a recursion version of the solution. I implemented it in Ruby. It took me quite a time (about 1 hour) to complete the code shown below. Please take a look if you are interested.

require 'test/unit'

class Node
  attr_accessor :value
  attr_accessor :next

  def initialize(value)
    self.value = value
  end

  def add(node)
    n = self
    until n.next.nil?
      n = n.next
    end  
    n.next = node
  end

  def self.from_array(a)
    return nil if a.nil? || a.size == 0
    list = nil 
    a.each do |value|
      if list.nil?
        list =  Node.new(value)
      else
        list.add(Node.new(value))
      end 
    end
    list
  end

  def to_array
    arr = []
    n = self
    until n.nil?
      arr.push(n.value)
      n = n.next
    end
    arr
  end 
end

# returns [head, tail]
def reverse_linked_list_impl(list)
  if list.next.nil?
    return [list, list]
  end
  head, tail = reverse_linked_list_impl(list.next)
  tail.next = list
  list.next = nil 
  return [head, list]
end

def reverse_linked_list(list)
  head, tail = reverse_linked_list_impl(list)
  return head
end

class TestAlgorithm < Test::Unit::TestCase
  def test_from_array
    list = Node.from_array([1, 2, 3])
    assert_equal(1, list.value)
    assert_equal(2, list.next.value)
    assert_equal(3, list.next.next.value)
  end

  def test_to_array
    list = Node.new(3)
    list.add(Node.new(5))
    list.add(Node.new(7))
    assert_equal([3, 5, 7], list.to_array) 
  end
  
  def test_reverse_linked_list
    arr = [1]    
    assert_equal(arr.reverse, reverse_linked_list(Node.from_array(arr)).to_array)
    arr = [1, 2]   
    assert_equal(arr.reverse, reverse_linked_list(Node.from_array(arr)).to_array)
    arr = [3, 1, 2]   
    assert_equal([2, 1, 3], reverse_linked_list(Node.from_array(arr)).to_array)
    arr = [5, 3, 1, 2]   
    assert_equal([2, 1, 3, 5], reverse_linked_list(Node.from_array(arr)).to_array)
 end

 end

TweetMonkey allows you to tweet from any page on the web - now Google Chrome extension supports OAuth

TweetMonkey is a web browser tool that allows you to post messages on Twitter from any web page on the spot. With this application, It takes just a few clicks to tweet.



Last year, I built a Google Chrome extension for TweetMonkey.

TweetMonkey allows you to tweet from any page on the web - latest Google Chrome version has been released.

Shortly after this release, however, Twitter stopped offering Basic Authentication. All Twitter clients are now required to support OAuth. Implementing OAuth was so painful that it took me a long time to complete the OAuth supported version of TweetMonkey.

Prerequisites
All you need should be the latest version of Google Chrome. Mine is version 13.0.782.112 on Mac.
Google Chrome on Windows should also work.

How to install
Click on the link below to start the installation. You will be navigated to Chrome Web Store.

Install TweetMonkey now

Once the installation is completed, you will be navigated to a Twitter page and asked to authorize TweetMonkey to access to your Twitter account. Please authorize it (you can always disallow it by logging out on the option screen). Twitter page will show it as "TweetMonkeyEx" but this is what you want to get. Please be assured.

How to use
You left-click on the TweetMonkey icon and will see a pop up show up. Enter a text and click on "Update" button to tweet. You can also enter the title and a shorten URL of the active tab by clicking on the chain icon.

Right-click TweetMonkey icon in the right top corner of Chrome and choose "Option". Once the option screen shows up, you can log out and prevent TweetMonkey from accessing to your Twitter account.

Have fun!

References
This time, I check out so many websites to gather the information. I would like to show my gratitude to all the authors. Especially, I learned a lot on how to implement OAuth and Google Chrome extension from Twitter Notifier. I would like to thank its auther, Peter Josling.

Source code
You can get a file called tweet_monkey.crx from the download link above. This is the extension file but it is merely a zipped file. Once you unzip it, you can have a look at source code of this software.

Maybe I should post this to Chrome Webstore to reach broader audience. Before making this extension public, I would like to change the icon of the application. This "t" shape icon was taken from an old Twitter official website, so I need to change it to something original. If you could help me, please give me a shout. I would be very grateful.

A "Hello World" Twitter client with OAuth

Last year I wrote a Twitter client that allows you to tweet on any webpage in the browser. Shortly after I released it, Twitter abolished BASIC authentication and my Twitter client was not working any longer because of it. The age of OAuth has come, but I haven't done anything about it.

Now I've started working on OAuth stuff again. I took a look at some blog entries and tried to build my first "Hello World" progarm for Twitter API with OAuth. This looked simple but it took me some time to write it. I will show you a few steps on how to write a Twitter client with OAuth in Ruby.

As a prerequisite, you need to have two Ruby gem packages installed on your system. If not, run the following commands on the terminal:

sudo gem install oauth
sudo gem install twitter

1. Get a consumer key and a consumer secret by registering your client at Twitter's website.

2. Have the users authorize your Twitter client to use their account

Type "irb" to start irb on the terminal. Copy and paste the below(double-click on the pane and you can copy and paste more easily):

require 'rubygems'
require 'oauth'

CONSUMER_KEY = "(your consumer key)"
CONSUMER_SECRET = "(your consumer secret)" 

consumer = OAuth::Consumer.new(CONSUMER_KEY, CONSUMER_SECRET, :site => "http://twitter.com")

request_token = consumer.get_request_token 
request_token.authorize_url

Navigate to the URL for user authorization and have users to authorize your client to access to their account information.(Most likely, your client's first user is yourself. If so, authorize your client to access to your own Twitter account).

3. Get OAuth token and secret to access to the account information of your Twitter client users.

Keep entering the below on the irb session:

require 'twitter'

oauth_verifier = "(a number shown on the user authorization screen)" 

access_token = request_token.get_access_token(:oauth_verifier => oauth_verifier )
token = access_token.token
secret = access_token.secret

Twitter.configure do |config|
  config.consumer_key = CONSUMER_KEY 
  config.consumer_secret = CONSUMER_SECRET
  config.oauth_token = token
  config.oauth_token_secret = secret 
end 

Twitter.update("Hello World!")

Congratulations! Now you should be able to see a tweet with "Hello World" posted to the authorized account.

Sorting algorithms in Ruby

If you wish to learn sort algorithms, this is the best website to visit. Bad news for English speakers is that this site is written in Japanese.

The author of the website uses Java for his sample code. I could write Java code but I am not a big fan of it since Java forces me to type too much (Who wants to type "HashMap<nteger, Boolean> map = new HashMap<Integer, Boolean>()" when you can do the same task by typing "map = {}" in Ruby?). So I rewrote his sample programs in Ruby.

There are three interesting algorithms: heap sort, merge sort and quick sort. They are the most efficient ones among all the sorting algorithms.

Let's start with heap sort.

class HeapSort
def initialize
@heap = []
end

def push(item)
@heap << item
    i = @heap.size
    j = i / 2
    while i > 1
      if @heap[i - 1] < @heap[j - 1]
        t = @heap[i - 1]
         @heap[i - 1] = @heap[j - 1]
         @heap[j - 1] = t
       end
       i /= 2 
       j = i / 2
    end
  end 

  def pop
   res = @heap.shift
   return res if @heap.size == 0
   last_item = @heap.pop
   # bring the last item to the root
     @heap.unshift(last_item)
     i = 1
     j = 2
     while j <= @heap.size
       if j < @heap.size && @heap[j - 1] > @heap[j]
       j += 1
    end
    if @heap[i - 1] > @heap[j - 1]
      t = @heap[i - 1]
      @heap[i - 1] = @heap[j - 1]
      @heap[j - 1] = t
    end
    i = j
    j *= 2
  end
  res
end

def run(list)
    list.each do |item|
    push(item)
end

res = []
while item = pop
res << item
    end

    res 
  end
end

Heap sort is a bit tricky in terms of how to maintain a balanced binary tree. It looks complicated especially when you remove the root element from the tree (look at pop() method above). The second algorithm is merge sort.

class MergeSort
  def initialize
  end

  def merge(a1, a2, a)
    i = 0
    j = 0
    while i < a1.size || j < a2.size
      if j >= a2.length || (i < a1.length && a1[i] < a2[j])
        a[i+j] = a1[i]
        i += 1
      else
        a[i+j] = a2[j]
        j += 1
      end 
    end
  end

  def merge_sort(a) 
    if a.size > 1
      m = a.size / 2
      n = a.size - m
      a1 = []
      a2 = []
      0.upto(m - 1) do |i|
        a1[i] = a[i]
      end
      0.upto(n - 1) do |i|
        a2[i] = a[m + i]
      end 
      merge_sort(a1);
      merge_sort(a2);
      merge(a1, a2, a);
    end 
  end 

  def run(list)
    a = list.dup
    merge_sort(a)
    a
  end
end

The idea of merge sort is rather simple. You can implement it with recursion elegantly. And the last one is the queen of sorting algorithms, quick sort.

class QuickSort
  def initialize
  end
  
  def pivot(a, i, j)
    k = i + 1
    while k <= j && a[i] == a[k] 
      k += 1
    end
 
    if k > j  
      return -1 
    end
  
    if a[i] >= a[k] 
      return i
    end
 
    return k
 end

  def partition(a, i, j, x)
    l=i
    r=j
    while l <= r
      while l<=j && a[l] < x  
        l += 1
      end
      while r>=i && a[r] >= x 
        r -= 1
      end
      if l > r 
        break
      end
      t=a[l]
      a[l]=a[r]
      a[r]=t
      l += 1
      r -= 1
    end 
    return l
  end 

  def quick_sort(a, i, j)
    if i == j 
      return
    end
    p = pivot(a, i, j)
    if p != -1
      k = partition(a, i, j, a[p])
      quick_sort(a, i, k - 1)
      quick_sort(a, k, j)
    end 
  end 

  def run(list)
    a = list.dup
    quick_sort(a, 0, a.size - 1)
    a
  end
end

Although finding a pivot is a little tricky, quick sort is a cool algorithm. It is so elaborated that it almost looks like magic.

Usually Java or C/C++ is used to describe algorithms, but Ruby is also great because it can highlight the essence of algorithms with a fewer lines. I LOVE RUBY, MAY RUBY LIVE FOREVER!

A philosophical difference in hiring processes for software engineers between US and Japan

A person currently working in US suggested me reading a book named "Cracking the Coding Interview". He told me that the book was one of the most famous books that let software engineers prepare for their recruiting interviews. I was so impressed and excited because the way US software companies hire engineers is so rational.

It says that interviewers can ask very intricate technical questions that relate to algorithm and coding. Sounds great! That's the way it should be.

In Japan, interviewers rarely test candidates with coding questions, odd as it might sound. Japan's IT industry was dominated by a few big software "general contractors" such as NTT Data and they usually don't look into candidates' technical skill set scrupulously. Instead, they rather attach greater importance to candidates' "communication skills", a vague concept that allegedly guarantees a candidate to be a good "team player".

However, I think that this is an absolute nonsense. A software engineer is supposed to be hired to code, not to chat. If a candidate is a very likable nice guy, but is unable to code even a line, he is useless in the workplace of software production. No wonder that Japanese IT industry has lost its competitive edge.

I feel very encouraged. I have finally found a reason to study computer science in earnest. If nobody really cares about proper knowledge on algorithm, who is willing to make serious efforts to learn it, after all?