[Fab.com] Two elements whose sum is closest to zero

An array of integer is given , both +ve and -ve. Find two elements whose sum is closest to zero.

[Microsoft]100 bulbs puzzles

Microsoft] Print last 10 lines

Given some text lines in a string, each line is separated by '\n' characters. print the last 10 lines. If no of lines is less than 10 , then print all the lines.

Deepest left leaf mode in a binary tree

Given a binary tree, find the deepest leaf node which is left child of its parent.

[Fab.com] Find the celebrity

Given a function know(A,B) which returns true if A knows B , otherwise false. Now there is one celebrity who is known to everyone and who does not know anyone. Given an array , find the celebrity in less than linear time.

[Amazon] Find an element in array whose element differ by 1

Given an array in which two elements differ by +1 or -1. Find an element k in such an array in less than linear time.

[Fab.com] Design a car parking lot.

Design a car parking lot. Tell about all the classes and functions. It should be able to say full, empty, normal.
The lot has 3 different kind of parking : regular, handicapped and compact.

[Fab.com] Power of 2

Write a function to check if it is a power of 2.

[Fab.com] Ugly number

Write a function to find n ugly numbers.

[Fab.com] Occurence of first 1 in the sorted array of 0s and 1s

Find the ocuurence of first 1 in the array which contains 0s and 1s in the sorted manner.

[Fab Interview] Segregate 0s and 1s

Given an array of 0s and 1s in random order. Segregate 0s on the left side and 1s on the right side.
Traverse the array only once.

Input Array: {0,1,0,1,1,1}
Output Array: {0,0,1,1,1,1}

[Amazon] Subarray with sum 0

Given an array of integers with positive and negative numbers. Find if there exist a subarray with sum 0. If any, print the starting index, otherwise print 0.

Example:  Input Array: {1,2, 3, -1, 4, -3, 2}
               Subarray is: {-1, 4, -3} which gives sum as 0.

[Amazon Interview]: Append and delete node in unordered DLL

Append and delete a node in an unordered DLL.

[Amazon]: Decode a run length encoded String

Decode a run length encoded string. Don't use extra space. Time Complexity- O(n)
Input String: A3B4C
Output: AAABBBBC

[Microsoft]: Insertion in Sorted Circular linked list

Write a C function to insert an element in a sorted circular linked list.

[Adobe]: Lowest Common Ancestor

Write a program to find lowest common ancestor in a Binary search tree.

[Goldman Sachs]: Check if a tree is BST or not

Write a program with time complexity O(n) and space complexity O(1) to check if a tree is BST or not.

[Microsoft]: Maximum sum subarray

Find the maximum sum sub-array of an array. 

[Amazon Interview] Pairs with smallest absolute difference

Given a list of numbers, find the numbers which have smallest absolute difference between them. If there are more than one pair, print them all.

[247 ILabs]: Convert a sorted Array to balanced BST

[247 ILabs]: Print a given matrix in spiral order

[Airpush]: How are pipes used in Linux system

[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..