## Posts

Showing posts from 2012

### Number is palindrome or not

Determine whether a number is palindrome or not without using extra space. Don't forget to mention whether your Algo will work for negative numbers or not.

### Sum of four elements equals X

Given an array of integers, find all combination of four elements in the array whose sum is equal to a given value X.
For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and X = 23, then your function should print “3 5 7 8″ (3 + 5 + 7 + 8 = 23).
Note: Numbers should not be overlapping. eg(3,5,7,4) will generate 3+5=8 and 5+7=12 , for sum equals 20, 5 is overlapping.

### All possible IP Address combinations

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

### Difference in program size

What is the difference in terms of program size in case of these two types of declarations
int a[100];
or,
int a[100]={10};

### Exchange gold coins

In a monetary system each coin has an integer number written on it. A coin 'n' can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down. You can also sell coins for dollars and their exchange rate is 1:1. You have one gold coin. What is the maximum amount of dollars you can get for it? eg: for a coin with value 120 you can get 144 dollars.Suggest an algorithm to solve the problem.

### [Adobe]Search for an element in unsorted array

The successive elements of an unsorted array differ by either + 1 or -1. How will u search for an integer k in this array ?
eg: 4,5,4,4,5,6,7,8,7
for each element 'n' the next element is always n+1 or n-1.

### Maximum sum 2-d subarray

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size or greater located within the whole array. As an example, the maximal sub-rectangle of the array:
is in the lower-left-hand corner: and has the sum of 15.

### [Amazon]Two unsorted array form same BST

Given two unsorted array, check if both will create the same bst. eg: 2, 1, 4, 0 and 2, 1, 0, 4 will both form same BST.
2 / \ 1 4 / 0but,2,1,4,0 and 2,0,1,4 will not.

### [AMAZON] Subtree with largest sum

Given a binary tree, every node has a int value, return the root node of subtree with the largest sum up value.

### [AMAZON] Vertical sum of nodes

Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples:
1 / \ 2 3 / \ / \ 4 5 6 7The tree has 5 vertical lines
Vertical-Line-1 has only one node 4 => vertical sum is 4
Vertical-Line-2: has only one node 2=> vertical sum is 2
Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12
Vertical-Line-4: has only one node 3 => vertical sum is 3
Vertical-Line-5: has only one node 7 => vertical sum is 7
So expected output is 4, 2, 12, 3 and 7

You are given a singly link-list such that each node of this list is also a
head of another link list of the same type. So, suggest an algorithm to flatten the

struct node {
void *data; /* could be anything */
struct node *next;
struct node *down;
};

### Implement tail utility

How will you implement tail utility in c/c++ without using inbuilt tail command.
Note: tail -n <filename> will output the last 'n' lines of the file.

### Find the Least Length Path Which Sums to S

Given a BST and a number 'N' there can be several paths from root of the bst to leaves such that sum of data of all the nodes will make number 'N'. Suggest an efficient algorithm to find out the path of least length.

### [MS]Form Largest Number from given number

Write a function to make the largest number from the digits of a given number.
Example.
number: 32441
Output: 44321

### Convert a Binary Tree To hold Children Sum Property

Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node.
For example, the below tree doesn’t hold the children sum property, convert it to a tree that holds the property.
50 / \ / \ 7 2 / \ /\ / \ / \ 3 5 1 30

### Connect nodes of a binery tree at same Level

Write a function to connect all the adjacent nodes at the same level in a binary tree. Structure of the given Binary Tree node is like following.structnode { intdata; structnode* left; structnode* right; structnode* nextRight; } Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node. You can use only constant extra space.
Consider this example for your solution:
1 / \ 2 3 / \ / \ 4 5 6 7 / \ / \ 8 9 10 11 nextRight for node with value 9 will be 10 and not NULL.

### perfect cubes

It is possible, to find integers greater than 1 that satisfy the "perfect cube" equation a^3 = b^3 + c^3 + d^3 (e.g. a quick calculation will show that the equation 12^3 = 6^3 + 8^3 + 10^3 is indeed true). This problem requires that you write a program to find all sets of numbers {a,b,c,d} which satisfy this equation for a <= N.

### Euclidean Distance

You are given a multiset of points on the plane with integer coordinates. Find the maximum distance between two points from this multiset.

### Pair of Numbers

Let's assume that we have a pair of numbers (a, b). We can get a new pair (a + b, b) or (a, a + b) from the given pair in a single step.
Let the initial pair of numbers be (1,1). Your task is to find number k, that is, the least number of steps needed to transform (1,1) into the pair where at least one number equals n.

### Convert to Sum Tree

Given a Binary Tree where each node has positive and negative values. Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0.
For example, the following tree

10 / \ -2 6 / \ / \ 8 -4 7 5should be changed to

20(4-2+12+6) / \ 4(8-4) 12(7+5) / \ / \ 0 0 0 0

### [AMAZON]All combination of balanced parenthesis

Write a function to generate all possible n pairs of balanced parentheses.
For example, if n=1
{}
for n=2
{}{}
{{}}

### Playing Card Game

A player has several cards. Each card contains two non-negative integers inscribed, one at the top of the card and one at the bottom. At the beginning of the round the player chooses one of his cards to play it. If the top of the card contains number ai, and the bottom contains number bi, then when the player is playing the card, he gets ai points and also gets the opportunity to play additional bi cards. After the playing the card is discarded.The round ends when the counter reaches zero or the player runs out of cards.
We want him to get as many points as possible. Can you determine the maximum number of points he can score provided that you know his cards?

### [AMAZON]Find two nodes which sums equal to 'K'

Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space.

### Number of distinct decoding

