[Amazon Interview] Largest Rectangular area in a histogram

Find the largest rectangular are in a histogram where largest area can be made up of contiguous bars.
For simplicity, assume that all bars have same width of 1 unit.

Binary tree to doubly linked list

Convert a given linked list into doubly linked list in O(n) time.

Coin Change

Given a value N, we want to make change for N cents and we have infinite supply of each of S={S1, S2...Sm}valued coins, how many ways we can make the change? The order of coins does not matter.

For example for N=4, and S={1,2,3}, there are four solutions: {1,1,1,1}, {1,1,2}, {2,2},{1,3}. So output should be 4.

[Microsoft] All subset of a set

Generate all subset of a given set. Example: Given set- {1,2,3}
Output: {}, {1}, {2}, {3},{1,2},{1,3},{2,3},{1,2,3}

[Amazon Interview] Queue using stack

Implement a queue using two stacks.

[Inmobi Interview] String: Replace space with %20

Write a method to replace all spaces in a string with %20.

Print all combination of balanced parenthesis

Write a function to generate all possible pair of parenthesis.

For example: if n=1 , then output: {}
                     if n=2, then output {}{}, {{}}

[Amazon Interview] Copy of a linked list

Given a DLL, with next pointer pointing to the next node in the list and one arbit pointer which can point to any node, not just the previous one. Duplicate this linked list in O(n) time and O(1) space complexity.

Kth maximum and minimum in BST

Find Kth maximum and minimum element in a BST.

Inorder Traversal of BST without stack and recursion

Write a program to do inorder traversal of a BST in O(n) time.

Array: Rearrange characters and intergers

Given an array[a1b2c3d4] -> convert to [abcd1234] with O(1) space and O(n) complexity.

[Amazon interview] Equilibrium Index of an Array

Equilibrium index of an array is an index such that sum of elements at lower indexes is equal to sum of the elements at higher indexes.

For example:  in an array {-7, 1, 5, 2, -4, 3, 0}, 3 and 6 are the equilibrium indexes.
Write a function equilibrium(int a[], int n) that prints all equilibrium indexes if present .
Time complexity should be O(n).

Quick Sort for an array

Write a program to do quick sort for an array.

Merge Sort for an Array

Write a program to do merge sort for a given array.

[Amazon interview] Leftmost node at each level in a tree

Print the leftmost node of each level in a tree.

[Amazon interview] Minimum absolute difference between two arrays

Given two sorted arrays of equal length, how do u find a pair of numbers one from each array such that absolute difference between two numbers is minimum.

[Amazon interview] Stock Buy Sell to maximize profit

The cost of stock is given on each day. Find the maximum profit that you can make by buying and selling it on those days. There can be two conditions.
1. You can buy and sell only once
2. You can buy and sell multiple times

For example: If the given array is {100,180,260, 310, 40, 535, 695}
The maximum profit can be earned by buying on Day 0, selling on day 3. Again buy on day 4 and sell on Day 6.

[Amazon Interview] Binary search tree

You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create

another array ar_low[] such that ar_low = number of elements lower

than or equal to ar in ar[i+1:n-1].

So the output of above should be {0,2,1,2,2,1,0}

Time complexity : O(nlogn)

use of extra space allowed.

[Dynamic programming] Longest Increasing Subsequence

Find the length of longest sub sequence of a given sub sequence such that all the elements of the sub sequence are sorted in increasing order.

For example : length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6.

[Amazon Online Written Test] Pattern Searching Algorithm

Write a function search (char pat[], char txt[]) that searches for pat[] in txt[] and print all the occurences of pat[] in txt[].

[Amazon Online written test] Rectangle Overlapping problem

Write a function to check if two rectangles defined as below, have common area or not. The functions take the top left and bottom right coordinate as input and return 1 if they have common area, otherwise return 0.

Input                              Output
10                                         1
20
20
10
10
20
20
10

[Amazon Online written test] N Coin problem

Given a list of N coins, their values {a1, a2, ...aN} and the total sum S. Find the minimum number of coins , the sum of which is S(we can use as many coins of one type as we want) or return -1 if it's not possible to select coins in such a way that they sum upto S.

Explanation for algorithm is given here:
http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

[Amazon Written test] Run Length Encoding

Write a function to convert AAABBBBBCDEHH to A3B5CDEH2 and a method to generate the original string back.

Linked List: Merge a linked list into another

Given two linked list, insert nodes of second linked list into first at alternate position of first list.

Ex- first List is 1->2->3->4->5 and second list is 6->7->8->9->10
first list should be 1->6->2->7->3->8->4->9->5->10 and second list empty

The nodes of second list should be inserted only if positions are available.
Ex- first List is 1->2->3- and second list is 4->5->6->7->8
first list should be 1->4->2->5->3->6 and secodn list should be 7->8

