Microsoft Coding Questions

Microsoft coding questions

Microsoft Coding Questions and Answers

On this page, the 2022–23 Microsoft Coding Questions and Answers are discussed. One of the most crucial rounds for landing a job at Microsoft is the coding round.

You can use this section to analyse the level of complexity of the Microsoft problem. Understanding the level of complexity and question format for the coding phase is made easier by practising Microsoft coding questions and answers.

The Microsoft Coding Round questions and their solutions in different languages can be found below. For a good grade, you must be prepared for the Microsoft code problems.

Coding Test Format

  • Coding round contains 2 questions that will have to be attended in 2 hours.
  • Each questions have different difficulty level.
  • There is one Easy problem based on Algorithm , Aptitude and Data structures.
  • One is of Hard difficulty level, and usually based on Dynamic Programming/Greedy Algorithm
No. Of QuestionsTime limit
Question 160 mins
Question 260 mins

Question 1

Problem Statement:

Given an array of integers and a value, determine if there are any two integers in the array whose sum is equal to the given value.

Run
import java.util.*;
public Class Main {
  static boolean twoSum(int[] A, int val) {
    Set val = new HashSet();
    for (int a : A) {
      if (val.contains(val - a)) {
        return true;
      }

      val.add(a);
    }
    return false;
  }

  public static void main(String[] args) {
    int[] v = new int[] {5, 7, 1, 2, 8, 4, 3};
    int[] test = new int[] {3, 20, 1, 2, 7};
    
    for(int i = 0; i < test.length; i++){
    boolean output = twoSum(v, test[i]);
    System.out.println("twoSum(v, " + test[i] + ") = " + (output ? "true" : "false"));
    }
  }
}

Run
def fun(arr, s):
   for i in arr:
       if s-i in arr:
           return True
   return False


ar = list(map(int, input().split()))
s = int(input())
print(fun(sorted(ar, s)))

Question 2

Problem Statement:

Given a two-dimensional array, if any element within is zero, make its whole row and column zero.

 

Run
import java.util.*;
import java.lang.*;
import java.io.*;

Class Main{
  static void make_zeroes(int[][] matrix) {
    if (matrix.length == 0) {
      return;
    }

    Set zero_rows = new HashSet();
    Set zero_cols = new HashSet();

    int rows = matrix.length;
    int cols = matrix[0].length;

    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        if (matrix[i][j] == 0) {
          if (!zero_rows.contains(i)) {
            zero_rows.add(i);  
          }

          if (!zero_cols.contains(j)) {
            zero_cols.add(j);  
          }
        }
      }
    }

    for (int r : zero_rows) {
      for (int c = 0; c < cols; ++c) {
        matrix[r][c] = 0;
      }
    }

    for (int c : zero_cols) {
      for (int r = 0; r < rows; ++r) {
        matrix[r][c] = 0;
      }
    }
  }
  static int[][] create_random_matrix(int rows, int cols) {
    int[][] v = new int[rows][cols];

    for(int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        int t = new Random().nextInt() % 100;
        v[i][j] = t + 1;
        if (Math.abs(t) % 100 <= 5) {
          v[i][j] = 0;
        }
      }
    }
    return v;
  }

  static void print_matrix(int[][] m) {
    System.out.println();
    for (int i = 0; i < m.length; ++i) {
      for (int j = 0; j < m[i].length; ++j) {
        System.out.print(m[i][j]);
        System.out.print("\t");
      }
      System.out.println();
    }
  }
  static boolean is_row_or_col_zero(int[][] matrix, int r, int c) {
    int rows = matrix.length;
    int cols = 0;
    if (rows > 0) {
      cols = matrix[0].length;
    }

    for (int i = 0; i < cols; ++i) {
      if (matrix[r][i] == 0) {
        return true;
      }
    }

    for(int i = 0; i < rows; ++i) {
      if (matrix[i][c] == 0) {
        return true;
      }
    }

    return false;
  }

  static void verify(int[][] matrix) {
    int[][] mat_copy = new int[matrix.length][];
    for (int i = 0; i < matrix.length; ++i) {
      mat_copy[i] = matrix[i].clone();
    }

    make_zeroes(matrix);

    int rows = matrix.length;
    int cols = 0;
    if (rows > 0) {
      cols = matrix[0].length;
    }

    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        if (is_row_or_col_zero(mat_copy, i, j)) {
          assert(matrix[i][j] == 0);
        }
      }
    }
  }


  public static void main(String[] args) {
    int[][] matrix = {
      {1, 5, 45, 0, 81},
      {6, 7, 2, 82, 8},
      {20, 22, 49, 5, 5},
      {0, 23, 50, 4, 92}
    };
    print_matrix(matrix);
    verify(matrix);
    print_matrix(matrix);

    matrix = create_random_matrix(5, 5);
    print_matrix(matrix);
    verify(matrix);
    print_matrix(matrix);

    for (int i = 0; i < 25; i++) {
      for (int j = 0; j < 25; j++) {
        matrix = create_random_matrix(i, j);
        verify(matrix);
      }
    }
  }
}
Run
def fun():
   ra = []
   ca = []
   for i in range(r):
       if 0 in arr[i]:
           if arr[i].count(0) == 1:
               ra.append(i)
               ca.append(arr[i].index(0))
           else:
               for j in range(c):
                   if arr[i][j] == 0:
                       ra.append(i)
                       ca.append(j)
   print(ra, ca)
   for i in range(len(ra)):
       fun2(ra[i], ca[i])


