Oyo Rooms
20+ Oyo Rooms Interview Questions and Answers
Q1. Water Jug Problem Statement
You have two water jugs with capacities X
and Y
liters respectively, both initially empty. You also have an infinite water supply. The goal is to determine if it is possible to measu...read more
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.
Q2. Minimum Cost to Destination
You are given an NxM matrix consisting of '0's and '1's. A '1' signifies that the cell is accessible, whereas a '0' indicates that the cell is blocked. Your task is to compute the mi...read more
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.
Q3. Zig-Zag String Problem Statement
Given a string 'STR' of length 'N' and an integer 'M' representing the number of rows in the zig-zag pattern, your task is to return the string formed by concatenating all 'M' r...read more
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
Q4. Count Ways to Complete Journey in Triangular Pyramid
Given a triangular pyramid with vertices marked as ‘O’, ‘X’, ‘Y’, and ‘Z’, and an integer 'N', you need to calculate the number of ways Bob can start at ‘O’,...read more
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
Q5. Maximum Profit Problem Statement
Mukesh is evaluating the maximum profit from his business over a series of days. Given a list of profits over 'N' days, Mukesh wants to determine the highest profit achievable o...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.
Q6. 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 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
Q7. Position of Right Most Set Bit
Determine the position of the rightmost set bit in the binary representation of a given number N.
Input:
T: Number of test cases
N: An integer for which the position of the rightmo...read more
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.
Q8. Rotate Matrix Right K Times
You are given a matrix MAT
of size 'N' * 'M', where 'N' is the number of rows and 'M' is the number of columns, along with a positive integer 'K'. Your task is to rotate the matrix t...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
Q9. Word Search Problem Statement
Given a two-dimensional grid of size N x M
consisting of upper case characters and a string 'WORD', determine how many times the 'WORD' appears in the grid.
The 'WORD' can be forme...read more
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.
Q10. Problem Statement: Largest Island
You are provided with a non-empty grid consisting of only 0s and 1s. Your task is to determine the maximum area of an island within the given grid.
An island consists of a clus...read more
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.
Q11. Pythagorean Triplet Problem
Determine if there exists a Pythagorean triplet within a given array of integers. A Pythagorean triplet consists of three numbers, x, y, and z, such that x^2 + y^2 = z^2.
Explanation...read more
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.
Q12. Top View of Binary Tree Problem Statement
Given a Binary Tree of integers, you are tasked with finding the top view of the binary tree. The top view is the set of nodes visible when the tree is viewed from the ...read more
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.
Q13. Fixing a Swapped Binary Search Tree
Given a Binary Search Tree (BST) where two nodes have been swapped by mistake, your task is to restore or fix the BST without changing its structure.
Input:
The first line of...read more
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.
Q14. Rat in a Maze Problem Statement
You need to determine all possible paths for a rat starting at position (0, 0) in a square maze to reach its destination at (N-1, N-1). The maze is represented as an N*N matrix w...read more
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.
Q15. Count Pairs with Given Sum
Given an integer array/list arr
and an integer 'Sum', determine the total number of unique pairs in the array whose elements sum up to the given 'Sum'.
Input:
The first line contains ...read more
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.
Q16. 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 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.
Q17. Maximum Sum of Non-Adjacent Elements
You are given an array/list of integers. The task is to return the maximum sum of a subsequence such that no two elements in the subsequence are adjacent in the given array/...read more
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
Implement Stack with Linked List
Your task is to implement a Stack data structure using a Singly Linked List.
Explanation:
Create a class named Stack
which supports the following operations, each in O(1) time:
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.
Q19. Sum Tree Conversion
Convert a given binary tree into its sum tree. In a sum tree, every node's value is replaced with the sum of its immediate children's values. Leaf nodes are set to 0. Finally, return the pre...read more
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.
Q20. Triangle Formation Using Array Elements
Given an integer array/list ARR
of length 'N', determine if it is possible to form at least one non-degenerate triangle using the values of the array as the sides of the ...read more
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.
Q21. Running Median Problem
Given a stream of integers, calculate and print the median after each new integer is added to the stream.
Output only the integer part of the median.
Example:
Input:
N = 5
Stream = [2, 3,...read more
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.
Q23. merge sort algorithm and divide array in the chunks
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).
Q24. Reverse a LinkedList from m to n
Reverse a LinkedList from m to n
Traverse the list to m-1th node
Reverse the nodes from m to n
Connect the reversed list to the original list
Interview Process at Oyo Rooms
Top Software Developer Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month