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 

First non repeating element in the array

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

Question: Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’. Answer: Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic. [Read More]
kodeknight  String  duplicate  array  hashes  unique 

Find anagrams in the array of Strings

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

Question: You are given an array of strings and you are asked to display all the anagrams within the array. For those who don’t know, two words are anagrams if they contain the same characters. We have already discussed how to check if 2 strings are anagrams here. Answer: The brute force solution would be to take each string and compare it to every other string in the array one character at a time ( O(n^4) solution, assuming there are n strings with maximum n characters each). [Read More]
kodeknight  String  anagrams  array 

Implement 3 stacks in 1 array

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

Problem - Implement 3 stacks in 1 array Solutions Method 1 - Create 3 stacks with fixed max size Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: “[” means inclusive, while “(” means exclusive of the end point). for stack 1, we will use [0, n/3) for stack 2, we will use [n/3, 2n/3) for stack 3, we will use [2n/3, n) Here is the code : [Read More]
kodeknight  array  CrackingTheCodingInterview  stack 

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 

Next Greater Element in an array

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

Problem Given an array, print the next greater element for every element. Elements for which no greater element exist, print next greater element as -1. Example For the elements of the array [4, 5, 2, 25, 20, 11, 13, 21, 3] greater elements are as follows. 4 –> 5 5 –> 25 2 –> 25 25 –> -1 20 –> 21 11 –> 13 13 –> 21 21 –> -1 [Read More]
kodeknight  greater  array  next-big-number