Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0

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

Problem Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0 Example **Input : ** 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Output : 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Solution Method 1 - Using the extra space and O(n^2) solution [Read More]
kodeknight  Microsoft  2DArray  java-code  binary array  boolean  matrix  CrackingTheCodingInterview  zero 

Sorting Array of Three Kinds or The Dutch National Flag Problem OR three color sort

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

Question: given an array of three different kinds of value such as array(1, 2, 0, 2, 1) and array(a, b, a, c, b), write an algorithm to sort the array. For example, input array(1, 2, 0, 2, 1) becomes array(0, 1, 1, 2, 2) and input array(a, b, a, c, b) becomes array(a, a, b, b, c). This problem is also called three color sort. Solution: the Dutch National Flag Algorithm sorts an array of red, blue, and white objects by separating them from each other based on their colors. [Read More]
kodeknight  quicksort  binary array  sorting  incomplete  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)  |  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 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

in your Pseudocode, the if condition should be if …

RM - May 3, 2014

in your Pseudocode, the if condition should be if (low < high).

Thanks Rish. I have made the change a[low] > a[high] rather than low < low. :). Thanks for correcting me.

kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Sort a binary array - array containing 0s and 1s in 1 pass. This is also called two color sort. Example Input - Binary unsorted array A = {0,1,1,0,0,1}; Output - binary sorted array B = {0,0,0,1,1,1} Solution This is similar to quicksort partition algorithm. Though normal sorting takes O(n log n) time, but we have to just partition 0 from 1, and hence it should only take time of partitioning - O(n). [Read More]
kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero