Problem of the day: kth permutation

Problem of the day for today is kth permutation: Given numbers n and k, 1 <= k < INT_MAX, return kth permutation of the set [1,2,…,n]. For example, given n=3 and k=4, the permutations of [1,2,3] in order are:

  1. “123”
  2. “132”
  3. “213”
  4. “231”
  5. “312”
  6. “321”

k=4th permutation is “231”. To simplify the output, a string concatenation of the numbers is returned.

Continue reading

Problem of the day: Largest rectangle in a histogram

Problem of the day for today is Largest rectangle in a histogram: Given n non-negative integers representing the histogram’s bar heights where the width of each bar is 1, find the area of largest rectangle in the histogram.


In this example, we are given 7 heights [6, 2, 5, 4, 5, 1, 6] and can see that the area of the largest rectangle is 3*4 = 12.

Continue reading

Problem of the day: Detecting cycle in a linked list

Today I was looking at problems related to linked lists. They tend to be asked quite a lot in interviews but some of them look artificial with their complexity arising from linked lists being a poor data structure for the problem (e.g., median of a sorted linked list). The problem of the day for today is Detecting cycle in a linked list: Given a linked list, return the node where the cycle begins or null if there is no cycle. For example, in the image below, 4 should be returned.


Continue reading

The true cost of FREE!

I just finished reading this wonderful book: Predictably Irrational by Dan Ariely. It describes how we systematically behave irrationally, hence making it predictable. Although I consider myself a fairly rational person, I must confess I’ve acted rather irrationally a few times in the past (Ah, to be young and foolish). I would’ve thought that those were erratic, one-off cases but the book presents a case that there are patterns underlying our fallibility. One pattern that really resonated with me was how we behave irrationally around zero cost. There’s a particular allure for free stuff.

Continue reading