Peter's CodeCrushing

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 an M $\times$ N matrix in which each row and each column are sorted in ascending order, write a method to find an element.

Problem Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string. Example input: find "ball" in  {"at", "", "", "","ball", "", "", "car", "", "". "dad", "",""} Output: 4

Problem Imagine you have a 20 GB file with one string per line. Explain how you would sort strings in the file.

Problem You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write the algorithm to merge A and B without allocation additional memory.

Problem   Imagine you are building some sort of service that will be called by up to 1000 client applications to get simple end of day stock price information (open, close, high, low). You may assume that you already have the data, and you can store it in any format you wish. How would you design the client-facing service which provides the information to the client applications?   You are responsible for the development, rollout, and ongoing monitoring and maintenance of the feed. Describe the different methods you considered and why you would recommend your approach. Your service and use any technologies you wish, and can distribute the information to the client applications in any mechanism you choose.

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