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.

Problem of the day: kth permutation

Problem of the day for today is k^th permutation: Given numbers n and k, 1 <= k < INT_MAX, return k^th 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=4^th permutation is “231”. To simplify the output, a string concatenation of the numbers is returned.

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.

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.

Problem of the day: Longest palindromic substring

Problem of the day for today is Longest palindromic substring: Given a string, find its longest palindromic substring.. For example, given the string “ababab”, the longest palindromic substring would be “ababa”.