Circus tower sorting problem

 Posted on March 29, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower. EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) [Read More]
kodeknight  Dynamic Programming  DP  CrackingTheCodingInterview  sorting-and-searching 

Searching in a sorted array of strings with empty strings

 Posted on March 29, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string. Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “"] will return 4 Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “"] will return -1 Solution The worst we can do is O(n) where we just do a linear search. [Read More]
kodeknight  binary search  CrackingTheCodingInterview  sorting-and-searching 

Sorting a 2GB file with one string per line

 Posted on March 28, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem If you have a 2GB file with one string per line, which sorting algorithm would you use to sort the file and why? Solution When an interviewer gives a size limit of 2GB, it should tell you something – in this case, it suggests that they don’t want you to bring all the data into memory. So what do we do? We only bring part of the data into memory. [Read More]
kodeknight  sorting  CrackingTheCodingInterview  sorting-and-searching  limited memory 

Sort an array of strings so that anagrams are next to each other

 Posted on March 28, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Write a method to sort an array of strings so that all the anagrams are next to each other. Example INPUT : "xyz", "ca", "ab", "ac", "ba", "zyx" OUTPUT: "ab", "ba", "ac", "ca", "xyz", "zyx" Lets see the solutions now. Solution Method 1 - Using bubble sort Check if two pairs of strings are anagrams or not, if yes, swap. Java code private static boolean areAnagrams(String s1, String s2) { if (s1. [Read More]
kodeknight  sorting  anagrams  compare  CrackingTheCodingInterview  sorting-and-searching 

Merge two sorted arrays - One having big enough buffer to hold another

 Posted on March 28, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. Another way to ask same question Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. [Read More]
kodeknight  merge  sorting  two-arrays  two-sorted-arrays  CrackingTheCodingInterview  sorted-array  sorting-and-searching 

Search an element in the sorted rotated array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Answer: We can do a binary search with some modified checks. So lets take arr as array, start be start of the array, end be arr. [Read More]
ArraySearch  kodeknight  Amazon  recursion  array  binary search  rotated array  CrackingTheCodingInterview  sorted-array  sorting-and-searching  java 

Find an element in matrix in which rows and columns are sorted

 Posted on December 18, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Problem Given a matrix in which each row and each column is sorted, write a method to find an element in it. Example 1 4 7 13 2 5 9 15 3 6 10 16 Solution Here we can have 2 cases - Case when array is sorted such that last element of nth row is less than first element of n+1 th row Generic case - simply put rows and columns CASE 1 - If last element of each row is less than first element of next row [Read More]
kodeknight  2DArray  2DSortedArray  binary search  CrackingTheCodingInterview  sorting-and-searching