In 1975, Microsoft was established in New Mexico, and migrated to Washington in 1979, where it flourished into remarkable global cooperation. At its core, Microsoft believes that having a diverse work environment contributes to the development of quality products and services for its clients and consumers. It offers a plethora of scholarship opportunities, fulltime careers, and internships that will help you develop your abilities. To be considered for a position with this large IT corporation, applicants must pass many interview rounds. To help you get there, we've compiled a list of top Microsoft interview questions in 2022.
Microsoft Core Competencies
 Collaboration: Effective communication both inside and between teams.
 Drive for results: By adhering determinedly to commitments, always pursuing significant obstacles, and keeping oneself and others responsible.
 Customer focus: The objective of Microsoft is to enable every individual and every business to achieve greater success.
 Influencing for Impact: Persuading and influencing people successfully via good communication.
 Judgment: Thoroughly exploring difficult challenges and making knowledgebased judgments via business acumen.
 Adaptability: Capacity to react quickly to confusing and unpredictable events or challenges.
Microsoft Interview Process

Apply for Microsoft
It is always recommended that you submit your application via the official Microsoft Careers page for the position you seek. There are several job hunting sites available, including LinkedIn, Indeed, and Glassdoor. It is also recommended that you network with current Microsoft workers in order to get employment references. If you are found to be a good match for the position that is being advertised, you will be called for an online interview with the recruiter.

Online Round
Microsoft is attentively following the directives of Covid19 and working to ensure the safety of job applicants and employees. For the time being, they have moved all inperson interviews throughout the world to be conducted digitally. Every interview in this stage is conducted through Teams and any other platform available to the participants.
Your recruiter will let you know about the platform and provide you with information about the interview and guidelines through email. Be prepared to illustrate how you fulfill the job requirements by providing concrete instances from your history or suggestions for how you would do a certain task. In your interview, be careful to explain how your previous work experience will help you succeed in the position that you are applying for. In order to be considered for some positions, you may be required to provide a coding sample, a design portfolio, or other evidence of your abilities. The behavioral questions are also included in this round.

Technical Round
In technical interviews, candidates demonstrate their problemsolving skills and technological expertise. For this test, you will be judged on a variety of factors, including your ability to use technical ideas and methodologies to solve issues, as well as your problemsolving strategy. Other competencybased and resumerelated questions will be asked during the interview as well. Depending on the position you're seeking and your level of expertise, you may encounter a series of technical rounds throughout the application process.

After the Interview
Inquire with the Prospective Employer or Recruiter at the conclusion of the interview session as to when you may probably hear back about the following stages or a hiring decision. When the recruiting process is complete, your Recruiter will contact you to discuss the results of your interviews and provide you with feedback. Recruiters like receiving thankyou emails, which they will pass on to the Prospective Employer and interviewers.
Interview Process

Recruiter Connect
If you want to get a job at Microsoft, it's essential to have a strong LinkedIn profile. Connecting with current Microsoft workers is also a good way to receive employment leads. The individual may also apply for a job via the company's website.

Interview Rounds
The first step in the interview process is a DS/Algobased screening interview. The more technical aspects of DS/Algo and system design are emphasized in the later rounds.

After Interviews
The candidate's performance is evaluated in light of their previous interviews, and a decision is made. The hiring manager sits together with all of the panelists to discuss and argue the applicant evaluations.

Hired
There is a formal offer letter created by the recruiters whenever you and the team are ready to begin and you are officially hired!
Microsoft Interview Rounds

Screening Interview (1 Round)
To determine whether or not the applicant is a good match for Microsoft, a telephone interview may be undertaken. It's possible that a coding exam will take the place of an interview. A 3045minute session may be expected to address 23 DS/Algo issues.

