csTechie

Find the maximum rectangle completely contained inside a histogram where each bars has a width of 1 unit. The heights of the bars of the histograms are given in an array e.g. {4,2,10,8,12,13,15,8,6} and they have a fixed width w = 1, say. The rectangles formed here are: 4X1, 2X9, 10X1, 8X6, 12X3, 13X2, 15X1, 8X6, 6X7 Thus, max-area rectangle = 8X6 = 48

Find the longest palindrome in a given string

Find Median of 2 sorted arrays

Given a Binary Search Tree, write a program to print the kth smallest element

This is a very common interview questions and comes in various forms. The most common one is of the following format
Problem 1
Given an array of 999 distinct integers ranging from 1 to 1000 including. Find which number is missing. Restrictions: loop over the array only once, can’t allocate an additional array.

Another version of the problem is where 2 numbers are missing.
Problem 2
Given an array of 998 distinct integers ranging from 1 to 1000 including. Find which 2 numbers are missing.

Restrictions: loop over the array only once, can’t allocate an additional array.

Write an algorithm to shuffle an array of 52 integers so that each number has equal probability to be in any of the 52 positions.