FreshoKartz Interview Question
Software Engineer InternsCountry: India
Interview Type: Phone Interview
public static int greatestSmallerTidyNumber(int n) {
char[] chars = String.valueOf(n).toCharArray();
boolean foundbig = false;
int lastEqualIndex = -1;
for (int i = 0; i < chars.length - 1; i++) {
if (foundbig) {
chars[i] = '9';
continue;
}
if (chars[i] == chars[i + 1]) {
lastEqualIndex = i;
continue;
}
if (chars[i] > chars[i + 1]) {
if (lastEqualIndex != -1 && lastEqualIndex == i - 1) {
--chars[i - 1];
}
if (chars[i] == '1') {
chars[i] = '9';
} else {
--chars[i];
}
foundbig = true;
}
}
if (foundbig) {
chars[chars.length - 1] = '9';
}
if (Integer.valueOf(new String(chars).trim()) > n) {
chars[chars.length - 1] = ' ';
}
return Integer.valueOf(new String(chars).trim());
}
@rajendra : I actually gave you an up vote. Later, I found, almost there but not there.
Observe this :
Input : 332 Expected : 299
Actual : 229
I was looking for branch conditions. Gotha.
I guess the dumb approach wins here :-)
def find_unoptimal( n ){
while( !is_tidy(n) ){ n -= 1 }
n // return
}
Obviously I will try to improve, but there are some very interesting edge scenarios.
I am hungry, SRH lost so frustrated, but this should do the trick :
/*
The find next lower tidy number is
not a classically trivial one.
Obvious trivial solution is :
def find_unoptimal( n ){ while( !is_tidy(n) ){ n -= 1 } }
But that is a mess.
A better solution will be:
1. Search for inversion of order ( d[i] > d[i+1] ) from left.
2. If on the inversion, we can down the digit:
Down(x) = x - 1
and d[i-1] < d[i] - 1 then we can down the digit, replace rest by 9.
3. If we can not do that ( 12222334445555123 ),
we search for a digit change from right: ( d[i]<d[i+1] )
where we can change d[i+1] to d[i] and replace all right digits by 9
*/
def find_last_tidy( n ){
sn = str(n)
l = size(sn)
i = index( [0:l-1] ) :: { sn[$.o] > sn[$.o+1] }
if ( i < 0 ) return n // this is first step
// is there a left digit? if not...
if ( i == 0 ) return int( '' + ( int(sn[0]) - 1 ) + ( '9' ** (l - 1) ) )
// there is
// if it is like 12222334445555|123 ?
// then we need to check j is the repeat size
j = index( [i:-1] ) :: { sn[$.o] != sn[i] }
ns = sn[0:i-j] + ( int(sn[i]) - 1 ) + ( '9' ** (l - i + j - 2 ) )
int ( ns )
}
println( find_last_tidy(@ARGS[0]) )
@NoOne, here is the improved one which will work for all edge cases.
public static int greatestSmallerTidyNumber(int n) {
int k = -1;
char[] chars = String.valueOf(n).toCharArray();
boolean foundbig = false;
for (int i = 0; i < chars.length - 1; i++) {
if (foundbig) {
chars[i] = '9';
continue;
}
if (chars[i] > chars[i + 1]) {
k = i;
while (--k >= 0) {
if (chars[k] != chars[i]) {
break;
}
}
i = k + 1;
if (chars[i] == '1') {
chars[i] = '9';
} else {
--chars[i];
}
foundbig = true;
}
}
if (foundbig) {
chars[chars.length - 1] = '9';
}
if (Integer.valueOf(new String(chars).trim()) > n) {
chars[chars.length - 1] = ' ';
}
return Integer.valueOf(new String(chars).trim());
}
public static int greatestSmallerTidyNumber(int n) {
int k = -1;
char[] chars = String.valueOf(n).toCharArray();
boolean foundbig = false;
for (int i = 0; i < chars.length - 1; i++) {
if (foundbig) {
chars[i] = '9';
continue;
}
if (chars[i] > chars[i + 1]) {
k = i;
while (--k >= 0) {
if (chars[k] != chars[i]) {
break;
}
}
i = k + 1;
if (chars[i] == '1') {
chars[i] = '9';
} else {
--chars[i];
}
foundbig = true;
}
}
if (foundbig) {
chars[chars.length - 1] = '9';
}
if (Integer.valueOf(new String(chars).trim()) > n) {
chars[chars.length - 1] = ' ';
}
return Integer.valueOf(new String(chars).trim());
}
function isTidy(n) {
var s = n.toString();
var prev = 0;
for(var i = 0; i < s.length; i++) {
if (s[i] < prev) {
return false;
break;
}
else {
prev = s[i];
}
}
return true;
}
let input = 143456;
if (isTidy(input)) {
console.log(input)
}
else {
for(var i = input; i > 0; i--) {
if (isTidy(i)) {
console.log(i);
break;
}
}
}
#include <iostream>
#include <math.h>
using namespace std;
int tidy_num(int num);
int main() {
// your code goes here
tidy_num(81231);
return 0;
}
int tidy_num(int num)
{
int dig, quo, prev, curr, new_num = num, count = 1;
while(num/10 >0)
{
dig = num % 10; quo = num/10;
prev = dig; curr = quo % 10;
if(prev < curr)
{
new_num = (quo * pow(10, count)) - 1;
}
num = num/10;
count++;
}
cout<<new_num;
}
int tidy(int n)
{
int i;
int last =0, cnt=10;
int l= n;
for (i=1;i < 20; i++){
if((l/10)%10 > l%10){
last =i;
printf("%d < %d = %d\n",(l/10)%10, l%10 , i);
}
l /= 10;
if(l == 0) break;
}
l = n;
for(i = 0;i<last; i++){
l /= 10;
}
if(last > 0)
l--;
for(i = 0;i<last; i++){
l =l*10 +9;
}
return l;
}
- AreDigitsTidyWild July 05, 2018