Onsite Interviews (45 Rounds)
There will be a series of interviews. Some rounds are DS/Algobased, and others are system designbased. Array/Strings/LinkedList questions are often asked by Microsoft. Hence candidates are suggested to focus on these areas. Finding the best answer is essential in this case. With regards to designing complex structures like Gmail, YouTube, and Uber, the applicant is tested in the design rounds.
Microsoft Interview Questions and Answers
Let us start with generic behavioral Microsoft interview questions and answers.
Microsoft Behavioral Interview Questions
1. Tell me anything about yourself.
If you've applied for a position at Microsoft, it's critical that you concentrate on your talents, abilities, traits, and experiences. We all know that Microsoft is a very successful company. Thus, displaying your excitement and positivism is strongly suggested. There should be examples in the answer. You'll be able to show that you're an asset to a group that already has a lot of experience.
For example:
“I am really determined. And a goaloriented individual who is a firm believer that substantial progress can be made at an enterprise like Microsoft only if everyone on the team works in unison.”
You've spoken well about the organization, but you've also emphasized your own qualities, which are goaloriented and strongly determined. All of your efforts, when combined with those of the team in which you are to be employed, will always provide you with a path inside the organization.
“Through my prior work experiences, I have gained knowledge and understanding of the capabilities that are a great match for the job description. The fact that my past supervisors have given me positive feedback on my performance demonstrates that I am an excellent candidate who is eager to contribute to a wellestablished and highachieving firm such as Microsoft.”
Additionally, you have said that your prior company's experiences have been emphasized and appreciated by your management. As a result, you are a qualified applicant. Additionally, you might discuss your own experiences and ambitions.
2. Why are you interested in working with Microsoft?
This can help you come up with the greatest response for the interviewer if you have done your homework ahead of time. Do your best to provide a thoughtful response that stands out as a real contribution to the discussion.
For example:
“As a Microsoft employee, I'll have a lot of advantages. There are many reasons why working for Microsoft for the long term will have a significant impact on my career. Because of Microsoft's long and successful history, I feel motivated to contribute to its future successes. In addition, the uniqueness of Microsoft's products will always allow me to learn something new and apply it to my future in order to reach new heights.”
Now, you could be thinking that I'm being really selfcentered right now. To be fully honest, this is exactly what the employer is looking for in a candidate.
3. Which three characteristics do you believe are required to work at Microsoft?
There is no onesizefitsall solution to this question. It's as simple as doing a lot of study about Microsoft. Do not forget to note down three key values or points from your investigation. It doesn't matter what you say, so long as you convey it in a proper manner to your potential employer.
For example:
“A good team member with a strong commitment to the project is essential, as I discovered throughout my research. They are hired to understand and assist their coworkers and to treat everyone with the same level of dignity and respect. As a firm, Microsoft's principles are based on treating everyone in the workplace as an equal. A person must now have and comprehend this to be able to put it into practice in their employment if they are recruited. With a constructive attitude and cooperation with colleagues, everyone's suggestions should be welcomed and taken into consideration. Microsoft's success may be attributed in large part to its commitment to creating a positive work environment.”
Here, you've explained why Microsoft is so popular and how they've gotten to where they are. In this manner, you've demonstrated three positive aspects of Microsoft and explained that you have some of these attributes yourself, making you a suitable candidate for employment.
4. Describe a time at work when you took a risk
As a general rule, it's best to avoid jumping right into a dire predicament. A major red signal is when individuals begin their responses to this question by painting a negative picture. That means you're disclosing your weaknesses to the hiring manager, something you don't want. Take stock of your own unique set of skills and abilities, and figure out what best suits you.
For example:
“While I was working on a project with a tight deadline and a problem that needed to be fixed by one of my coworkers, I worked on weekends to grasp the requirements and comprehend them to fulfill the project deadline. Not only was I able to complete the assignment within the specified time, but I also avoided putting my teammate in danger and averting a significant loss for the organization.”
Here you have demonstrated your own personal strengths in comparison to those of your coworkers. Furthermore, you have said that this has had a significant positive impact on the organization. You've answered the question directly and without mentioning any bad scenarios.
Microsoft Technical Interview Questions and Answers
Now, let's have a look at some of the technical Microsoft interview questions and answers.
1. Write a program that prints the k largest elements in an unordered array efficiently.
There are three main approaches to solving this problem.
Approach 1  Modified bubble sort method
Time Complexity: O(n*k)
1) Change Bubble Sort so that the outer loop is run at least k times.
2) Print the array's final k elements acquired in step 1.
O(n*k) Time Complexity
Approach 2  Storing the K largest elements from arr[0..n1]
Time Complexity: O((nk)*k)
1) Create a temp[0..k1] array with the first k items.
2) Find the smallest element in temp[ ] and assign it to the min variable.
3) arr[k] to arr[n1] for each element x, remove min from temp[] and insert x if x is greater than the min.
4) Next, calculate the new min from temp[].
4) Print the final k items of temp[].
Approach 3  First, sort the elements and then printing
Time Complexity: O(n*log(n)+k)
1) In O(n*log(n)), sort the components in descending order.
2) Print the sorted array’s first k numbers.
Program:
#include <bits/stdc++.h>
using namespace std;
void kLarge(int ar[], int n, int k)
{
sort(ar, ar + n, greater<int>());
for (int j = 0; j < k; j++)
cout << ar[j] << " ";
}
int main()
{
int ar[] = { 90, 33, 89, 7, 23, 0, 100 };
int n = sizeof(ar) / sizeof(ar[0]);
int k = 3;
kLarge(ar, n, k);
}
Output:
100 90 89
2. Define objects and classes in C++?
A class is a data type with member functions and data members that is defined by the user. The data members are the variables in the data, and the member functions are the functions that operate on them. A class's instance is an object. An object can be referred to as a variable of a class because it is a userdefined data type.
Example:
class C //defining a class
{
private:
int data; //data members
public: void funcName() //member function
{
}
};
3. Write a function returning true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2 given an array of numbers.
Program
class Main {
static boolean isTriplet(int arr[], int n)
{
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int x = arr[i] * arr[i], y = arr[j] * arr[j], z = arr[k] * arr[k];
if (x == y + z  y == x + z  z == x + y)
return true;
}
}
}
return false;
}
public static void main(String[] args)
{
int arr[] = { 80, 11, 40, 26, 52};
int arr_size = arr.length;
if (isTriplet(arr, arr_size) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
Output
No
Q4: How does operator overloading work?
To conduct operations on userdefined data types, operator overloading is a critical component. The default meaning of operators such as +, , *, /, =, and so on can be changed using operator overloading.
Example:
#include <iostream>
using namespace std;
class Calculate {
public:
static int addition(int a,int b){
return a + b;
}
static int addition(int a, int b, int c)
{
return a + b + c;
}
};
int main(void) {
Calculate C; //object declaration
cout<<C.addition(11, 23)<<endl;
cout<<C.addition(23, 8, 93);
return 0;
}
Output:
34
124
5. In C++, how do you allocate and release memory?
In C++, the new operator is used to allocate memory, whereas the delete operator is used to deallocate memory.
Example
int value=val;
delete value;
int *ar=val[10];
delete []ar;
6. Determine if there are any two integers in the array whose sum equals the provided value, given an array of integers and a value.
There are two main approaches to this problem 
 Using Bruteforce
 Using Sorting
Using Bruteforce
The simplest method is to consider each pair in the given array and return true if the desired total is obtained.
Time Complexity: O(n^2)
Program: The below is an implementation of the same in Java.
class Main
{
public static void findingPair(int[] num, int x)
{
for (int i = 0; i < num.length  1; i++)
{
for (int j = i + 1; j < num.length; j++)
{
if (num[i] + num[j] == x)
{
System.out.println("The Pair that are found are (" + num[i] + "," + num[j] + ")");
return;
}
}
}
System.out.println("No Pair found");
}
public static void main (String[] args)
{
int[] num = { 5, 90, 45, 20, 13, 111 };
int x = 25;
findingPair(num, x);
}
}
Output
The Pair that are found are (5,20)
Using Sorting
The goal is to sort the given array in ascending order while preserving search space by keeping two indices (low and high) that point to the array's two endpoints. Then, for each iteration of the loop, reduce the search space num[low...high] by comparing the sum of elements present at indices low and high to the desired sum. If the total is less than the expected total, increment low; otherwise, increment high if the total is greater than the desired total. Return the pair if it is discovered.
Time Complexity: O(n log(n))
Program
import java.util.Arrays;
class Main
{
public static void findingPair(int[] num, int x)
{
Arrays.sort(num);
int low = 0;
int high = num.length  1;
while (low < high)
{
if (num[low] + num[high] == x)
{
System.out.println("The Pair found is (" + num[low] + "," +
num[high] + ")");
return;
}
if (num[low] + num[high] < x) {
low++;
}
else {
high;
}
}
System.out.println("The Pair was not found");
}
public static void main (String[] args)
{
int[] num = { 18, 78, 12, 66, 16, 11 };
int x = 34;
findingPair(num, x);
}
}
Output
The Pair found is (16,18)
7. If any element in the given twodimensional array is zero, make the entire row and column zero.
One obvious solution is to scan the 2D matrix and, if a zero is found, make the entire column and row zero. However, this solution is incorrect. Even if there is just one zero in the matrix, the entire matrix will be zero.
Approach
Scan the 2D array to find all the rows and columns that contain zero and divide them into two sets.
Time Complexity  O(m.n)
Program
class makeZeros{
static void make_zeroes(int[][] matrix) {
if (matrix.length == 0) {
return;
}
Set<Integer> zero_rows = new HashSet<Integer>();
Set<Integer> zero_cols = new HashSet<Integer>();
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 = {
{23, 0, 40, 34, 11},
{60, 17, 23, 89, 18},
{24, 76, 0, 50, 15},
{10, 43, 67, 0, 47}
};
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);
}
}
}
}
Output
23 0 40 34 11
60 17 23 89 18
24 76 0 50 15
10 43 67 0 47
0 0 0 0 0
60 0 0 0 18
0 0 0 0 0
0 0 0 0 0
39 12 18 46 77
34 55 52 36 20
33 31 80 76 92
16 18 0 98 83
14 36 58 31 76
39 12 0 46 77
34 55 0 36 20
33 31 0 76 92
0 0 0 0 0
14 36 0 31 76
8. Given the head pointers of two linked lists, add them and return the new linked list. Each linked list represents an integer number (each node is a digit).
Approach: Add preceding zeros in the list with lesser numbers to the end of both lists. Then, on the start nodes of both lists, execute a recursive function that calls itself for the following nodes of both lists until it reaches the end. This function returns the carry after creating a node for the sum of the current digits.
Program
class LinkedList {
static Node head1, head2;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
void addTwoLists(Node first, Node second) {
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;
addPrecedingZeros(start1, start2);
Node result = new Node(0);
if (sumTwoNodes(start1.next, start2.next, result) == 1) {
Node node = new Node(1);
node.next = result.next;
result.next = node;
}
printList(result.next);
}
private int sumTwoNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int number = first.data + second.data + sumTwoNodes(first.next, second.next, result);
Node node = new Node(number % 10);
node.next = result.next;
result.next = node;
return number / 10;
}
private void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null && next2 != null) {
while (next2 != null) {
Node node = new Node(0);
node.next = start1.next;
start1.next = node;
next2 = next2.next;
}
} else if (next2 == null && next1 != null) {
while (next1 != null) {
Node node = new Node(0);
node.next = start2.next;
start2.next = node;
next1 = next1.next;
}
}
}
void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("");
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.head1 = new Node(14);
list.head1.next = new Node(51);
list.head1.next.next = new Node(19);
list.head1.next.next.next = new Node(42);
list.head1.next.next.next.next = new Node(16);
System.out.print("The First List is ");
list.printList(head1);
list.head2 = new Node(83);
list.head2.next = new Node(34);
System.out.print("The Second List is ");
list.printList(head2);
System.out.print("The Final List is ");
list.addTwoLists(head1, head2);
}
}
Output
The First List is 14 51 19 42 16
The Second List is 83 34
The Final List is 1 9 4 2 0 0
9. You're given a linked list with two pointers at each node. The regular 'next' pointer is the first. 'Arbitrary pointer' is the second pointer, and it can point to any node in the linked list. Your task is to write code that creates a deep copy of the linked list provided. Any operations on the original list (inserting, updating, and removing items) should have no effect on the cloned list.
Approach: This method follows arbitrary nodes pointed by the original list using a map. In two passes, you'll make a deep clone of the original linked list.
 Create a copy of the original linked list in the first pass. While creating this duplicate, use the same values for data and arbitrary pointers in the new list. Also, keep adding entries to the map with the key being the old node's address and the value being the new node's address.
 After the copy is made, run over the copied linked list again, updating arbitrary references to the new address with the map established in the first pass.
