## Epic Systems Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
8
of 8 vote

``````static void Dfs(long s, long e , long length , long num)
{
if (length-1 == 0)
{
if ( s <= num && num <=e)
Console.WriteLine(num);
return;
}
var lastDigit = num%10;
if (lastDigit == 0)
{
Dfs(s , e,length-1 , num*10+1);
}
else if (lastDigit == 9)
{
Dfs(s, e, length - 1, num*10 + 8);
}
else
{
Dfs(s , e,length-1 , num*10+lastDigit-1);
Dfs(s , e,length-1 , num*10+lastDigit+1);
}
}

static void Main(string[] args)
{
long s = 1;
long e = 1000000000000000;
var sLength = (int)Math.Floor(Math.Log10(s) + 1);
var eLength = (int)Math.Floor(Math.Log10(e) + 1);
for (long i = sLength; i <= eLength; ++i)
{
for (long j = 1; j < 10; ++j)
{
Dfs(s , e, i , j);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

@GK
It would be very thankful if you explain a bit.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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 :)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

How to calculate time complexity for the above program?

Comment hidden because of low score. Click to expand.
4
of 6 vote

``````public static List<Integer> steppingNo(int s, int e) {
ArrayList<Integer> res = new ArrayList<Integer>();
int i = 0;
while (s <= e) {
if (isStepping(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;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Your algorithm works too slow. Try to get all stepping numbers from s = 1 to e = 10^15.

Comment hidden because of low score. Click to expand.
0

Sorry about the efficiency. Your dfs is absolutely more efficient than the brute-force checking. I just wrote down my first idea.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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))
}
System.out.print(result);
}
public static boolean check(int i)
{
ArrayList<Integer> a = new ArrayList<Integer>();
while(i/10>=1)
{

i=i/10;
}
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);
}

}``````

Comment hidden because of low score. Click to expand.
0

it leaves out the case where the number only has one digit.

Comment hidden because of low score. Click to expand.
0

I think if the number only has one digit, it will return true;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

s=100, e=200, print all stepping number between 100 to 200

Comment hidden because of low score. Click to expand.
0

I see. Thx.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do you mean 343,545 instead of 8,343,545?

Comment hidden because of low score. Click to expand.
0

It looks like commas separate groupings of numbers, as 35 in 3545 are not adjacent

Comment hidden because of low score. Click to expand.
0

It is 8,343,545. If we are given startNum as 8 and endNum as n should print out all stepping numbers from 8 to n (including both). Hence the 8.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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) {
return emptyList;
} else {
breakIntegerIntoNumbers(number / 10, emptyList);
return emptyList;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````for(i = s; i < e; i++ )
{
int copy = i;
do{
a = copy %10;
copy = copy / 10;
b = copy%10;
}while((a==b-1||a-1==b）&& copy > 10);
if(copy < 10)
{
if(a==b-1 || a-1 == b)
{
printf("%d",i);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)
}
System.out.println(numbers);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0

types can be changed if longer range is needed

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.BufferedReader;
import java.io.IOException;

class P3{
public static void main(String args[]) throws IOException{
int m = 0;
int n = 0;

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.BufferedReader;
import java.io.IOException;

class P3{
public static void main(String args[]) throws IOException{
int m = 0;
int n = 0;

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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))
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;

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void printSteppingNum(int n,int n1){

for(int i=n;i<=n1;i++){

for(int k=i;k>0;k=k/10){
if (k/10==0){
System.out.println(i);
break;
}

if ((k/10)%10 - k%10!=1 && (k/10)%10 - k%10!=-1 ){

break;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}
}

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}

}
//``````

Comment hidden because of low score. Click to expand.
-2
of 6 vote

``````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);

}

}

}``````

Comment hidden because of low score. Click to expand.
0

@Payel Hazra Can you please explain your code in brief?
It would be very helpful.

Comment hidden because of low score. Click to expand.
0

@payel Hazra
Kindly please explain your code a bit.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Have you tried to change int to long for s and e and run with input s = 1 and e = 10^15 ? Your implementation will take huge amount of time for evaluating all stepping numbers.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.