# My solutions to a few Microsoft interview questions

Written on June 17th, 2019 by @10000TBOriginally, there was an online post sharing microsoft interview questions. I was free at the time, and got interested and took some coding up some solutions.

The problems - https://leetcode.com/discuss/interview-question/310636/Microsoft-or-OA-2019-or-Reverse-String-and-Remove-Prime-Numbers-From-List

My solutions

**JAVA & Python - Short & concise solutions with explanations**

- Reverse string recursively During reversion, first char in string will become last one. Then if we have reversed version of the string (from 1 to last), then we know the result ! That is reverse(s[1:]) + s[0]. Base case is when it is empty string, in which case we simply return empty string.

*Python*

```
def reverse(s):
if not s: return s
return reverse(s[1:])+s[0]
```

*JAVA*

```
public static String reverse(String s) {
if (s==null || s.isEmpty()) { return s; }
return reverse(s.substring(1)) + s.charAt(0);
}
```

- Print number ( Assume positive number )
- right to left Every time, we print right most digit, and truncate it from the number. Doing so until we hit zero.

*Python*

```
def printdigits(n):
if n == 0: print '0'
while n > 0:
print n % 10
if n / 10 > 0: print "\n"
n /= 10
```

*JAVA*

```
public static void printDigits(int n) {
if (n==0) { System.out.println(n); }
while (n>0) {
System.out.println(n%10);
n /= 10;
}
}
```

- left to right We can pursue either of the two ways: 1) stacking up digits from right to left in a list and finally print out digits from left to right according to the list. 2) Or we recursively probe each digit from right to left, and start printing from deepest call upwards. That gives left to right order of all digits. Space complexity of both ways are O(n).

*Python*

```
def printdigits(n):
def doit(curr, n):
if 1 <= curr <= 9: print n if curr == n else curr
elif n > 9:
doit(curr/10, n)
print curr % 10
if n == 0: print 0
else: doit(n, n)
```

*JAVA*

```
private static void doit(int curr, int n) {
if (1<= curr && curr <=9){
if (curr==n) { System.out.println(n);}
else { System.out.println(curr); }
} else {
doit(curr/10, n);
System.out.println(curr%10);}
}
public static void printDigits(int n) {
if (n==0) { System.out.println(n); }
else { doit(n, n); }
}
```

- Remove prime numbers Do it recursively from end to beginning using the call stacks. Use a separate function to check each node’s value is prime or not.

*Python*

```
def isprime(n):
return all(n%i !=0 for i in xrange(2, math.sqrt(n)+1) ) if n > 0 else False
def remove(head):
if not head: return None
head.next = remove(head.next)
return head.next if isprime(head.val) else head
```

*JAVA*

```
private static boolean isPrime(int n) {
if (n==1 || n==2) { return true;}
else {
for(int i=2; i < Math.sqrt(n); i++) { if (n%i ==0) {return false;} }
return true;
}
}
public static void remove(ListNode head) {
if (head==null) { return None }
head.next = remove(head.next)
if isPrime(head.val) { return head.next } else { return head}
}
```

- Regarding using
**Sieve of Eratosthenes**algo to decide if a number is prime of or not. If interviewer clearly states that all values in the linked list are smaller than a certain upper bound say N, we can use SoE algorithm to find out all prime numbers that are smaller than N, then it does gives a lot of time boost overall (Note there is extra O(N) space overhead, and O(NloglogN) time overhead for SoE preprocessing). However, if upper bound of nodes’ values are not clear, then we can still use SoE, read it out how here on wikipedia: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. But for this interview, under time constraints, I favor simplicity.

(Also here - https://leetcode.com/discuss/interview-question/310636/Microsoft-or-OA-2019-or-Reverse-String-and-Remove-Prime-Numbers-From-List/289088)

Feel free to share!