Time Complexity: O(n)
Program
class arbitraryPointer{
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<LinkedListNode, LinkedListNode> map =
new Hashtable<LinkedListNode,LinkedListNode>();
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;
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);
}
}
Output
Original: 0, 1, 2, 3,
Copied: 0, 1, 2, 3,
10. Display the node values at each level of a binary tree given the root.
Approach: Use the function to print a current level
Time Complexity: O(n^2)
Program
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
public BinaryTree() { root = null; }
/* function to print level order traversal of tree*/
void printLevelOrder()
{
int h = height(root);
int i;
for (i = 1; i <= h; i++)
printCurrentLevel(root, i);
}
int height(Node root)
{
if (root == null)
return 0;
else {
int lheight = height(root.left);
int rheight = height(root.right);
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}
void printCurrentLevel(Node root, int level)
{
if (root == null)
return;
if (level == 1)
System.out.print(root.data + " ");
else if (level > 1) {
printCurrentLevel(root.left, level  1);
printCurrentLevel(root.right, level  1);
}
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(3);
tree.root.left = new Node(7);
tree.root.right = new Node(12);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(0);
System.out.println("The Level order traversal of binary tree is ");
tree.printLevelOrder();
}
}
Output
The Level order traversal of binary tree is
3 7 12 2 0
11. Join the sibling pointer to the samelevel node. Each level's last node should point to the tree's first level's initial node.
A binary tree is a data structure consisting of nodes, each of which has a "left" and "right" reference as well as a data element. The root is the highest node in the tree. Except for the 'root' node, each node is connected to exactly one other node by a directed edge. This node is known as that node's parent. Each node, on the other hand, can be connected to an unlimited number of offspring. Siblings are nodes that have the same parent node.
Along with the left and right pointers, each node in the above binary tree has one extra pointer, next. The command 'Next' is used to link two nodes together. A linkedlistlike structure with the root node as the head is generated once siblings are connected. Two pointers are kept: current and last. The current node is the one we're working on, and the last node in the linked list is the one we've already built.
Time complexity: O(n)
Program
class connectSiblings{
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<Integer> get_level_order_traversal_with_sibling(BinaryTreeNode root)
{
List<Integer> l = new ArrayList<Integer>();
while(root != null) {
l.add(root.data);
root = root.next;
}
return l;
}
public static void main(String[] args) {
List<Integer> input = new ArrayList<Integer>();
input.add(50);input.add(15);input.add(95);input.add(5);input.add(34);input.add(20);input.add(30);
input.add(23);input.add(12);input.add(39);input.add(26);input.add(74);
BinaryTreeNode root = BinaryTree.create_BST(input);
BinaryTree.display_level_order(root);
populate_sibling_pointers(root);
System.out.println("Root > next: "+ root.next.data);
System.out.println("Root>right>left>next: "+ root.right.left.next.data);
System.out.println("Root>right>right>next: "+ root.right.right.next.data);
System.out.println("Root>right>right>left>next: "+ root.right.right.left.next);
List<Integer> l1 = BinaryTree.get_level_order(root);
List<Integer> 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);
}
}
Output
50, 15, 95, 5, 34, 74, 12, 20, 39, 30, 23, 26,
Root > next: 15
Root>right>left>next: 12
12. In a given sentence or an array of characters, reverse the order of words.
Approach: We can perform splitting, and simply swapping the string from the middle can be performed. Because direct swapping is used, less space is used.
Time Complexity: O(n)
Program
class GFG{
public static String[] reverse(String[] s,
int l)
{
if (l % 2 == 0)
{
int j = l / 2;
while (j <= l  1)
{
String temp;
temp = s[l  j  1];
s[l  j  1] = s[j];
s[j] = temp;
j += 1;
}
}
else
{
int j = (l / 2) + 1;
while (j <= l  1)
{
String temp;
temp = s[l  j  1];
s[l  j  1] = s[j];
s[j] = temp;
j += 1;
}
}
return s;
}
public static void main(String[] args)
{
String s = "To be a pioneer at something, " +
"we need a lot of practice";
String[] words = s.split("\\s");
words = reverse(words, words.length);
s = String.join(" ", words);
System.out.println(s);
}
}
Output
practice of lot a need we something, at pioneer a be To
13. Given a string, discover all nonsingle letter palindrome substrings.
Approach: Start expanding to the left and right for each letter in the input string, searching for even and odd length palindromes. If we know there isn't a palindrome, move on to the next letter.
We compare and expand one character to the left and right. We print the palindrome substring if both of them are equal.
Time Complexity: O(n^2)
Program
class PalindromeSubStrings{
public static int findPalindromesInSubString(String input, int j, int k) {
int count = 0;
for (; j >= 0 && k < input.length(); j, ++k) {
if (input.charAt(j) != input.charAt(k)) {
break;
}
System.out.println(input.substring(j, k+1));
count++;
}
return count;
}
public static int findAllPalindromeSubstrings(String input) {
int count = 0;
for(int i = 0 ; i < input.length() ; ++i) {
count+= findPalindromesInSubString(input, i1, i+1);
count+= findPalindromesInSubString(input, i, i+1);
}
return count;
}
public static void main(String[] args) {
String str = "bbaabbbaba";
int count = findAllPalindromeSubstrings(str);
System.out.println("The palindrome substrings in the given string are: " + count);
}
}
Output
bb
aa
baab
bbaabb
bb
bbb
abbba
bb
bab
aba
The palindrome substrings in the given string are: 10
14. Return the buy and sell prices to generate the most profit from a list of daily stock prices (integers for simplicity). The single buy/sell profit must be maximized. If you can't make any money, strive to cut your losses as much as possible.
Approach: Kadane’s algorithm
The array's values represent the daily cost of a stock. Because we can only purchase and sell the stock once, we must identify the optimal buy and sell prices that maximize our profit (or minimize our loss) over a specific period of time.
This problem has a hard linear solution that requires us to cycle through the whole array of stock prices while preserving current_buy_price (which is the smallest value observed so far), current_profit, and global_profit. We will compare the current_profit to the global_profit at each iteration and update the global_profit accordingly.
Time Complexity: O(n)
Program
class Tuple<X, Y> {
public X x;
public Y y;
public Tuple(X x, Y y) {
this.x = x;
this.y = y;
}
}
class StockPrices{
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 = {23, 12, 34, 41, 27, 31, 67};
Tuple result = null;
result = findBuySellStockPrices(array);
System.out.println(String.format("The Buy Price is: %d, The Sell Price is: %d", result.x, result.y));
int[] array2 = {32, 61, 25, 21, 13, 22, 11};
result = findBuySellStockPrices(array2);
System.out.println(String.format("The Buy Price is: %d, The Sell Price is: %d", result.x, result.y));
}
}
Output
The Buy Price is: 12, The Sell Price is: 67
The Buy Price is: 32, The Sell Price is: 61
15. Given an array of positive numbers ranging from 1 to n, with all but one of the numbers 'x' present. We must locate 'x.' There is no sorting in the input array.
Approach: The arithmetic series sum formula is used: Sum(1  n) = n(n+1)
n(n+1)
Time Complexity: O(n)
The steps to locating the missing number are as follows:
 Find the sum of all the numbers in the array using the 'sum_of_elements' variable. This would necessitate a linear scan, according to O. (n).
 Then, using the arithmetic series sum formula (n * (n + 1)) / 2, determine the sum 'expected_sum' of the first 'n' values.
 The missing value in the array is the difference between these, i.e. 'expected_sum  sum_of_elements'.
