Peter's CodeCrushing

Problem You are given two arrays of length M and N having elements in the range 0-9. Your task is to create the maximum number of length K from elements of these two arrays such that the relative order of elements is the same in the final number as in the array, they are taken from i.e. If two elements a, and b are taken from array1 and a comes before b in array1 so in the final number a should come before b (Relative order kept same).  Example: N=4 and M =6  Array1 = { 3 , 4, 6,5} Array2 ={9,1,2,5,8,3} Suppose K = 5, then the number will be {9,8,6,5,3} You can see {9,8,3} are taken from Array2 in the same order as they are in Array2. Similarly {6,5} are taken from Array1 in the same order and number 98653 is the maximum possible number.

Problem Given an array of elements, return an array of values pertaining to how many   elements are greater than that element remaining in the array.   e.g [3,4,5,9,2,1,3]      return [3,2,1,0,1,1,0]   Running time should be faster than O(N^2)

Problem Array of size (n - m) with numbers from 1..n with m of them missing. Find all of the missing numbers in O(log n). Array is sorted.   example:   n = 8   m = 2   arr = = {1,2,4,5,6,8}   output = {3,7}   n = 8   m = 2   arr = = {2,3,4,5,6,7}   output = {1, 8}

Problem Given the arithmetic expression, $2+3+3-4*2+12/3$, your algorithm should return the result of the calculation.

Problem You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of values that satisfy A+B = C + D, where A,B,C and D are integers values in the array.  Eg: Given [3,4,7,1,2,9,8] array 3+7 = 1+ 9  satisfies A+B=C+D so print (0,2,3,5)

Problem Implement the pattern function producing the following pattern:   0: 1   1: 11   2: 21   3: 1211   4: 111221   5: 312211  Your function should generate the  string sequences shown above, given the input as a integer.   For example, input = 4, output should be 111221

Problem Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is $O(Log N)$ For example, given array, {8,8,8,9,9,11,15,16,16,16}, the occurrence of 8 should be 3.

Problem You are given the pointer to the binary tree and the value. You algorithm should find the pointer to the node that has the closest value to the given value. For example, in the given tree in Figure 1. If a 13 is given, your algorithm should return 12.

Problem   Given an array of ages(integers) sorted lowest to highest, output the number of occurrence for each age.   For instance:   [8,8,8,9,9,11,15,16,16,16]   8: 3   9: 2   11: 1   15: 1   16: 3   Running time should be $\le O(N)$

Problem Your are given the pointer to the root of the tree, with nodes having the following structure. struct node {     node * parent;     node * left;     node * right;     int value; }; You algorithm should find out whether the given tree is BST (Binary search tree or not)

Problem You are given the list of time duration as below:  ( 3 , 4 ),   (10 , 13 ),  ( 5 , 6 ),  ( 5 , 7 )),  ( 7 , 9 ) Your algorithm should be able to tell whether there is overlap among these time durations. 

Problem Your are given the pointer to the root of the tree, with nodes having the following structure. struct node {     node * left;     node * right;     int value; }; You algorithm should find out whether the given tree is BST (Binary search tree or not)

Problem You are given the array of integers, each of which represents the stock price of each day. You need to find the maximum drop in the stock price and buying and selling date, such that input[x] > input[y], where  x > y  For example, given stock prices {2,4,-1,5, 7,6, 1}, the maximum drop should be 8, and [2, 4] will be an answer because the drop from -1 to 7 is 8, and the biggest increase. If the stock is bout when its price is at -1 and sells it when its price is at 7 the gain will be 8.

Problem Given a list of child->parent relationships, build a binary tree out of it. All the element Ids inside the tree are unique.  Example:  Given the following relationships:  Child Parent IsLeft  15 20 true  19 80 true  17 20 false  16 80 false  80 50 false  50 null false  20 50 true  You should return the following tree:         50         /    \     20      80     /  \     /   \  15 17 19 16