def fun2(rr, cc):
   for i in range(c):
       arr[rr][i] = 0
   for i in range(r):
       arr[i][cc] = 0


r, c = map(int, input("Enter number of Row's & column: ").split())
arr = []
for i in range(r):
   arr.append(list(map(int, input(f"Enter Column {i + 1}: ").split())))
print(arr)
fun()
for i in arr:
   print(i)

Question 3

Problem Statement:

Given the head pointers of two linked lists where each linked list represents an integer number (each node is a digit), add them and return the resulting linked list.

Run
class Main{
  static LinkedListNode add_integers(
      LinkedListNode integer1, 
      LinkedListNode integer2) {
  
    LinkedListNode result = null;
    LinkedListNode last = null;
    int carry = 0;

    while (
        integer1 != null ||
        integer2 != null ||
        carry > 0) {
    
      int first = (integer1 == null ? 0 : integer1.data);
      int second = (integer2 == null ? 0 : integer2.data);
      int sum = first + second + carry;
      LinkedListNode pNew = new LinkedListNode(sum % 10);
      carry = sum / 10;
      if (result == null) {
        result = pNew;
      } else {
        last.next = pNew;
      }

      last = pNew;
      if (integer1 != null) {
        integer1 = integer1.next;
      }
      if (integer2 != null) {
        integer2 = integer2.next;
      }
    }
    return result;
  }
  public static void main(String[] args) {

    int[] v1 = new int[]{1, 2, 3}; // 321
    int[] v2 = new int[]{1, 2}; // 21
  
    LinkedListNode first = LinkedList.create_linked_list(v1);
    LinkedListNode second = LinkedList.create_linked_list(v2);

    // sum should be 321 + 21 = 342 => 2->4->3
    LinkedListNode result = add_integers(first, second);
    int[] r = new int[]{2, 4, 3}; // 342
    LinkedListNode expected = LinkedList.create_linked_list(r);
    System.out.println(LinkedList.is_equal(result, expected));

    System.out.printf("\nFirst:");
    LinkedList.display(first);
    System.out.printf("\nSecond:");
    LinkedList.display(second);
    System.out.printf("\nResult:");
    LinkedList.display(result);

    result = add_integers(first, null);
    System.out.println(LinkedList.is_equal(result, first));

    result = add_integers(null, second);
    System.out.println(LinkedList.is_equal(result, second));

}
} 

Question 4

Problem statement: You are given a linked list where the node has two pointers. The first is the regular ‘next’ pointer. The second pointer is called ‘arbitrary_pointer’ and it can point to any node in the linked list.

Your job is to write code to make a deep copy of the given linked list. Here, deep copy means that any operations on the original list (inserting, modifying and removing) should not affect the copied list.

