20+ Oyo Rooms Software Developer Interview Questions and Answers

The Water Jug Problem involves determining if a specific amount of water can be measured using two jugs of different capacities.

• Start by considering the constraints and limitations of the problem.

• Think about how the operations allowed can be used to reach the target measurement.

• Consider different scenarios and test cases to understand the problem better.

• Implement a function that can determine if the target measurement is possible using the given jugs.

Find the minimum cost to reach a destination in a matrix with blocked cells.

• Use Breadth First Search (BFS) algorithm to explore all possible paths from the starting point to the destination.

• Keep track of the cost incurred at each cell and update it as you move through the matrix.

• Return the minimum cost to reach the destination or -1 if it is unreachable.

Given a string and number of rows, return the concatenated string formed by arranging the input string in a zig-zag pattern over the specified number of rows.

• Iterate through the string and distribute characters in zig-zag pattern over 'M' rows

• Keep track of the direction of movement (up or down) while distributing characters

• Concatenate characters row-wise to get the final zig-zag pattern string

Calculate the number of ways to complete a journey in a triangular pyramid starting and ending at a specific vertex after taking a certain number of steps.

• Use dynamic programming to calculate the number of ways to return to the starting vertex after 'N' steps.

• Consider the possible movements from each vertex to adjacent vertices.

• Keep track of the number of ways to reach each vertex after each step.

• Return the total number of ways modulo 1000000007.

• Example: For 'N' = 2, valid se...read more

The task is to find the maximum profit achievable over any consecutive days within a specified range {‘A’, ‘B’}.

• Iterate through the profit array and calculate the cumulative sum for each possible consecutive days within the range {‘A’, ‘B’}.

• Keep track of the maximum profit obtained during the iteration.

• Return the maximum profit as the final result.

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 from left to right

• Traverse the right boundary nodes in a bottom-up manner

• Handle cases where duplicates occur in the boundary nodes

• Implement the function without printing as printing is already managed

Find the position of the rightmost set bit in a given number's binary representation.

• Convert the number to binary representation.

• Find the position of the rightmost set bit by counting from right to left.

• Return the position of the rightmost set bit.

Count the total number of unique pairs in an array whose elements sum up to a given value.

• Use a hashmap to store the frequency of each element in the array.

• Iterate through the array and for each element, check if (Sum - current element) exists in the hashmap.

• Increment the count of pairs if the complement exists in the hashmap.

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 using different denominations.

• Iterate through the denominations and update the array accordingly.

• The final answer will be stored in the last cell of the array.

• Consider edge cases like when the value to make change for is 0.

Find all possible paths for a rat in a maze from source to destination.

• Use backtracking to explore all possible paths in the maze.

• Keep track of visited cells to avoid revisiting them.

• Explore all possible directions (up, down, left, right) from each cell.

• Add the current direction to the path and recursively explore further.

• When reaching the destination, add the path to the list of valid paths.

Find the maximum sum of non-adjacent elements in an array.

• Use dynamic programming to keep track of the maximum sum at each index, considering whether to include the current element or not.

• At each index, the maximum sum can be either the sum excluding the current element or the sum including the current element but excluding the previous element.

• Iterate through the array and update the maximum sum accordingly.

• Example: For [3, 2, 7], the maximum sum would be 7 (3 + 7) as 3 and ...read more

Rotate a matrix to the right 'K' times by shifting each column to the right 'K' times.

• Iterate 'K' times to perform right rotation on the matrix

• Shift each column to the right by one position in each rotation

• Handle wrapping around the matrix when shifting columns

• Return the matrix elements row-wise after 'K' rotations

Count how many times a given word appears in a 2D grid by moving in any of the eight possible directions.

• Iterate through each cell in the grid and check if the word can be formed starting from that cell in any of the eight directions.

• Use recursion to explore all possible paths from a starting cell to form the word.

• Keep track of visited cells to avoid revisiting the same cell in the same path.

• Return the count of how many times the word can be formed in the grid.

Find the maximum area of an island in a grid of 0s and 1s.

• Iterate through the grid and perform depth-first search (DFS) to find connected 1s.

• Keep track of the area of each island found and return the maximum area.

• Consider all four directions (horizontal, vertical, and diagonal) while exploring the island.

• Handle edge cases like grid boundaries and already visited cells during DFS.

• If no island is present, return 0 as the maximum area.

Check if there exists a Pythagorean triplet in a given array of integers.

• Iterate through all possible triplets in the array and check if they form a Pythagorean triplet.

• Use a nested loop to generate all possible combinations of three numbers from the array.

• Check if the sum of squares of two numbers is equal to the square of the third number.

Find the top view of a Binary Tree by returning a list of visible nodes when viewed from the top.

• Traverse the Binary Tree in level order and keep track of the horizontal distance of each node from the root.

• Use a map to store the nodes at each horizontal distance, and only keep the topmost node for each horizontal distance.

• Return the values of the topmost nodes in the map as the top view of the Binary Tree.

Restore a Binary Search Tree by fixing two swapped nodes without changing its structure.

• Identify the two nodes that are swapped by mistake in the BST.

• Swap the values of the two identified nodes to restore the BST.

• Perform an in-order traversal of the BST to verify the correct restoration.

• Ensure no extra space other than the recursion stack is used for the solution.

Implement a Stack data structure using a Singly Linked List with operations like getSize, isEmpty, push, pop, and getTop in O(1) time.

• Create a class named Stack with methods for getSize, isEmpty, push, pop, and getTop.

• Use a Singly Linked List to store the elements of the stack.

• Ensure that each operation runs in constant time O(1).

• Handle edge cases like empty stack appropriately.

• Test the implementation with sample queries to verify correctness.

Convert a binary tree into a sum tree by replacing each node's value with the sum of its children's values. Return preorder traversal.

• Traverse the tree in a bottom-up manner, starting from the leaf nodes.

• For each node, update its value to the sum of its children's values.

• Set leaf nodes to 0.

• Return the preorder traversal of the modified tree.

Determine if it is possible to form a non-degenerate triangle using array elements as sides.

• Check if the sum of any two sides is greater than the third side for all combinations of sides.

• If the above condition is met for any combination, return true; otherwise, return false.

Calculate and print the median after each new integer is added to the stream.

• Use a min heap to store the larger half of the numbers and a max heap to store the smaller half

• Keep the sizes of the two heaps balanced to efficiently calculate the median

• If the total number of elements is odd, the median will be the top element of the max heap

• If the total number of elements is even, the median will be the average of the top elements of both heaps

Core concepts of indexing in DBMS include types of indexes, benefits of indexing, and factors affecting index performance.

• Types of indexes: B-tree, Hash, Bitmap, etc.

• Benefits of indexing: Faster data retrieval, improved query performance, reduced disk I/O.

• Factors affecting index performance: Selectivity, clustering factor, index fragmentation.

• Examples: Creating an index on a column in a table to speed up search queries.

Merge sort is a sorting algorithm that divides an array into smaller chunks and then merges them in sorted order.

• Merge sort is a divide-and-conquer algorithm.

• It recursively divides the array into two halves until each subarray has only one element.

• Then it merges the subarrays in sorted order.

• The merge step compares elements from both subarrays and places them in the correct order.

• It has a time complexity of O(n log n).