Interview Question Software Developers
Country: United States
Interview Type: In-Person
I use BFS to find the shorter path between m and n.
public class ConvertNumber {
private static class Paar {
int val;
int dist;
Paar(int v, int d) {
val = v;
dist = d;
}
}
int getMinOperation(int m, int n) {
if (m == n)
return 0;
if ((m < 0) && (n > 0))
return -1;
Queue<Paar> q = new LinkedList<>();
q.add(new Paar(m,0));
while (!q.isEmpty()) {
Paar current = q.poll();
Integer el = current.val;
if (el == n) {
return current.dist;
}
else {
if ((n >= 0) && (m >=0)) {
if (el - 1 >= 0)
q.add(new Paar(el - 1,current.dist + 1));
q.add(new Paar(el*2,current.dist + 1));
} else {
if (el-1 >= n)
q.add(new Paar(el-1,current.dist + 1));
if (el*2 >= n)
q.add(new Paar(el*2,current.dist + 1));
}
}
}
return - 1;
}
}
This solution has exponential time & space complexity (getting OutOfMemoryError when converting 42 to 733).
Please check out my solution that is O(logm) worst case.
What were the constraint for numbers m and n - positive, negative? what should be system logic if iti is impossible to convert one number to the other ?
Here is my solution . I use BFS to find the shorter path between m and n.
public class ConvertNumber {
private static class Paar {
int val;
int dist;
Paar(int v, int d) {
val = v;
dist = d;
}
}
int getMinOperation(int m, int n) {
if (m == n)
return 0;
if ((m < 0) && (n > 0))
return -1;
Queue<Paar> q = new LinkedList<>();
q.add(new Paar(m,0));
while (!q.isEmpty()) {
Paar current = q.poll();
Integer el = current.val;
if (el == n) {
return current.dist;
}
else {
if ((n >= 0) && (m >=0)) {
if (el - 1 >= 0)
q.add(new Paar(el - 1,current.dist + 1));
q.add(new Paar(el*2,current.dist + 1));
} else {
if (el-1 >= n)
q.add(new Paar(el-1,current.dist + 1));
if (el*2 >= n)
q.add(new Paar(el*2,current.dist + 1));
}
}
}
return - 1;
}
}
public class NumberConversion {
public static void main(String[] args) {
System.out.println(new NumberConversion().findShoretesRoute(10, 550));
}
public String findShoretesRoute(int num1, int num2) {
StringBuilder path = new StringBuilder();
if (num1 == num2 || num1 < 0 || num2 < 0) {
path.append("Invalid numbers. Both numbers should be positive integere and should not be equal.");
return path.toString();
}
path.append(num1);
int multiplication = 0;
int substraction = 0;
while (num1 != num2) {
if (num1 > num2) {
for (int i = num2; i < num1; i++) {
substraction++;
num1 -= 1;
}
} else {
multiplication++;
num1 *= 2;
}
}
return path.append(" x ( " + multiplication + " Times *2 ) + ( " + substraction + " Times -1 ) = " + num2)
.toString();
}
}
public class NumberConversion {
public static void main(String[] args) {
System.out.println(new NumberConversion().findShoretesRoute(10, 550));
}
public String findShoretesRoute(int num1, int num2) {
StringBuilder path = new StringBuilder();
if (num1 == num2 || num1 < 0 || num2 < 0) {
path.append("Invalid numbers. Both numbers should be positive integere and should not be equal.");
return path.toString();
}
path.append(num1);
int multiplication = 0;
int substraction = 0;
while (num1 != num2) {
if (num1 > num2) {
for (int i = num2; i < num1; i++) {
substraction++;
num1 -= 1;
}
} else {
multiplication++;
num1 *= 2;
}
}
return path.append(" x ( " + multiplication + " Times *2 ) + ( " + substraction + " Times -1 ) = " + num2)
.toString();
}
}
/**
* Given two numbers 'a' and 'b'. Convert 'a' to 'b' with minimum number of operations.
* The only possible operations are: "+1" and "*2".
* <p>
* Use BFS like search.
* <p>
* k - shortest path
* time: O(2^k)
* space: O(2^k)
*/
private static String findShortestTransformation(int value, int valueToReach) {
Deque<Map.Entry<Integer, String>> queue = new ArrayDeque<>();
queue.add(new AbstractMap.SimpleEntry<>(value, ""));
while (!queue.isEmpty()) {
Map.Entry<Integer, String> solution = queue.poll();
int solutionValue = solution.getKey();
String solutionRes = solution.getValue();
if (solutionValue == valueToReach) {
return solution.getValue();
}
queue.add(new AbstractMap.SimpleEntry<>(solutionValue - 1, solutionRes + " -1"));
if (solutionValue < valueToReach) {
queue.add(new AbstractMap.SimpleEntry<>(solutionValue * 2, solutionRes + " *2"));
}
}
return "";
}
/**
* Given two numbers 'a' and 'b'. Convert 'a' to 'b' with minimum number of operations.
* The only possible operations are: "+1" and "*2".
* <p>
* Use BFS like search.
* <p>
* k - shortest path
* time: O(2^k)
* space: O(2^k)
*/
private static String findShortestTransformation(int value, int valueToReach) {
Deque<Map.Entry<Integer, String>> queue = new ArrayDeque<>();
queue.add(new AbstractMap.SimpleEntry<>(value, ""));
while (!queue.isEmpty()) {
Map.Entry<Integer, String> solution = queue.poll();
int solutionValue = solution.getKey();
String solutionRes = solution.getValue();
if (solutionValue == valueToReach) {
return solution.getValue();
}
queue.add(new AbstractMap.SimpleEntry<>(solutionValue - 1, solutionRes + " -1"));
if (solutionValue < valueToReach) {
queue.add(new AbstractMap.SimpleEntry<>(solutionValue * 2, solutionRes + " *2"));
}
}
return "";
}
def get_minimum_operations(src, dst):
step = 0
operations = []
if src == dst:
return 0
if dst < src:
return src-dst
while dst > src:
if dst & 0x01:
step += 1
operations.append("-1")
dst = (dst+1) >> 1
operations.append("*2")
step += 1
for i in range(0, src-dst):
operations.append("-1")
return (((src - dst) + step), operations)
src = 38
dst = 100
output = ""
(steps, operations) = get_minimum_operations(src, dst)
print(steps)
try:
while operations:
i = operations.pop()
if i == "*2":
if output == "":
output += "(" + str(src) + "*2" + ")"
else:
output = "(" + output + "*2" + ")"
if i == "-1":
if output == "":
output += "(" + str(src) + "-1" + ")"
else:
output = "(" + output + "-1" + ")"
except IndexError:
pass
print(output)
Solution based on simple arithmetic.
import java.util.ArrayList; import java.util.Collections; public class ConvertWithOperations { public static int convert(int m, int n, ArrayList<String> path) { if (m == n) { return 0; } if (m > n) { // only way is to do -1 (m-n) times path.add(("'-1' "+(m-n)+" times")); return m-n; } if (m <= 0 && n > 0) { return -1; // not possible } if (n % 2 == 1) { // n is odd path.add(("'-1'")); return 1 + convert(m, n+1, path); } else { // n is even path.add(("'x2'")); return 1 + convert(m, n/2, path); } } public static void main(String[] args) { int m = 42; int n = 733; ArrayList<String> path = new ArrayList<String>(); System.out.println("# Operations: "+convert(m,n, path)); Collections.reverse(path); System.out.println("Operations: "+path); } }Prints:
- ikoryf January 15, 2016