## Interview Question for Software Developers

• 0

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

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
return m-n;
}
if (m <= 0 && n > 0) {
return -1; // not possible
}
if (n % 2 == 1) { // n is odd
return 1 + convert(m, n+1, path);

} else { // n is even
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:

``````# Operations: 26
Operations: ['-1' 19 times, 'x2', 'x2', 'x2', 'x2', '-1', 'x2', '-1']``````

Comment hidden because of low score. Click to expand.
0

Worst case complexity is O(logn) :)

Comment hidden because of low score. Click to expand.
0

Worst case complexity is O(logn), I think

Comment hidden because of low score. Click to expand.
0

In your (m>n) case, would'nt it make sense to use *2 (after using -1 operation to get to -1) if n is a negative number say m = 42 and n= (-8). You code gives 50 operations of -1. Rather we can do 42 -1 and 3 (*2) total of 45 operations to get there

Comment hidden because of low score. Click to expand.
1
of 1 vote

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<>();
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;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

If the shortest path has length p. Then, BFS would take O(2^p) time and space.

I believe the length of shortest path is at most log(n) + m/2, for example when m = 2^k-1 and n = 2^k
In that case, BFS would take O(2^(m/2)) time and space, which is exponential.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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<>();
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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* 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<>();

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 "";
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* 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<>();

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 "";
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.