Problem of the day: Queue with min operation

I came across this incredibly interesting problem that took me quite a while to solve: implementing a queue that supports the minimum operation, i.e., aside from the normal queue operations (enqueue, dequeue), it should also support a minimum operation, whereby a client could ask for the minimum element in the queue at any point. Before someone jumps in and says well that’s just a min priority queue, no, there’s a difference. Priority queues don’t return elements in the order in which they were inserted but in the order of their priority. This queue has to return elements in the order in which they were inserted and also support querying for the current minimum element in the queue.

Continue reading

Advertisements

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.

largest-rectangle-in-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.

cycle-in-linked-list

Continue reading