Peter's CodeCrushing

Question You are given a stream of records about a particular stock. Each record contains a timestamp and  the corresponding price of the stock at that timestamp. Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect.  Another record with the same timestamp may appear later in the stream   correcting the price of the previous wrong record. Design an algorithm that: Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp. Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded. Finds the maximum price the stock has been based on the current records. Finds the minimum price the stock has been based on the current records. Implement the StockPrice class: StockPrice() Initializes the object with no price records. void update(int timestamp, int price) U...

Question For input (separated by a tab) from this link , compute the shortest path from a vertex, 0 to the following vertices. The file contains an adjacency list representation of an undirected weighted graph with 200 vertices labeled 1 to 200.  Each row consists of the node tuples that are adjacent to that particular vertex along with the length of that edge. For example, the 6th row has 6 as the first entry indicating that this row corresponds to the vertex labeled 6. The next entry of this row "141,8200" indicates that there is an edge between vertex 6 and vertex 141 that has a length of 8200.  The rest of the pairs of this row indicate the other vertices adjacent to vertex 6 and the lengths of the corresponding edges. Report the shortest path in the same order of given vertices vertices = [7,37,59,82,99,115,133,165,188,197] if you find that all ten of these vertices except 115 are at a distance of 1000 away from vertex 1 and 115 is 2000 distances away, then your answer s...

Problem Pattern Matching  ----------------  Characters: a to z  Operators: * +  * -> matches zero or more (of the character that occurs previous to this operator)  + -> matches one or more (of the character that occurs previous to this operator)  Output if a given pattern matches a string.  Example:  pattern:a*b  string:aaab b, ab, aab, aaab, ab  output:1  pattern:a+aabc  string:ab aabc, aaabc, aaaabc ..  output:0  pattern:aa*b*ab+  string:aab aab, aabab, aaaabbab  output:1  pattern: a+a*b*  string: a ab, aab, aaabb  output: 1  Valid Assumptions: Please assume that both the pattern and string input are valid

Problem A robot has to move in a grid which is in the form of a matrix. It can go to  1.) A(i,j) --> A(i+j,j) (Down)  2.) A(i,j)-->A(i,i+j) (Right)  Given it starts at (1,1) and it has to go to A(m,n), find the minimum number of STEPS it has to take to get to (m,n) and write  public static int minSteps(int m,int n)  For instance to go from (1,1) to m=3 and n=2 it has to take (1, 1) ->(1, 2) ->(3, 2) i.e. 2 steps

You have a room-full of balances and weights. Each balance weighs ten pounds and is considered perfectly balanced when the sum of weights on its left and right sides are exactly the same. You have placed some weights on some of the balances, and you have placed some of the balances on other balances. Given a description of how the balances are arranged and how much additional weight is on each balance, determine how to add weight to the balances so that they are all perfectly balanced. There may be more than one way to balance everything, but always choose the way that places additional weight on the lowest balances. The input file will begin with a single integer, N, specifying how many balances there are. Balance 0 is specified by lines 1 and 2, balance 1 is specified by lines 3 and 4, etc... Each pair of lines is formatted as follows: WL WR WL and WR indicate the weight added to the left and right sides, respectively. is a space-delimited list of t...

Problem Implement read using read4 class ArbitraryIO { private :     // returns bytes read or 0, sizeof(buf) >= 4     // reads up to 4 bytes at a time into caller allocated buf     int read4( char * buf); public :   // IMPLEMENT:toRead > 4 or < 4 or = 4, buf allocated by caller, return number of bytes read   int read( char * buf, size_t toRead) {   } }; Your method should pass the following test cases: ------ test case  --- // assume reader is reading over ->  a b c d e f g h i j ArbitraryIO r; char buf[ 1024 ]; int x; x = r.read(buf, 2 ); EXPECT(x == 2 ); EXPECT(buf[ 0 ] == 'a' ); EXPECT(buf[ 1 ] == 'b' ); x = r.read(buf, 5 ); EXPECT(x == 5 ); EXPECT(buf[ 0 ] == 'c' ); EXPECT(buf[ 1 ] == 'd' ); EXPECT(buf[ 2 ] == 'e' ); EXPECT(buf[ 3 ] == 'f' ); EXPECT(buf[ 4 ] == 'g' ); x = r.read(buf, 1024 ); EXPECT(x == 3...

Problem Write function to determine if given unsigned 32-bit number is a power of 3     int is_power_of_3(uint32_t n)

Problem [Revised] Design the BigString class which has the following public methods // method to add char to the word at the specified index. void insert (char c, int pos) {   // } //method to return the word at the specified index. word * search(int index) { // } Example) insert('a', 0); ==> [a] insert('b', 0); ==> [ba] insert(' ', 0); ==> [ ba] insert('c', 0); ==> [c ba] insert('e', 11) ==> [c ba       e] insert('f', 8); ==> [c ba    f   e] insert('o', 3)  ==> [c boa    f   e] insert('u', 10) ==> [c boa    fu   e] search(0) ==>  c search(1) ==>  boa search(2) ==>  fu search(3) ==>  e

Problem Find the shortest string [] containing the keyword inside Example, Words: sky cloud google search sky work blue Keywords: sky blue Return: sky work blue

Problem Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to  x). Implement the data structures and algorithms to support these operations.  The following methods need to be implemented. // method to take new number x void track(int x);  // method to return the number of values that are less than or equal to x (not including x itself) int get_rank(int x);  Example: Stream (in order of appearance): 5, 1, 4, 4,  5,  9, 7, 13, 3 get_rank(1) = 0 get_rank(3) = 1 get_rank(4) = 3

Problem Given the input string str1 and the seed string str 2, write the program to find the minimum sub-string of str1 that is inclusive of str 2. Example)  Case 1) str1 = "abbcbcba" and str2 = "abc", answer = "cba" Case 2) str1 = "caaababc" and str2 = "abc", answer = "abc"

Problem Given arithmetic equation, 2+(3-1)*4/(5-6), write the program to calculate the result of the equation.

Problem Given a boolean expression consisting of the symbols 0,1, &, |, and ^, and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result. Example) Expression: 1^0|0|1 Desired result: false (0) Output: 2 ways. 1^( (0|0)|1) and 1^(0|(0|1)).

Problem Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses. EXAMPLE Input: 3 Output: ( ( ( ) ) ) , (()()), (())(), ()(()), ()()()

Problem Given the array of integers, A, the target sum, S, and the limit on number of integers to use, K, write the program to return the K integers, whose sum equals, S. Example: A = { 1,2 ,4, 5, 9}, with K = 2, S = 6,  output  = {4, 5}

Problem You have a list of words with ranking. Now you need to create a function that will take this list as input and provide a way so that a T9 keyboard can provide three top results of probable words based on rankings for the numbers punched in. To help the understanding here is the picture of T9 keyboard. Figure 1: example T9 keyboard For example, given the list words with ranking: [ ( "test", 13 ) , ("tax", 7), ("tom", 50), ("text", 100), ("top", 79),("tub", 101), ("tap", 3))] Following input from the T9 keyboard, should return the following output. key = 8: [ (tap, 3)(tax, 7)(test, 13)] key = 82: [ (tap, 3)(tax, 7)] key = 83: [ (test, 13)(text, 100)] key = 86: [ (tom, 50)(top, 79)] key = 2: [ ]

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

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)