Run
class Main{
  public static LinkedListNode deep_copy_arbitrary_pointer(
        LinkedListNode head) {

      if (head == null) {
        return null;
      } 

      LinkedListNode current = head;
      LinkedListNode new_head = null;
      LinkedListNode new_prev = null;
      Hashtable map = 
        new Hashtable();

      // create copy of the linked list, recording the corresponding
      // nodes in hashmap without updating arbitrary pointer
      while (current != null) {
        LinkedListNode new_node = new LinkedListNode(
          current.data);

        new_node.arbitrary_pointer = current.arbitrary_pointer;

        if (new_prev != null) {
          new_prev.next = new_node;
        }
        else {
          new_head = new_node;
        }

        map.put(current,new_node);

        new_prev = new_node;
        current = current.next;
      }

      LinkedListNode new_current = new_head;

      // updating arbitrary_pointer
      while (new_current != null) {
        if (new_current.arbitrary_pointer != null) {
          LinkedListNode node = 
            map.get(new_current.arbitrary_pointer);

          new_current.arbitrary_pointer = node;
        }

        new_current = new_current.next;
      }

      return new_head;
    }
   
    public static void main(String[] args) {
      LinkedListNode node3 = new LinkedListNode(
        3, null, null);
      LinkedListNode node2 = new LinkedListNode(
        2, node3, null);
      LinkedListNode node1 = new LinkedListNode(
        1, node2, node3);
      LinkedListNode list_head = new LinkedListNode(
        0, node1, node2);

      LinkedListNode list_head_2 = 
      deep_copy_arbitrary_pointer(list_head);

      System.out.print("Original: ");
      LinkedList.display(list_head);

      System.out.print("Copied: ");
      LinkedList.display(list_head_2);
    } 
} 

 Question 5

Problem Statement :

Given the root of a binary tree, display the node values at each level.

Run
class Main{
    // Using two queues
  public static void level_order_traversal_1(
      BinaryTreeNode root) {

    if (root == null) {
      return;
    }
  
    ArrayList> queues = 
      new ArrayList>();

    queues.add(new ArrayDeque());
    queues.add(new ArrayDeque());

    Queue current_queue = queues.get(0);
    Queue next_queue = queues.get(1);

    current_queue.add(root);
    int level_number = 0;

    while (!current_queue.isEmpty()) {
      BinaryTreeNode temp = current_queue.poll();
      System.out.print(temp.data + ",");

      if (temp.left != null) {
        next_queue.add(temp.left);
      }

      if (temp.right != null) {
        next_queue.add(temp.right);
      }

      if (current_queue.isEmpty()) {
        System.out.println();
        ++level_number;
        current_queue = queues.get(level_number % 2);
        next_queue = queues.get((level_number + 1) % 2);
      }
    }
    System.out.println();
  }
  public static void main(String[] argv) {

    List input = new ArrayList();
    input.add(100);input.add(50);input.add(200);input.add(25);input.add(75);input.add(350);
    BinaryTreeNode root = BinaryTree.create_BST(input);
    level_order_traversal_1(root);
    System.out.println();


    System.out.print("Inorder = ");
    BinaryTree.display_inorder(root);

  }
}  

Question 6

Problem Statement:

Connect the sibling pointer to the next node in the same level. The last node in each level should point to the first node of the next level in the tree.

Run
import java.util.*;
public class Main{
  public static void populate_sibling_pointers(BinaryTreeNode root) {
    if(root == null)
      return;

    BinaryTreeNode current = root;
    BinaryTreeNode last = root;

    while(current != null) {
      if(current.left != null) {
        last.next = current.left;
        last = current.left;
      }

      if(current.right != null){
        last.next = current.right;
        last = current.right;
      }
    
      last.next = null;
      current = current.next;
    }
  }
  public static List get_level_order_traversal_with_sibling(BinaryTreeNode root)
  {
    List l = new ArrayList();
    while(root != null) {
      l.add(root.data);
      // System.out.print(root.data + ", ");
      root = root.next;
    }
    return l;
  }

  public static void main(String[] args) {
    
    List input = new ArrayList();
    input.add(100);input.add(25);input.add(75);input.add(15);input.add(350);input.add(300);input.add(10);
    input.add(50);input.add(200);input.add(400);input.add(325);input.add(375);
    BinaryTreeNode root = BinaryTree.create_BST(input);

    BinaryTree.display_level_order(root);
    populate_sibling_pointers(root);
    
    System.out.println("Root -> next: "+ root.next.data); //25
    System.out.println("Root->right->left->next: "+ root.right.left.next.data); //400
    System.out.println("Root->right->right->next: "+ root.right.right.next.data); //10
    System.out.println("Root->right->right->left->next: "+ root.right.right.left.next); //None

    List l1 = BinaryTree.get_level_order(root);
    List l2 = get_level_order_traversal_with_sibling(root);
    System.out.println("Connected? = "+ Boolean.toString(ListUtil.is_equal(l1, l2)));
    System.out.println();
    ListUtil.print(l1);
  }
}  