Use of extra space is not allowed. Expected tiem complexity should be O(n) where n is the number of nodes.

[Amazon Interview] Longest substring

Given two string s1 and s2, find longest substring which is prefix of s1 as well as suffix of s2.

Dynamic Programming: Longest Common Substring

Given two strings, find the length of longest common substring.
For example: Given strings are:  "GeeksForGeeks" and  "GeeksQuiz". The out put should be 5.

Bit Magic: Count set bits in floating point number

Givenn a floating point number, write a function to count ste bits in its binary representation.
For example: Floating point representation of 0.15625 has 6 set bits.

[Amazon Online written test] Array In-place transposition

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn].

Sample Testcases:

Input #00:

{1,2,3,4,5,6,7,8,9,10,11,12}

Output #00:

{1,5,9,2,6,10,3,7,11,4,8,12}

Explanation:

Here as you can notice, the array is of the form

{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4}

Array: Rearrange Positive and negative numbers

Rearrange positive and negative numbers in O(n) time and O(1) complexity. If there are more positive or negative number, they will appear at the end of the array.
Ex:
Input Array : {-1,2,-3,4,5,6,-7,8,9}
Output  Array:  {9,-7,8,-3,5,-1,2,4,6} 

Fibonacci Number

How to check if a number is fibonacci number or not?

[Amazon] Pair wise swap in Linked List

Given a singly linked list, write a function to swap elements pairwise.

Ex-  If linked list is 1->2->3->4->5
       Result will be 2->1->4->3->5

[Amazon] Long subtraction

Given two arrays A and B containing elements of digit, return array A-B. Your machine can only do calculation of less than 20.
Ex: A- {1,2,5,7,5}
      B-    {3,4,8,9}
     A-B = {9,0,8,6}

Permutation of a String

Write a C program which prints all permutation of a given string.

[Microsoft Interview] Binary Matrix

Given a n by m matrix of bits find the largest X that is formed in the matrix and return the size of the diagonal of that X. An X is defined as 2 equally sized diagonals that share a single 1. 

For instance, the matrix: 

00100001 
00010010 
00001100 
00001100 
00010010 
00100001 

Will return a size of 1, because the given X is invalid as the middle part does not share a single 1. On the other hand, the following matrix 

101 
010 
101 

Will return a value of 3, as the diagonal is 3. Write such program,

Maximum size square sub-matrix with all 1s

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example consider the below matrix:

0 1 1 0 1

1 1 0 1 0

0 1 1 1 0

1 1 1 1 0

1 1 1 1 1

0 0 0 0 0

The maximum square sub-matrix with all set bits is 

1 1 1

1 1 1

1 1 1

[Microsoft Interview] Array

Given a n by m matrix of bits find the largest X that is formed in the matrix and return the size of the diagonal of that X. An X is defined as 2 equally sized diagonals that share a single 1.

For instance, the matrix:

00100001
00010010
00001100
00001100
00010010
00100001

Will return a size of 1, because the given X is invalid as the middle part does not share a single 1. On the other hand, the following matrix

101
010
101

Will return a value of 3, as the diagonal is 3. Write such program,

[Microsoft Interview] Array

Given an n X n matrix, find all elements which are zero. When found, set all elements in that row and column as zero.

[Microsoft Interview] Array

Print the number between 30 to 3000.
Constraint:
The number should not contain digits either in increasing or decreasing order.

Followings not allowed:
##123, 234, 345, 1234 ##increasing order
## 32, 21, 321, 432, 3210 ## decreasing order

Following Allowed:
243, 27, 578, 2344, etc.

[Microsoft Interview] Array

Without copying the original, and in one loop, find the start and end index of a range in an array that will give maximum sum.

Ex- {5,6,-4,3}=0,1
      {8,9,-6,0,3,9}=0,5

[Microsoft Interview] String Manipulation

Given a string say "ABCD". Now create a new string with duplicates of each character in the original string and append the reverse of the same string (with duplicates) excluding the last character. 

First iteration: AABBCCCCBBAA 
[ABC three types of chars; Here c is the last char.Ignore duplicates after the last char c] 

Second iteration: AABBBBAA 

[here b is the last char] 

Third iteration: AAAA 
[no second char left]

[Adobe Interview] Fibonacci Number

Fibonacci Numbers: A number is said to be Fibonacci number if it follows the fibonacci property. (Ex: 112, 1123, etc). But additionally, it need not necessarily start with 1, as with the normal fibonacci series. So, in this new definition, 112(1,1,2) is a fibonacci number and so is 121224(12,12,24), and so is 252550(25,25,50). So, given any two numbers as input, print out all the Fibonacci Numbers within that range..