Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
Sure! Algorithm is quite simple.
First of all, you have to count length of s and e: |s| and |e| accordingly. Hence we have to iterate through stepping number's length from |s| and |e| (from 1 to 16 in my example).
Let's make obvious remark: leading digit can't be zero. F.e. number 012 is stepping, but it's length = 2.
Then we use simple induction:
Base : According to remark, base of induction is stepping number which contains only one digit (from 1 to 9).
Step : On the previous steps we generated stepping sequence of digits. Ok! Let's take last of them and find all possible wariants for the next one. For 0 the only possible wariant is 1 , for 9 it's 8, for others - (other-1) and (other +1). Add them to our sequence and repeat step if we haven't reached necessary length.
Here is small example:
s = 10 , e = 1000
length = 2
1 (base) -> for 1 next digit can be 0 or 2 - > hence 10 and 12 (they are stepping, length == 2 reached)
2 (base) -> for 2 next digit can be 1 or 3 -> 21 and 23
...
9 (base) -> for 9 the only variant is 8 - > 98
length = 3
1(base) -> 10 -> 101
12 -> 121 and 123
2(base) -> 21 -> 210 and 212
23 -> 232 and 234
...
Hope this explanation is clear :)
By the way,you can implement optimization for this code : each time you increase length of stepping number you may use stepping numbers, evaluated for length-1.
public static List<Integer> steppingNo(int s, int e) {
ArrayList<Integer> res = new ArrayList<Integer>();
int i = 0;
while (s <= e) {
if (isStepping(s)) {
res.add(s);
}
s++;
}
return res;
}
private static boolean isStepping(int i) {
if (i >= 0 && i <= 9) return true;
while (i >= 10) {
if (Math.abs(i % 10 - (i / 10) % 10) != 1) { // compare last two digits
return false;
}
i = i / 10;
}
return true;
}
Your algorithm works too slow. Try to get all stepping numbers from s = 1 to e = 10^15.
Sorry about the efficiency. Your dfs is absolutely more efficient than the brute-force checking. I just wrote down my first idea.
This wont work for 8,343,545... because u need to make grouping of 3.
Else 5-3=2 and 8-3=5
Please verify if I am thinking correctly.
import java.util.ArrayList;
public class StepNum {
public static void stepNum(int start,int end)
{
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i = start;i<=end;i++)
{
if(check(i))
result.add(i);
}
System.out.print(result);
}
public static boolean check(int i)
{
ArrayList<Integer> a = new ArrayList<Integer>();
while(i/10>=1)
{
a.add(i%10);
i=i/10;
}
a.add(i);
for(int k =0;k<a.size()-1;k++)
{
if(a.get(k)-a.get(k+1)==1||a.get(k+1)-a.get(k)==1)
continue;
else
return false;
}
return true;
}
public static void main(String[] args)
{
int start = 100;
int end = 500;
stepNum(start,end);
}
}
Any constraint on the number of digits? Since infinite valid numbers can be generated with only start number and end number. For example, if s = 2 , e = 5 then
2345, 234345, 23434345, 2343434345, .......
Do I misunderstand this question?
public static void stepping(int start, int end) {
ArrayList<Integer> integers = new ArrayList<Integer>();
for (int i = start; i <= end; i++) {
integers.clear();
integers = breakIntegerIntoNumbers(i, integers);
int arrayIndex = 0;
boolean isStepping = true;
while (isStepping && arrayIndex < integers.size()) {
if (arrayIndex != integers.size() - 1) {// not last ele
if (Math.abs(integers.get(arrayIndex) - integers.get(arrayIndex + 1)) != 1) {
isStepping = false;
}
}
arrayIndex++;
}
if (isStepping) {
System.out.println("stepping"+i);
}else{
// System.out.println("not stepping -" +i);
}
}
}
public static ArrayList<Integer> breakIntegerIntoNumbers(int number, ArrayList<Integer> emptyList) {
if (number < 10) {
emptyList.add(number);
return emptyList;
} else {
breakIntegerIntoNumbers(number / 10, emptyList);
emptyList.add(number % 10);
return emptyList;
}
}
public static void stepCheck(int start,int end){
int flag = 0;
for(int i = start;i < end;i++)
{int n = i;
while(n>9){
if((n%10 + 1 == (n/10)%10) || (n%10 - 1 == (n/10)%10)){
flag = 1;
}
else{
flag = 0;
break;
}
n = n/10;
}// While
if(flag == 1)
System.out.println("number: "+i);
}//for
}// stepcheck
import java.util.ArrayList;
import java.util.List;
public class SteepingNumber {
public static void main(String[] args) {
int[] nums = {01 };
findSteepingNumber(nums);
}
private static void findSteepingNumber(int[] nums) {
List<Integer> numbers = new ArrayList<Integer>();
boolean flag = false;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
while (num > 9) {
if (((num % 10) - ((num / 10) % 10)) == 1
|| ((num % 10) - ((num / 10) % 10)) == -1) {
flag = true;
} else {
flag = false;
break;
}
num = num / 10;
}
if (flag)
numbers.add(nums[i]);
}
System.out.println(numbers);
}
}
// SteppingNumber.cpp : Defines the entry point for the console application.
/*
The stepping number:
A number is called as a stepping number if the adjacent digits are having a difference of 1. For eg. 8,343,545 are stepping numbers. While 890, 098 are not. The difference between a ‘9’ and ‘0’ should not be considered as 1.
Given start number(s) and an end number(e) your function should list out all the stepping numbers in the range including both the numbers s & e.
*/
#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <math.h>
#include <array>
using namespace std;
int digits(int s,int i){
int c = (s / ((int)pow(10, i))) % 10;
cout << c;
return c;
}
int length_number(int s){
int len=1;
if (s > 0)
{
for (len = 0; s > 0; len++){
s = s / 10;
}
}
//cout <<"LENGTH"<< len;
return len;
}
vector<int> numbers(int s, int e){
vector<int> range;
//int k = length_number(s);
//int j = length_number(e);
for (int i = s; i <= e; i++){
int d = length_number(i);
vector<int> L;
for (int m = d-1; m >=0; m--){
L.push_back(digits(i,m));
}
bool flag;
for (int j = 1; j < d;j++){
if (L.at(j)==((L.at(j+1)+1) || (L.at(j+1)-1))){
//range.push_back(i);
flag = true;
}
else{ flag = false; }
}
if (flag = true){
range.push_back(i);
}
}
return range;
}
int main(){
unsigned int a, b;
cout << "Starting Number:"<<endl;
cin >> a;
cout << "Ending Number:"<<endl;
cin>>b;
//int k=digits(a,1);
//length_number(a);
vector<int> k=numbers(a,b);
for (std::vector<int>::iterator it = k.begin(); it != k.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
getchar();
return 0;
}
// SteppingNumber.cpp : Defines the entry point for the console application.
/*
The stepping number:
A number is called as a stepping number if the adjacent digits are having a difference of 1. For eg. 8,343,545 are stepping numbers. While 890, 098 are not. The difference between a ‘9’ and ‘0’ should not be considered as 1.
Given start number(s) and an end number(e) your function should list out all the stepping numbers in the range including both the numbers s & e.
*/
#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <math.h>
#include <array>
using namespace std;
int digits(int s,int i){
int c = (s / ((int)pow(10, i))) % 10;
cout << c;
return c;
}
int length_number(int s){
int len=1;
if (s > 0)
{
for (len = 0; s > 0; len++){
s = s / 10;
}
}
//cout <<"LENGTH"<< len;
return len;
}
vector<int> numbers(int s, int e){
vector<int> range;
//int k = length_number(s);
//int j = length_number(e);
for (int i = s; i <= e; i++){
int d = length_number(i);
vector<int> L;
for (int m = d-1; m >=0; m--){
L.push_back(digits(i,m));
}
bool flag;
for (int j = 1; j < d;j++){
if (L.at(j)==((L.at(j+1)+1) || (L.at(j+1)-1))){
//range.push_back(i);
flag = true;
}
else{ flag = false; }
}
if (flag = true){
range.push_back(i);
}
}
return range;
}
int main(){
unsigned int a, b;
cout << "Starting Number:"<<endl;
cin >> a;
cout << "Ending Number:"<<endl;
cin>>b;
//int k=digits(a,1);
//length_number(a);
vector<int> k=numbers(a,b);
for (std::vector<int>::iterator it = k.begin(); it != k.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
getchar();
return 0;
}
#include <iostream>
#include <cmath>
using namespace std;
void stepping(int start,int end)
{ int flag=0;
for(int i=start;i<=end;i++)
{
int n=i;
while(n>9)
{
if(abs((n%10)-(n/10)%10)==1)
flag=1;
else
{
flag=0;
break;
}
n=n/10;
}
if(flag==1)
cout<<i<<" ";
}
}
int main()
{
stepping(1,100);
}
public class SteppingNumber{
public static void main(String args[]){
int start = 100;
int end = 1000;
for(int i = start; i<=end;i++){
checkStepping(i);
}
}
public static void checkStepping(int num){
String strNum = Integer.toString(num);
boolean flag = true;
for(int i = 1; i<= strNum.length()-1;i++){
if (!(Math.abs(Character.valueOf(strNum.charAt(i)) - Character.valueOf(strNum.charAt(i-1))) == 1)){
flag = false;
break;
}
}
if(flag){
System.out.println(num);
}
}
}
#include<iostream>
#include<sstream>
#include<string>
#include<cmath>
using namespace std;
bool step_number(int n){
stringstream ss;
ss<<n;
string str;
ss>>str;
if(str.length()==1)
return true;
for(int i=0;i<str.length()-1;i++){
int diff= abs(((int)str[i]-(int)str[i+1]));
if(diff!=1)
return false;
}
return true;
}
void disp_numbers(int low,int high){
for(int i=low;i<=high;i++){
if(step_number(i))
cout<<i<<endl;
}
}
int main(){
int low =343,high =545;
disp_numbers(low,high);
return 0;
}
#include <stdio.h>
#include <string.h>
main()
{
int start,stop,i,test;
int prev,rem,flag;
start=1;
stop=500;
printf("start:%d\n",start);
for(i=start;i<=stop;i++)
{
test=i;
flag=0;
while(test!=0 && flag==0)
{
rem=test%10;
if(i!=test)
{
if(!(prev==rem-1 || prev==rem+1))
{flag++;}
}
prev = rem;
test/=10;
}
if(flag==0)
{printf("%d\n",i);}
}
printf("stop:%d\n",stop);
}
//SKb
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class P3{
public static void main(String args[]) throws IOException{
int m = 0;
int n = 0;
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
m = Integer.parseInt(bf.readLine());
n = Integer.parseInt(bf.readLine());
for(int i=m;i<=n;i++){
if(steppingNumber(i)){
System.out.println(i);
}
}
}
public static boolean steppingNumber(int num){
String str = num+"";
char arr[] = str.toCharArray();
for(int i=arr.length-1;i > 0;i--){
int x = Character.getNumericValue(arr[i]);
int y = Character.getNumericValue(arr[i-1]);
if(Math.abs(x-y) != 1){
return false;
}
}
if(Math.abs(arr[arr.length-1] - arr[0]) != 1){
return false;
}
return true;
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class P3{
public static void main(String args[]) throws IOException{
int m = 0;
int n = 0;
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
m = Integer.parseInt(bf.readLine());
n = Integer.parseInt(bf.readLine());
for(int i=m;i<=n;i++){
if(steppingNumber(i)){
System.out.println(i);
}
}
}
public static boolean steppingNumber(int num){
String str = num+"";
char arr[] = str.toCharArray();
for(int i=arr.length-1;i > 0;i--){
int x = Character.getNumericValue(arr[i]);
int y = Character.getNumericValue(arr[i-1]);
if(Math.abs(x-y) != 1){
return false;
}
}
if(Math.abs(arr[arr.length-1] - arr[0]) != 1){
return false;
}
return true;
}
}
How about this... I know its doesn't deal with number like 012, 01212,... which start with ZERO.
public class SteppingNumbers {
public static void main(String[] args)
{
int start = 1;
int end = 50;
System.out.println("starting");
for(int i=start; i<=end; i++)
{
if(isSteppingNumber(i))
System.out.print(i+", ");
}
}
private static boolean isSteppingNumber(int i)
{
boolean result = false;
if(i <=9)
result = true;
else
{
String number = Integer.toString(i);
for(int j=1; j<number.length(); j++)
{
int x = Integer.parseInt(number.charAt(j-1)+"");
int y = Integer.parseInt(number.charAt(j)+"");
if(Math.abs(x-y)==1)
{
result = true;
}
else{
result = false;
break;
}
}
}
return result;
}
}
I got to admit GK's idea is good. Like what he/she did, DFS+memoization is used.
Some modifications are applied in my code. If the range contains negative numbers, different cases need to be investigated. Other than that, nothing different from GK's code.
Playable code at
ideone.com/o6Qq4z
void stepGen(int pre, int low, int high, vector<int> &res) {
if (pre > high) return;
if (pre >= low && pre <= high) res.push_back(pre);
int lastdigit = pre % 10;
if (pre == 0) {
for (int st = 1; st <= 9; ++st) stepGen(st, low, high, res);
}
else {
if (lastdigit < 9) stepGen(pre * 10 + lastdigit + 1, low, high, res);
if (lastdigit > 0) stepGen(pre * 10 + lastdigit - 1, low, high, res);
}
}
vector<int> step(pair<int, int> bound) { // call me
vector<int> res;
if (bound.first > bound.second) return res;
if (bound.first * bound.second < 0) {
stepGen(0, 0, -bound.first, res);
for (auto &e : res) e *= -1;
stepGen(0, 1, bound.second, res); // here 1 is used as lower bound since 0 has been
// considered in negative part.
}
else {
if (bound.first < 0) {
stepGen(0, -bound.second, -bound.first, res);
for (auto &e : res) e *= -1;
}
else stepGen(0, bound.first, bound.second, res);
}
return res;
}
public class SteppingNumber {
public static void printSteppingNumber(String str) {
int length = str.length();
// Any number from 0 to 10 is a stepping number
if(Integer.parseInt(str) >=0 && Integer.parseInt(str) <=10) {
System.out.println(str);
}
for(int i = 0; i < length; i++) {
int arange = i+1;
int brange = i+2;
/**
* Checking the adjacent digits, ensure range is within length of string
*/
if(arange > length || brange > length)
break;
int a = Integer.parseInt(str.substring(i, arange));
int b = Integer.parseInt(str.substring(i+1,brange));
int difference = Math.abs(a - b);
if(difference != 1)
return;
}
System.out.println(str);
}
public static void main(String[] args) {
int start = 8, end = 545;
for(int i = start; i <= end; i++) {
printSteppingNumber(String.valueOf(i));
}
}
}
// output: Stepping of 789 and 987[789, 876, 878, 898, 987]
package interviews.epic;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author venkatramreddykunta
*/
public class SteppingNo {
public static void main(String[] args) {
System.out.println("Stepping of 789 and 987"+steppingNo(789,987));
}
public static List<Integer> steppingNo(int s, int e) {
ArrayList<Integer> steppingNumbers = new ArrayList<Integer>();
int i = 0;
while (s <= e) {
if (isStepping(s))
steppingNumbers.add(s);
s++;
}
return steppingNumbers;
}
// 9
// 9876
private static boolean isStepping(int i) {
if(i<=9 && i>=0)
return true;
if(Math.abs(i%10-(i/10)%10)==1)
return isStepping(i/10);
else
return false;
}
}
This is not DP problem. There is no way to split into subproblems and reuse solutions
Here is the greedy solution
{{
public static void PrintSteppingNumbers(int start, int end)
{
for (var input = start; input < end; input++)
{
var isFirst = true;
var notMatch = false;
int previous = 0;
while (input > 0)
{
if (isFirst)
{
isFirst = false;
previous = input % 10;
}
else
{
if (Math.Abs(previous - (input % 10)) != 1)
{
notMatch = true;
break;
}
}
input = input / 10;
}
if (!notMatch)
{
Console.WriteLine(input);
}
}
}
}}
public class SteppingNumber {
public static void dfs(int n, int m, int stepNum){
if(stepNum <= m && stepNum >= n)
System.out.println(stepNum + " ");
if(stepNum == 0 || stepNum >m)
return;
int lastDigit = stepNum%10;
int stepNumA = stepNum*10 + (lastDigit - 1);
int stepNumB = stepNum*10 + (lastDigit +1);
if(lastDigit == 0)
dfs(n,m,stepNumB);
else if(lastDigit == 9)
dfs(n,m,stepNumA);
else{
dfs(n, m, stepNumA);
dfs(n, m, stepNumB);
}
}
public static void displaySteppingNumbers(int n, int m){
for(int i = 0; i<=9; i++)
dfs(n,m,i);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
displaySteppingNumbers(20,42);
}
}
//
public class SteppingNumber {
public static void main(String[] args)
{
int start, end;
Scanner sc=new Scanner(System.in);
System.out.println("Enter the start number");
start=sc.nextInt();
System.out.println("Enter the end number");
end=sc.nextInt();
int copy,a,b,c1=0,c2=0;
for(int i=start;i<=end;i++)
{
copy=i;
c1=c2=0;
a=copy%10;
copy=copy/10;
while(copy!=0)
{
b=copy%10;
if(b==(a-1)||a==(b-1))
{
c1++;
}
copy=copy/10;
a=b;
c2++;
}
if(c1==c2)
System.out.println(i);
}
}
}
- GK October 14, 2014