Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
In this statement:
for(int i=(prev+1); i<(11-n); i++){
why is
i<(11-n)
used instead of
i<10
? I tried the latter and it produces the same result while running
printWellOrdered(0, 0, 4)
#include <iostream>
using namespace std;
/*
* This function generates all the well ordered
* combinations of passwords for a given length.
* Parameters -
* length : The length of the password to be generated.
* curr_length : The length generated so far.
* pswd - The password represented as an integer. This
* puts a constraint that the password can't begin with
* a zero.
*/
void Generate (int length, int curr_length, int pswd) {
/*
* If the below if clause is true, then we have
* generated the required number of digits. So
* now print that password and return.
*/
if (curr_length == length) {
cout << pswd << "\t";
return;
}
/*
* Get the least significant digit from the password
* generated so far. This helps us check if the next
* loop iteration will yield a well ordered password
* or not.
*/
int unit_digit = pswd % 10;
for (int i = 1; i < 10; i++) {
/*
* Only if 'i' is greater than 'unit_digit',
* then 'i' will become the new least significant
* digit. If not, then the well-ordered condition
* fails and we just continue looping.
*/
if (i > unit_digit) {
/*
* Make 'i' the least significant digit
* in the password now.
*/
pswd = pswd * 10 + i;
/*
* Recursively call the Generate function again
* to generate the next least significant digit.
* This will continue till curr_length will become
* equal to the desired length.
*/
Generate (length, curr_length + 1, pswd);
/*
* You are now done with one possible password.
* Now remove the least significant digit and
* proceed to the next possible combination.
*/
pswd = pswd / 10;
}
}
}
int main ( ) {
// Length of the password
int length;
cout << "Enter the length of the password: ";
cin >> length;
/*
* Password's most significant number ranges from
* 1 to 9. Hence looping 9 times. Remember, this
* looping is only for the most significant number.
* The lesser significant numbers are generated in
* the Generate function.
*/
for (int pswd = 1; pswd < 10; pswd++) {
Generate (length, 1, pswd);
}
cout << endl;
return 0;
}
If n is the length of password, we can choose 10Cn different combinations of the 10 digits. Since there is only one possible order among the numbers, the total number of distinct passwords is 10Cn.
your answer is correct if we are not suppose to use same number multiple times..........
your answer is correct if we are not suppose to use same number multiple times..........
your answer is correct if we are not suppose to use same number multiple times..........
your answer is correct if we are not suppose to use same number multiple times..........
your answer is correct if we are not suppose to use same number multiple times..........
u cannot use the same number multiple times as by definition of well-ordered number says x<y<z not x<=y<=z keeping the digit requirements distinct. Maybe discussing about this other case will give rise unique solutions.
def pwd(n):
return _pwd("", range(1,10), n)
def _pwd(p, rest, n):
if n == 0: print p
for i, x in enumerate(rest):
_pwd(p+str(x), rest[i+1:], n-1)
pwd(5)
#include "iostream.h"
void func(int level, int lastLevelNum);
int gPossiblePasswordCount = 0;
int main()
{
int passwordLength;
cout<<"Enter the length of the Password: ";
cin>>passwordLength;
func(passwordLength, 0); // We will start wih '0' as the lastLevelNum
cout<<"\nNo. of Possible Passwords:"<<gPossiblePasswordCount;
return 0;
}
void func(int level, int lastLevelNum)
{
if(level == 1 && lastLevelNum == 0)
{
gPossiblePasswordCount = 0;
return;
}
for(int i = lastLevelNum + 1; i <= 10 - level; i++)
{
if(level == 1)
gPossiblePasswordCount++;
else
func(level - 1, i);
}
}
Can you provide some more information? can you say 832 is wel-ordered number? 8>3>2?
also how about characters? it can be any combination, and we need to check the index of chars also along with numbers?
public void printPass(int n)
{
for(int i=1;i<=10-n;i++)
{
for(j=0;j<n;j++)
{
System.out.print(i+j);
}
System.out.println();
}
}
static void wellFormed(int index, int n)
{
int i;
if(n>9)
{
System.out.println("Cannot form Well Formed NUmbers with the given size of n");
return;
}
if(s.length()==n)
{
System.out.print(s.toString()+" ");
return;
}
for(i=index;i<10;i++)
{
s.append(i);
wellFormed(i+1,n);
s.delete(s.length()-1,s.length());
}
}
public static void main(String[] args)
{
System.out.println(s.toString());
wellFormed(1,9);
System.out.println("\n\n"+s.toString());
}
#include <iostream>
#include <vector>
using namespace std;
void printNum(int numRemaining,vector<int> vec, int num)
{
if(numRemaining == 0)
{
cout<<num<<endl;
return;
}
vector<int>::iterator iter,titer;
int test = 0;
int ind = 0;
for(iter = vec.begin(); iter < vec.end(); iter++,ind++)
{
int currD = *iter;
test = num*10 + currD;
if(test != 0)
{
vector<int> tempVec = vec;
titer = tempVec.begin() + ind;
tempVec.erase(tempVec.begin(),titer+1);
printNum(numRemaining -1 , tempVec, num*10 + currD);
}
}
}
int main()
{
vector<int> digits(10);
int i = 0;
const int numDigits = 7;
vector<int>::iterator iter;
for(iter = digits.begin();iter < digits.end();iter++)
{
*iter = i++;
}
int num= 0;
printNum(numDigits,digits,num);
}
#include <iostream>
#include <vector>
using namespace std;
void printNum(int numRemaining,vector<int> vec, int num)
{
if(numRemaining == 0)
{
cout<<num<<endl;
return;
}
vector<int>::iterator iter,titer;
int test = 0;
int ind = 0;
for(iter = vec.begin(); iter < vec.end(); iter++,ind++)
{
int currD = *iter;
test = num*10 + currD;
if(test != 0)
{
vector<int> tempVec = vec;
titer = tempVec.begin() + ind;
tempVec.erase(tempVec.begin(),titer+1);
printNum(numRemaining -1 , tempVec, num*10 + currD);
}
}
}
int main()
{
vector<int> digits(10);
int i = 0;
const int numDigits = 7;
vector<int>::iterator iter;
for(iter = digits.begin();iter < digits.end();iter++)
{
*iter = i++;
}
int num= 0;
printNum(numDigits,digits,num);
}
public static List<String> generateAllCombinations( String[] arr, int combinationLength ){
if( arr == null ){
throw new IllegalArgumentException("Can't generate combination from NULL array");
}
return generateCombinations( Arrays.copyOf(arr, arr.length), combinationLength, 0 );
}
private static List<String> generateCombinations( String[] arr, int combinationLength, int fromIndex ){
if( combinationLength > 2 ){
List<String> combinations = new ArrayList<String>();
int index = fromIndex;
++fromIndex;
while( index < arr.length - combinationLength ){
String value = arr[index];
List<String> smallerCombinations = generateCombinations( arr, combinationLength-1, fromIndex );
for( String smallComb : smallerCombinations ){
combinations.add( value + smallComb );
}
++index;
++fromIndex;
}
// Create and add final combination
StringBuilder finalComb = new StringBuilder();
while( index < arr.length ){
finalComb.append( arr[index] );
++index;
}
combinations.add( finalComb.toString() );
return combinations;
}
// generate all possible 2-combination
List<String> twoCombinations = new ArrayList<String>();
for( int i = fromIndex; i < arr.length-1; i++ ){
for( int j = i+1; j < arr.length; j++ ){
twoCombinations.add( arr[i] + arr[j] );
}
}
return twoCombinations;
}
String[] arr = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
List<String> passwords = CombinationsUtils.generateAllCombinations( arr, 3);
System.out.println( passwords.size() ); // 120
System.out.println( passwords); // [012, 013, 014, ....., 789]
#include<stdio.h>
void well(int,int,char []);
//int count =0;
int num=2; // number of digits
int numb_of=0;
int main()
{
char s[10];
well(1,0,s);
printf("\n%d\n",numb_of);
return 0;
}
void well(int p,int count,char str[])
{
int j;
if(count==num)
{
str[count]='\0';
printf("%s\n",str);
numb_of++;
}
else
{
for(j=p;j<=9;j++)
{
str[count] = j+48;
well(j+1,count+1,str);
}
}
}
public static List<string> Well(int start, int size)
{
List<string> output = new List<string>();
if (size == 1)
output.Add(start.ToString());
else
{
for (int i = start; i <= 10 - size; i++)
{
List<string> temp = Well(i + 1, size - 1);
foreach (string str in temp)
{
output.Add(i.ToString() + str);
}
}
}
return output;
}
#!/usr/bin/env python
import sys
numbers = ['0','1','2','3','4','5','6','7','8','9']
def findPasswd(length,psswd):
if length <= 0:
print 'length <=0'
return
if length == 1:
psswd[:] = numbers[:]
else:
findPasswd(length-1,psswd)
for i in xrange(len(psswd)):
last_c = psswd[i][-1]
for x in numbers:
if x > last_c:
psswd.append(psswd[i]+x)
psswd[i] = psswd[i] + last_c
def foo(psswd):
for x in numbers:
psswd.append(x)
if __name__ == '__main__':
length = int(sys.stdin.readline())
psswd = []
findPasswd(length,psswd)
for x in psswd:
print x
#!/usr/bin/env python
import sys
numbers = ['0','1','2','3','4','5','6','7','8','9']
def findPasswd(length,psswd):
if length <= 0:
print 'length <=0'
return
if length == 1:
psswd[:] = numbers[:]
else:
findPasswd(length-1,psswd)
for i in xrange(len(psswd)):
last_c = psswd[i][-1]
for x in numbers:
if x > last_c:
psswd.append(psswd[i]+x)
psswd[i] = psswd[i] + last_c
def foo(psswd):
for x in numbers:
psswd.append(x)
if __name__ == '__main__':
length = int(sys.stdin.readline())
psswd = []
findPasswd(length,psswd)
for x in psswd:
print x
protected void btn_Click(object sender, EventArgs e)
{
int length=Convert.ToInt32(TextBox1.Text);
string strStart = "1";
string strEnd = "9";
for (int i = 1; i < length; i++)
{
strStart += "0";
strEnd += "9";
}
int start = Convert.ToInt32(strStart);
int end = Convert.ToInt32(strEnd);
for (int j = start; j <= end; j++)
{
string temp = j.ToString();
if (Palindrome(temp))
{
Response.Write(temp + "\n");
}
}
}
bool Palindrome(string str1)
{
bool Flag = false;
if (ReverseString(str1) == str1)
{
Flag = true;
}
return Flag;
}
public static string ReverseString(string s)
{
char[] arr = s.ToCharArray();
Array.Reverse(arr);
return new string(arr);
}
#include<stdio.h>
int getpasswd(int n, int p, int num)
{
if(n==0)
{
printf("%d\n",num);
return;
}
int i;
for(i=p+1;i<10;i++)
{
num=num*10+i;
getpasswd(n-1,i,num);
num=(num-i)/10;
}
}
void main()
{
getpasswd(n,0,0); //n is the length od password
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Password {
// TODO Auto-generated method stub
public static void main(String args[]) {
int len = 0;
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
System.out.println("enter the length");
len = Integer.parseInt(br.readLine());
System.out.println("length is " + len);
find("",0,len);
} catch (Exception e) {
e.printStackTrace();
}
}
public static void find(String str,int passed,int len ){
int i;
if(len==0){
System.out.println(str);
}
for(i=passed+1;i<=9;i++){
find(str.concat(Integer.toString(i)),i,len-1);
}
}
}
#include <stdio.h>
void generatePswd(int level, int curtDigit, int num)
{
if (level == 0)
{
printf("%d\n", num);
return ;
}
int newNum = num * 10;
for (int ire = curtDigit + 1; ire < 10; ire++)
{
generatePswd(level - 1, ire, newNum + ire);
}
}
int main(int argc, char **argv)
{
generatePswd(3, 0, 0);
return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Password {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter two numbers");
String s1 = br.readLine();
int i, j, k, l, count = 0;
i = Integer.parseInt(s1);
l = Integer.parseInt(br.readLine());
for (j = i + 1; j < l; j++) {
for (k = j + 1; k < l; k++) {
System.out.println("Unique password" + i + j + k + l);
count++;
}
}
System.out.println("Combinations" + count);
}
}
public class program6 {
public static String g = "123456789";
public static void Combination(String source,int len,int index,String generator)
{
if(source.length()==len)
{
System.out.println(source);
}
else
{
if(index<generator.length())
{
for(int i=0;i<=(generator.length()-index);i++)
{
Combination(source+generator.charAt(i),len,index-1,generator.substring(i+1));
}
}
else
{
for(int i=0;i<generator.length();i++)
{
Combination(source+generator.charAt(i),len,index-1,generator.substring(i+1));
}
}
}
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
System.out.println("Enter the length of password: ");
int len = in.nextInt();
String s ="";
Combination(s,len,len,g);
}
}
import java.util.Scanner;
public class printpasswords {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
System.out.println("Enter the length of password:");
int len = in.nextInt();
genpassword("", len, -1);
}
private static void genpassword(String prefix, int len, int previous){
if (len == 0){
System.out.println(prefix);
return;
}
else {
for (int i=previous+1; i<10; i++){
genpassword(prefix+i, len-1, i);
}
}
}
}
import java.util.Scanner;
public class printpasswords {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
System.out.println("Enter the length of password:");
int len = in.nextInt();
genpassword("", len, -1);
}
private static void genpassword(String prefix, int len, int previous){
if (len == 0){
System.out.println(prefix);
return;
}
else {
for (int i=previous+1; i<10; i++){
genpassword(prefix+i, len-1, i);
}
}
}
}
Working Python code, using recursion.
"""
3:40
@Python 2.7
Find all the possible passwords, given the length of the password and that it is a well ordered number (159 is well-ordered as 1<5<9)
- S.A.M on March 10, 2012 in United States Report Duplicate | Flag
"""
class IncPWD(object):
def __init__(self, n):
if n is None:
print 'Invalid N'
raise SystemExit
self._n = n
self._src = [str(x) for x in range(10)]
self._output = []
def findAll(self, pos = 0):
if len(self._output) == self._n:
print ''.join(self._output)
return
while pos < 10 - self._n + 1 + len(self._output):
self._output.append(self._src[pos])
self.findAll(pos + 1)
self._output.pop()
pos += 1
if __name__ == '__main__':
ip = IncPWD(4)
ip.findAll()
#include <stdio.h>
/* start = starting digit
arr = string that holds the results
pos = position in arr
len = len of pwd
*/
void pwd(int start, char *arr, int pos, int len)
{
if (pos == len)
{
arr[len] = '\0';
printf("%s\n", arr);
return;
}
int gen;
gen = start + 1;
while (gen <=9)
{
char ch = gen + '0';
arr[pos] = ch;
pwd(gen, arr, pos+1, len);
gen++;
}
}
int main()
{
char arr[5];
pwd(0, arr, 0, 4);
}
#include <stdio.h>
/* start = starting digit
arr = string that holds the results
pos = position in arr
len = len of pwd
*/
void pwd(int start, char *arr, int pos, int len)
{
if (pos == len)
{
arr[len] = '\0';
printf("%s\n", arr);
return;
}
int gen;
gen = start + 1;
while (gen <=9)
{
char ch = gen + '0';
arr[pos] = ch;
pwd(gen, arr, pos+1, len);
gen++;
}
}
int main()
{
char arr[5];
pwd(0, arr, 0, 4);
}
#include <stdio.h>
/* start = starting digit
arr = string that holds the results
pos = position in arr
len = len of pwd
*/
void pwd(int start, char *arr, int pos, int len)
{
if (pos == len)
{
arr[len] = '\0';
printf("%s\n", arr);
return;
}
int gen;
gen = start + 1;
while (gen <=9)
{
char ch = gen + '0';
arr[pos] = ch;
pwd(gen, arr, pos+1, len);
gen++;
}
}
int main()
{
char arr[5];
pwd(0, arr, 0, 4);
}
public class Passwords {
public static void main(String[] args) {
generatePassword(1,5,0);
}
static void generatePassword(int prev, int n, int num) {
for (int i = prev; i < 10; i++) {
if (n == 1)
System.out.println(num+i);
else
generatePassword(i + 1, n - 1, (int) (num + i * Math.pow(10, n - 1)));
}
}
}
public class WellOrderedNumber
{
public void order(String str, int leng)
{
if(leng==0)
{
System.out.println(str);
}
char c;
if(str.length()==0)
{
c = '0';
}
else
{
c = (char)(str.charAt(str.length()-1)+1);
}
for(;c<='9';c++)
{
order(str+c,leng-1);
}
}
public static void main(String args[])
{
WellOrderedNumber w = new WellOrderedNumber();
w.order("", 3);
}
}
package p1;
import java.util.ArrayList;
import java.util.Scanner;
public class possiblepasswords {
public static void main(String arg[])
{
Scanner keyboard = new Scanner(System.in);
System.out.println("enter an integer from keyboard and press enter");
int myint = keyboard.nextInt();
System.out.println(myint);
int[] num=new int[myint];
int p=0;
perm(num,p);
}
static void perm(int[] num,int p){
ArrayList ar=new ArrayList();
for(int i=p;i<num.length;i++)
{
for(int j=0;j<10;j++)
{
num[i]=j;
perm(num,i+1);
}
}
if(asc(num)){
for(int j=0;j<num.length;j++)
{
System.out.print(num[j]);
}
System.out.println();
}
}
static boolean asc(int[] num)
{
for (int i = 0; i < num.length - 1; i++) {
if (num[i] > num[i+1] || num[i] == num[i+1]) {
return false;
}
}
return true;
}
}
import itertools
def orderedPasswd(length):
lengthStr = str(length)
if not lengthStr.isdigit():
return None
allPasswdList = [[str(j) for j in range(10)] for i in range(length)]
#filter
allCombination = [''.join(i) for i in itertools.product(*allPasswdList)]
candiPasswd = filter(lambda x: str(x) == ''.join(sorted(str(x))), allCombination)
return candiPasswd
import itertools
def orderedPasswd(length):
lengthStr = str(length)
if not lengthStr.isdigit():
return None
allPasswdList = [[str(j) for j in range(10)] for i in range(length)]
#filter
allCombination = [''.join(i) for i in itertools.product(*allPasswdList)]
candiPasswd = filter(lambda x: str(x) == ''.join(sorted(str(x))), allCombination)
return candiPasswd
void main()
{
clrscr();
int i,j,k,l;
for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
{
for(k=j+1;k<10;k++)
{
for(l=k+1;l<10;l++)
{
printf("%d %d %d %d\n",i,j,k,l);
}
}
}
}
getch();
}
length of password is 4 ...i think it will print all the password in the given X<y<w<z format .....
u need to use recursion, for say a "n" number of digits, u r hardcoding the value n=4. By doing this, u might be able to get the idea of how to proceed (which is recursion, from my point of view).
/*Find all the possible passwords, given the length of the password
and that it is a well ordered number (159 is well-ordered as 1<5<9)*/
package com.prac;
import java.util.*;
public class Password {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.print("Enter the length of the password minimum being 2:");
int n=sc.nextInt();//n is the input
int a[]=new int[n];
int length=n;//for array index
int length1;
int flag;
int num;
if(n<2)
System.out.println("Input entered invalid please enter input greater than equal to 2");
else
{
System.out.print("The possible paswords are:");
for(int i=(int)Math.pow(10,n-1);i<(int)Math.pow(10,n);i++)
{
num=i;
length1=n;
flag=0;
for(int j=0;j<length;j++)
{
a[j]=num/(int)Math.pow(10, length1-1);
num=num%(int)Math.pow(10, length1-1);
length1=length1-1;
}
for(int k=0;k<length-1;k++)
{
if(a[k]<a[k+1])
{
flag+=1;
}
else
{
flag=0;
}
if(flag==(n-1))
System.out.print(i+" ");
}
}
}
}
}
//
Solution in java..
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<String> res = new ArrayList<String>();
findPass(3, res);
for (String h : res)
System.out.println(h);
System.out.println(res.size());
}
private static void findPass(int len, ArrayList<String> res) {
// TODO Auto-generated method stub
String number = "0123456789";
ArrayList<String> foundTill = new ArrayList<String>();
if (len > number.length())
return;
for (int i = 0; i < number.length(); i++) {
ArrayList<String> temp = new ArrayList<String>();
for (String s : foundTill) {
if (s.length() < len)
temp.add(s + number.charAt(i));
}
foundTill.addAll(temp);
foundTill.add(number.charAt(i) + "");
}
for (String h : foundTill) {
if (h.length() == len)
res.add(h);
}
}
printWellOrdered(0,0,4); // 4 digit numbers
- agnithin August 21, 2012private static void printWellOrdered(int number, int prev, int n) {
if(n==0){
System.out.println(number);
return;
}
for(int i=(prev+1); i<(11-n); i++){
printWellOrdered(number*10 + i, i, n-1) ;
}
}