Program
class findMissing{
static int find_missing(List<Integer> input) {
int sum_of_elements = 0;
for (Integer x : input) {
sum_of_elements += x;
}
int n = input.size() + 1;
int actual_sum = (n * ( n + 1 ) ) / 2;
return actual_sum  sum_of_elements;
}
static void test(int n) {
int missing_element = (new Random()).nextInt(n) + 1;
List<Integer> v = new ArrayList<Integer>();
for(int i = 1; i <= n; ++i) {
if (i != missing_element)
v.add(i);
}
int actual_missing = find_missing(v);
System.out.print("The Expected Missing is ");
System.out.print(missing_element);
System.out.print("The Actual Missing is ");
System.out.println(actual_missing);
System.out.println("The Missing Element == The Actual Missing is "+ (missing_element == actual_missing));
}
public static void main(String[] args) {
for (int n = 0; n < 10; ++n)
test(90000);
}
}
Output
The Expected Missing is 9205The Actual Missing is 9205
The Missing Element == The Actual Missing is true
The Expected Missing is 39967The Actual Missing is 39967
The Missing Element == The Actual Missing is true
The Expected Missing is 38569The Actual Missing is 38569
The Missing Element == The Actual Missing is true
The Expected Missing is 17812The Actual Missing is 17812
The Missing Element == The Actual Missing is true
The Expected Missing is 62805The Actual Missing is 62805
The Missing Element == The Actual Missing is true
The Expected Missing is 58975The Actual Missing is 58975
The Missing Element == The Actual Missing is true
The Expected Missing is 35654The Actual Missing is 35654
The Missing Element == The Actual Missing is true
The Expected Missing is 10310The Actual Missing is 10310
The Missing Element == The Actual Missing is true
The Expected Missing is 77532The Actual Missing is 77532
The Missing Element == The Actual Missing is true
The Expected Missing is 84418The Actual Missing is 84418
The Missing Element == The Actual Missing is true
16. Print all feasible combinations of positive integers that add up to the target number given a positive integer, target.
Approach: We will go through all potential sum combinations recursively. We'll print that combination whenever the running sum equals the target.
The procedure will check all the integers that add up to the target in a recursive manner. There is a for loop in each recursive call that runs from start to target. 1 is the beginning start. In every recursive call, the variable current sum is incremented.
The reasoning of the code is as follows: whenever a value is added to the current_sum, it is also added to the result list, which is the sum combination for that call. We can be sure that the result list contains a possible combination for target whenever current_sum equals target. This list is appended to the output list at the end.
An element is added to the result before each recursive call. However, this element is removed from the list after each call in order to reset the list.
Time Complexity: O(2^n)
Program
class sumCombinations{
static void print(ArrayList<ArrayList<Integer>> arr) {
for (int i = 0; i < arr.size(); i++) {
System.out.print("[");
for (int j = 0; j < arr.get(i).size(); j++) {
System.out.print(arr.get(i).get(j) + ", ");
}
System.out.println("]");
}
}
static void print_all_sum_rec(
int target,
int current_sum,
int start, ArrayList<ArrayList<Integer>> output,
ArrayList<Integer> result) {
if (target == current_sum) {
output.add((ArrayList)result.clone());
}
for (int i = start; i < target; ++i) {
int temp_sum = current_sum + i;
if (temp_sum <= target) {
result.add(i);
print_all_sum_rec(target, temp_sum, i, output, result);
result.remove(result.size()  1);
} else {
return;
}
}
}
static ArrayList<ArrayList<Integer>> print_all_sum(int target) {
ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> result = new ArrayList<Integer>();
print_all_sum_rec(target, 0, 1, output, result);
return output;
}
public static void main(String[] args) {
int n = 7;
ArrayList<ArrayList<Integer>> result = print_all_sum(n);
print (result);
}
}
Output
[1, 1, 1, 1, 1, 1, 1, ]
[1, 1, 1, 1, 1, 2, ]
[1, 1, 1, 1, 3, ]
[1, 1, 1, 2, 2, ]
[1, 1, 1, 4, ]
[1, 1, 2, 3, ]
[1, 1, 5, ]
[1, 2, 2, 2, ]
[1, 2, 4, ]
[1, 3, 3, ]
[1, 6, ]
[2, 2, 3, ]
[2, 5, ]
[3, 4, ]
17. Using regular expression matching, determine if a pattern matches the text completely or not at all given a text and a pattern. Assume that the pattern can only contain two operators: '.' and '*' for simplicity. The operator '*' in the pattern indicates that the character preceding '*' may or may not appear in the text. The operator '.' only matches any character in the text once.
Approach: We will compare the text and pattern character by character, then compare the rest of the text and pattern recursively. Instead of producing substrings, we use indices of text and pattern in this solution and pass the same strings in the recursive operations.
This solution's worstcase time complexity is still exponential, but we save memory and time that would otherwise be spent copying strings.
Time Complexity: O(2^n)
Program
class RegxMatch {
public static boolean regxMatchRec(String text, String pattern, int i, int j) {
if (text.length() == i && pattern.length() == j) {
return true;
}
if (j<pattern.length()  1 && pattern.charAt(j + 1) == '*') {
for (int k = i; k<= text.length(); ++k) {
if (regxMatchRec(text, pattern, k, j + 2)) {
return true;
}
if (k >= text.length()) {
return false;
}
if (pattern.charAt(j) != '.' && text.charAt(k) != pattern.charAt(j)) {
return false;
}
}
} else if (i<text.length() && j<pattern.length() &&
(pattern.charAt(j) == '.'  pattern.charAt(j) == text.charAt(i))) {
return regxMatchRec(text, pattern, i + 1, j + 1);
}
return false;
}
public static boolean regxMatch(String text, String pattern) {
return regxMatchRec(text, pattern, 0, 0);
}
public static void main(String[] args) {
String s = "afbbabbbcaa";
String p = ".ab*c";
boolean output2 = regxMatch(s, p);
Pattern pattern = Pattern.compile(p);
Matcher matcher = pattern.matcher(s);
if (output2) {
System.out.print(s + " " + p + " match");
} else {
System.out.print(s + " " + p + " did not match.");
}
}
}
Output
afbbabbbcaa .ab*c did not match.
18. Given the root node of a directed graph, clone the graph by making a deep copy of it with the same vertices and edges as the original graph.
Approach: While traversing the graph, we employ depthfirst traversal and make a copy of each node. We'll use a hashtable to store each completed node and won't revisit nodes that already exist in the hashtable to prevent getting stuck in loops. The hashtable key will be a node from the original graph, and the value will be the cloned graph's corresponding node.
Time Complexity: O(n)
Program
class Node {
public int data;
public List<Node> neighbors = new ArrayList<Node>();
public Node(int d) {data = d;}
}
class Graph {
private static Node clone_rec(
Node root,
HashMap<Node, Node> nodes_completed) {
if (root == null) {
return null;
}
Node pNew = new Node(root.data);
nodes_completed.put(root, pNew);
for (Node p : root.neighbors) {
Node x = nodes_completed.get(p);
if (x == null){
pNew.neighbors.add(clone_rec(p, nodes_completed));
} else {
pNew.neighbors.add(x);
}
}
return pNew;
}
public static Node clone(Node root) {
HashMap<Node, Node> nodes_completed =
new HashMap<Node, Node>();
return clone_rec(root, nodes_completed);
}
}
class clone_graph {
static ArrayList<Node> create_test_graph_undirected(int nodes_count, int edges_count) {
ArrayList<Node> vertices = new ArrayList<Node>();
for (int i = 0; i < nodes_count; ++i) {
vertices.add(new Node(i));
}
List<Pair<Integer, Integer>> all_edges = new ArrayList<Pair<Integer, Integer>>();
for (int i = 0; i < vertices.size(); ++i) {
for (int j = i + 1; j < vertices.size(); ++j) {
all_edges.add(new Pair<Integer, Integer>(i, j));
}
}
Collections.shuffle(all_edges);
for (int i = 0; i < edges_count && i < all_edges.size(); ++i) {
Pair<Integer, Integer> edge = all_edges.get(i);
vertices.get(edge.first).neighbors.add(vertices.get(edge.second));
vertices.get(edge.second).neighbors.add(vertices.get(edge.first));
}
return vertices;
}
static void print_graph(List<Node> vertices) {
for (Node n : vertices) {
System.out.print(n.data + ": {");
for (Node t : n.neighbors) {
System.out.print(t.data + " ");
}
System.out.println();
}
}
static void print_graph(Node root, HashSet<Node> visited_nodes) {
if (root == null  visited_nodes.contains(root)) {
return;
}
visited_nodes.add(root);
System.out.print(root.data + ": {");
for (Node n : root.neighbors) {
System.out.print(n.data + " ");
}
System.out.println("}");
for (Node n : root.neighbors) {
print_graph(n, visited_nodes);
}
}
static void print_graph(Node root) {
HashSet<Node> visited_nodes = new HashSet<Node>();
print_graph(root, visited_nodes);
}
static boolean are_graphs_equal_rec(Node root1, Node root2, HashSet<Node> visited) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null  root2 == null) {
return false;
}
if (root1.data != root2.data) {
return false;
}
if (root1.neighbors.size() != root2.neighbors.size()) {
return false;
}
for (Node nbr1 : root1.neighbors) {
boolean found = false;
for (Node nbr2 : root2.neighbors) {
if (nbr1.data == nbr2.data) {
if (!visited.contains(nbr1)) {
visited.add(nbr1);
are_graphs_equal_rec(nbr1, nbr2, visited);
}
found = true;
break;
}
}
if (!found) {
return false;
}
}
return true;
}
public static void main(String[] args) {
ArrayList<Node> vertices = create_test_graph_undirected(7, 18);
print_graph(vertices.get(0));
Node cp = Graph.clone(vertices.get(0));
System.out.println();
System.out.println("After copying: ");
print_graph(cp);
HashSet<Node> set = new HashSet<Node>();
System.out.println(are_graphs_equal_rec(vertices.get(0), cp, set));
}
}
Output
0: {3 6 2 5 4 }
3: {0 6 2 1 5 4 }
6: {3 2 0 5 1 }
2: {6 3 4 5 0 1 }
4: {1 2 0 3 5 }
1: {4 3 2 6 }
5: {2 6 3 0 4 }
After copying:
0: {3 6 2 5 4 }
3: {0 6 2 1 5 4 }
6: {3 2 0 5 1 }
2: {6 3 4 5 0 1 }
4: {1 2 0 3 5 }
1: {4 3 2 6 }
5: {2 6 3 0 4 }
true
19. Given N people and an MxM grid, determine the spot where all people must travel the least total distance to meet.
Approach: To find the shortest distance traveled, this technique uses a 'centroid.'
The arithmetic mean or average position of all the points in a twodimensional region is the centroid. We can find the centroid of all the points on the grid with individuals, and that will be the place with the shortest distance traveled. It can be calculated in the following way:
centroid = (x1+x2+x3…+xn , y1+y2+y3…+yn)  This is the average of xcoordinates and ycoordinates.
The centroid is the correct answer in most circumstances, but in rare cases, the centroid offers the closest point to the correct position. So, in this situation, we'll determine the centroid first, then check the eight spots around it for the likely shortest distance traveled point. The minimal distance traveled point will be any of those points with a distance less than the distance at the centroid.
Because we take the average of all the points and then round off the figure, regardless of the minimum distance covered by all points, the centroid occasionally yields an inaccurate point. This will almost always produce a point that is in the center of all the points, which is correct. However, the nearest point may be found at any of the input locations, which we will never be able to determine using the Centroid calculation. To tackle this case, we doublecheck the neighbors of the "closest point."
Time Complexity: O(n)
Program
class point {
private int x;
private int y;
point(int x, int y) {
this.x = x;
this.y = y;
}
int getX() {
return x;
}
void setX(int x) {
this.x = x;
}
int getY() {
return y;
}
void setY(int y) {
this.y = y;
}
double calculate_distance(point p) {
double distance;
distance = Math.sqrt((p.x  this.x) * (p.x  this.x) + (p.y  this.y) * (p.y  this.y));
return distance;
}
double calculate_sum_of_distances(
ArrayList < point > points) {
double distance_sum;
distance_sum = 0;
for (int i = 0; i < points.size(); i++) {
distance_sum += this.calculate_distance(points.get(i));
}
return distance_sum;
}
};
class distance {
public point shortest_distance_travelled_2(int m, ArrayList < point > points) {
point min_pt = new point(0, 0);
double x = 0;
double y = 0;
point centroid = new point(0, 0);
for (int i = 0; i < points.size(); i++) {
x += points.get(i).getX();
y += points.get(i).getY();
}
centroid.setX((int) Math.round(x / points.size()));
centroid.setY((int) Math.round(y / points.size()));
min_pt.setX(centroid.getX());
min_pt.setY(centroid.getY());
double min_distance = min_pt.calculate_sum_of_distances(points);
for (int i = min_pt.getX()  1; i < min_pt.getX() + 2; i++) {
for (int j = min_pt.getY()  1; j < min_pt.getY() + 2; j++) {
if (i < 1  j > m) {
continue;
}
point pt = new point(i, j);
double distance = pt.calculate_sum_of_distances(points);
if (distance < min_distance) {
min_distance = distance;
min_pt.setX(pt.getX());
min_pt.setY(pt.getY());
}
}
}
return min_pt;
}
public static void test_grid1() {
System.out.println("The testing grid 1 is \n");
int m = 7;
ArrayList < point > points = new ArrayList < point > ();
points.add(new point(1, 2));
points.add(new point(3, 3));
points.add(new point(4, 2));
System.out.println("Solution 2 is ");
distance d = new distance();
point pt = d.shortest_distance_travelled_2(m, points);
System.out.println("The Shortest Distance Point = p(" + pt.getX() + ", " + pt.getY() + ")");
}
public static void test_grid2() {
System.out.println("The Testing grid 2 is \n");
int m = 21;
ArrayList < point > points = new ArrayList < point > ();
points.add(new point(1, 1));
points.add(new point(3, 5));
points.add(new point(6, 2));
points.add(new point(7, 7));
points.add(new point(8, 4));
System.out.println("Solution 2 is ");
distance d = new distance();
point pt = d.shortest_distance_travelled_2(m, points);
System.out.println("The Shortest Distance Point = p(" + pt.getX() + ", " + pt.getY() + ")");
}
public static void test_grid3() {
System.out.println("The Testing grid 3 is \n");
int m = 9;
ArrayList < point > points = new ArrayList < point > ();
points.add(new point(4, 3));
points.add(new point(5, 5));
points.add(new point(2, 7));
System.out.println("Solution 2 is ");
distance d = new distance();
point pt = d.shortest_distance_travelled_2(m, points);
System.out.println("The Shortest Distance Point = p(" + pt.getX() + ", " + pt.getY() + ")");
}
public static void main(String[] args) {
test_grid1();
test_grid2();
test_grid3();
}
}
Output
The testing grid 1 is
Solution 2 is
The Shortest Distance Point = p(3, 3)
The Testing grid 2 is
Solution 2 is
The Shortest Distance Point = p(5, 4)
The Testing grid 3 is
Solution 2 is
The Shortest Distance Point = p(4, 5)
20. We've been given a 2D array with all elements in each row or column sorted. We must search or find the position of a given key in such a matrix.
Approach: One simple method is to scan the entire 2D array in O(mn) time for the key. However, using the sorted property of a matrix, there are superior ways with less time complexity. To determine whether the key exists in a row, we can perform a binary search on each row. This solution has an O(m * log n) time complexity. Though it appears to be a nice answer, we have a superior one.
We begin by comparing the value of the upper right corner of the matrix to the key. If they're the same, we've determined the key's location. We change one position to the left if the key is smaller than the current element. We move one position down if the key is greater than the current element.
Because the matrix is sorted, moving left will result in lower values, and moving right will result in higher values than the present value. We repeat this approach until we either find the element or reach the matrix's border (which indicates that the key does not exist). This approach will only visit m + n elements in the matrix, giving us an O(m + n) time complexity. It's also worth noting that we can't start our search from the top left or bottom right corners because the keys on either side of that corner are increasing or decreasing.
It's worth noting that we can begin our search from the bottom left corner, which will get comparable results to starting from the top right.
Time Complexity: O(m+n)
Program
class searchMatrix{
public static IntPair
search_in_matrix(int matrix[][], int value) {
int M = matrix.length;
int N = matrix[0].length;
int i = 0, j = N1;
while (i < M && j >= 0) {
if (matrix[i][j] == value) {
return new IntPair(i, j);
}
else if (value < matrix[i][j]) {
j;
}
else {
++i;
}
}
return new IntPair(1, 1);
}
public static void verify_search(int [][] matrix) {
for (int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix[0].length; ++j) {
System.out.println("We are verifying at " + i + ", " + j);
IntPair val_loc = search_in_matrix(matrix, matrix[i][j]);
assert(val_loc.first == i);
assert(val_loc.second == j);
}
}
}
public static void main(String[] args) {
int [] [] matrix = new int [] [] {
{11, 53, 23, 18, 32},
{67, 17, 8, 35, 12},
{90, 28, 39, 95, 26},
{28, 73, 65, 100, 54}
};
verify_search(matrix);
}
}
Output
We are verifying at 0, 0
We are verifying at 0, 1
We are verifying at 0, 2
We are verifying at 0, 3
We are verifying at 0, 4
We are verifying at 1, 0
We are verifying at 1, 1
We are verifying at 1, 2
We are verifying at 1, 3
We are verifying at 1, 4
We are verifying at 2, 0
We are verifying at 2, 1
We are verifying at 2, 2
We are verifying at 2, 3
We are verifying at 2, 4
We are verifying at 3, 0
We are verifying at 3, 1
We are verifying at 3, 2
We are verifying at 3, 3
We are verifying at 3, 4
Advance your career as a MEAN stack developer with the Full Stack Web Developer  MEAN Stack Master's Program. Enroll now!
Master Full Stack Web Development With Simplilearn
Microsoft is a dream company for many and requires effort to land a job. Most importantly, you should have the relevant experience and skills to ace the interview rounds and stand apart from other candidates. These Microsoft interview questions and answers will surely help you answer the interviews with confidence and help you crack it with ease.
Simplilearn offers a global online Post Graduate Program in Full Stack Web Development to help you realize your dream. Enroll in the course today to upskill yourself. Simplilearn also offers a plethora of other courses to help you land your dream job in Microsoft’s other business units too. Explore more now.