CareerCup

lets say to find this we need a sort of back tracking mechanism.

start at least significant digit position and check if changing it makes it prime if so save that result in an array or vector(first try to change it to the same least significant digit of target). Else check the next significant digit and change it and so forth. If at any stage if we are not able to change any digit to arrive at a prime number then we have reached the end of road. so we backtrack to the previously saved value and start from there. We continue this until we change the orig number to target number.

Some thoughts.. Not complete though..

Assume a set S (hashset) which contains the list of all 4 digit prime numbers.
Now in N1 try to change last digit to match with N2. Check if the resultant number is prime. If yes repeat it for the remaining digits. If not, try with 2,3,4 placed digits. If the resultant number is not a prime for any of the digits, figure a prime number that can be obtained by changing only one digit of N1. Repeat the process.

Pseudo Code
char[] n1 = new char[4];
char[] n2 = new char[4];
while (n1 != n2) {
char[] tmp = new char[4];
tmp[0] = n1[0];
tmp[1] = n1[1];
tmp[2] = n1[2];
tmp[3] = n2[3];

if (isTmpPrime(tmp)) {
n1 = tmp;
} else {
tmp[2] = n2[2];
tmp[3] = n1[3];
if (isTmpPrime(tmp)) {
n1 = tmp;
} else {
tmp[1] = n2[1];
tmp[2] = n1[2];
if (isTmpPrime(tmp)) {
n1 = tmp;
} else {
tmp[0] = n2[0];
tmp[1] = n1[1];
if (isTmpPrime(tmp)) {
n1 = tmp;
} else {
n1 = getNextPrime(n1);
}
}
}

}
}

My solution was...

Prepare a graph structure where each node prepresents a 4 digit prime number and each edge represents one digit change.
Assume such graph is avaiable.

Then do BFS from N1 to find N2... no of edges btw N1 and N2 is the required digit changes.

Hi Arang, what are they asking in phone interview? how many rounds do they take in face to face?

Hi Anarg
Did they ask only Data Structure stuffs or other also such as os, puzzles, unix etc.
I have heard that AMAZON asks a lot of questions on UNIX too..

Can we use Edit distance algorithm right?

public class ConvertPrime {

/* what we need is a hashmap which stores the index with the changed number
each time we call the function we check if the value is there in the hashmap
each time we check if the value is present , and after replacing the number
* if the number becomes prime then we replace the value of that
* else we just keep on calling that function for the next value in hashmap
*
*/
Map map = new HashMap<Integer,Integer>();
public void convertToPrime(int [] a,int [] b){

int index=0;
//so here you populate the map for which the indexes differ
while(!isEqual(a,b) || map.isEmpty()){
if(a[index]!=b[index])map.put(new Integer(index),new Integer(a[index]));
index++;

}

Iterator it = map.entrySet().iterator();

while(!map.isEmpty()){
// while map is not empty
if(it.hasNext()) {
Map.Entry entry = (Map.Entry) it.next();
Integer key = (Integer) entry.getKey();
Integer value = (Integer) entry.getValue();
// check if the key value pair if placed in the index i
// get you a prime number
int [] temp = new int[b.length];
temp=b;
temp[key]=value; // replace the temp array created and check if the temp is a prime
boolean isprime= isPrime(temp);
if(isprime){
// if the number is prime then
// delete the key value pair from hashmap

map.remove(key);
}
}else it = map.entrySet().iterator();
// else you again interate through the map.till the map is not empty

}


}

private boolean isPrime(int [] array){

// implementation independent
return false;
}
}

I was thinking of a simple solution. We have to just calculate the number of digit changes....... So

int change = 0;
for(i=0;i<4;i++)
{
x = N1%10;
y = N2%10;

if(x != y )
{
change ++;
}

}

return change;