Amazon Interview Question
SDE-3sCountry: United States
Actual problem can be solved, for all inputs this way , worthy of SDE 3 tag. Kudos Amazon.
/*
select domain of inversions,
and imagine starting with (0,0) which is sorted ascending.
*/
def find_if_whatever( array ){
N = size(array)
if ( N < 2 ) return true // boundary condition
// now, anything else.
domains = list()
domain = { 's' : 0, 'e' : 0 , 'st' : true }
for ( i : [ 1 : N ] ){
sorted = ( array[domain.e] <= array[i] )
if ( sorted == domain.st ){
// add to domain
domain.e = i
} else {
// end domain, create domain
domains += domain
domain = { 's' : i, 'e' : i , 'st' : sorted }
}
}
// now am done ...
domains += domain
println( jstr( domains ) ) // debug???
// now, well, well...
D = size( domains)
if ( D > 3 ) return false // no go... right?
// this is a clear go
if ( D == 1 ) return true
// now, when D=2, we have.. problems.. so
if ( D == 2 ){
if ( domains[0].st && !domains[1].st ) return array[domains[0].e] <= array[domains[1].s]
if ( !domains[0].st && domains[1].st ) return array[domains[0].s] <= array[domains[1].s]
return false
}
// now when D==3, so... larger problems...
if ( domains[0].st && domains[2].st ) {
return array[domains[0].e] <= array[domains[1].e] &&
array[domains[1].s] <= array[domains[2].s]
}
return false // done
}
println( find_if_whatever([ 1, 10,-1 ]) )
println( find_if_whatever([ 1, 2,3,4,8,7,6,9 ]) )
println( find_if_whatever([ 1,2,3,50,40,90,10,23,99 ]) )
- ribhu April 09, 2019