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.
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.
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)
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.
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.
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.
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.
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
linked-list in single level link-list.
struct node {
void *data; /* could be anything */
struct node *next;
struct node *down;
};
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.
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
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.
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.
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.
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
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?
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.
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.
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?
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
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:
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}
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?
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]);
}
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.
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
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:
Explanation Re-arranging "Resistance" gives "Ancestries", similarly re-arranging "Gainly" results in "Laying". As stated in the problem, anagrams are case-insensitive
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. …
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 cachevoidput(K key, T data);}where k is key and T is data part.Note: All operation should be o(1).
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.