Two people want to send coded messages to each other. One possible encoding scheme is to simply replace each letter with its numerical value in the alphabet and then string all the digits together without spaces. Determine the number of possible ways to decode a message encoded this way.
eg: the message encoded as 25114 can be decoded as BEAAD, BEAN, YAD, YAN, ‘YKD’ and ‘BEKD’, so there are 6 different decoding of given string value.

### [Inmobi]Maximum sum of increasing sequence

Variation of LIS:
Given an integer array, how will you find out the increasing subsequence which gives the largest sum. For example,
50,23,1,67,30 in this subsequence a few possible increasing subsequences are
1)    23,30
2)    23,67
2)    50,67
3)    1,67
4)    1,30
5)    67
6)    30

but 50, 67 gives the maximum sum. How to find it
Note: In the above scenario however if we have 128 at index 0 then it will have the max sum although it is not forming longest LIS.

### [AMAZON] Stock purchase problem

Suppose we are given an array of n integers where each index represent stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.
Clearly there is an O(n2) solution to the algorithm by trying out all possible (buyDay, sellDay) pairs and taking the best out of all of them. However, is there a better algorithm, perhaps one that runs in O(n) time?

### [AMAZON]Longest palindrome substring

Given a string S, find the longest palindromic substring in S.

### [DP]Coin Counting Problem

Given 1, 2, 5, and 10 paise coins, how many ways can you make a rupee?
Hint: Order doesn't matter.

### Getminimum steps

On a positive integer, you can perform any one of the following 3 operations.
1.) Subtract 1 from it. ( n = n - 1 )  2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2)
3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ). Now given a positive integer n, find the minimum number of steps that takes n to 1

### [AMAZON]printKDistanceNodes

You are given a function printKDistanceNodeswhich takes in a root node of a binary tree, a start node and an integer K.  Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.
Example:

Sample Input:

Root node: 5
Given start node: 8
Distance (K): 1
Sample Output:
5
6
9

### [AMAZON]Arrange Array elements

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

PS: Do it without using extra memory
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}

### Sum of 15

Two players are playing a game and take alternating turns. Initially, there are 9 cards with numbers from 1 to 9 on the table. On each turn, a player takes one of the cards. The first player to have exactly 3 cards with numbers that sum to 15 wins. If no one can after all cards are distributed, then it's a draw.

Can you tell who wins and how to play this game without using a computer to analyze all possible positions?

### [c++]vector insert method

Suppose I'd like to copy an array of ints into the front of a vector. (The
data might be in an array instead of a vector in the first place, because the data came from a legacy C API. )
What is the performance wise difference in the two method:

int data[numValues];
vector<int>::iterator insertLoc(v.begin());
for (int i = 0; i < numValues; ++i) {
insertLoc = v.insert(insertLoc, data[i]);
}

### Find the two repeating elements in a given array

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.
For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5
The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

### [AMAZON]Length of the LIS

Given an integer array sequence, return the length of the longest increasing subsequence (LIS)
A longest increasing subsequence is defined as a subsequence in the given sequence of integers such that the elements in the subsequence are in sorted order, lowest to highest and in which the subsequence is as long as possible

Sample Test Cases:

Input #00:
1, 2, 3

Output:
3

Explanation:
The sequence in itself is an increasing one

Input #01:
4, 5, 6, 7, 8, 1, 2, 1, 2, 3, 5, 4, 6, 7, 8, 9, 0, 6, 7

Output #01:
8

Explanation:
The length of the LIS is 8. The LIS elements from the sequence are highlighted: 4, 5, 6, 7, 8, 1, 2,1, 2, 3, 5, 4, 6,7, 8, 9, 0, 6, 7

### [AMAZON]Print Anagrams

Given an array of strings, please complete the function printAnagrams which prints each anagram pair in every line. Any word that exactly reproduces the letters in another order is an anagram. Anagrams are case-insensitive
Sample Test Cases:

Input #00:
Resistance, Ancestries, Gainly, Laying, test, troop

Output #00:
Resistance Ancestries
Gainly Laying

Explanation
Re-arranging "Resistance" gives "Ancestries", similarly re-arranging "Gainly" results in "Laying".
As stated in the problem, anagrams are case-insensitive

### [AMAZON]File_Mapping

Write a program that reads a series of data sets representing a computer file structure. A data set ends with a line containing a single *, and the end of valid data is denoted by a line containing a single #. The data set contains a series of file and directory names. (The root directory is assumed to be the starting point.) The end of a directory is denoted by a ']' Directory names begin with a lower case 'd' and file names begin with a lower case 'f' File names may or may not have an extension (such as fmyfile.dat or fmyfile). File and directory names may not contain spaces.

Output:

Note that the contents of any directory should list any subdirectories first, followed by files, if any. All files should be in alphabetical order within each directory. Note that each data set output is marked by the label "DATA SET x:" where x denotes the number of the set, beginning at 1. Note also the blank line between the output data sets. …

### Check brace expression are valid

Implement an algorithm to check whether brace expressions are valid or not

boolean isGood(String s, String braces);  //assume braces are valid,{}[]()

### [Amazon]Implement LRU cache

Implement the LRU cache algorithm. Given following interface. CacheStrategy<K, T> {// get the data by key from the cache. T get(K key); // put <key, data> pair to the cache voidput(K key, T data); } where k is key and T is data part. Note: All operation should be o(1).

### Find index of special symbol

Given an infinite array in which the first n cells contain integers in sorted order and the rest of the cells are filled with some special symbol (say \$).Assume we do not know the 'n' value.Give an algorithm that finds the index of the symbol.
Note :size of the array is not known.