Amazon Interview Question
Country: United States
Sorry if this is naive, but isn't
s.substring(0, i) + s.substring(i + 1, len)
the same as
s
In pseudo-code something along the lines of:
public void print(int length)
{
printHelper(length, "");
}
public void printHelper(int lengthLeft, String strSoFar)
{
if(lengthLeft == 0)
{
cout << strSoFar << endl;
return;
}
for(int i = 0; i <= 9; i++)
{
printHelper(lengthLeft-1, strSoFar + toString(i));
}
}
You keep track of how much longer (how many digits) there is to go and call recursively once for every digit at that position. You also need to pass in the digits so far so you can print em at the end.
void printPerm(char *num, int len_so_far,int actual_len)
{
int start,i;
if(len_so_far == actual_len)
{
num[actual_len] = '\0';
printf("%s",num);
}
if(len_so_far ==0 )
start = 1;
else
start = 0;
for(i=start;i<9;i++)
{
num[len_so_far] = itoa(i);
printPerm(num, len_so_far + 1, actual_len);
}
}
public static void permutation(int [] target, boolean []used,int length, int level,StringBuffer out){
if( level == length ){
System.out.println( out.toString() );
return;
}
for( int i = 0; i < target.length; ++i ){
if( used[i] ) continue;
out.append( target[i] );
used[i] = true;
permutation( target, used, length, level + 1,out );
used[i] = false;
out.setLength( out.length() - 1 );
}
}
public class PrintAllNumberByDigit {
public static void printSequential(int digit, String base) {
for(int j=0; j < 10; j++) {
if(base.indexOf(String.valueOf(j)) == -1) {
String newBase = base + j;
if(digit > 1) {
printSequential(digit-1, newBase);
} else {
System.out.println(newBase);
}
}
}
}
public static void printSequential(int digit) {
printSequential(digit, "");
}
public static void main(String[] args) {
printSequential(5);
}
}
You used permutations and combinations as synonymous in your question, they are not. Google for permutations vs combinations.
Here is a solution (recursive of course - its really awful to do a permutation problem if one does not user recursion) without string manipulation.
It is in C++. I feel that this would be the answer that would score more brownie points in an interview:
#include <vector>
#include <iostream>
using namespace std;
void permutations(int s, int e, vector<int>& prfx) {
if (!e) {
for (int i=0; i < prfx.size(); i++)
cout << prfx[i];
cout << endl;
}
for (int i=s; i < 10; i++) {
prfx.push_back(i);
p(s+1, e-1, prfx);
prfx.pop_back();
}
}
int main() {
vector<int> t;
permutations(0,4, t);
return 0;
}
static void print_permutate(int K){
print_permutate_sub(new boolean[10], 0, K, 0);
}
static void print_permutate_sub(boolean[] used , int num , int K , int d){
if (d > K)
return;
else if (d == K){
System.out.println(num);
return;
}
int base = 0;
if (d == 0)
base = 1;
for (int i = base ; i < 10 ; i++){
if (!used[i]){
used[i] = true;
print_permutate_sub(used , num * 10 + i , K , d+1);
used[i] = false;
}
}
}
static void print_permutate(int K){
print_permutate_sub(new boolean[10], 0, K, 0);
}
static void print_permutate_sub(boolean[] used , int num , int K , int d){
if (d > K)
return;
else if (d == K){
System.out.println(num);
return;
}
int base = 0;
if (d == 0)
base = 1;
for (int i = base ; i < 10 ; i++){
if (!used[i]){
used[i] = true;
print_permutate_sub(used , num * 10 + i , K , d+1);
used[i] = false;
}
}
}
- Dhass April 11, 2013