# My solutions to a few Microsoft interview questions

Originally, 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

1. 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);
}

1. 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); }
}

1. 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



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 }