Microsoft Corporation
60+ Carelon Global Solutions Interview Questions and Answers
Q1. Mean, Median, Mode Calculation
You are given an array 'ARR' consisting of 'N' integers. Your task is to calculate the three statistical measures for the given array:
- Mean - Implement the function
mean()
to cal...read more
Implement functions to calculate mean, median, and mode of an array of integers.
Implement a function mean() to calculate the mean of the array by summing all elements and dividing by the total count.
Implement a function median() to calculate the median of the array by sorting the array and finding the middle element(s).
Implement a function mode() to find the mode of the array by counting frequencies and returning the smallest element with the highest frequency.
Q2. Dice Throw Problem Statement
You are provided with D
dice, each having F
faces numbered 1 to F
, inclusive. Your task is to determine the number of possible ways to roll the dice such that the sum of the face-up...read more
The problem involves finding the number of ways to achieve a target sum by rolling a given number of dice with a certain number of faces.
Use dynamic programming to keep track of the number of ways to achieve each sum from 1 to the target sum.
Iterate through the dice and faces to update the number of ways to reach each sum.
Return the number of ways to achieve the target sum modulo 10^9 + 7.
Q3. Nth Term of Geometric Progression (GP) Series
Determine the Nth term of a geometric progression (GP) series given the first term, common ratio, and the term number.
Explanation:
The general form of a GP series ...read more
Calculate the Nth term of a geometric progression series given the first term, common ratio, and term number.
Use the formula for the Nth term of a GP series: A * (R^(N-1))
Ensure to take the modulo 10^9 + 7 as the output
Handle multiple test cases efficiently within the given time limit
Q4. Arithmetic Expression Evaluation Problem Statement
You are provided with a string expression
consisting of characters '+', '-', '*', '/', '(', ')' and digits '0' to '9', representing an arithmetic expression in...read more
Evaluate arithmetic expressions in infix notation with given operators and precedence rules.
Parse the infix expression to postfix using a stack.
Evaluate the postfix expression using a stack.
Handle operators precedence and parentheses while evaluating.
Ensure no division by zero cases and operands fit in 32-bit integer.
Q5. Distinct Subsequences of a String
Given a string S
of length N
that may contain duplicate alphabets, your task is to compute the count of distinct subsequences of this string.
Example:
Input:
S = "deed"
Output:...read more
Compute the count of distinct subsequences of a string with possible duplicates.
Use dynamic programming to keep track of distinct subsequences.
Consider the cases where the current character is included or excluded in the subsequence.
Use a hashmap to store the last occurrence index of each character to handle duplicates efficiently.
Q6. Delete Kth Node from End of Linked List
This problem requires you to delete the Kth node from the end of a given singly linked list with N nodes containing integer data.
You are asked to efficiently remove this...read more
To delete the Kth node from the end of a singly linked list efficiently without finding the length of the list and using O(1) extra space.
Use two pointers approach - one pointer moves K steps ahead of the other.
When the first pointer reaches the end, the second pointer will be at the Kth node from the end.
Adjust the pointers to remove the Kth node efficiently.
Ensure to handle edge cases like deleting the head or tail node.
Example: For input 1 -> 2 -> 3 -> 4 -> NULL and K = 2,...read more
Q7. Identical Trees Problem Statement
Given two binary trees with 'N' and 'M' nodes respectively, determine if the two trees are identical. Return true
if they are identical, otherwise return false
.
Input:
The firs...read more
Check if two binary trees are identical by comparing their nodes in level order.
Traverse both trees in level order and compare corresponding nodes for equality
Use a queue to keep track of nodes to be compared
Return false if nodes are not equal or if one tree has more nodes than the other
Q8. Rotate Matrix by 90 Degrees Problem Statement
Given a square matrix 'MATRIX' of non-negative integers, rotate the matrix by 90 degrees in an anti-clockwise direction using only constant extra space.
Input:
The ...read more
Rotate a square matrix by 90 degrees in an anti-clockwise direction using constant extra space.
Iterate through each layer of the matrix from outer to inner layers
Swap elements in groups of 4 to rotate the matrix
Handle odd-sized matrices separately by adjusting the loop boundaries
Q9. Longest Common Prefix After Rotation
You are given two strings 'A' and 'B'. While string 'A' is constant, you may apply any number of left shift operations to string 'B'.
Explanation:
Your task is to calculate ...read more
Calculate minimum left shift operations to achieve longest common prefix between two strings.
Apply left shift operations to string B to find longest common prefix with string A
Count number of shifts needed to achieve longest common prefix
Handle circular rotation of characters in string B
Return minimum number of left shift operations for each test case
Q10. Connect Nodes at the Same Level
Given a binary tree where each node has at most two children, your task is to connect all adjacent nodes at the same level. You should populate each node's 'next' pointer to its ...read more
Connect adjacent nodes at the same level in a binary tree by populating each node's 'next' pointer.
Traverse the tree level by level using a queue.
For each level, connect nodes from left to right using their 'next' pointers.
Set the 'next' pointer of the rightmost node in each level to NULL.
Example: For the given binary tree, connect nodes 2->3, 4->5, 5->6, and set 1, 3, 6 'next' pointers to NULL.
Q11. Longest Palindromic Subsequence Problem Statement
Given a string A
consisting of lowercase English letters, determine the length of the longest palindromic subsequence within A
.
Explanation:
- A subsequence is d...read more
The problem involves finding the length of the longest palindromic subsequence in a given string of lowercase English letters.
Iterate through the string and create a 2D array to store the lengths of palindromic subsequences for each substring.
Use dynamic programming to fill the array based on the characters in the string.
Consider the base cases where the length of the substring is 1 or 2.
Update the array based on whether the characters at the start and end of the substring ma...read more
Q12. Sort Stack Problem Statement
You are given a stack S
. Your task is to sort the stack recursively in descending order.
Constraints:
- Looping through the stack is not allowed.
- Return the stack sorted in descendin...read more
Sort a given stack in descending order recursively without using loops.
Use recursion to pop elements from the stack and insert them in the correct position.
Maintain a temporary stack to hold elements while sorting.
Compare the top element of the stack with the top element of the temporary stack to insert in descending order.
Q13. Problem Statement: Sibling Nodes
You are provided with a Binary Tree consisting of 'N' nodes, where each node holds an integer value. Your objective is to identify and list all nodes that do not possess a sibli...read more
Identify and list nodes in a Binary Tree that do not have a sibling.
Traverse the Binary Tree in level order and keep track of nodes without siblings.
Check if each node has a sibling by comparing with its parent's other child.
Output the values of nodes without siblings in ascending order.
Handle cases where the root node is considered a sibling node.
Q14. Minimum Operations Problem Statement
You are given an array 'ARR'
of size 'N'
consisting of positive integers. Your task is to determine the minimum number of operations required to make all elements in the arr...read more
Determine minimum operations to make all array elements equal using addition, subtraction, multiplication, or division.
Iterate through array to find the maximum and minimum elements.
Calculate the difference between maximum and minimum elements.
The minimum number of operations needed is the difference between the maximum and minimum elements.
Q15. Median of Two Sorted Arrays
Given two sorted arrays A
and B
of sizes N
and M
, find the median of the merged array formed by combining arrays A
and B
. If the total number of elements, N + M
, is even, the median ...read more
Find the median of two sorted arrays by merging them and calculating the middle element(s).
Merge the two sorted arrays into one sorted array.
Calculate the median based on the total number of elements in the merged array.
If the total number of elements is even, take the mean of the two middle elements as the median.
Q16. Number of Islands Problem Statement
You are given a non-empty grid that consists of only 0s and 1s. Your task is to determine the number of islands in this grid.
An island is defined as a group of 1s (represent...read more
The task is to determine the number of islands in a grid of 0s and 1s connected horizontally, vertically, or diagonally.
Iterate through the grid and perform depth-first search (DFS) to find connected 1s forming islands
Mark visited cells to avoid counting the same island multiple times
Count the number of islands found during DFS traversal
Q17. N Queens Problem
Given an integer N
, find all possible placements of N
queens on an N x N
chessboard such that no two queens threaten each other.
Explanation:
A queen can attack another queen if they are in the...read more
The N Queens Problem involves finding all possible placements of N queens on an N x N chessboard without threatening each other.
Use backtracking algorithm to explore all possible configurations
Check if the current placement is safe by verifying rows, columns, and diagonals
Print valid configurations where queens do not attack each other
Q18. Pair Sum Problem Statement
You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to find and return a list of all pairs of elements where each sum of a pair equals 'S'.
Note:
Each pa...read more
Find pairs of elements in an array that sum up to a given value, sorted in a specific order.
Iterate through the array and for each element, check if the complement (S - current element) exists in a set.
If the complement exists, add the pair to the result list.
Sort the result list based on the criteria mentioned in the problem statement.
Q19. Minimum Number of Platforms Problem
Your task is to determine the minimum number of platforms required at a railway station so that no train has to wait.
Explanation:
Given two arrays:
AT
- representing the ar...read more
Determine the minimum number of platforms needed at a railway station so that no train has to wait.
Sort the arrival and departure times arrays in ascending order.
Use two pointers to iterate through the arrays and keep track of the number of platforms needed.
Increment the number of platforms needed when a train arrives and decrement when a train departs.
Return the maximum number of platforms needed at any point.
Q20. Mirror String Problem Statement
Given a string S
containing only uppercase English characters, determine if S
is identical to its reflection in the mirror.
Example:
Input:
S = "AMAMA"
Output:
YES
Explanation:
T...read more
Determine if a given string is identical to its reflection in the mirror.
Iterate through the string and compare characters from start and end simultaneously.
If characters are not equal, return 'NO'.
If all characters match, return 'YES'.
Q21. Maximum Product Subarray Problem Statement
Given an array of integers, determine the contiguous subarray that produces the maximum product of its elements.
Explanation:
A subarray can be derived from the origin...read more
Find the contiguous subarray with the maximum product of elements in an array.
Iterate through the array and keep track of the maximum and minimum product ending at each index.
Update the maximum product by taking the maximum of current element, current element * previous maximum, and current element * previous minimum.
Update the minimum product by taking the minimum of current element, current element * previous maximum, and current element * previous minimum.
Return the maximu...read more
Q22. Quadratic Equation Root Finder
Given three integers A
, B
, and C
representing the coefficients of a quadratic equation A*X^2 + B*X + C = 0, your task is to determine the real roots of the equation. If no real ro...read more
Given coefficients of a quadratic equation, find the real roots or return -1 if no real roots exist.
Calculate the discriminant (B^2 - 4AC) to determine the nature of roots.
If discriminant is positive, roots are real and distinct. If zero, roots are real and repeated. If negative, roots are imaginary.
Use the quadratic formula to find the roots: (-B ± sqrt(discriminant)) / 2A.
Return the roots as integers, rounding down if necessary.
Q23. Trapping Rain Water Problem Statement
You are given a long type array/list ARR
of size N
, representing an elevation map. The value ARR[i]
denotes the elevation of the ith
bar. Your task is to determine the tota...read more
Calculate the total amount of rainwater that can be trapped between given elevations in an array.
Iterate through the array and calculate the maximum height on the left and right of each bar.
Calculate the amount of water that can be trapped at each bar by taking the minimum of the maximum heights on the left and right.
Sum up the trapped water at each bar to get the total trapped water for the entire array.
Q24. Travelling Salesman Problem
Given a list of cities numbered from 0 to N-1 and a matrix DISTANCE
consisting of 'N' rows and 'N' columns, representing the distances between each pair of cities, find the shortest ...read more
Implement a function to find the shortest route visiting each city exactly once and returning to the starting city.
Use backtracking to explore all possible routes and find the minimum distance.
Keep track of visited cities to ensure each city is visited exactly once.
Consider pruning techniques like dynamic programming to optimize the solution.
Example: Start at city 0, visit cities 1 and 2 in any order, and return to city 0 for the first test case.
Example: Start at city 0, visi...read more
Q25. LCA of Binary Tree Problem Statement
You are given a binary tree of distinct integers, along with two nodes, ‘X’ and ‘Y’. Your task is to determine the Lowest Common Ancestor (LCA) of ‘X’ and ‘Y’.
The LCA of tw...read more
Find the Lowest Common Ancestor of two nodes in a binary tree.
Traverse the binary tree to find the paths from the root to nodes X and Y.
Compare the paths to find the last common node, which is the LCA.
Handle cases where one node is an ancestor of the other.
Consider using recursion to solve the problem efficiently.
Q26. Possible Words From A Phone Number
After years of research, Ninja has invented a time machine and found himself in the era where T9 keypads were commonly used in mobile phones. Being curious, Ninja seeks to det...read more
Given a string of digits from 2 to 9, determine all possible strings that can be generated using T9 keypad letter mappings.
Create a mapping of digits to corresponding letters on a T9 keypad
Use recursion to generate all possible combinations of letters for the input string
Sort the generated strings lexicographically
Return the array of generated strings
Q27. Find the Largest Common Ancestor Problem
Given a binary search tree and two distinct nodes within it, the task is to determine their largest common ancestor. This ancestor is defined as the common ancestor with...read more
Find the largest common ancestor of two nodes in a binary search tree.
Implement a function to find the largest common ancestor of two nodes in a binary search tree.
Use level order traversal input to construct the tree.
Ensure both nodes are present in the tree.
Return the value of the largest common ancestor.
Q28. Ways To Make Coin Change
Given an infinite supply of coins of varying denominations, determine the total number of ways to make change for a specified value using these coins. If it's not possible to make the c...read more
The task is to find the total number of ways to make change for a specified value using given denominations.
Use dynamic programming to solve this problem efficiently.
Create a 2D array to store the number of ways to make change for each value up to the specified value.
Iterate through each denomination and update the array accordingly.
The final answer will be the value at the last index of the array.
Q29. Validate BST Problem Statement
Given a binary tree with N
nodes, determine whether the tree is a Binary Search Tree (BST). If it is a BST, return true
; otherwise, return false
.
A binary search tree (BST) is a b...read more
Validate if a given binary tree is a Binary Search Tree (BST) or not.
Check if the left subtree of a node contains only nodes with data less than the node's data.
Check if the right subtree of a node contains only nodes with data greater than the node's data.
Ensure that both the left and right subtrees are also binary search trees.
Q30. Ninja's Dance Competition Pairing Problem
Ninja is organizing a dance competition and wants to pair participants using a unique method. Each participant chooses a number upon entry, and Ninja selects a number ‘...read more
Find the number of distinct pairs of participants with a given difference in their chosen numbers.
Iterate through the list of numbers and check for pairs with the required difference 'K'.
Use a hash set to keep track of unique pairs to avoid counting duplicates.
Return the size of the hash set as the number of distinct pairs.
Q31. Longest Palindromic Substring Problem Statement
You are provided with a string STR
of length N
. The goal is to identify the longest palindromic substring within this string. In cases where multiple palindromic ...read more
Given a string, find the longest palindromic substring, prioritizing the one with the smallest start index.
Iterate through the string and expand around each character to find palindromes
Keep track of the longest palindrome found and its starting index
Return the longest palindromic substring with the smallest start index
Q32. Smallest Window Problem Statement
Given two strings S
and X
containing random characters, the task is to find the smallest substring in S
which contains all the characters present in X
.
Input:
The first line co...read more
Find the smallest substring in a given string that contains all characters from another given string.
Use a sliding window approach to find the smallest window in S that contains all characters in X.
Maintain a frequency map for characters in X and a window map for characters in the current window.
Slide the window to the right, updating the window map and shrinking the window from the left if all characters in X are present.
Keep track of the smallest window found so far.
Return ...read more
Q33. Find K'th Character of Decrypted String
You are given an encrypted string where repeated substrings are represented by the substring followed by its count. Your task is to find the K'th character of the decrypt...read more
Given an encrypted string with repeated substrings represented by counts, find the K'th character of the decrypted string.
Parse the encrypted string to extract substrings and their counts
Iterate through the decrypted string to find the K'th character
Handle cases where counts are more than one digit or in parts
Q34. Maximum Subarray Sum Problem Statement
Given an array arr
of length N
consisting of integers, find the sum of the subarray (including empty subarray) with the maximum sum among all subarrays.
Explanation:
A sub...read more
Find the sum of the subarray with the maximum sum among all subarrays in an array of integers.
Iterate through the array and keep track of the maximum sum subarray seen so far.
Use Kadane's algorithm to efficiently find the maximum subarray sum.
Consider the case where all elements in the array are negative.
Handle the case where the array contains only one element.
Q35. Total Area of Overlapping Rectangles Problem Statement
Determine the total area covered by two given rectangles on a 2-D coordinate plane, which may have an overlapping area.
Input:
The first line contains an i...read more
Calculate the total area covered by two overlapping rectangles on a 2-D coordinate plane.
Parse input coordinates for two rectangles
Calculate the area of each rectangle
Find the overlapping area by determining the intersection of the rectangles
Calculate the total area by adding the areas of both rectangles and subtracting the overlapping area
Q36. Infix to Postfix Conversion
Convert a given infix expression, represented as a string EXP
, into its equivalent postfix expression.
Explanation:
An infix expression is formatted as a op b
where the operator is p...read more
Convert infix expression to postfix expression.
Use a stack to keep track of operators and operands.
Follow the rules of precedence for operators.
Handle parentheses to ensure correct order of operations.
Q37. Most Frequent Word Problem Statement
You are given two strings 'A' and 'B' composed of words separated by spaces. Your task is to determine the most frequent and lexicographically smallest word in string 'A' th...read more
Find the most frequent and lexicographically smallest word in string 'A' that is not present in string 'B'.
Split strings 'A' and 'B' into words
Count frequency of each word in 'A'
Check if word is not in 'B' and is the most frequent and lexicographically smallest
Return the word or -1 if no such word exists
Q38. Spiral Matrix Problem Statement
You are given a N x M
matrix of integers. Your task is to return the spiral path of the matrix elements.
Input
The first line contains an integer 'T' which denotes the number of ...read more
The task is to return the spiral path of elements in a given matrix.
Iterate through the matrix in a spiral path by keeping track of boundaries.
Print elements in the order of top, right, bottom, and left sides of the matrix.
Handle cases where the matrix is not a square (N != M) separately.
Consider edge cases like single row, single column, and empty matrix.
Q39. Swap Numbers Without Temporary Variable
Your task is to interchange the values of two numbers given as variables 'X' and 'Y' without using a temporary variable or any additional variable.
Explanation:
You need ...read more
Swap two numbers without using a temporary variable.
Use bitwise XOR operation to swap the values of X and Y without using a temporary variable.
The XOR operation works by flipping the bits of the numbers.
After swapping, X = X XOR Y and Y = X XOR Y.
Finally, X = X XOR Y to get the original value of Y in X.
Q40. Minimum Steps for a Knight to Reach Target
Given a square chessboard of size 'N x N', determine the minimum number of moves a Knight requires to reach a specified target position from its initial position.
Expl...read more
Calculate minimum steps for a Knight to reach target position on a chessboard.
Use BFS algorithm to find shortest path from Knight's starting position to target position.
Consider all possible moves of the Knight on the chessboard.
Track visited positions to avoid revisiting them during traversal.
Q41. Cycle Detection in a Singly Linked List
Determine if a given singly linked list of integers forms a cycle or not.
A cycle in a linked list occurs when a node's next
points back to a previous node in the list. T...read more
Detect if a singly linked list forms a cycle by checking if a node's next pointer points back to a previous node.
Use Floyd's Cycle Detection Algorithm to determine if there is a cycle in the linked list.
Maintain two pointers, one moving at twice the speed of the other.
If the two pointers meet at any point, there is a cycle in the linked list.
Q42. Boundary Traversal of a Binary Tree
Given a binary tree of integers, your task is to return the boundary nodes of the tree in Anti-Clockwise direction starting from the root node.
Input:
The first line contains...read more
Return the boundary nodes of a binary tree in Anti-Clockwise direction starting from the root node.
Traverse the left boundary nodes in a top-down manner
Traverse the leaf nodes in a left-right manner
Traverse the right boundary nodes in a bottom-up manner
Avoid duplicates in boundary nodes
Q43. Minimum Subarray with Required Sum Problem Statement
Given an array of positive integers ARR
and an integer X
, determine the minimum length subarray where the sum of its elements is strictly greater than X
.
Not...read more
Find the minimum length subarray with sum greater than X in a given array.
Iterate through the array while maintaining a sliding window to find the subarray with sum greater than X.
Keep track of the minimum length subarray found so far.
Return the subarray with the minimum length and sum greater than X.
Q44. Palindrome Partitioning Problem Statement
Given a string S
, the task is to partition S
so that every substring in the partition is a palindrome. Return all possible palindrome partitions of S
.
Example:
Input:
S...read more
Given a string, partition it into palindromic substrings and return all possible partitions.
Use backtracking to generate all possible partitions by checking if each substring is a palindrome.
Keep track of the current partition and add it to the result when the entire string is processed.
Optimize by using memoization to store the results of subproblems to avoid redundant calculations.
Q45. Flatten the Multi-Level Linked List
You are provided with a multi-level linked list containing N
nodes. Each node has pointers next and child, which could potentially point to additional nodes. The task is to f...read more
Flatten a multi-level linked list into a single-level linked list and return the head of the singly linked list.
Traverse the multi-level linked list using depth-first search (DFS).
Maintain a stack to keep track of nodes with child pointers.
Connect the child nodes to the current node's next pointer and update the current node.
Continue this process until all nodes are flattened into a single-level linked list.
Q46. Problem: Sort an Array of 0s, 1s, and 2s
Given an array/list ARR
consisting of integers where each element is either 0, 1, or 2, your task is to sort this array in increasing order.
Input:
The input starts with...read more
Sort an array of 0s, 1s, and 2s in increasing order.
Use a three-pointer approach to partition the array into sections for 0s, 1s, and 2s.
Iterate through the array and swap elements based on their values and the pointers.
After sorting, the array will have 0s at the beginning, followed by 1s, and then 2s.
Q47. LRU Cache Design Question
Design a data structure for a Least Recently Used (LRU) cache that supports the following operations:
1. get(key)
- Return the value of the key if it exists in the cache; otherwise, re...read more
Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.
Implement a doubly linked list to maintain the order of keys based on their recent usage.
Use a hashmap to store key-value pairs for quick access and update.
When capacity is reached, evict the least recently used item before inserting a new item.
Update the order of keys in the linked list whenever a key is accessed or updated.
Handle get and put operations effic...read more
Q48. Reverse Stack with Recursion
Reverse a given stack of integers using recursion. You must accomplish this without utilizing extra space beyond the internal stack space used by recursion. Additionally, you must r...read more
Reverse a given stack of integers using recursion without using extra space or loops.
Use recursion to pop all elements from the original stack and store them in function call stack.
Once the stack is empty, push the elements back in reverse order using recursion.
Make use of the top(), pop(), and push() stack methods provided.
Example: If the input stack is [1, 2, 3], after reversal it should be [3, 2, 1].
Q49. Division to N Decimal Places
Your task is to compute the division of two integers, X / Y, and output the result formatted to contain exactly N decimal places.
Input:
The first line contains an integer ‘T’, repr...read more
Compute the division of two integers and output the result formatted to contain exactly N decimal places.
Read the input values for X, Y, and N
Perform the division X / Y
Format the result to contain exactly N decimal places
Output the result as a string with N decimal places
Q50. Find All Triplets with Zero Sum
Given an array Arr
consisting of N
integers, find all distinct triplets in the array that sum up to zero.
Explanation:
An array is said to have a triplet {Arr[i], Arr[j], Arr[k]}...read more
Find all distinct triplets in an array that sum up to zero.
Use a nested loop to iterate through all possible triplets.
Sort the array to easily identify duplicates and skip them.
Use two-pointer technique to find the remaining element for each pair.
Handle edge cases like duplicates and empty list of triplets.
Return the list of triplets found in any order.
Q51. Regular Expression Match Problem Statement
Given a string str
and a string pat
, where str
may contain wildcard characters '?' and '*'.
If a character is '?', it can be replaced with any single character. If a c...read more
Given a string with wildcard characters, determine if it can be transformed to match another string.
Iterate through both strings simultaneously, handling wildcard characters '?' and '*' accordingly.
Use dynamic programming to keep track of matching characters.
Handle cases where '*' can match an empty sequence or multiple characters.
Return true if at the end both strings match, false otherwise.
Q52. Sort 0 1 2 Problem Statement
Given an integer array arr
of size 'N' containing only 0s, 1s, and 2s, write an algorithm to sort the array.
Input:
The first line contains an integer 'T' representing the number of...read more
Sort an array of 0s, 1s, and 2s in linear time complexity.
Use three pointers to keep track of the positions of 0s, 1s, and 2s in the array.
Iterate through the array and swap elements based on the values encountered.
This approach sorts the array in a single scan without using any extra space.
Q53. Angle Calculation Between Clock Hands
Given a specific time in hours and minutes, your task is to calculate the smallest possible angle between the hour hand and the minute hand of a clock.
Example:
Input:
T = ...read more
Calculate the smallest angle between the hour and minute hands of a clock given a specific time.
Calculate the angle formed by the hour hand with respect to 12 o'clock position
Calculate the angle formed by the minute hand with respect to 12 o'clock position
Find the absolute difference between the two angles and take the minimum of the two possible angles
Return the floor value of the calculated angle
Q54. Minimum Operation Needed to Convert to the Given String
You are given two strings str1
and str2
. Determine the minimum number of operations required to transform str1
into str2
.
Explanation:
An operation is def...read more
Determine the minimum number of operations needed to transform one string into another by moving characters to the end.
Iterate through each character in str1 and check if it matches the first character in str2.
If a match is found, calculate the number of operations needed to move the characters to the end.
Return the minimum number of operations needed for each test case, or -1 if transformation is not possible.
Q55. Diagonal Traversal of a Binary Tree
You are provided with a binary tree composed of integers. Your task is to determine all the diagonal paths within the binary tree. A diagonal path is defined as a sequence of...read more
Implement a function to find diagonal paths in a binary tree.
Traverse the binary tree in a diagonal manner, starting from the rightmost path and moving downwards.
Use a hashmap to store nodes at each diagonal level and then traverse the hashmap to get the diagonal paths.
Handle the case where nodes without left or right children are present by using -1.
Return the diagonal traversal as a single line with nodes arranged by their diagonal paths.
Q56. Total Number of BSTs Using Array Elements as Root Node
You are given a sequence array 'ARR' of 'N' integers. For each ARR[i] where 0 <= 'i' < 'N', your task is to find the number of Binary Search Trees (BST) po...read more
Find the number of BSTs possible with each element of an array as the root node.
Iterate through each element of the array and calculate the number of BSTs possible with that element as the root node.
Use dynamic programming to calculate the number of BSTs for each element efficiently.
Output the results modulo (10^9 + 7) to handle large numbers.
Q57. Binary Search Tree Insertion
Given the root node of a binary search tree and a positive integer, you need to insert a new node with the given value into the BST so that the resulting tree maintains the properti...read more
Insert a new node with a given value into a binary search tree while maintaining the properties of a BST.
Traverse the BST starting from the root node to find the correct position for insertion.
Compare the value to be inserted with the current node's value to determine whether to go left or right.
Create a new node with the given value and insert it at the appropriate position in the BST.
Ensure that the resulting tree maintains the binary search tree properties after insertion.
Q58. Reverse a Linked List Problem Statement
Given a singly linked list of integers, your task is to return the head of the reversed linked list.
Example:
Input:
The given linked list is 1 -> 2 -> 3 -> 4-> NULL.
Out...read more
Reverse a singly linked list of integers and return the head of the reversed linked list.
Iterate through the linked list and reverse the pointers to point to the previous node instead of the next node.
Keep track of the previous, current, and next nodes while reversing the linked list.
Update the head of the reversed linked list to be the last node encountered.
Ensure to handle edge cases like an empty linked list or a linked list with only one node.
Q59. Valid Parentheses Problem Statement
Given a string 'STR' consisting solely of the characters “{”, “}”, “(”, “)”, “[” and “]”, determine if the parentheses are balanced.
Input:
The first line contains an integer...read more
The task is to determine if a given string consisting of parentheses is balanced or not.
Use a stack data structure to keep track of opening parentheses.
Iterate through the string and push opening parentheses onto the stack.
When encountering a closing parenthesis, pop the top element from the stack and check if it matches the corresponding opening parenthesis.
If the stack is empty at the end of the iteration and all parentheses have been matched, the string is balanced.
If the ...read more
Optimal strategy to minimize number of drops to find highest floor an egg can be dropped without breaking.
Start by dropping the first egg from a lower floor and incrementally increase the floor until it breaks.
Once the first egg breaks, use the second egg to perform a binary search between the last successful drop and the floor below the breaking point.
This strategy ensures the minimum number of drops required to find the highest floor.
Mutexes and semaphores are synchronization mechanisms used in concurrent programming to control access to shared resources.
Mutexes are used to provide mutual exclusion, allowing only one thread to access a resource at a time.
Semaphores can be used to control access to a resource by multiple threads, with the ability to allow a certain number of threads to access it simultaneously.
Mutexes are binary semaphores with a lock and unlock mechanism.
Semaphores can have a count greate...read more
Design an elevator system for a single building with N floors.
Create a data structure to track the current floor of the elevator and the requested floors.
Implement algorithms for elevator movement such as FIFO, SCAN, or LOOK.
Consider factors like peak hours, weight capacity, and emergency situations.
Include features like door open/close buttons, emergency stop button, and floor selection panel.
- Assumptions
- System considerations
- Design components
Design a search engine for a global retail application.
Assumptions: assume the search engine will need to handle a large volume of products and users from around the world
System considerations: scalability, speed, relevance of search results, multi-language support
Design components: indexing system, query processing, ranking algorithm, user interface
Q64. minimum number of operations required to set all elements of a binary matrix
The minimum number of operations required to set all elements of a binary matrix to 0 or 1.
Count the number of 0s and 1s in each row and column separately.
For each row and column, choose the minimum between the count of 0s and 1s as the number of operations needed.
Sum up the minimum operations for all rows and columns to get the total minimum operations.
Q65. Print all permutations of a string
Print all permutations of a string
Use recursion to swap each character with every other character in the string
Repeat the process for the remaining characters
Stop when there are no more characters to swap
Use a set to avoid duplicates
Q66. What is ts & why we should use over js
TypeScript (ts) is a superset of JavaScript (js) that adds static typing and other features to improve code quality and maintainability.
TypeScript provides static typing, which helps catch errors at compile time rather than runtime.
TypeScript supports modern JavaScript features like classes, interfaces, and modules.
TypeScript can be transpiled into JavaScript, making it compatible with all browsers and environments.
TypeScript has a rich ecosystem with tools like TypeScript co...read more
More about working at Microsoft Corporation
Interview Process at Carelon Global Solutions
Top Software Developer Intern Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month