Introduction
This article will discuss the most common Microsoft interview questions and answers that will help you prepare well for your upcoming interview.
Microsoft is an American multinational corporation that provides computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus in Redmond, Washington, United States.
Microsoft Interview Questions
Explain the key differences between the B+ tree and the B tree?
- B-trees are a sort of self-balancing tree structure used to store and retrieve large quantities of data quickly.
- They are frequently confused with the Binary Search Tree, which is a close relative. The Binary Search Tree is a specific form of B-tree, despite the fact that they're both m-way search trees.
- Multiple key/value pairs can be found in a node of a B-tree, which is sorted ascendingly by key order. This key/value pair is referred to as a payload.
- When it comes to insert, remove, and search operations, B-trees are seen to be particularly useful because they give logarithmic O(log(n)) time complexity.
- In a doubly-linked list, all leaf nodes are linked together. Only the leaf nodes store satellite data. Internal nodes solely serve as routers to the correct leaf node and store keys.
- Data put on the leaf node improves the search efficiency in B+trees because we can store more keys in internal nodes, requiring us to access fewer nodes.
- Because we just need to delete data from leaf nodes, deleting data from a B+tree is easier and faster.
- In fact, B+trees are used for indexing in 99 per cent of database management systems.
What is overloading and overriding?
Function overloading is a concept in which two or more functions in the same class with the same name are defined with the condition that their parameters differ in number or type.
Function overriding is a concept in which two functions with the same name and parameters are defined, with the condition that one function must be present in a base class and the other function in a derived class.
What are the different types of access modifiers?
Public members
The class members declared under the public specifier can be accessed by everyone, including other classes and functions.
It can be accessed anywhere through the dot (.) operator.
Private members
The class members who are declared private can only be accessed within the class. Any foreign class or a function can not access these private members. But a friend function can access the private members.
If we want to access variables declared private outside the class, we can access them through the member functions declared as public.
Protected members
The class members who are declared protected can only be accessed by their derived classes, also known as subclasses.
What is the difference between malloc() and new operator?
A few of the differences between malloc() and new operator which are used to allocate dynamic memory are as follows:
- The new operator calls the constructor, whereas malloc() doesn't.
- In the case of the new operator, the compiler calculates the required size of memory, whereas, in the case of malloc(), the programmer has to manually calculate the size of memory.
- The new operator returns the exact data type, whereas malloc() returns void.
Where in the JVM memory is an Array kept?
JVM has five memory locations, and these memory locations are :
- Heap
- Stack
- PC registers
- Execution Engine and
- Native method stacks.
In Java, an array is an object. As a result, the Java Virtual Machine stores an array in heap memory. Arrays are reference types, so these are stored in heap areas.
What is merge sort?
The merge sort algorithm employs the "divide and conquer" strategy, in which we divide the problem into subproblems and solve each one individually.
These subproblems are then combined or merged to form a complete solution.
- By dividing the list on the middle element, the list is divided into two arrays of equal length. The list is considered sorted if the number of elements in it is either 0 or 1.
- Each sublist is sorted individually using a recursive merge sort.
- The sorted sublists are then combined or merged to form the final sorted list.
Psudeocode-
Declare an array Arr of length N
If N=1, Arr is already sorted
If N>1,
Left = 0, right = N-1
Find middle = (left + right)/2
Call merge_sort(Arr,left,middle) =>sort first half recursively
Call merge_sort(Arr,middle+1,right) => sort second half recursively
Call merge(Arr, left, middle, right) to merge sorted arrays in above steps.
ExitWhat is a binary search tree, and how is it implemented?
Ans: A binary search tree (BST) is a tree data structure where each node has at most two children, and the left child is always less than the parent, and the right child is greater than the parent. It allows for efficient searching, inserting, and deleting of elements in a sorted manner.
Here's an example implementation of a BST in C++:
- C++
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
class BST {
Node *root;
public:
BST() {
root = nullptr;
}
Node* get_root() {
return root;
}
Node* create_node(int value) {
Node *node = new Node;
node->data = value;
node->left = nullptr;
node->right = nullptr;
return node;
}
void insert(int value) {
root = insert_node(root, value);
}
Node* insert_node(Node *node, int value) {
if (node == nullptr) {
return create_node(value);
}
if (value < node->data) {
node->left = insert_node(node->left, value);
}
else {
node->right = insert_node(node->right, value);
}
return node;
}
void inorder_traversal(Node *node) {
if (node == nullptr) {
return;
}
inorder_traversal(node->left);
cout << node->data << " ";
inorder_traversal(node->right);
}
void preorder_traversal(Node *node) {
if (node == nullptr) {
return;
}
cout << node->data << " ";
preorder_traversal(node->left);
preorder_traversal(node->right);
}
void postorder_traversal(Node *node) {
if (node == nullptr) {
return;
}
postorder_traversal(node->left);
postorder_traversal(node->right);
cout << node->data << " ";
}
bool search(Node *node, int value) {
if (node == nullptr) {
return false;
}
if (node->data == value) {
return true;
}
else if (value < node->data) {
return search(node->left, value);
}
else {
return search(node->right, value);
}
}
};
int main() {
BST bst;
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(17);
cout << "Inorder traversal: ";
bst.inorder_traversal(bst.get_root());
cout << endl;
cout << "Preorder traversal: ";
bst.preorder_traversal(bst.get_root());
cout << endl;
cout << "Postorder traversal: ";
bst.postorder_traversal(bst.get_root());
cout << endl;
int value = 7;
bool found = bst.search(bst.get_root(), value);
if (found) {
cout << value << " found in the BST." << endl;
}
else {
cout << value << " not found in the BST." << endl;
}
return 0;
}
Output:
Inorder traversal: 3 5 7 10 12 15 17
Preorder traversal: 10 5 3 7 15 12 17
Postorder traversal: 3 7 5 12 17 15 10
7 found in the BST.
In this implementation, the binary search tree is defined as a class BST with a private variable root that points to the tree's root node. The Node struct defines the structure of each node in the tree, which has a data field and pointers to the left and right child nodes. The other operations are done accordingly.
How can you find the middle element of a linked list?
We can find the middle element of the linked list by traversing the linked list twice. First time for finding the length of the linked list and then traversing the linked list for (N/2) length.
A better approach would be using two-pointers.
- We will use two pointers, "slow" and "fast" Set both pointers to the head node at first.
- Traverse the linked list using a loop (fast!= NULL, and fast->next!= NULL) until the fast pointer reaches the last node of the linked list.
- The slow pointer moves one node per iteration, while the fast pointer moves two nodes.
- When the fast pointer reaches the last node, the slow pointer points to the middle node.
if(head == NULL){
return NULL;
}
struct node *slow, *fast;
slow = fast = head;
while(fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
return slow->data;How will you create an immutable class in java?
You can create an immutable class in Java by implementing the following points:
- First, make the class as final such that the class cannot be further inherited.
- Then, make all the data members private such that they will not be accessible from outside the class.
- Do not provide setter methods for the variables.
- Deep copy of objects should be performed in the getter methods.
Explain Character Encoding. What is the difference between UTF-8 and UTF-16?
- Encoding is the way to convert the data from one form to another.
- Character encoding refers to the method when a character is represented in bytes.
- UTF-8 uses 1 byte or 8 bits of memory to store the character, whereas UTF-16 uses 2 bytes or 16 bits of memory to store the character.
What are infix, postfix, and prefix expressions?
Infix:
The operator appears between two operands in the infix expression. T. For example, 2 + 3, a * b, 6 / 3, and so on.
We can read it as two is added to three.
operator > operand1 > operand2Prefix:
The operator comes before the two operands in prefix expression. For example: + 6 8, * x y, - 3 2, and so on.
We can read it as Add two and three.
operand 1 > operand 2 > operatorPostfix:
The operator comes after the two operands in postfix expression. For example, 5 7 +, a b *, 12 6 /, and so on.
We can read it as 2 and 3 are added.
operator > operand 1 > operand 2How do you implement a breadth-first search?
Breadth-first search is an algorithm used to traverse and search a graph or a tree data structure. Here is an implementation of the Breadth-First Search algorithm in Python.
- Python
Python
from collections import deque
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bfs(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
curr_node = queue.popleft()
result.append(curr_node.val)
if curr_node.left:
queue.append(curr_node.left)
if curr_node.right:
queue.append(curr_node.right)
return result
# Example usage
root = Node(1, Node(2), Node(3, Node(4), Node(5)))
bfs_result = bfs(root)
print(bfs_result)
Output:
[1, 2, 3, 4, 5]
In this program, we define a Node class that represents a node in a binary tree. Each Node has a val attribute that stores the value at that node, and left, and right attributes that point to the left and right children, respectively.
We also define a bfs function that performs a breadth-first search on the binary tree and returns a list of node values in the order they were visited. We use a deque from the built-in collections module to keep track of the nodes to be visited next. We start with the root node and add it to the queue. Then, we repeatedly dequeue the front node, add its value to the result list, and enqueue its children (if they exist) to the back of the queue.
To use this program, we create a binary tree by instantiating Node objects and setting their val, left, and right attributes. We then call bfs on the root node and output the result.
You are given the text ‘IPAddress’. Your task is to check if the given text ‘IPAddress’ is a valid ‘IPv4’ or not.
Conditions for a valid ‘IPv4’ are:
1. Text form of ‘IPAddress’ must be ‘a.b.c.d’
2. The values of a,b,c and d can vary from ‘0’ to ‘255’ and both ‘0’ and ‘255’ are inclusive.
- C++
C++
#include <bits/stdc++.h>
#include<string.h>
using namespace std;
bool isValidIPv4(string ipAddress) {
int n = ipAddress.length();
int count = 0;
int num = 0; // To store the current octet value
for (int i = 0; i < n; ++i) {
char currChar = ipAddress[i];
if (isdigit(currChar)) {
num = num * 10 + (currChar - '0');
// Check if the number is between 0 and 255
if (num < 0 || num > 255) {
return false;
}
} else if (currChar == '.') {
// Increment the octet count and reset the num for the next octet
++count;
num = 0;
} else {
// Non-digit character is not allowed
return false;
}
}
// Check if there are exactly 3 dots (4 octets)
return count == 3;
}
int main()
{
std::string ip1 = "100.100.110.101";
isValidIPv4(ip1) ? cout << "Valid IP address\n"
: cout << "Invalid IP address\n";
return 0;
}Output
Valid IP AddressWrite a program to detect cycle in an undirected graph using (BFS).
BFS is a traversal technique where we visit the nodes level-wise. It first visits the nodes of the same level and then moves to the next level.
The intuition is that we start from a node BFS level-wise. If we visit a single node twice, it means we came via two paths to end up at the same node. It implies there is a cycle in the graph.
To detect a cycle in an undirected graph using Breadth-First Search (BFS), you can maintain a visited array to keep track of visited vertices and a parent array to store the parent of each visited vertex. If you encounter a vertex that has already been visited and its parent is not the current vertex, it indicates the presence of a cycle.
Let's look at the Python implementation of the above problem.
- Python
Python
from collections import defaultdict
def isCyclic(graph, start):
queue = [(start, -1)] # (vertex, parent)
visited = set()
while queue:
vertex, parent = queue.pop(0)
visited.add(vertex)
for neighbour in graph[vertex]:
if neighbour not in visited:
queue.append((neighbor, vertex))
elif neighbour != parent:
return True
return False
# Example
graph = defaultdict(list)
graph[0] = [1, 2]
graph[1] = [0, 2]
graph[2] = [0, 1, 3]
graph[3] = [2]
start_vertex = 0
if isCyclic(graph, start_vertex):
print("Graph contains a cycle.")
else:
print("Graph does not contain a cycle.")Output:
Graph contains a cycle.
In this code, the isCyclic function takes an undirected graph represented as a dictionary and a starting vertex. It performs BFS on the graph starting from the start vertex. The visited set keeps track of visited vertices. If a neighbour is already visited and is not the parent of the current vertex, it means there is a cycle in the graph.
The time complexity of the cycle detection algorithm using Breadth-First Search (BFS) in an undirected graph is O(V + E), where V is the number of vertices and E is the number of edges in the graph. In the worst-case scenario, the algorithm will visit every vertex and every edge in the graph.
The space complexity of the algorithm is O(V), where V is the number of vertices. This is because, in the worst case, the algorithm needs to store the visited set, which can contain all vertices in the graph.
You are given a String and you need to find the length of the Longest Palindromic Substring.
- The idea is to generate all the even length and the odd length palindromes and keep the track of the longest palindromic substring seen so far.
- To generate the odd length palindrome, Fix a center and expand in both directions for longer palindromes, i.e. fix the i (index) pointer as the center and two indices, i1 = i + 1 and i2 = i - 1
- Compare i1 and i2. If they are equal then decrease the i2 pointer and increase the i1 pointer and find the maximum length.
- Use a similar technique to find the even-length palindromic substring.
- Take the two indices i1 = i and i2 = i - 1 and compare the characters at the i1 and i2 index and find the maximum length till all pairs of compared characters are equal and store the maximum length.
- Return the maximum length.
public class Solution {
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2){
return s;
}
for (int i = 0; i < len-1; i++) {
//assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i);
//assume even length.
extendPalindrome(s, i, i+1);
}
return s.substring(lo, lo + maxLen);
}
private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k))
{
j--;
k++;
}
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}
}
Time Complexity: The time complexity for the above code is O(N * N) because we are fixing the middle position ‘i’ and then calling extendPalindrome() function which runs in o(N) time.
Space Complexity: The space complexity for the above code is O(1) because we are using constant auxiliary space.
Explain Bellman-Ford Algorithm.
Bellman-Ford is a dynamic programming algorithm that iteratively relaxes the edges of the graph to find the shortest distances. Bellman-Ford’s algorithm works fine with negative edges as well as it is able to detect if the graph contains a negative cycle.
This program takes a graph represented as a dictionary, a graph, and a source vertex source. It initializes all distances as infinity except for the source vertex, which is set to 0.
The algorithm then iteratively relaxes the edges of the graph V-1 times. During each iteration, it checks if the distance from the source vertex to a neighbouring vertex can be reduced by considering the current path. If so, it updates the distance.
After V-1 iterations, the algorithm checks for negative cycles. If there is a negative cycle, it means that the graph contains a cycle with negative weight, and the algorithm cannot find the shortest distances.
Let's take a look at the python implementations of the above approach.
import sys
- Python
Python
def bellman_ford(graph, source):
distances = {v: sys.maxsize for v in graph} # Initialize distances with infinity
distances[source] = 0 # Distance from source to source is 0
# Relax edges repeatedly
for _ in range(len(graph) - 1):
for u, edges in graph.items():
for v, weight in edges.items():
new_dist = distances[u] + weight
if new_dist < distances[v]:
distances[v] = new_dist
# Check for negative cycles
for u, edges in graph.items():
for v, weight in edges.items():
if distances[u] + weight < distances[v]:
return None # Graph contains negative cycle
return distances
# Example
graph = {
'A': {'B': -1, 'C': 4},
'B': {'C': 3, 'D': 2, 'E': 2},
'C': {},
'D': {'B': 1, 'C': 5},
'E': {'D': -3},
}
source_vertex = 'A'
distances = bellman_ford(graph, source_vertex)
if distances is None:
print("Graph contains negative cycle")
else:
print("Shortest distances from", source_vertex + ":")
for vertex, distance in distances.items():
print(vertex, ":", distance)Output
Shortest distances from A:
A : 0
B : -1
C : 2
D : -2
E : 1
The time complexity of the Bellman-Ford algorithm is O(V * E), where V is the number of vertices and E is the number of edges in the graph. It performs relaxation for each edge V-1 times.
The space complexity is O(V) since the algorithm stores the distances in a dictionary with V entries.
Write a program to find the minimum path sum in a grid(matrix).
The program finds the minimum path sum in a grid represented as a 2D matrix. The minimum path sum is the smallest sum of numbers obtained by moving only right or down from the top-left cell to the bottom-right cell of the grid.
The program uses dynamic programming to compute the minimum path sums. It utilizes a 2D table, dp, where dp[i][j] represents the minimum path sum to reach the cell at coordinates (i, j).
Algorithm
- Initialize the first cell dp[0][0] as the value in the top-left cell of the grid.
- Initialize the first-row dp[0][j] by summing up the values in the first row of the grid and the previous cell's sum.
- Initialize the first column dp[i][0] by summing up the values in the first column of the grid and the previous cell's sum.
- Fill the rest of the dp table by taking the minimum of the previous cell's sum (from left or above) and adding the current cell's value.
- Return the value at the bottom-right cell of the dp table, which represents the minimum path sum.
Let's look at the python implementation of the following approach.
- Python
Python
def min_path_sum(grid):
m = len(grid)
n = len(grid[0])
# Create a 2D table to store the minimum path sums
dp = [[0] * n for _ in range(m)]
# Compute minimum path sums
dp[0][0] = grid[0][0]
for i in range(1, n):
dp[0][i] = dp[0][i - 1] + grid[0][i]
for j in range(1, m):
dp[j][0] = dp[j - 1][0] + grid[j][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[m - 1][n - 1]
# Example usage
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
min_sum = min_path_sum(grid)
print("Minimum Path Sum:", min_sum)
Output
Minimum Path Sum: 7
The time complexity of the program is O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because we fill the entire dp table by iterating through each cell once.
The space complexity of the program is O(m * n) as well since we create a dp table of the same size as the input grid.
What is the difference between a stack and a queue? (Data Structure Interview Questions and Answers (2024)
The difference between a stack and a queue is given below.
Key Points | Stack | Queue |
Methods or Approach used | LIFO (Last In, First Out). | FIFO (First In, First Out). |
Insertion | Add element to the top (push). | Add element to the rear (enqueue). |
Deletion | Remove element from the top (pop). | Remove element from the front (dequeue). |
Access | Access only the top element. | Access both the front and rear elements. |
Use cases | Backtracking algorithms, expression evaluation, browser history. | Job scheduling, printing, buffering. |
Example | Undo/Redo operations, Call stack in programming. | Ticket queue, Message queue. |
You are given an unsorted array/list 'ARR' of 'N' integers. Your task is to return the length of the longest consecutive sequence. The consecutive sequence is in the form ['NUM', NUM' + 1, 'NUM' +2, "NUM' + L], where 'NUM' is the starting integer of the sequence and L' + 1 is the length of the sequence.
Input: [9,5,4,9,10,10,6]
Output: 3
Explanation: The longest consecutive sequence is [4,5,6].
We will follow the given algorithm to solve this
- The idea is to sort the array, then iterate through the array and find the longest subarray containing consecutive elements.
- We first initialize the variable ‘COUNT’ = 0, which stores the length of the consecutive sequence, and ‘MX’ = 0, which stores the longest length of the consecutive subsequence.
- Now run a loop and check if ‘ARR[i - 1]’ + 1 is equal to ‘ARR[i]’ then it will include in the current consecutive subsequence by increment ‘COUNT’ by 1.
- If ‘ARR[i - 1]’ is equal to ‘ARR[i]’, then it means it shouldn’t be considered in consecutive sequence because the consecutive sequence is of the form ['NUM', 'NUM' + 1, 'NUM' + 2,...,'NUM' + L].
- Else If ‘ARR[i - 1]’ + 1 is not equal to ‘ARR[i]’, then we set ‘COUNT’ to 1. For finding the longest length, we update ‘MX’ with a maximum of ‘COUNT’ and ‘MX’.
#include <algorithm>
int lengthOfLongestConsecutiveSequence(vector<int> &arr, int n) {
// Sort the given array in ascending order.
sort(arr.begin(), arr.end());
// To store length of longest consecutive sequence.
int mx = 0;
// To store the length of the current consecutive Sequence.
int count = 0
for (int i = 0; i < n; i++) {
// Check if previous value is consecutive to the current value.
if (i > 0 && (arr[i] == arr[i - 1] + 1)) {
count++;
}
// Skip if the current value is equals to the previous value.
else if (i > 0 && arr[i] == arr[i - 1]) {
continue;
}
// Reseting count for next upcoming consecutive sequence.
else {
count = 1;
}
mx = max(mx, count);
}
return mx;
}What is an IP address, and how do networking protocols use IP addresses?
An IP address is a unique identifier assigned to every device that connects to a network. It is a numerical label that allows devices to communicate with each other over the internet or a local network. An IP address consists of a network ID and a host ID, separated by dots. The network ID identifies the network, and the host ID identifies a particular device on the network.
Networking protocols use IP addresses to route data packets between devices. For example, when a computer wants to send data to another device on the network or internet, it needs the IP address of the recipient device to send the data to the correct destination.
IP addresses are divided into classes based on their range. Class A: 1-126, Class B: 128-191, Class C: 192-223.
An example in IP address: 192.168.1.10 is a 32-bit address used in IPv4. It is represented in binary as 11000000.10101000.00000001.00001010. It belongs to class A.
Suppose you are given an integer ‘K’ and a string array of size ‘N’ where each string may represent a very large number up to 100 digits. Your task is to print the Kth largest number present in the array.
For example, given an array ARR = { “213” “34” ”566” “74” ”22”} and we need to find the 2nd largest number present in this array. In this case, 566 is the largest number, and 213 is the 2nd largest number. Hence 213 is our answer.
Approach
The naive approach to solving this problem is converting all the strings to integers and then sorting the array and returning the kth largest integer. This approach is good for small numbers, but if the size of the string exceeds 18, then this approach fails as the range of long is 10^18, as it is not possible to convert such strings to integers.
The correct approach to solve this problem is based on the Greedy Algorithm. Here we sort all the strings bypassing the custom compare function in our sort function.
Algorithm
- Create custom function ‘cmp’ which takes two strings.
- If the value of the 1st string is greater than the 2nd one, then return the 1st one else, return the 2nd one.
- Pass this custom function in our inbuilt sort function as the third argument.
- Call the sort function.
- Print the Kth value of the array.
Program
- C++
C++
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// Custom function to overload the sort function.
bool cmp(string &s1, string &s2)
{
// if both the strings have the same length then return max.
if (s1.size() == s2.size())
return s1 > s2;
// if both the strings have different lengths.
return s1.size() > s2.size();
}
// Function to find the Kth largest number in the vector of strings.
void Kthlargest(int n, int k, vector<string> &vec)
{
// Sort the vector by passing a custom function.
sort(vec.begin(), vec.end(), cmp);
string largest = vec[k - 1];
// Printing the K-th largest number in the array.
cout << largest;
}
int main()
{
// Variable 'N' to store the number of elements in the array and variable 'K' to indicate the Kth largest number.
int n, k;
cin >> n;
// Declaring vector of size 'N'.
vector<string> vec(n);
// Taking vector input.
for (int i = 0; i < n; i++)
cin >> vec[i];
cin >> k;
// Calling function 'Kthlargest()';
Kthlargest(n, k, vec);
return 0;
}Output
Input
7
70 40 100 10 55 85 120
3
Output
85
134+ registered 