Question 7

Problem Statement:

Given a list of daily stock prices (integers for simplicity), return the buy and sell prices for making the maximum profit. You need to maximize the single buy/sell profit. If you can’t make any profit, try to minimize the loss.

 

Run
import java.util.*;
import java.lang.*;
import java.io.*;

class Tuple<X, Y> {             
  public X x; 
  public Y y; 

  public Tuple(X x, Y y) { 
    this.x = x; 
    this.y = y; 
  } 
}

Class Main{
  public static Tuple findBuySellStockPrices(int[] array) {
    if(array == null || array.length < 2) {
        return null;
      }

    int current_buy = array[0];
    int global_sell = array[1];
    int global_profit = global_sell - current_buy;

    int current_profit = Integer.MIN_VALUE;
  
    for(int i=1; i<array.length; i++) { current_profit = array[i] - current_buy; if(current_profit > global_profit) {
        global_profit = current_profit;
        global_sell = array[i];
      }

      if(current_buy > array[i]) {
        current_buy = array[i];
      }
    }

    Tuple<Integer, Integer> result = 
      new Tuple<Integer, Integer>(global_sell - global_profit, global_sell);

    return result;
  }
   public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 3, 2, 1, 2, 5};
        Tuple result = null;
        result = findBuySellStockPrices(array);
        System.out.println(String.format("Buy Price: %d, Sell Price: %d", result.x, result.y));

        int[] array2 = {8, 6, 5, 4, 3, 2, 1};
        result = findBuySellStockPrices(array2);
        System.out.println(String.format("Buy Price: %d, Sell Price: %d", result.x, result.y));

    }
}  

Run
def fun():
   ra = []
   ca = []
   for i in range(r):
       if 0 in arr[i]:
           if arr[i].count(0) == 1:
               ra.append(i)
               ca.append(arr[i].index(0))
           else:
               for j in range(c):
                   if arr[i][j] == 0:
                       ra.append(i)
                       ca.append(j)
   print(ra, ca)
   for i in range(len(ra)):
       fun2(ra[i], ca[i])


def fun2(rr, cc):
   for i in range(c):
       arr[rr][i] = 0
   for i in range(r):
       arr[i][cc] = 0


r, c = map(int, input("Enter number of Row's & column: ").split())
arr = []
for i in range(r):
   arr.append(list(map(int, input(f"Enter Column {i + 1}: ").split())))
print(arr)
fun()
for i in arr:
   print(i)

Question 8

Problem Statement:

Find the largest continuous sequence in an array which sums to zero.
Example:

Input: {1 ,2 ,-2 ,4 ,-4}
Output: {2 ,-2 ,4 ,-4}


NOTE : If there are multiple correct answers, return the sequence which occurs first in the array,

Run
import java.util.*;


public class Solution {
    
    public static void main(String[] args){
        ArrayList A = new ArrayList<>();
        A.add(1);
        A.add(2);
        A.add(-2);
        A.add(4);
        A.add(-4);
        ArrayList ans = lszero(A);
        System.out.println(ans);
    }
    public static ArrayList lszero(ArrayList A) {
        ArrayList sumList = new ArrayList<>();
        Map map = new HashMap<>();
        ArrayList result = new ArrayList();
        
        map.put(0,-1);
        
        int start = -1;
        int end = -1;
        int sum = 0;
        int maxLen = -1;
        
        for (int i=0;i= 0 && end >= 0) {
            for(int i = start; i <= end; i++) {
                result.add(A.get(i));
            }
        }
        
        return result;
    }
}

Run
def fun(arr, l):
   ml = 0
   ans = []
   for i in range(l - 1):
       for j in range(i, l):
           if sum(arr[i:j + 1]) == 0:
               ans.append(arr[i:j + 1])
               ml = max(ml, j - i + 1)
   for i in ans:
       if len(i) == ml:
           return i


