MakeMyTrip Software Developer Interview Questions and Answers for Experienced

Convert a sorted array to balanced binary search tree

• Find the middle element of the array and make it the root of the tree

• Recursively construct the left subtree using the left half of the array

• Recursively construct the right subtree using the right half of the array

• Repeat until all elements are added to the tree

Reverse a singly linked list in groups of k in­place

• Divide the linked list into groups of k nodes

• Reverse each group of k nodes

• Connect the reversed groups to form the final linked list

A recursive routine to calculate a ^ n

• The base case is when n is 0, in which case the result is 1

• For any other value of n, the result is a multiplied by the result of a^(n-1)

• The recursive function should call itself with a^(n-1) as the new input

Design optimal data structure for never-ending stream of numbers for insertion, deletion, searching, kth largest and kth smallest.

• Use a balanced binary search tree like AVL or Red-Black tree for efficient insertion, deletion, and searching.

• Maintain two heaps, one for kth largest and one for kth smallest.

• For finding kth largest, use a min heap of size k and for kth smallest, use a max heap of size k.

• Alternatively, use a...read more

Search an element in sorted rotated array.

• Use binary search to find the pivot point where the array is rotated.

• Divide the array into two subarrays and perform binary search on the appropriate subarray.

• Handle the cases where the target element is at the pivot point or not present in the array.

Find the Kth largest element in an array.

• Sort the array in descending order and return the element at index K-1.

• Use a max heap to find the Kth largest element efficiently.

• Implement a quickselect algorithm to find the Kth largest element in linear time.

Reverse a linked list in groups of n elements.

• Divide the linked list into groups of n elements.

• Reverse each group individually.

• Connect the reversed groups to form the final linked list.

• Handle cases where the number of elements is not a multiple of n.

• Example: 1->2->3->4->5->6->7->8, n=3 -> 3->2->1->6->5->4->8->7

Find the median of two sorted arrays.

• Merge the two arrays into one sorted array and find the median.

• Use binary search to find the median in O(log(min(m, n))) time complexity.

• Handle edge cases like empty arrays or arrays of different lengths.

Count number of paths from (0, 0) to (m, n) in a matrix while crossing through some indexes were not allowed.

• Use dynamic programming to solve the problem

• Create a 2D array to store the number of paths

• Traverse the matrix and update the array based on the allowed paths

• Return the value at the last index of the array

The question asks to convert the leaves of a binary tree into a doubly linked list without using extra space.

• Traverse the binary tree in a depth-first manner

• When a leaf node is encountered, update its left and right pointers to form the doubly linked list

• Keep track of the previous leaf node to update its right pointer

• Return the head of the doubly linked list

Count number of ways to reach opposite corner of a m*n table moving in two directions only.

• Use dynamic programming to solve the problem

• The number of ways to reach a cell is the sum of the number of ways to reach the cell above it and the cell to the left of it

• The number of ways to reach the opposite corner is the number of ways to reach the cell in the last row and last column

• Example: For a 2*2 table, there are 2 ways ...read more

The number of ways to travel n steps by taking one or two steps at a time.

• This is a classic problem that can be solved using dynamic programming.

• The number of ways to travel n steps is equal to the sum of the number of ways to travel n-1 steps and n-2 steps.

• Use an array to store the number of ways for each step, starting with base cases for 0 and 1 steps.

• Iterate through the array to calculate the number of ways for eac...read more

Convert infix expression to postfix expression.

• Use a stack to keep track of operators.

• Iterate through the infix expression and push operands to output.

• If an operator is encountered, pop operators from stack until a lower precedence operator is found.

• Push the operator to stack.

• After iterating, pop remaining operators from stack and append to output.

• Reverse the output to get postfix expression.

Reverse a binary search tree while maintaining parent-child relationship.

• Start by swapping the left and right child of each node recursively.

• Use a depth-first search approach to traverse the tree.

• Make sure to update the parent-child relationships accordingly.

To find min and max element in stack in O(1), we can use an auxiliary stack.

• Create an auxiliary stack to keep track of the minimum and maximum elements.

