EMC Interview Question
Software Engineer / Developersclass AnagramApp
{
static int size;
static int count;
static char[] arrChar = new char[100];
//-----------------------------------------------------------
public static void main(String[] args) throws IOException
{
System.out.print("Enter a word: "); // get word
String input = getString();
size = input.length(); // find its size
count = 0;
for(int j=0; j<size; j++) // put it in array
arrChar[j] = input.charAt(j);
doAnagram(size); // anagram it
} // end main()
//-----------------------------------------------------------
public static void doAnagram(int newSize)
{
int limit;
if(newSize == 1) // if too small,
return; // go no further
for(int j=0; j<newSize; j++) // for each position,
{
doAnagram(newSize-1); // anagram remaining
if(newSize==2) // if innermost,
displayWord(); // display it
rotate(newSize); // rotate word
}
}
//-----------------------------------------------------------
// rotate left all chars from position to end
public static void rotate(int newSize)
{
int j;
int position = size - newSize;
char temp = arrChar[position]; // save first letter
for(j=position+1; j<size; j++) // shift others left
arrChar[j-1] = arrChar[j];
arrChar[j-1] = temp; // put first on right
}
//-----------------------------------------------------------
public static void displayWord()
{
if(count < 99)
System.out.print(" ");
if(count < 9)
System.out.print(" ");
System.out.print(++count + " ");
for(int j=0; j<size; j++)
System.out.print( arrChar[j] );
System.out.print(" ");
System.out.flush();
if(count%6 == 0)
System.out.println("");
}
//-----------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//-----------------------------------------------------------
} // end class AnagramApp
////////////////////////////////////////////////////////////////
#include<stdio.h>
void rotate(int a[],int n);
void print(int a[],int n);
main()
{
int a[3];
int i,j,k;
for(i=0;i<3;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<3;i++)
{
printf("%d%d\n",a[0],a[i]);
}
for(i=0;i<3;i++)
{
rotate(a,3);
print(a,3);
}
}
void rotate(int a[],int n)
{
int i,k;
int temp=0;
for(i=0;i<n-1;i++)
{
k=i+1;
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
void print(int a[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf("%d",a[i]);
}
printf("\n");
}
I have come up with this stack based approch for this problem in C#.anyway it need bit additional memory for stack.
static void getPossibleIntegers(int[] inArray, int[] outArray)
{
Stack<int> stkArray = new Stack<int>();
int len = inArray.Length;
int curPos = -1,digit, temp;
for (int i = 0; i < len; i++)
{
digit = 1;
outArray[++curPos] = inArray[i]*digit;
stkArray.Push(inArray[i] * digit);
while (stkArray.Count > 0)
{
temp = stkArray.Pop();
for (int j = 0; j < len; j++)
{
if ((inArray[i] == inArray[j]) || (temp % 10 == inArray[j])) continue;
digit *= 10;
if (temp*digit < Math.Pow(10, len - 1))
stkArray.Push(temp*digit + inArray[j]);
outArray[++curPos]= temp*digit + inArray[j];
digit /= 10;
}
}
}
}
<pre lang="" line="1" title="CodeMonkey19527" class="run-this">#include<stdio.h>
#include<string.h>
#include<math.h>
int a[100],n;
void print()
{
int i,k,j;
for(i=0;i<pow(2,n);i++)
{
j=0;
k=i;
while(k)
{
if(k%2)
printf("%d",a[j]);
k/=2;
j=j+1;
}
printf("\n");
}
}
main()
{
int i;
printf("howmany nentumbers u want to enter ?");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
print();
}
</pre><pre title="CodeMonkey19527" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey29943" class="run-this">#include<stdio.h>
#include<string.h>
#include<math.h>
int a[100],n;
void print()
{
int i,k,j;
for(i=0;i<pow(2,n);i++)
{
j=0;
k=i;
while(k)
{
if(k%2)
printf("%d",a[j]);
k/=2;
j=j+1;
}
printf("\n");
}
}
main()
{
int i;
printf("howmany nentumbers u want to enter ?");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
print();
}
</pre><pre title="CodeMonkey29943" input="yes">
this code works for single digit integers</pre>
<pre lang="" line="1" title="CodeMonkey9503" class="run-this">#include<stdio.h>
#include<string.h>
#include<math.h>
int a[100],n;
void print()
{
int i,k,j;
for(i=0;i<pow(2,n);i++)
{
j=0;
k=i;
while(k)
{
if(k%2)
printf("%d",a[j]);
k/=2;
j=j+1;
}
printf("\n");
}
}
main()
{
int i;
printf("howmany nentumbers u want to enter ?");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
print();
}
</pre><pre title="CodeMonkey9503" input="yes">
this code works for single digit integers</pre>
public static void permutationAll(char [] ch, StringBuilder sb,int count, boolean [] used){
for (int i=0;i<ch.length;++i){
if (used[i]){
continue;
}
sb.append(ch[i]);
System.out.println(sb.toString());
used[i]=true;
permutationAll(ch,sb,count+1,used);
sb.setLength(sb.length()-1);
used[i]=false;
}
}
public static List<Integer> allNumbers(List<Integer> numbers) {
final List<Integer> result = new ArrayList<Integer>();
allNumbers(0, numbers, result);
return result;
}
private static void allNumbers(int parent, List<Integer> numbers, List<Integer> result) {
for (int index = 0; index < numbers.size(); index++) {
final int current = numbers.get(index) + 10 * parent;
result.add(current);
final List<Integer> copy = new ArrayList<Integer>(numbers);
copy.remove(index);
allNumbers(current, copy, result);
}
}
public static void permutationAll(char [] ch, StringBuilder sb,int count, boolean [] used){
for (int i=0;i<ch.length;++i){
if (used[i]){
continue;
}
sb.append(ch[i]);
System.out.println(sb.toString());
used[i]=true;
permutationAll(ch,sb,count+1,used);
sb.setLength(sb.length()-1);
used[i]=false;
}
}
# include <stdio.h>
# include <conio.h>
void main()
{
int a[6],i;
printf("\n Enter the digits (1-9)");
for (i=0; i<3; i++)
{
scanf("%d",&a[i]);
a[i+3]=a[i];
}
printf("\n All possible numbers using given digits are \n");
for (i=0; i< 3; i=i+1)
{
printf("%d ",a[i]);
printf("%d%d ",a[i],a[i+1]);
printf("%d%d ",a[i],a[i+2]);
printf("%d%d%d ",a[i],a[i+1],a[i+2]);
printf("%d%d%d ",a[i],a[i+2],a[i+1]);
}
}
recursively generate all the combinations; put every result into a hash table; what end up in the hash table is the complete set of possible numbers of those 3 integers.
- syrus August 13, 2010