30+ Optimized Solutions Interview Questions and Answers
Q1. Hotel Room Booking Problem
You are managing a hotel with 10 floors numbered from 0 to 9. Each floor contains 26 rooms labeled from A to Z. You will receive a sequence of strings representing room bookings where...read more
Given a sequence of room bookings and freeings, find the room that is booked the most times.
Create a hashmap to store the count of each room booking.
Iterate through the sequence of bookings and freeings, updating the count in the hashmap.
Find the room with the highest count and return it. In case of a tie, return the lexicographically smaller room.
Example: For input n = 6, Arr[] = {"+1A", "+3E", "-1A", "+4F", "+1A", "-3E"}, the output would be "1A".
Q2. Majority Element - II Problem Statement
Given an array/list ARR
of integers with length 'N', identify all elements that appear more than floor(N/3)
times within the array/list.
Input:
T (number of test cases)
Fo...read more
Q3. Remove K Corner Elements - Problem Statement
Given an array "arr" consisting of "N" integer elements, your task is to remove "K" elements from the beginning or the end of the array. You must return the maximum ...read more
Given an array, remove K elements from beginning or end to maximize sum of remaining elements.
Iterate through all possible combinations of removing K elements from beginning and end
Calculate sum of remaining elements for each combination
Return the maximum sum obtained
Q4. Minimum Time To Solve The Problems
Given 'N' subjects, each containing a certain number of problems, and 'K' friends, assign subjects to friends such that each subject goes to exactly one friend, maintaining co...read more
Assign subjects to friends to minimize maximum workload, find minimum time for most loaded friend.
Sort subjects in descending order
Assign subjects to friends one by one until all subjects are assigned
The maximum workload will be the sum of problems assigned to the friend with the most problems
Return the maximum workload as the minimum time required
Q5. Sum of LCM Problem Statement
Given an integer 'N', calculate and print the sum of the least common multiples (LCM) for each integer from 1 to N with N.
The sum is represented as:LCM(1, N) + LCM(2, N) + ... + LC...read more
Calculate and print the sum of least common multiples (LCM) for each integer from 1 to N with N.
Iterate from 1 to N and calculate LCM of each number with N
Sum up all the calculated LCMs to get the final result
Implement a function to calculate LCM of two numbers
Q6. Minimum Removals Problem Statement
Given an integer array ARR
of size N
and an integer K
, determine the minimum number of elements that need to be removed so that the difference between the maximum and minimum ...read more
Q7. Distance Between Two Nodes in a Binary Tree
Given a binary tree and the values of two distinct nodes, determine the distance between these two nodes in the tree. The distance is defined as the minimum number of...read more
Q8. Maximum Sum Path from Leaf to Root Problem
You are tasked with finding the path from a leaf node to the root node in a binary tree, such that this path has the maximum sum among all root-to-leaf paths.
Input:
T...read more
Find the path from a leaf node to the root node in a binary tree with the maximum sum.
Traverse the binary tree from leaf to root while keeping track of the sum along the path.
Compare the sums of all root-to-leaf paths and return the path with the maximum sum.
Use recursion to traverse the tree efficiently and update the sum as you go.
Consider edge cases like null nodes and negative values in the tree.
Q9. Consecutive Elements
Given an array arr
of N
non-negative integers, determine whether the array consists of consecutive numbers. Return true if they do, and false otherwise.
Input:
The first line of input conta...read more
Q10. BFS Traversal in a Graph
Given an undirected and disconnected graph G(V, E) where V vertices are numbered from 0 to V-1, and E represents edges, your task is to output the BFS traversal starting from the 0th ve...read more
BFS traversal of an undirected and disconnected graph starting from vertex 0.
Implement BFS algorithm to traverse the graph starting from vertex 0.
Use a queue to keep track of visited nodes and their neighbors.
Ensure to print the nodes in numerical sort order when multiple neighbors are present.
Handle disconnected components by checking for unvisited nodes.
Output the BFS traversal sequence for each test case in a separate line.
Q11. Delete Leaf Nodes with Value X
Given a binary tree where each node contains an integer value, and an integer X, your task is to delete all leaf nodes that have the value X. Continue to remove newly formed leave...read more
Delete all leaf nodes with value X in a binary tree until no such leaves exist.
Traverse the tree in postorder fashion to delete leaf nodes with value X
Recursively call the function on left and right subtrees
Update the root of the tree after removing leaf nodes with value X
Q12. Maximum Time Problem Statement
You are given a string that represents time in the format hh:mm
. Some of the digits are blank (represented by ‘?’
). Your task is to fill in ‘?’
such that the time represented by t...read more
Given a string representing time with some digits as '?', fill in '?' to get maximum time.
Iterate through each digit of the input string and replace '?' with the maximum possible digit based on the position.
For the first digit (hours), if it is '?', replace it with '2' if the second digit is also '?', else replace it with '1'.
For the second digit (hours), if it is '?', replace it with '3' if the first digit is '2', else replace it with '9'.
For the third digit (minutes), if it...read more
Q13. Sum of Bit Difference Among All Pairs Problem Statement
Given an array of integers, determine the sum of bit differences among all possible pairs that can be formed using the elements of the array.
The bit diff...read more
Calculate sum of bit differences among all pairs in an array of integers.
Iterate through all pairs of elements in the array
Convert each pair of elements to binary representation
Count the differing bits in the binary representations
Sum up the differing bits for all pairs to get the final result
Q14. Problem: Search In Rotated Sorted Array
Given a sorted array that has been rotated clockwise by an unknown amount, you need to answer Q
queries. Each query is represented by an integer Q[i]
, and you must determ...read more
Search for integers in a rotated sorted array efficiently using binary search.
Use binary search to efficiently find the index of each query integer in the rotated sorted array.
Handle the rotation of the array by finding the pivot point first.
Check which half of the array the query integer falls into based on the pivot point.
Return the index of the query integer if found, else return -1.
Q15. Min Steps to One Using Dynamic Programming
Given a positive integer N
, your task is to determine the minimum number of steps required to reduce N
to 1.
Allowed Operations:
1) Subtract 1 from it: n = n - 1
2) If ...read more
Implement a function to find the minimum steps to reduce a positive integer to 1 using given operations.
Use dynamic programming to store the minimum steps for each number from 1 to N.
Iterate through each number from 1 to N and calculate the minimum steps based on the given operations.
Consider the cases where N is divisible by 2 or 3, and also when subtracting 1 is the only option.
Return the minimum steps required to reduce N to 1.
Q16. Ninja and the Bulbs Challenge
Ninja owns an electronic shop and possesses 'N' bulbs. To verify the quality of the bulbs, Ninja performs a unique technique. After 'N' rounds of this process, bulbs that remain on...read more
Determine the number of good quality bulbs remaining after 'N' rounds of a unique technique.
In each round, bulbs are toggled based on their position (e.g. every second bulb, every third bulb, etc.)
At the end of 'N' rounds, count the bulbs that remain on to determine the number of good quality bulbs.
Example: For N = 4, bulbs 1 and 4 remain on, so the output is 2.
Q17. Wildcard Queries Problem Statement
Given a dictionary D
with N
words, each of a fixed length L
and consisting only of lowercase English alphabets, answer Q
queries. Each query consists of a word W
of the same l...read more
Given a dictionary and queries with wildcard characters, determine how many words in the dictionary can match each query.
Iterate through each query and dictionary word to check for matches
Replace '?' with all possible lowercase letters and compare with dictionary words
Count the number of matches for each query
Q18. Subset OR Problem Statement
You are given an array/list ARR
of N
positive integers. Your task is to determine the size of the smallest subset that achieves the maximum possible OR value among all subsets.
Input...read more
Find the size of the smallest subset with maximum OR value among all subsets of an array of positive integers.
Iterate through all possible subsets of the array
Calculate the OR value for each subset
Track the size of the smallest subset with maximum OR value
Q19. Count Ways to Reach the N-th Stair Problem Statement
You are provided with a number of stairs, and initially, you are located at the 0th stair. You need to reach the Nth stair, and you can climb one or two step...read more
The problem involves finding the number of distinct ways to climb N stairs by taking 1 or 2 steps at a time.
Use dynamic programming to solve the problem efficiently.
The number of ways to reach the Nth stair is the sum of the number of ways to reach the (N-1)th stair and the (N-2)th stair.
Handle base cases for N=0 and N=1 separately.
Consider using modulo operation to avoid overflow for large values of N.
Q20. Problem Statement: Delete Node In A Linked List
Given a singly linked list of integers and a reference to a node, your task is to delete that specific node from the linked list. Each node in the linked list has...read more
Given a singly linked list of integers and a reference to a node, delete the specified node from the linked list.
Traverse the linked list to find the node to be deleted.
Update the pointers to skip over the node to be deleted.
Print the modified linked list after deletion.
Ensure the node to be deleted is not the tail node.
Q21. Maximum Subarray Sum Problem Statement
Given an array ARR
consisting of N
integers, your goal is to determine the maximum possible sum of a non-empty contiguous subarray within this array.
Example of Subarrays:...read more
Find the maximum sum of a contiguous subarray within an array of integers.
Use Kadane's algorithm to find the maximum subarray sum efficiently.
Initialize two variables: maxEndingHere and maxSoFar.
Iterate through the array and update the variables accordingly.
Return the maxSoFar as the result.
Q22. 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.
Initialize the array with base cases and then iterate through the denominations to fill up the array.
The final answer will be in the last cell of the array.
Example: For N=3, D=[1, 2, 3], V=4, the output should be...read more
Q23. 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 to reach its destination, given a matrix representation of the maze.
Use backtracking to explore all possible paths from the starting position to the destination.
Keep track of the current path and explore all possible directions at each step.
Terminate the exploration when reaching the destination and add the path to the result list.
Sort the result list of paths in alphabetical order before returning.
Q24. Count Distinct Bitwise OR of All Subarrays
Given an array of positive integers, determine the number of distinct values obtained by applying the bitwise OR operation on all possible subarrays.
Explanation:
A su...read more
Count distinct values obtained by applying bitwise OR operation on all possible subarrays of an array of positive integers.
Use a set to store distinct values obtained by bitwise OR operation on all subarrays.
Iterate through all subarrays efficiently to calculate distinct values.
Optimize the solution to handle large input sizes efficiently.
Q25. House Robber Problem Statement
Mr. X is a professional robber with a plan to rob houses arranged in a circular street. Each house has a certain amount of money hidden, separated by a security system that alerts...read more
House Robber problem - determine maximum amount of money to rob without triggering alarm in circular arrangement of houses.
Use dynamic programming to keep track of maximum money robbed at each house.
Consider two cases: robbing the first house and not robbing the first house.
Handle circular arrangement by considering the first and last house separately.
Example: For arr[] = {2, 3, 2}, the output is 3. Mr. X robs house 2.
Example: For arr[] = {1, 2, 3, 1}, the output is 4. Mr. X ...read more
Q26. 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 binary tree is a Binary Search Tree (BST) based on given properties.
Check if the left subtree of a node contains only nodes with data less than the node's data.
Verify 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.
Traverse the tree in level order form to validate the BST properties.
Return true if the binary tree is a BST, otherwise return false.
Q27. Sliding Window Maximum Problem Statement
You are given an array/list of integers with length 'N'. A sliding window of size 'K' moves from the start to the end of the array. For each of the 'N'-'K'+1 possible wi...read more
The problem involves finding the maximum element in each sliding window of size 'K' in an array of integers.
Use a deque to store indices of elements in the current window in decreasing order of their values.
Remove indices that are out of the current window from the front of the deque.
Add the maximum element (at the front of the deque) to the result for each window.
Q28. Sudoku Solver
Given a 9x9 Sudoku board, your task is to fill the empty slots and return the completed Sudoku solution.
A Sudoku is a grid composed of nine 3x3 smaller grids. The challenge is to fill in the numb...read more
Implement a Sudoku solver for a 9x9 grid with constraints on row, column, and 3x3 grid.
Create a recursive function to solve the Sudoku puzzle by trying out different numbers in empty slots.
Use backtracking to backtrack and try different numbers if a conflict is encountered.
Ensure each number appears only once in each row, column, and 3x3 grid.
Implement a function to check if a number can be placed in a particular position based on Sudoku rules.
Test the solver with different S...read more
Q29. Count Palindrome Words in a String
Given a string 'S' consisting of words, your task is to determine the number of palindrome words within 'S'. A word is considered a palindrome if it reads the same backward as...read more
Count the number of palindrome words in a given string.
Split the string into words using whitespace as delimiter.
Check each word if it is a palindrome by comparing it with its reverse.
Increment a counter for each palindrome word found.
Output the final count of palindrome words for each test case.
Q30. What is software intern developer
A software intern developer is a student or recent graduate who works on software development projects under the guidance of experienced developers.
Assists in coding, testing, and debugging software applications
Learns new programming languages and technologies
Participates in team meetings and contributes to project discussions
More about working at Google
Interview Process at Optimized Solutions
Top Software Developer Intern Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month