Problem Rahul is playing a very interesting game. He has some N different types of matchboxes. All matchboxes may have a different number of matchsticks (S1, S2, S3... Sn). Rahul chooses two random numbers F and K. K should be less than N. The game is that Rahul wants to select any K matchboxes out of N matchboxes such that the total number of matchsticks in these K-selected matchboxes should be multiple of F.  You can only take one patch from each box. No duplicate number is allowed At the same time, Rahul wants the sum of matchsticks of all the selected match boxes should be the minimum possible.  Input Specifications:  1) Array S = {S1,S2,S3,...Sn} of size N corresponding to the number of match sticks in N matchboxes (0<=N<=1000}  2) F-Value (as explained above)  3) K-Value ( as explained above)  Output:  1 2 3 4 5 Here 3 is the number of matchsticks in matchboxes I II III IV V minimum possible total number of matchsticks such t

Problem Given the binary tree as shown below: Figure 1. Binary Tree Convert the tree into a double-linked list, where the left pointer and right pointer become the prev and next pointer respectively. Your algorithm should produce the double-linked list as below:

Problem Given the root pointer of the binary tree and the pointer to the target node, find the predecessor of the target node. For example, in Figure 1 . the predecessor of  5 is 4.

Problem Find all triangle combination from a given array of integers. For example, given array of integers, {8,7,3,2,5,6,1,4}, your algorithm should produce list of combinations that makes triangle.

Problem You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase ? For example, If there are 3 stairs, there are three possible ways to climb them. {1,1,1}, {1, 2}, {2, 1} Your algorithm should print out the total number of ways to climb the stairs. (Optional: should also print out the different ways as above)

Problem You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase ? For example, If there are 3 stairs, there are three possible ways to climb them. {1,1,1}, {1, 2}, {2, 1} Your algorithm should print out the total number of ways to climb the stairs. (Optional: should also print out the different ways as above)

Problem You are given a Binary Tree (not BST) along with two pointers to nodes somewhere in the tree. Your algorithm should returns the pointer to the common parent to given nodes. For example, in the following tree Figure 1. Binary Search Tree example The common ancestor of "d" and "f" is "a".

Problem You are given a BST (Binary Search Tree) along with two pointers to nodes somewhere in the tree. Your algorithm should returns the pointer to the common parent to given nodes. For example, in the following tree Figure 1. Binary Search Tree example The common ancestor of "d" and "f" is "a".  In this question, the pointer to the parent is given as part of the feature of the BST.

Problem Given a list of integers, find the highest value obtainable by concatenating these together. For example, given numbers, {1000, 898, 77, 55,8989}, 898989877551000 will be the biggest number that can be produced.  Roughly, we can sort the integers in descending order and concatenate them. This will run in O( N log N), where N is the number of integers in the input list.

Problem   Given two strings, return boolean True/False, if they are only one edit apart.   Edit can be insert/delete/update of only one character in the string.      Eg.:      True:   xyz, xz   xyz, xyk   xy, xyz   False:   xyz, xyz   xyz, xzy   x, xyz  In comparing two strings there are two cases to be considered.

Problem Having a home defined linked list with the following structure, where the next will point to the node in the list and the random will point to a random node in the list. Create a copy of the structure(the data field in each node is not unique for different nodes. As shown Figure 1 and Figure 2, adding an duplicate node between existing nodes in the list can be done in O(N) time. Figure 1. Original linked list Figure 2. After adding duplicate nodes.

You are the event coordinator and want to find out how many event rooms you will need to accommodate the event schedules. Given the event schedule as follows: {8-9}, {9-10}, {8-10}, {11,14}, {14,15},{13,16}, {10, 13},{10,12}, {13,15} Event time can not overlap unless one event ends in the same hour as the other event start. e.g. event 1 {2,3} and even 2 {3-4} can be held in the same event room. Your program should calculate how many rooms are necessary.

Problem Let's say there is a double square number X, which can be expressed as the sum of two perfect squares, for example, 10 is double square because 10 = 3^2 + 1^2        Determine the number of ways which it can be written as the sum of two squares