Peter's CodeCrushing

Problem Given two strings, write a method to decide if one is a permutation of the other. Example)  Given two strings, "mom", "grandmom", your algorithm should return True because "mom" is the permutation of "grandmom".

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

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 Write a method to compute all permutations of a string For example: given an input string, "abc", your program should print the following permutations: a ab abc ac acb b ba bac bc bca c ca cab cb cba

Problem Write a method to return all subsets of a set. For example, given set of characters, A = { a, b, c, d} The output should be as blow: ['a', 'ab', 'abc', 'abcd', 'abd', 'ac', 'acd', 'ad', 'b', 'bc', 'bcd', 'bd', 'c', 'cd', 'd']

Problem A magic index in an array A [0. . .n-1] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A. FOLLOW UP What if the values are not distinct?

Problem A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the a child can run up the stairs.

Problem Write the program that takes the series of intervals and returns a total length covered by the added intervals.  If several intervals intersect, the intersection should be counted only once.  Example:  addInterval(3, 6)  addInterval(8, 9)  addInterval(1, 5)  getTotalCoveredLength() =>; 6  I.e. [1,5) and [3,6) intersect and give a total covered interval [1,6).       [1,6) and [8,9) don't intersect, so the total covered length is a sum of both intervals, that is 5+1=6.                     ______                                        _           _________          0  1  2  3  4  5  6  7  8  9  10      Now, implement the following two methods.       public :      void  addInterval( int  from,  int  to)     {         // implement the methods     }     int getTotalCoveredLength()     {     }

Problem   An efficient way to sort patient files in an array of just 3 types, "high-importance', 'med-importance', 'low-importance', which are in an arbitrary order(unsorted)   The output preference should start with the highest.   example: [high, low, low, med, high, low]

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 Write the program to shuffle the deck of cards in statistically random order.