• Push the first element to both the main and auxiliary stack.

• For each subsequent element, compare it with the top element of the auxiliary stack and push the smaller element to the auxiliary stack.

• To get the minimum element, simply return the top element of the auxiliary...read more

Given an array, find the next minimum element for each element.

• Iterate through the array

• For each element, compare it with the elements on its right

• Find the minimum element greater than the current element

• If no such element exists, assign -1

• Build the resultant array

Remove characters from string A that appear in string B, considering their frequency in B.

• Use a frequency counter for string B to track occurrences of each character.

• Iterate through string A and build a new string excluding characters found in B.

• Example: A = 'hello', B = 'l' -> Result: 'heo'.

• Example: A = 'banana', B = 'an' -> Result: 'b'.

• Consider edge cases like empty strings or no common characters.

Find median of input stream in minimum time complexity using online algorithm.

• Use two heaps, one max heap for elements smaller than current median and one min heap for elements greater than current median.

• Maintain balance between the two heaps by ensuring that the size difference is at most 1.

• If the size of both heaps is equal, median is the average of the top elements of both heaps. Else, median is the top element of ...read more

To make a copy of a linked list with two pointers, iterate through the original list and create a new node for each element.

• Iterate through the original linked list

• Create a new node for each element

• Set the 'next' pointer of each new node

• Set the 'arbitrary' pointer of each new node

Implementing caching, optimizing queries, and using CDNs can reduce latency when accessing data from social networking sites.

• Use caching mechanisms like Redis or Memcached to store frequently accessed data.

• Optimize database queries to reduce response time, e.g., using indexes.

• Implement pagination to load data in chunks instead of all at once.

• Utilize Content Delivery Networks (CDNs) to serve static assets closer to user...read more

Use a min-heap to efficiently find the m closest points to an origin in a coordinate system.

• 1. Use a min-heap (priority queue) to store points based on their distance from the origin.

• 2. Calculate the distance using the Euclidean formula: distance = sqrt((x2 - x1)^2 + (y2 - y1)^2).

• 3. Insert points into the heap and maintain its size to m to keep only the closest points.

• 4. Example: For points (1,2), (3,4), (5,6) and orig...read more

Reverse the nodes of a linked list in pairs of n

• Iterate through the linked list in pairs of n

• Reverse the nodes within each pair

• Connect the reversed pairs together

• Handle cases where the number of nodes is not a multiple of n

Find a number in a consecutive integer array using binary search for optimal time complexity.

• The array is sorted and consists of consecutive integers, e.g., [1, 2, 3, 4, 5].

• Use binary search to find the number in O(log n) time complexity.

• Calculate the mid index and compare the middle element with the target.

• If the target is less than the middle element, search the left half; otherwise, search the right half.

• Example: To...read more

To check if a singly linked list is a palindrome, reverse the second half and compare it with the first half.

• Traverse the linked list to find the middle node

• Reverse the second half of the linked list

• Compare the reversed second half with the first half to check for palindrome

Given a preorder of binary tree with leaf nodes represented by N, construct the tree.

• Start by creating an empty stack.

• Iterate through the preorder list.

• If the current element is N, create a leaf node and push it onto the stack.

• If the current element is not N, create a new node and set its left child to the top of the stack.

• Pop the top of the stack and set it as the right child of the new node.

• Push the new node onto the...read more

The question asks to find the maximum occupancy word in each line of a given multiline string and also count the occupancy of capital and small letters separately.

• Split the multiline string into individual lines

• For each line, split it into words

• Initialize variables to store the maximum occupancy word and its count

• Iterate through each word and count the occupancy of each letter

• If the current word has a higher occupancy ...read more

Validate user passwords against predefined conditions to ensure security and compliance.

• Password must be at least 8 characters long. Example: 'Password1' is valid, 'Pass' is invalid.

• Password must contain at least one uppercase letter. Example: 'Password1' is valid, 'password1' is invalid.

• Password must contain at least one lowercase letter. Example: 'Password1' is valid, 'PASSWORD1' is invalid.

• Password must include at l...read more