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 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Please give review to this post http://rawjava.blo…

Unknown - Apr 1, 2015

Please give review to this post
http://rawjava.blogspot.com/2015/04/java-program-to-find-maximum-number.html

Good question and equally good answer..Enjoyed your post :)

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Question : **Find Nth largest element in the rotated sorted array 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 Solution So, to find the Nth largest element in normal sorted array is a[N]. But in this case it is rotated k, which we don’t know. [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

for(int j=arrIndex/2 ; j < arrIndex;j++) …

shanky - Nov 0, 2014

for(int j=arrIndex/2 ; j < arrIndex;j++)
{
if(array[j]==1)
return j;//this is our index
}

This makes the approach O(n)
Do a regular binary search after finding the cap , with range i/2 to i

Hi Shanky, you are right. That’s what I have done :)

search  ArraySearch  kodeknight  binary array  Amazon  Interview Question  array  binary search  integer-array  integer-sort  zero 

Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Approach 1(bad): Iterating over the array until we find 1, as the array is sort. In worst case it will go till the last element, and hence this is bad approach. Approach 2 : Club binary search approach and array’s random access property Since the array is infinitely increasing i.e. we don’t know array size in advance, so we can’t directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach). [Read More]
search  ArraySearch  kodeknight  binary array  Amazon  Interview Question  array  binary search  integer-array  integer-sort  zero 

Searching the element in sorted infinite array of integers

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Question : Given an infinite array of integers which is sorted. How would you search for an integer in this array? Here is the algo (in java): public static int searchInf(int A,int high,int x){ // Assume we are searching for x if (A11 > x){ return -1; } if(Ahighhigh == x){ return high; } else{ int low = high; int higher = (int) Math.pow(2,high); if (Ahighhigh>x){ binarySearch(A,low,higher); } else{ searchInf(A,higher,x); } }// end else return -1; }// end searchInf method So if we find some element greater than element x, perform normal binary search, else call the search inf function. [Read More]
search  ArraySearch  kodeknight  sorting  binary search 

Find the minimum element in the rotated sorted sorted array

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

def findMin(arr): print(“Finding min in a…

Anonymous - Sep 4, 2014

def findMin(arr):
print(“Finding min in a rotated sorted array of integers”)

low = 0
high = len(arr) - 1
while low < high:
mid = int((low + high)/2)
left = mid - 1
right = high

if arr[mid] > arr[left] and arr[mid] > arr[right]:
low = mid
elif arr[mid] > arr[left] and arr[mid] < arr[right]:
high = mid
else:
return arr[mid]

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

Find the minimum element in the rotated sorted sorted array

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

Question : Find the minimum element in the rotated sorted array. 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 - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B, [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

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