Microsoft Coding Questions
Microsoft Coding Questions and Answers
On this page, the 2023 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.
Microsoft Coding Questions and Answers 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 Questions | Time limit |
|---|---|
| Question 1 | 60 mins |
| Question 2 | 60 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.
import java.util.*;
public class Main
{
static boolean twoSum (int[]A, int val)
{
Set value = new HashSet ();
for (int a:A)
{
if (value.contains (val - a))
{
return true;
}
value.add (a);
}
return false;
}
public static void main (String[]args)
{
int[] test = new int[]{ 5, 7, 1, 2, 8, 4, 3 };
int[] value = new int[]{ 3, 20, 1, 2, 7 };
for (int i = 0; i < value.length; i++)
{
boolean output = twoSum (test, value[i]);
System.out.println ("Value(" + value[i] + ") = " + (output ? "true" : "false"));
}
}
}
def fun(arr, s):
result = []
for x in s:
found = False
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] + arr[j] == x:
found = True
break
if found:
break
result.append(found)
return result
# Example inputs
ar = [5, 7, 1, 2, 8, 4, 3]
s = [3, 20, 1, 2, 7]
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.
public class Main {
public static void zeroMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
public static void main(String[] args) {
int[][] matrix = {{0, 2, 3, 4},
{5, 6, 0, 8},
{0, 10, 11, 12},
{13, 14, 15, 16}};
System.out.println("Before zeroMatrix():");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
zeroMatrix(matrix);
System.out.println("After zeroMatrix():");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}
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
# Example input
r, c = 3, 4
arr = [ [1, 2, 3, 4],
[5, 6, 7, 8],
[9, 0, 11, 12]
]
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.
public class Main
{
private static Node head;
private static class Node
{
private int value;
private Node next;
Node (int value)
{
this.value = value;
}
}
public void add (Node node)
{
if (head == null)
{
head = node;
}
else
{
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = node;
}
}
public void print (Node printNode)
{
Node temp = printNode;
while (temp != null)
{
System.out.format ("%d ", temp.value);
temp = temp.next;
}
System.out.println ();
}
public static Node reverseList (Node node)
{
if (node == null || node.next == null)
{
return node;
}
Node remaining = reverseList (node.next);
node.next.next = node;
node.next = null;
return remaining;
}
// This function will do sum of numbers represented by linked list
public Node findSum (Node l1, Node l2)
{
int carry = 0;
Node newHead = null;
Node tempNodeForIteration = null;
int sum = 0;
int firstIter = 0;
while (l1 != null || l2 != null)
{
firstIter++;
sum = carry;
if (l1 != null)
{
sum = sum + l1.value;
l1 = l1.next;
}
if (l2 != null)
{
sum = sum + l2.value;
l2 = l2.next;
}
carry = sum / 10;
sum = sum % 10;
// Check if it first node for the result
if (firstIter == 1)
{
tempNodeForIteration = new Node (sum);
newHead = tempNodeForIteration;
}
else
{
Node tempSumNode = new Node (sum);
tempNodeForIteration.next = tempSumNode;
tempNodeForIteration = tempNodeForIteration.next;
}
}
if (carry != 0)
{
Node tempNode = new Node (carry);
tempNodeForIteration.next = tempNode;
}
return newHead;
}
public static void main (String[]args)
{
Main list = new Main ();
// Creating a linked list
Node head1 = new Node (8);
list.add (head1);
list.add (new Node (4));
list.add (new Node (7));
list.add (new Node (2));
list.add (new Node (6));
System.out.print ("Linked List 1: ");
list.print (head1);
head = null;
Node head2 = new Node (9);
list.add (head2);
list.add (new Node (0));
list.add (new Node (3));
list.add (new Node (6));
System.out.print ("Linked list 2: ");
list.print (head2);
// Reversing first linkedList
head1 = reverseList (head1);
//Reversing second linkedList
head2 = reverseList (head2);
Node result = list.findSum (head1, head2);
result = reverseList (result);
System.out.print ("Sum: ");
list.print (result);
}
}
More Microsoft Coding Questions and Answers
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.
import java.io.*;
import java.util.HashMap;
class Node {
int val;
Node next;
Node arbit;
// Constructor
Node(int x)
{
this.val = x;
this.next = null;
this.arbit = null;
}
}
class Main {
static Node cloneLinkedList(Node head)
{
// Mapping of old nodes with new ones
HashMap < Node, Node > mp = new HashMap < > ();
Node temp, nhead;
// Duplicate of the first node
temp = head;
nhead = new Node(temp.val);
mp.put(temp, nhead);
// duplicates of nodes are created using next pointer only
while (temp.next != null) {
nhead.next = new Node(temp.next.val);
temp = temp.next;
nhead = nhead.next;
mp.put(temp, nhead);
}
temp = head;
// Loop to clone the arbit pointers
while (temp != null) {
mp.get(temp).arbit = mp.get(temp.arbit);
temp = temp.next;
}
// Return the clone
return mp.get(head);
}
static void print(Node head)
{
System.out.print(head.val + "(" + head.arbit.val
+ ")");
head = head.next;
while (head != null) {
System.out.print(" -> " + head.val + "("
+ head.arbit.val + ")");
head = head.next;
}
System.out.println();
}
public static Node reverseList(Node node) {
if (node == null || node.next == null) {
return node;
}
Node remaining = reverseList(node.next);
node.next.next = node;
node.next = null;
return remaining;
}
public static void main(String[] args)
{
// Creating a linked list with random pointer
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head.arbit = head.next.next;
head.next.arbit = head;
head.next.next.arbit = head.next.next.next.next;
head.next.next.next.arbit = head.next.next;
head.next.next.next.next.arbit = head.next;
// Print the original list
System.out.println("The original linked list:");
print(head);
// Function call
Node sol = cloneLinkedList(head);
System.out.println("The cloned linked list:");
print(sol);
}
}
Question 5
Problem Statement :
Given the root of a binary tree, display the node values at each level.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main {
public static List < List < Integer > > levelOrder(TreeNode root) {
List < List < Integer > > result = new ArrayList < > ();
if (root == null) {
return result;
}
Queue < TreeNode > queue = new LinkedList < > ();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List < Integer > level = new ArrayList < > ();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(level);
}
return result;
}
public static void main(String[] args) {
// create a binary tree
TreeNode root = new TreeNode(5);
root.left = new TreeNode(9);
root.right = new TreeNode(12);
root.right.left = new TreeNode(25);
root.right.right = new TreeNode(7);
// print the level order traversal
List < List < Integer > > result = levelOrder(root);
for (List < Integer > level : result) {
System.out.println(level);
}
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
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.
import java.util.Queue;
import java.util.LinkedList;
public class Main {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode sibling;
TreeNode(int val) {
this.val = val;
}
public String toString() {
return Integer.toString(val);
}
}
static void connectSiblings(TreeNode root) {
if (root == null) {
return;
}
Queue < TreeNode > queue = new LinkedList < > ();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
TreeNode prev = null;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (prev != null) {
prev.sibling = node;
System.out.println(prev + " - > " + node);
}
prev = node;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
if (prev != null) {
prev.sibling = null;
System.out.println(prev + " - > null");
}
}
}
public static void main(String[] args) {
/*
* Create the following binary tree:
* 1
* / \
* 2 3
* / \ \
* 4 5 7
*/
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(7);
connectSiblings(root);
}
}
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.
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;
}
}
public 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));
}
}
class Tuple:
def __init__(self, x, y):
self.x = x
self.y = y
def findBuySellStockPrices(array):
if array == None or len(array) < 2:
return None
current_buy = array[0]
global_sell = array[1]
global_profit = global_sell - current_buy
current_profit = float('-inf')
for i in range(1, len(array)):
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]
result = Tuple(global_sell - global_profit, global_sell)
return result
array = [1, 2, 3, 4, 3, 2, 1, 2, 5]
result = findBuySellStockPrices(array)
print("Buy Price: {}, Sell Price: {}".format(result.x, result.y))
array2 = [8, 6, 5, 4, 3, 2, 1]
result = findBuySellStockPrices(array2)
print("Buy Price: {}, Sell Price: {}".format(result.x, result.y))
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,
import java.util.*;
public class Main {
public static List< Integer > findLargestZeroSumSequence(int[] arr) {
Map< Integer, Integer > map = new HashMap < > ();
int maxLen = 0, endIndex = -1, sumSoFar = 0;
map.put(0, -1);
for (int i = 0; i < arr.length; i++) {
sumSoFar += arr[i];
if (map.containsKey(sumSoFar)) {
int len = i - map.get(sumSoFar);
if (len > maxLen) {
maxLen = len;
endIndex = i;
}
} else {
map.put(sumSoFar, i);
}
}
List < Integer > result = new ArrayList < > ();
int startIndex = endIndex - maxLen + 1;
for (int i = startIndex; i <= endIndex; i++) {
result.add(arr[i]);
}
return result;
}
public static void main(String[] args) {
int[] arr = {4, 2, -3, 1, 6,-2,5,-3,1,2,4,-7};
List< Integer > result = findLargestZeroSumSequence(arr);
System.out.println(result);
}
}
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
# Example inputs: [1, 2, -2, 4, -4]
ar = [4, 2, -3, 1, 6,-2,5,-3,1,2,4,-7]
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.
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) {
StringBuilder sb = new StringBuilder();
int sum = 0;
for(int i=shifts.length-1; i >=0; i--){
sum = (sum + shifts[i])%26;
int ascii = 0;
char c = s.charAt(i);
ascii = (int)c + sum;
if(ascii > 'z'){
ascii = (ascii%123)+97;
sb.insert(0, (char)ascii);
}
else
sb.insert(0, (char)ascii);
}
return sb.toString();
}
}
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]
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");
}
}
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))
Login/Signup to comment