ar = list(map(int, input().split()))
print(fun(ar, len(ar)))

Question 9

Problem statement: Shifting Letters says that we have given a string s and an array shifts.

Now for each shifts[i] = x, we want to shift the first i + 1 letters of s, x times. We have to return the final string after all shifts are applied.

Example 1:

Input: s = “abc”, shifts = [3,5,9]
Output:”rpl”
Explanation:We start with “abc”.

  • After Shifting the first 1 letter of s by 3, we have “dbc”.
  • After shifting the first 2 letters of s by 5, we have “igc”.
  • After shifting the first 3 letters of s by 9, we have “rpl”.
  • Hence “rpl” is our final answer.

Example 2:

Input: s = “aaa”, shifts = [1,2,3]
Output:”gfd”

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.
  • shifts.length == s.length
  • 0 <= shifts[i] <= 109

Approach

We have to calculate how many times the i-th character is shifted. So just calculate the number of shifts on each position, by shifts[i] += shift[i+1]. We will do the task in reverse order. We have to maintain a  reverse prefix sum of the shift array and this will be equal to the number of shifts for each character. One thing we should focus on is that if we found that our character ASCII score exceeds the value of the ASCII score of ‘z’ we should start counting from ‘a.

Run
class Main {
    
    public static void main(String[] args){
        String s ="aaa";
        int[] shifts = new int[]{1,2,3};
        String a = shiftingLetters(s,shifts);
        System.out.println(a);
    }
    public static String shiftingLetters(String s, int[] shifts) {
        int i,n=shifts.length;
        
        char[] str = s.toCharArray();
        for(i=n-1;i>=0;i--)
        {  if(i+125)
            {
                ind=ind-26;
            }               
            str[i] = (char)('a'+ind);
        }
        
         return new String(str);
    }
}
Run
def fun(arr, ss):
   for i in range(len(arr)):
       s = sum(ss[i:])
       arr[i] = chr(((ord(arr[i]) - 97 + s) % 26) + 97)
   return ''.join(arr)


s = input()
shifts = list(map(int, input().split()))
print(fun(list(s), shifts))

 Question 10

Problem Statement :

Find the longest increasing subsequence of a given array of integers, A. In other words, find a subsequence of an array in which the subsequence’s elements are in strictly increasing order, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. In this case, we only care about the length of the longest increasing subsequence.

Input Format:

  • The first and the only argument is an integer array A.

Output Format:

  • Return an integer representing the length of the longest increasing subsequence.

Constraints:

  • 1 <= length(A) <= 2500
  • 1 <= A[i] <= 2000

Example :

Input : A = [1, 2, 1, 5]
Output : 3
Explanation :The sequence : [1, 2, 5]

 

Input :A = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
Output : 6
Explanation : The sequence : [0, 2, 6, 9, 13, 15] or [0, 4, 6, 9, 11, 15] or [0, 4, 6, 9, 13, 15]

Run
class Main{
	static int max_ref;
	static int _lis(int arr[], int n)
	{
		// base case
		if (n == 1)
			return 1;
		int res, max_ending_here = 1;
		for (int i = 1; i < n; i++) {
			res = _lis(arr, i);
			if (arr[i - 1] < arr[n - 1]
				&& res + 1 > max_ending_here)
				max_ending_here = res + 1;
		}
		if (max_ref < max_ending_here)
			max_ref = max_ending_here;
		return max_ending_here;
	}
	static int lis(int arr[], int n)
	{
		max_ref = 1;
		_lis(arr, n);
		return max_ref;
	}
	public static void main(String args[])
	{
		int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
		int n = arr.length;
		System.out.println("Length of lis is " + lis(arr, n)
						+ "\n");
	}
}
Run
def lis(arr, n):
   global max_ref
   if n == 1:
       return 1
   max_ending_here = 1
   for i in range(1, n):
       res = lis(arr, i)
       if arr[i - 1] < arr[n - 1] and res + 1 > max_ending_here:
           max_ending_here = res + 1
       if max_ref < max_ending_here:
           max_ref = max_ending_here
   return max_ending_here


arr = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
max_ref = 1
n = len(arr)
print("Length of list is", lis(arr, n))