Problem Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule  Sample inputs  Input: 1,0,0,0,0,0,1,0,0  3 => true  4 => false  Input: 1,0,0,1,0,0,1,0,0  1 => true  2 => false  input: 0  1 => true  2 => false  public boolean canPlaceFlowers(List flowerbed, int numberToPlace) {  // Implementation here  }

Problem If I type some numbers in my cell, all phone numbers which have these typed numbers in any order should appear, tell data structure for this.  Example: if I type 926 then  932678....  92678...  9777726....  should appear.  Let me clear it through another example  eg: i enter 321, then  o/p(if they are in book)  9344241..  972153....

Problem Input was given as  List dict = new List (); that contains a list of 10000 words. Find all the words that match the given pattern without regular expressions. Ex : You are given a pattern like (h*t). The words matching it would be (hot, hit, hat, etc.)

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 In $N \times N$  chess board, you have to arrange N queens such that they do not interfere each other. Following is how you define interference of queens.  1. Two queens cannot be on the same diagonal  2. Two queens cannot be in same horizontal or vertical line  3. Queen can jump like a knight. So, two queens cannot be at a position where they can jump two and half steps like a knight and reach the other queen.  You should return the possible ways to arrange N queens on a chess board. 

Problem  Push all the zero's of a given array to the end of the array. In place only. Ex 1 , 2 , 0 , 4 , 0 , 0 , 8 becomes 1 , 2 , 4 , 8 , 0 , 0 , 0. No additional allocation of array is not allowed. Everything should happen in place.

Problem Assume you have very  K large arrays of integers stored in the Disk. It is so large that I would not fit into your computer memory. You need to write the application that merge all K large arrays into sorted one list and store it in the disk. Example, say the memory size, K = 6. Your program should be able to merge the following three arrays. Note that each file has sorted list of integers.   File 1  = { 3 , 7 , 9 , 15 , 35 };   File 2  = { 2 , 8 , 45 , 60 , 70 , 100 };   File 3  = { 5 , 6 , 50 , 101 , 110 }; You need to write a program that merges the arrays into one array with all the numbers sorted in ascending order.

Problem [reviewed on 2022/03/27] You are given the two array of strings: dountType: the first one is donut name and the second one is donut type [ [ "crullar", "vegan"], [ "beignet", "coffee"] ] order: the first one is the name of the people and the second one is donut type. [ [ "jose" , "vegan"], [ "john", "coffee"] ] You need to write the program listing the following output. [   ["john", "beignet"], ["jose", "cruller"] ] Each person can like either one donut for all donuts. If a person like all donuts, the input will be like below: ["Adam", "*"] In that case, the output should be [ "Adam", "beignet"], ["Adam", "crulller"] Note the output is sorted primarily by the name and secondarily by the donut name. You need to implement the following method: # c++ vector < vector < s

Problem   Given three arrays of integers, each of which is sorted, write the program that merges three arrays into one keeping the integers sorted.  Example inputs:   arr1  = { 3 , 7 , 9 , 15 , 35 };   arr2  = { 2 , 8 , 45 , 60 , 70 , 100 };   arr3  = { 5 , 6 , 50 , 101 ,  110 };

Problem Given the list of strings consisting of the asthmatic equation expressed in the Reverse Polish notation. Write the program that evaluates the equation and returns the result. Example:     For { "4" , "1" , "+" , "2.5" , "*" }, output =12.5     { "5" ,  "80" , "40" , "/" , "+" } = 7

Problem Write a function to print the rows of a binary tree, terminating each row with a carriage return.

Problem   Rearrange characters in a string so that no character repeats twice.   Input:  abcccddaaabc   output:  cacacbadcdab

Problem Find the maximum number of non-intersecting events in a Calender For example. given list of events each of which contains start date and end date as below: { [1,6], [1, 3], [1, 4], [5, 6] , [6,10], [9,10], [17,18] }. In this case, choosing the following events produce the maximum non-intersecting events. { [1, 3], [5, 6], [9,10], [17, 18] } Therefore, 4 should be returned.

Problem  There's a new language which uses the latin alphabet. However, you don't know the order among letters.   You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in the language. For example, given list of words, { "abcdefo", "begz", "hijk", "abcedefgh", "ikom"} One valid sequence would be {abcdefom}.

Problem Given a number array, including positive and negative numbers, the question is to find a sequential sub array which has the biggest sum and the time complexity is $O(n)$, For example, [1,-2,3,10,-4,7,2,-5] is an array, and the sub array [3, 10, -4, 7, 2] has the biggest sum which is 18.

Problem Given an array of integer A = {23, 5, 4, 7,2, 11}, and the length N, and target sum, S, write the algorithm that tells whether the sub array $A_{sub}$, where $\sum_{i=k}^p A_{sub} (i) = S$. For example, If N = 3, and S = 13, it should return sub array, {4,7, 2}.

Problem Given the array of integer, A = {1, 6, 8, 2. 7}, and target sum, 9, you need to write the problem to tell where there are two integers whose sum equals 9. 2022-03-22: Additional constraints How will you change your algorithm if the input has duplicate values and you can't use the same values twice? You should return all matching number pairs. A = {1,3,3,5,7,8,4,4}, target sum 8 [ [3,5], [4,4]]

Problem Given set of the prime numbers, P , find the nth biggest number that can be  expressed with the numbers in P.  e.g. prime set = {2, 3} ,  expressible numbers = { 1, 2, 3, 4, 6 .. } , Given N = 3, the 3rd largest expressible number is 3.

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

Problem Given the circular array of sorted values, search the specified value. For example, A = { 4,5,6, 1,2,3}, target = 1; output  = true Your algorithm should be better than O(N).

Problem Find h-index given array of numbers. For more information about h-index, check out the following link. https://en.wikipedia.org/wiki/H-index The idea is that you need to find the last value in the array where the value is larger than its index. For example,  Say Scientist A has 5 publications with the following citation count.   Publications = {10, 8, 5, 4, 3}. In this case, the h-index is 4 since 4 whose index is 3 is the last value which value is larger than its index.

Question: You are given the 2x2 array showing who is following and who is followed. Example) If array[0][1] = true, this means Person 0 follows person 1. Celebrity is one that everyone follows him/her but he/she does not follow anyone. Your algorithm should print out who is celebrity, given the 2X2 Array with followee-follower relationship.

Question: Given a binary tree with nodes containing integer values. Your algorithm should calculate the sum of values in each depth and returns sums. Example:           1          /   \        2     3       /  \   /  \     4   5 1    2 Output:  1, 5, 12

 Question  Given a list of strings, return a list of lists of strings that groups all anagrams.   Ex. given {trees, bike, cars, steer, arcs}   return {{cars, arcs}, {bike}, {tree, steer}}   m = # of words   n = length of longest word

Problem The palindrome problem is another classic algorithm question. Given the sentence, write the code checking if the sentence is a palindrome. Any non-alphabet characters should be ignored. Examples: A car, a man, a maraca. A dog, a plan, a canal: pagoda. A dog! A panic in a pagoda! A lad named E. Mandala A man, a plan, a canal: Panama.

Problem Given the list of numbers, find the local min or local max Local max or min is the number that exists between the first and last number. For example, 1 , 2 , 3 , 4 , 3 , 2  => local max exists, which is 4 1 , 2 , 3 , 4 , 5 , 6 , 7  => No local max or local min exists   5 , 4 , 3 , 2 , 1  => No local max or local min exists   9 , 8 , 7 , 6 , 5 , 6 , 7 , 8 , 9 => local min exists, which is 5. Challenging part is that your problem should run faster than O(N).

Problem Given N digits, find two numbers whose sum is equal to the given number T.