Amazon
300+ PLRC Interview Questions and Answers
Q1. Maximum Subarray Sum Problem Statement
Given an array of integers, determine the maximum possible sum of any contiguous subarray within the array.
Example:
Input:
array = [34, -50, 42, 14, -5, 86]
Output:
137
E...read more
Find the maximum sum of any contiguous subarray within an array of integers.
Iterate through the array and keep track of the maximum sum of subarrays encountered so far.
At each index, decide whether to include the current element in the subarray or start a new subarray.
Use Kadane's algorithm to efficiently find the maximum subarray sum in O(N) time complexity.
Q2. Minimum Number of Platforms Needed Problem Statement
You are given the arrival and departure times of N trains at a railway station for a particular day. Your task is to determine the minimum number of platform...read more
Determine the minimum number of platforms needed at a railway station based on arrival and departure times of trains.
Sort the arrival and departure times in ascending order.
Use two pointers to keep track of overlapping schedules.
Increment the platform count when a new train arrives before the previous one departs.
Return the maximum platform count needed.
Q3. Fenwick Tree Problem Statement
You are provided with an array/list ARR
consisting of 'N' integers, along with 'Q' queries. Each query can be of one of the following two types:
- Type 1 (Range Sum): Given two int...read more
Implement Fenwick Tree to handle range sum and point update queries on an array.
Implement Fenwick Tree data structure to efficiently handle range sum and point update queries.
For range sum queries, use prefix sum technique to calculate the sum of elements in the given range.
For point update queries, update the Fenwick Tree structure accordingly.
Handle each query type separately and output the required results.
Ensure to follow the constraints provided in the problem statement.
Q4. There is a 12 km road and a contractor who is in-charge of repairing it. Contractor updates you about the work which is done in patches. Like “Road between 3.2 km to 7.9 km repaired ”, “Road between 1.21 km to...
read moreThe longest continuous patch of a road repaired by a contractor is determined.
Iterate through the updates and keep track of the start and end points of each patch
Calculate the length of each patch and update the longest patch if necessary
Return the start and end points of the longest patch
Q5. Permutation in String Problem Statement
Determine if the string str2
contains a permutation of the string str1
as one of its substrings.
Input:
The first line contains an integer 'T', representing the number of...read more
Check if a permutation of one string is a substring of another string.
Create a frequency map of characters in str1.
Iterate through str2 with a window of size N and check if the frequency map matches.
Return 'Yes' if a permutation is found, 'No' otherwise.
Q6. Fire in the Cells Problem Statement
Given a matrix MAT
of size N * M
, where each cell is either on fire or safe, determine if a person can reach an escape cell without being burnt. The person starts from a give...read more
Determine if a person can reach an escape cell without encountering fire in a matrix.
Check if the person can reach an escape cell without encountering fire by simulating the movement of the person and fire spread.
If the person can reach an escape cell, return the time taken; otherwise, return -1.
Consider the constraints and edge cases while implementing the solution.
Q7. Find All Pairs Adding Up to Target
Given an array of integers ARR
of length N
and an integer Target
, your task is to return all pairs of elements such that they add up to the Target
.
Input:
The first line conta...read more
Given an array of integers and a target, find all pairs of elements that add up to the target.
Iterate through the array and for each element, check if the target minus the element exists in a hash set.
If it exists, add the pair to the result. If not, add the element to the hash set.
Handle cases where the same element is used twice to form a pair.
Return (-1, -1) if no pair is found.
Q8. Maximum Path Sum Between Two Leaves
Given a non-empty binary tree where each node has a non-negative integer value, determine the maximum possible sum of the path between any two leaves of the given tree.
Expla...read more
Find the maximum path sum between two leaf nodes in a binary tree.
Traverse the tree to find the maximum path sum between two leaf nodes
Consider both cases where the path passes through the root and where it doesn't
Use recursion to calculate the sum of paths from each leaf node to the root
Q9. Delete Alternate Nodes from a Singly Linked List
Given a Singly Linked List of integers, remove all the alternate nodes from the list.
Input:
The first and the only line of input will contain the elements of th...read more
Remove alternate nodes from a singly linked list of integers.
Traverse the linked list and skip every alternate node while updating the next pointers.
Make sure to handle cases where there are less than 3 nodes in the list.
Update the next pointers accordingly to remove alternate nodes.
Example: Input: 10 20 30 40 50 60 -1, Output: 10 30 50
Q10. Car Pooling Problem Statement
You are tasked with driving a cab that moves in a straight line, only forward, and initially has 'C' empty seats available for passengers.
Given 'N' trips, each defined by three in...read more
The problem involves determining if a cab with a certain capacity can successfully pick up and drop off passengers at specified points for multiple trips.
Create a function that takes in the car's capacity, number of trips, and trip details as input
Iterate through each trip and check if the total number of passengers picked up and dropped off is within the car's capacity
Return 'True' if all trips can be successfully completed, 'False' otherwise
Q11. Maximum Sum of Non-Adjacent Elements
Given an array/list of ‘N’ integers, your task is to return the maximum sum of the subsequence where no two elements are adjacent in the given array/list.
Example:
Input:
T ...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 skip it.
At each index, the maximum sum is either the sum of the current element and the element two positions back, or the sum at the previous index.
Iterate through the array and update the maximum sum at each index accordingly.
Return the maximum sum obtained at the last index as the final resul...read more
Q12. Search for Indices with Given Difference and Distance
You are provided with an array containing 'N' non-negative integers, along with two other non-negative integers 'K' and 'M'. Your task is to identify and re...read more
Find a pair of indices in an array with given difference and distance constraints.
Iterate through the array and check all possible pairs of indices to satisfy the conditions
Use nested loops to compare each pair of indices and their corresponding elements
Return 'valid' if a pair of indices is found that meets the conditions, otherwise return 'invalid'
Q13. Sum of Minimum and Maximum Elements of All Subarrays of Size K
You are provided with an array containing N integers along with an integer K. Your task is to compute the total sum of the minimum and maximum elem...read more
Calculate the sum of minimum and maximum elements of all subarrays of size K in an array.
Iterate through the array and maintain a deque to store the indices of elements in the current window of size K.
Keep track of the minimum and maximum elements in the current window using the deque.
Calculate the sum of minimum and maximum elements for each subarray of size K and return the total sum.
Q14. Spiral Matrix Problem Statement
You are provided with a 2-D array called MATRIX
with dimensions N x M containing integers. Your task is to return the matrix's elements in a spiral order.
Example:
Input:
The fi...read more
The task is to return the elements of a 2-D array in a spiral order.
Traverse the matrix in a spiral order by moving right, down, left, and up.
Keep track of the boundaries of the matrix as you move along.
Handle cases where the matrix is not a square (N != M).
Q15. Best Time To Buy and Sell Stock Problem Statement
You are given an array 'PRICES' of 'N' integers, where 'PRICES[i]' represents the price of a certain stock on the i-th day. An integer 'K' is also provided, ind...read more
Find the maximum profit achievable with at most K transactions by buying and selling stocks.
Iterate through the array and keep track of the minimum price to buy and maximum profit for each transaction.
Use dynamic programming to store the maximum profit at each day with each possible number of transactions.
Consider edge cases like when K is 0 or when the array is empty.
Example: For input N = 6, PRICES = [3, 2, 6, 5, 0, 3], K = 2, the output should be 7.
Q16. String Transformation Problem Statement
Given a string str
of length N, perform a series of operations to create a new string:
- Select the smallest character from the first 'K' characters of the string, remove ...read more
The problem involves selecting the smallest character from the first 'K' characters of a string and appending it to a new string until the original string is empty.
Iterate through the string, selecting the smallest character from the first 'K' characters each time.
Remove the selected character from the original string and append it to the new string.
If fewer than 'K' characters remain, sort and append them in order.
Repeat the process until the original string is empty.
Q17. Stock Trading Maximum Profit Problem
Given the stock prices for 'N' days, your goal is to determine the maximum profit that can be achieved. You can buy and sell the stocks any number of times but can only hold...read more
The goal is to determine the maximum profit that can be achieved by buying and selling stocks on different days.
Iterate through the stock prices and buy on days when the price is lower than the next day, and sell on days when the price is higher than the next day.
Calculate the profit by summing up the differences between buying and selling prices.
Repeat the process for each test case and output the maximum profit achieved.
Example: For prices [7, 1, 5, 3, 6, 4], buy on day 2 a...read more
Q18. Rotting Oranges Problem Statement
You are given a grid containing oranges where each cell of the grid can contain one of the three integer values:
- 0 - representing an empty cell
- 1 - representing a fresh orange...read more
Find the minimum time required to rot all fresh oranges in a grid.
Use Breadth First Search (BFS) to simulate the rotting process.
Track the time taken to rot all fresh oranges.
Return -1 if not all fresh oranges can be rotten.
Handle edge cases like empty grid or no fresh oranges.
Example: For the given grid, it takes 4 seconds to rot all fresh oranges.
Q19. Detect Cycle in a Directed Graph
You are provided with a directed graph composed of 'N' nodes. You have a matrix called 'EDGES' with dimensions M x 2, which specifies the 'M' edges in the graph. Each edge is di...read more
Detect cycle in a directed graph using depth-first search (DFS) algorithm.
Use DFS to traverse the graph and detect back edges indicating a cycle.
Maintain a visited array to keep track of visited nodes during traversal.
If a node is visited again during traversal and it is not the parent node, then a cycle exists.
Return true if a cycle is detected, false otherwise.
Q20. Rotten Oranges Problem Statement
Given a grid containing oranges in three possible states:
- Value 0 - Empty cell
- Value 1 - Fresh orange
- Value 2 - Rotten orange
Every second, any fresh orange adjacent (4-direct...read more
Given a grid with fresh and rotten oranges, determine the minimum time for all oranges to become rotten.
Create a queue to store the coordinates of rotten oranges and perform BFS to rot adjacent fresh oranges
Track the time taken to rot all oranges and return -1 if some fresh oranges remain
Handle edge cases like empty grid or no fresh oranges present
Example: For input grid = [[2,1,1],[1,1,0],[0,1,1]], the minimum time to rot all oranges is 4
Q21. Find Pair Sum Equal to K
Given an integer array arr
and an integer 'Sum'
, find and return the total number of pairs in the array which, when added together, result in the 'Sum'
.
Note:
The array can contain dupl...read more
Find total number of pairs in array that sum to given value.
Use a hashmap to store frequency of each element in the array.
Iterate through the array and check if (Sum - current element) exists in the hashmap.
Increment count of pairs if found and update hashmap accordingly.
Q22. Counting Derangements Problem
A derangement is a permutation of 'N' elements, where no element appears in its original position. For instance, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0} because each element ...read more
Count the total number of derangements possible for a set of 'N' elements.
A derangement is a permutation where no element appears in its original position.
Use the formula for derangements: !n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!).
Return the answer modulo (10^9 + 7) as the result could be very large.
Q23. Mike and Mobile Keypad Problem
Mike, a young math enthusiast, is playing with his mom’s mobile phone, which has a keypad with 12 buttons (10 digits: 0-9, and 2 special characters: ‘*’ and ‘#’). His challenge is...read more
Calculate the number of distinct numbers that can be formed by pressing 'N' buttons on a mobile keypad following specific rules.
Use dynamic programming to keep track of the number of distinct numbers that can be formed at each step.
Consider the possible transitions from each button to calculate the total number of distinct numbers.
Implement a solution that efficiently handles large values by using modulo arithmetic.
Ensure that the solution runs within the given time limit of ...read more
Q24. Strongly Connected Components (Tarjan’s Algorithm) Problem Statement
Given an unweighted directed graph with V
vertices and E
edges, your task is to identify and print all the strongly connected components (SCC...read more
Tarjan's Algorithm is used to find strongly connected components in an unweighted directed graph.
Tarjan's Algorithm is a depth-first search based algorithm.
It uses a stack to keep track of vertices in the current SCC.
The algorithm assigns a unique id to each vertex and keeps track of the lowest id reachable from the current vertex.
Once a SCC is identified, the vertices in the stack form that SCC.
The algorithm runs in O(V + E) time complexity.
Example: For the input graph with ...read more
Q25. Sort 0s, 1s, and 2s Problem Statement
You are provided with an integer array/list ARR
of size 'N' which consists solely of 0s, 1s, and 2s. Your task is to write a solution to sort this array/list.
Input:
The fi...read more
Sort an array of 0s, 1s, and 2s in linear time with a single scan approach.
Use three pointers to keep track of the positions of 0s, 1s, and 2s in the array.
Iterate through the array once and swap elements based on their values and the pointers.
After the single scan, the array will be sorted in the required order.
Q26. 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 0s, 1s, and 2s while traversing the array.
Swap elements based on the values encountered to sort the array in a single scan.
Final array will have 0s on the left, 1s in the middle, and 2s on the right.
Q27. Shortest Path in a Binary Matrix Problem Statement
Given a binary matrix of size N * M
where each element is either 0 or 1, find the shortest path from a source cell to a destination cell, consisting only of 1s...read more
Find the shortest path in a binary matrix from a source cell to a destination cell consisting only of 1s.
Use Breadth First Search (BFS) algorithm to find the shortest path in the binary matrix.
Keep track of visited cells to avoid revisiting them.
Update the path length as you traverse the matrix.
Return -1 if no valid path exists from source to destination.
Q28. Maximum 0-1 Distance Problem Statement
Given a binary matrix of size N*M, find the maximum distance 'di' for every 0-cell to its nearest 1-cell, where the distance is measured using Manhattan distance. The task...read more
Find the maximum Manhattan distance from a 0-cell to its nearest 1-cell in a binary matrix.
Iterate through the matrix to find all 0-cells and calculate their distances to nearest 1-cells using Manhattan distance formula
Keep track of the maximum distance found so far and update it if a larger distance is encountered
Return the maximum distance as the final result
Q29. Special Binary Tree Problem Statement
Determine whether an arbitrary binary tree is special. A binary tree is called special if every node in this tree has either zero or two children.
Example:
Input:
3
5 1
6 2 0...read more
Determine if a binary tree is special if every node has zero or two children.
Traverse the tree and check if each node has either 0 or 2 children.
Use a recursive approach to check children of each node.
If any node has only one child, return false immediately.
Example: For the given input, the output should be true.
Q30. Connecting Ropes with Minimum Cost
You are given 'N' ropes, each of varying lengths. The task is to connect all ropes into one single rope. The cost of connecting two ropes is the sum of their lengths. Your obj...read more
Connect ropes with minimum cost by merging the smallest ropes first.
Sort the array of rope lengths in ascending order.
Merge the two smallest ropes at each step to minimize cost.
Keep track of the total cost as you merge the ropes.
Repeat until all ropes are merged into one.
Return the total cost as the minimum cost to connect all ropes.
Q31. Minimum Window Subsequence Problem Statement
You are given two strings S
and T
. Your task is to determine the smallest contiguous substring W
of S
, such that T
is a subsequence of W
.
A subsequence is a sequence...read more
Find the smallest contiguous substring of S containing T as a subsequence.
Use dynamic programming to find the minimum length substring.
Iterate through S and T to find the minimum length substring.
Keep track of the indices of the characters in S that match with T.
Q32. Postfix Expression Evaluation Problem Statement
Given a postfix expression, your task is to evaluate the expression. The operator will appear in the expression after the operands. The output for each expression...read more
Evaluate postfix expressions by applying operators after operands. Return result modulo (10^9+7).
Iterate through each character in the postfix expression
If character is an operand, push it onto the stack
If character is an operator, pop two operands from stack, apply operator, and push result back
Continue until end of expression, return final result modulo (10^9+7)
Q33. Shortest Path in a Binary Maze
Find the length of the shortest path in a binary maze given in the form of a rectangular matrix of size M*N, where each element is 0 or 1. Calculate the shortest path from a desig...read more
Find the length of the shortest path in a binary maze from source to destination.
Use BFS algorithm to find the shortest path in the binary maze.
Create a visited matrix to keep track of visited cells.
Check for valid movements in all four directions.
Return the shortest path length or -1 if no path exists.
Example: For the given input, the shortest path length is 5.
Q34. Inversion Count Problem
Given an integer array ARR
of size N
with all distinct values, determine the total number of 'Inversions' that exist.
Explanation:
An inversion is a pair of indices (i, j)
such that:
AR...read more
Count the total number of inversions in an integer array.
Use a modified merge sort algorithm to count the inversions.
Keep track of the count of inversions while merging the subarrays.
The time complexity of the solution should be O(n log n).
Q35. Subtree of Another Tree Problem Statement
Given two binary trees, T and S, determine whether S is a subtree of T. The tree S should have the same structure and node values as a subtree of T.
Explanation:
A subt...read more
Given two binary trees T and S, determine if S is a subtree of T with the same structure and node values.
Create a function to check if tree S is a subtree of tree T by comparing their structures and node values.
Traverse both trees in level order and check if S is a subtree of T at each node.
Use recursion to check if the current nodes of T and S are equal, and then recursively check their left and right subtrees.
If S is found as a subtree of T, return true; otherwise, return f...read more
Q36. Stack with getMin Operation
Create a stack data structure that supports not only the usual push and pop operations but also getMin(), which retrieves the minimum element, all in O(1) time complexity without usi...read more
Implement a stack with push, pop, top, isEmpty, and getMin operations in O(1) time complexity without using extra space for storing additional stack data structures.
Use two stacks - one to store the actual elements and another to store the minimum element at each level.
When pushing an element, compare it with the current minimum and update the minimum stack accordingly.
For getMin operation, simply return the top element of the minimum stack.
Ensure all operations like push, po...read more
Q37. 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
Sliding window maximum problem where we find maximum element in each window of size K.
Use a deque to store indices of elements in decreasing order within the window.
Pop elements from the deque that are out of the current window.
Add the maximum element to the result for each window.
Q38. First and Last Position of an Element in a Sorted Array
Given a sorted array/list ARR
consisting of ‘N’ elements, and an integer ‘K’, your task is to find the first and last occurrence of ‘K’ in ARR
.
Explanatio...read more
Find the first and last occurrence of an element in a sorted array.
Use binary search to find the first occurrence of the element.
Use binary search to find the last occurrence of the element.
Handle cases where the element is not present in the array.
Q39. Character Frequency Problem Statement
You are given a string 'S' of length 'N'. Your task is to find the frequency of each character from 'a' to 'z' in the string.
Example:
Input:
S : abcdg
Output:
1 1 1 1 0 0 ...read more
The task is to find the frequency of each character from 'a' to 'z' in a given string.
Create an array of size 26 to store the frequency of each character from 'a' to 'z'.
Iterate through the string and increment the count of the corresponding character in the array.
Print the array of frequencies as the output.
Q40. Word Presence in Sentence
Determine if a given word 'W' is present in the sentence 'S' as a complete word. The word should not merely be a substring of another word.
Input:
The first line contains an integer 'T...read more
Check if a given word is present in a sentence as a complete word.
Split the sentence into words using spaces as delimiter.
Check if the given word matches any of the words in the sentence.
Ensure that the word is not just a substring of another word in the sentence.
Q41. 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.
Use a combination of hashmap and doubly linked list to implement the LRU cache.
Keep track of the least recently used item and update it accordingly.
Ensure to handle cache capacity by evicting the least recently used item when the cache is full.
Q42. Covid Vaccination Distribution Problem
As the Government ramps up vaccination drives to combat the second wave of Covid-19, you are tasked with helping plan an effective vaccination schedule. Your goal is to ma...read more
Given constraints and rules, find maximum vaccines administered on a specific day during a vaccination drive.
Iterate through each test case and calculate the maximum number of vaccines distributed on the specified day.
Distribute vaccines evenly across days while maximizing the number on the specified day.
Ensure that the sum of vaccines distributed does not exceed the maximum allowed.
Consider edge cases like when the number of days is equal to the maximum number of vaccines av...read more
Q43. Binary Strings Without Consecutive 1s Problem Statement
Given an integer K, your task is to generate all binary strings of length K such that there are no consecutive 1s in the string.
This means the binary str...read more
Generate all binary strings of length K without consecutive 1s in lexicographically increasing order.
Use backtracking to generate all possible binary strings without consecutive 1s.
Start with an empty string and recursively add '0' or '1' based on the condition of no consecutive 1s.
Keep track of the current string and its length to check for consecutive 1s.
Return the generated binary strings in lexicographically increasing order.
Q44. Path In A Tree Problem Statement
Given a binary tree with 'N' nodes and a specific node 'X', your goal is to print the path from the root node to the specified node 'X'.
Explanation:
A binary tree is a hierarch...read more
Given a binary tree and a target node, find the path from the root to the target node.
Traverse the binary tree from the root to the target node using depth-first search (DFS).
Store the path from the root to the target node while traversing the tree.
Print the stored path as the output for each test case.
Ensure uniqueness of node values and that the target node exists in the tree.
Q45. Maximum Consecutive Ones Problem Statement
Given a binary array 'ARR' of size 'N', your task is to determine the maximum length of a sequence consisting solely of 1’s that can be obtained by converting at most ...read more
The task is to find the maximum length of a sequence of 1's by converting at most K zeroes into ones in a binary array.
Iterate through the array and keep track of the current window of 1's and zeroes.
Use a sliding window approach to find the maximum length of consecutive 1's by flipping at most K zeroes.
Update the window based on the number of zeroes flipped and keep track of the maximum length found so far.
Return the maximum length of consecutive 1's obtained.
Q46. Dijkstra's Shortest Path Problem Statement
Given an undirected graph with V
vertices (labeled 0, 1, ..., V-1) and E
edges, each edge connects two nodes X
and Y
with a specified weight representing the distance ...read more
Dijkstra's algorithm is used to find the shortest path distance from a source node to all other nodes in an undirected graph.
Implement Dijkstra's algorithm to find the shortest path distance from node 0 to all other nodes in the graph.
Use a priority queue to efficiently select the next node with the shortest distance.
Initialize distances to all nodes as infinity, except for the source node which is 0.
Update distances to neighboring nodes if a shorter path is found, and contin...read more
Q47. Longest Decreasing Subsequence Problem Statement
Given an array/list of integers ARR
consisting of N
integers, your task is to determine the length of the longest decreasing subsequence.
Explanation:
A subseque...read more
Find the length of the longest decreasing subsequence in an array of integers.
Use dynamic programming to keep track of the length of the longest decreasing subsequence ending at each index.
Initialize an array to store the length of the longest decreasing subsequence for each element.
Iterate through the array and update the length of the longest decreasing subsequence for each element based on previous elements.
Return the maximum length of the longest decreasing subsequence fo...read more
Q48. Clone Linked List with Random Pointer Problem Statement
Given a linked list where each node has two pointers: one pointing to the next node and another which can point randomly to any node in the list or null, ...read more
Deep copy a linked list with random pointers and return its head.
Create a deep copy of the linked list by creating new nodes rather than copying references.
Ensure the random pointers are correctly pointing to the corresponding nodes in the cloned list.
Implement the function to clone the linked list and return its head.
Consider the constraints and input format provided in the problem statement.
Explore if the cloning can be achieved without utilizing extra space.
Q49. Search in a Row-wise and Column-wise Sorted Matrix Problem Statement
You are given an N * N matrix of integers where each row and each column is sorted in increasing order. Your task is to find the position of ...read more
Software testing is the process of evaluating a software item to detect differences between given input and expected output.
Software testing ensures that the software is working as expected
It helps to identify defects and errors in the software
Testing can be done manually or using automated tools
Types of testing include functional, performance, security, and usability testing
Q50. Unique Paths Problem Statement
Given the dimensions of an M x N matrix, determine the total number of unique paths from the top-left corner to the bottom-right corner of the matrix.
Allowed moves are only to th...read more
The problem involves finding the total number of unique paths from the top-left corner to the bottom-right corner of an M x N matrix by moving only right or down.
Use dynamic programming to solve this problem efficiently.
Create a 2D array to store the number of unique paths for each cell in the matrix.
Initialize the first row and first column with 1 as there is only one way to reach each cell in those rows and columns.
For each cell (i, j), the number of unique paths is the sum...read more
Q51. 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
Identify the longest palindromic substring in a given string.
Iterate through the string and expand around each character to find palindromes
Keep track of the longest palindrome found so far
Return the longest palindromic substring with the smallest start index
Q52. First Missing Positive Problem Statement
You are provided with an integer array ARR
of length 'N'. Your objective is to determine the first missing positive integer using linear time and constant space. This me...read more
Find the smallest positive integer missing from an array of integers.
Iterate through the array and mark positive integers as visited using index as hash
Iterate through the array again to find the first missing positive integer
Return the smallest positive integer that was not visited
Q53. Next Greater Element Problem Statement
You are provided with an array or list ARR
containing N
positive integers. Your task is to determine the Next Greater Element (NGE) for each element in the array.
The Next...read more
Find the Next Greater Element for each element in an array.
Iterate through the array from right to left and use a stack to keep track of elements.
Pop elements from the stack until a greater element is found or the stack is empty.
Store the next greater element for each element in a result array.
Q54. Find Row K Problem Explanation
You are given a square binary matrix mat[n][n]
. The task is to determine an integer 'K' such that:
- All elements in the Kth row are 0.
- All elements in the Kth column are 1.
The v...read more
Find the row and column in a binary matrix where all elements in the row are 0 and all elements in the column are 1.
Iterate through each row and column to check for the conditions mentioned in the problem statement.
If a row has all 0s and the corresponding column has all 1s, return the index of that row/column.
If no such row/column exists, return -1.
Q55. Trapping Rainwater Problem Statement
You are given an array ARR
of long type, which represents an elevation map where ARR[i]
denotes the elevation of the ith
bar. Calculate the total amount of rainwater that ca...read more
Calculate the total amount of rainwater that can be trapped within given elevation map.
Iterate through the array to find the maximum height on the left and right of each bar.
Calculate the amount of water that can be trapped above each bar by taking the minimum of the maximum heights on the left and right.
Sum up the trapped water above each bar to get the total trapped water for the elevation map.
Q56. Infix to Postfix Conversion
You are provided with a string EXP
which represents a valid infix expression. Your task is to convert this given infix expression into a postfix expression.
Explanation:
An infix exp...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 by pushing them onto the stack.
Process the expression from left to right to convert to postfix form.
Q57. 14. you have given a string of multiline. you have to print the maximum occupancy word in each line and if there is some capital letter in each line then print each capital letter occupancy and then small lette...
read moreThe 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 than the maximum occupancy word, update the maximum occupa...read more
Q58. What are the different types of hashing? Suggest an alternative and a better way for Linear Chaining.
Different types of hashing and alternative for Linear Chaining
Different types of hashing include division, multiplication, and universal hashing
Alternative for Linear Chaining is Open Addressing
Open Addressing includes Linear Probing, Quadratic Probing, and Double Hashing
Q59. 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
Q60. Number with Maximum Probability Problem Statement
In this game, players Ninja Misha and Ninja Andrew each choose an integer within the range of 1 to 'N'. After their choices, a random integer 'C' is drawn from ...read more
Find the optimal number for Andrew to choose to maximize his winning probability in a game against Misha.
Andrew should choose the number equidistant from Misha's number and the random integer C to maximize his winning probability.
The optimal number for Andrew to choose is the average of Misha's number and C, rounded up if the average is not an integer.
If the average of Misha's number and C is an integer, Andrew should choose that number or the next highest integer if it excee...read more
Q61. Unique Element in Array
Given an arbitrary array arr
consisting of N
non-negative integers where every element appears thrice except for one. Your task is to find the element in the array that appears only once...read more
Find the unique element in an array where every element appears thrice except for one.
Use XOR operation to find the unique element.
Iterate through the array and XOR each element to find the unique element.
The XOR operation cancels out elements that appear thrice, leaving only the unique element.
Example: arr = [2, 2, 3, 2], XOR of all elements = 3.
Example: arr = [0, 1, 0, 1, 0, 1, 99], XOR of all elements = 99.
Q62. Pair Sum Problem Statement
Given an integer array ARR
of size N
and an integer S
, your task is to return a list of all pairs of elements such that the sum of each pair equals S
.
Input:
The first line contains t...read more
The task is to find pairs of elements in an array that sum up to a given target value.
Iterate through the array and for each element, check if the complement (target - current element) exists in a hash set.
If the complement exists, add the pair to the result list.
Ensure pairs are sorted based on the criteria mentioned in the question.
Q63. Count Inversions Problem Statement
Given an integer array ARR
of size N
, your task is to find the total number of inversions that exist in the array.
An inversion is defined for a pair of integers in the array ...read more
Count the total number of inversions in an integer array.
Iterate through the array and for each pair of elements, check if the conditions for inversion are met.
Use a nested loop to compare each element with all elements to its right.
Keep a count of the inversions found and return the total count at the end.
Q64. Minimum Jumps Problem Statement
Bob and his wife are in the famous 'Arcade' mall in the city of Berland. This mall has a unique way of moving between shops using trampolines. Each shop is laid out in a straight...read more
Find the minimum number of jumps Bob needs to make from shop 0 to reach the final shop, or return -1 if impossible.
Use Breadth First Search (BFS) to find the minimum number of jumps needed.
Keep track of the maximum reachable index at each step.
If the maximum reachable index is less than the current index, return -1 as it's impossible to reach the last shop.
Q65. Minimum Cost to Connect All Points Problem Statement
You are provided with an array, coordinates
, which represents integer coordinates of several points on a 2D plane. The task is to determine the minimum cost ...read more
Calculate the minimum cost to connect all points on a 2D plane using Manhattan distance.
Calculate Manhattan distance between each pair of points
Use a minimum spanning tree algorithm like Kruskal's or Prim's to find the minimum cost
Sum up the distances in the minimum spanning tree to get the minimum cost
Q66. Right View of Binary Tree Problem Statement
Given a Binary Tree of integers, your task is to compute and print the right view of it.
The right view of a Binary Tree is a set of nodes visible when the tree is vi...read more
The task is to compute and print the right view of a Binary Tree when viewed from the right side.
Traverse the tree level by level and keep track of the rightmost node at each level.
Print the rightmost node of each level to get the right view of the Binary Tree.
Use a queue data structure for level-order traversal of the Binary Tree.
Q67. Min Stack Problem Statement
Design a special stack that supports the following operations in constant time:
Push(num)
: Insert the given number into the stack.Pop
: Remove and return the top element from the st...read more
Design a special stack supporting constant time operations like push, pop, top, and getMin.
Use an additional stack to keep track of the minimum element at each level.
When pushing a new element, compare it with the top of the minimum stack to update the minimum.
Ensure constant time complexity for all operations by maintaining the minimum stack.
Example: Push(1), Push(2), getMin() should return 1.
Q68. Minimum Direction Changes Problem Statement
You are given a 2D grid with N
rows and M
columns. Each cell in the grid has a character from the set { 'U', 'L', 'D', 'R' } indicating the allowable move direction: ...read more
Find the minimum number of direction changes required to reach the bottom-right cell in a grid by following cell directions.
Iterate through the grid cells and keep track of the direction changes needed to reach each cell.
Use dynamic programming to calculate the minimum direction changes from top-left to bottom-right cell.
Consider the possible directions at each cell and choose the one with minimum direction changes.
Return the minimum number of direction changes needed to reac...read more
Q69. 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 S containing all characters in X.
Use a sliding window approach to find the smallest window in S containing all characters in X.
Keep track of the characters in X using a hashmap.
Move the window to the right until all characters in X are found, then shrink the window from the left to find the smallest window.
Return the smallest window found.
Example: S = 'abdd', X = 'bd' -> Output: 'bd'
Q70. Stream of Characters Problem Statement
You are provided with a list, DICTIONARY[]
, which contains a collection of words, along with a stream of characters (queries). The task is to implement a class CharacterSt...read more
Implement a class to check if a string formed by the last queried characters exists in a dictionary of words.
Use a trie data structure to efficiently store and search for words in the dictionary.
When solving a query, traverse the trie starting from the most recently queried character.
Return true if a valid word is found in the trie, otherwise return false.
Q71. Reverse Doubly Linked List Nodes in Groups
You are given a doubly linked list of integers along with a positive integer K
that represents the group size. Your task is to modify the linked list by reversing ever...read more
Reverse groups of K nodes in a doubly linked list
Iterate through the linked list in groups of K nodes
Reverse each group of K nodes
Handle the case where the number of nodes left is less than K
Q72. Triplets in a Sorted Doubly Linked List
Given a sorted doubly linked list of distinct nodes, determine how many triplets in the list have a sum equal to a given value 'X'. Each node in the list contains a uniqu...read more
Given a sorted doubly linked list of distinct nodes, find and count triplets with a sum equal to a given value 'X'.
Iterate through the list and for each node, use two pointers to find the other two nodes that sum up to 'X'.
Keep track of the count of triplets found and return it at the end.
Handle edge cases like when the list has less than 3 nodes or no triplets are found.
Q73. Weighted Job Scheduling Problem Statement
You have 'N' jobs, each with a start time, end time, and profit. Your task is to identify the maximum profit that can be earned by scheduling these jobs such that no tw...read more
The Weighted Job Scheduling problem involves maximizing profit by scheduling non-overlapping jobs with start time, end time, and profit given.
Sort the jobs based on their end times in ascending order.
Use dynamic programming to keep track of the maximum profit that can be earned by including or excluding each job.
For each job, find the maximum profit that can be earned by including it and excluding it.
Choose the maximum profit from the two options for each job.
Repeat the proce...read more
Q74. Finding Triplets in a Binary Tree Problem Statement
You are given a Binary Tree of integers and an integer 'X'. Your task is to find all the triplets in the tree whose sum is strictly greater than 'X'. The node...read more
Find all triplets in a binary tree whose sum is greater than a given integer X, with a grandparent-parent-child relationship.
Traverse the binary tree to find all possible triplets with the required relationship.
Keep track of the sum of each triplet and compare it with the given integer X.
Return the triplets that satisfy the condition in any order.
Ensure each triplet follows the format (grand-parent, parent, child).
Q75. Next Smallest Palindrome Problem Statement
Find the next smallest palindrome strictly greater than a given number 'N' represented as a string 'S'.
Explanation:
You are given a number in string format, and your ...read more
Find the next smallest palindrome greater than a given number represented as a string.
Convert the string to an integer, find the next greater palindrome, and convert it back to a string.
Handle cases where the number is a palindrome or has all digits as '9'.
Consider both odd and even length numbers when finding the next palindrome.
Q76. Dice Throws Problem Statement
You are given D
dice, each having F
faces numbered from 1 to F
. The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up numbers e...read more
The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up numbers equals the given 'target' sum.
Use dynamic programming to solve the problem efficiently.
Create a 2D array to store the number of ways to achieve each sum with different number of dice.
Iterate through the dice and sum possibilities to fill up the array.
Return the result modulo 10^9 + 7.
Optimize the solution to use no more than O(S) extra space by using rolling arra...read more
Q77. Minimum Number of Swaps to Sort an Array
Find the minimum number of swaps required to sort a given array of distinct elements in ascending order.
Input:
T (number of test cases)
For each test case:
N (size of the...read more
The minimum number of swaps required to sort a given array of distinct elements in ascending order.
Use graph theory and cycle detection to find the minimum number of swaps
Count the number of cycles in the permutation
Each cycle requires (cycle_length - 1) swaps to sort
Q78. 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.
Initialize two pointers, one for arrival times and one for departure times.
Increment the platform count when a train arrives and decrement when it departs.
Keep track of the maximum platform count needed.
Return the maximum platform count as the minimum number of platforms needed.
Q79. Reverse Doubly Linked List in Groups Problem
You are provided with a Doubly Linked List consisting of integers and a positive integer 'K', which represents the size of the group. Your task is to modify the link...read more
Reverse groups of K nodes in a doubly linked list
Iterate through the linked list in groups of K nodes
Reverse each group of K nodes
Update the pointers accordingly
Handle cases where the number of remaining nodes is less than K
Q80. Square Root with Decimal Precision Problem
Your task is to compute the square root of a given integer N
, such that the result is as accurate as D
decimal places. The aim is to ensure that the absolute differenc...read more
Compute square root of integer with specified decimal precision.
Implement a function to calculate square root using binary search or Newton's method.
Keep track of the precision required and stop when the difference is within the limit.
Handle multiple test cases efficiently to meet the time limit.
Ensure the output is formatted to the specified decimal places.
Consider edge cases like maximum input values and precision requirements.
Q81. Left View of a Binary Tree
Given a binary tree, your task is to print the left view of the tree. The left view of a binary tree contains the nodes visible when the tree is viewed from the left side.
Input:
The ...read more
Print the left view of a binary tree, containing nodes visible from the left side.
Traverse the tree level by level and print the first node of each level.
Use a queue to keep track of nodes at each level.
Handle null nodes represented by -1 in the input.
Q82. Maximum Subtree Sum Problem Statement
Given an arbitrary binary tree consisting of N nodes, your task is to find the largest subtree sum.
Input:
First line of each input has a single integer T, denoting the num...read more
Find the largest subtree sum in an arbitrary binary tree.
Traverse the binary tree to calculate the subtree sum of each node.
Keep track of the maximum subtree sum encountered so far.
Recursively calculate the subtree sum for each node by considering its left and right children.
Consider edge cases like when the tree is empty or has only one node.
Q83. Find Number of Islands
You are provided with a 2-dimensional array/list of size N rows by M columns, containing ones (1) and zeroes (0). Here, 1 represents land, and 0 represents water.
A cell is considered con...read more
Find the number of islands in a 2D matrix of 1s and 0s.
Iterate through the matrix and perform depth-first search (DFS) to find connected 1s.
Use a visited array to keep track of visited cells to avoid counting the same island multiple times.
Increment the island count whenever a new island is encountered.
Q84. Kth Smallest Element in an Unsorted Array
Given an unsorted array arr
of distinct integers and an integer k
, your task is to find the k-th
smallest element in the array.
Input:
The first line of input contains ...read more
Find the k-th smallest element in an unsorted array of distinct integers.
Sort the array and return the k-th element.
Use a min-heap to find the k-th smallest element efficiently.
Implement quickselect algorithm to find the k-th smallest element in linear time.
Q85. Anagram Pairs Verification Problem
Your task is to determine if two given strings are anagrams of each other. Two strings are considered anagrams if you can rearrange the letters of one string to form the other...read more
Check if two strings are anagrams of each other by comparing their sorted characters.
Sort the characters of both strings and compare them.
Use a dictionary to count the frequency of characters in each string and compare the dictionaries.
Ensure both strings have the same length before proceeding with the comparison.
Q86. Longest Increasing Subsequence Problem Statement
Given 'N' students standing in a row with specific heights, your task is to find the length of the longest strictly increasing subsequence of their heights, ensu...read more
Find the length of the longest strictly increasing subsequence of heights of students in a row.
Iterate through the heights array and for each element, find the length of the longest increasing subsequence ending at that element.
Use dynamic programming to keep track of the longest increasing subsequence length for each element.
Return the maximum length found in the dynamic programming array as the result.
Q87. Anagram Pairs Verification
In this task, you need to verify if two provided strings are anagrams of each other. Two strings are considered anagrams if you can rearrange the letters of one string to form the oth...read more
Verify if two strings are anagrams of each other by rearranging the letters.
Create character frequency maps for both strings.
Compare the frequency of characters in both maps to check if they are anagrams.
Return 'True' if the frequencies match, else return 'False'.
Q88. Boundary Traversal Problem Statement
Given a binary tree of integers, your task is to return the boundary nodes of this binary tree in an anti-clockwise direction starting from the root node.
Example:
Input:
T ...read more
Return the boundary nodes of a binary tree in an 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
Avoid repeating nodes in the output
Example: For input 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, output should be 1 2 4 7 6 3
Q89. Minimum Path Sum Problem Statement
Consider a 2-dimensional grid 'GRID' with 'N' rows and 'M' columns in Ninjaland. Each cell in the grid has an associated cost. The goal is to determine the minimum path sum fr...read more
The Minimum Path Sum Problem involves finding the minimum sum of costs along a path from the top-left to the bottom-right of a grid.
Use dynamic programming to calculate the minimum path sum by considering the costs of moving down or right at each cell.
Initialize a 2D array to store the minimum path sum values for each cell in the grid.
Iterate through the grid to calculate the minimum path sum for each cell based on the previous cells.
Return the minimum path sum for the bottom...read more
Q90. Loot Houses Problem Statement
A thief is planning to steal from several houses along a street. Each house has a certain amount of money stashed. However, the thief cannot loot two adjacent houses. Determine the...read more
Determine the maximum amount of money a thief can steal from houses without looting two consecutive houses.
Use dynamic programming to keep track of the maximum amount of money that can be stolen up to each house.
At each house, the thief can either choose to steal from the current house and the house two steps back, or skip the current house and steal from the previous house.
Return the maximum amount of money that can be stolen at the last house.
Q91. Print Nodes at Distance K from a Given Node
Given an arbitrary binary tree, a node of the tree, and an integer 'K', find all nodes that are at a distance K from the specified node, and return a list of these no...read more
Given a binary tree, a target node, and an integer K, find all nodes at distance K from the target node.
Traverse the binary tree to find the target node.
Use BFS to traverse the tree from the target node to nodes at distance K.
Keep track of the distance while traversing the tree.
Return the values of nodes at distance K in any order.
Rearrange Array to Form Largest Number
Given an array ARR
consisting of non-negative integers, rearrange the numbers to form the largest possible number. The digits within each number cannot be changed.
Input:
Rearrange the array elements to form the largest possible number by concatenating them.
Sort the array elements in a custom comparator function to get the largest number.
Convert the sorted array elements to strings and concatenate them to form the final number.
Handle cases where the numbers have the same prefix by comparing the concatenated forms.
Q93. Find First and Last Positions of an Element in a Sorted Array
Given a sorted array ARR
consisting of N
integers and an integer X
, find the first and last positions of occurrence of X
in the array.
Note:
1. The ...read more
Find the first and last positions of an element in a sorted array efficiently.
Use binary search to find the first occurrence of X in the array.
Use binary search to find the last occurrence of X in the array.
Handle cases where X is not present or present only once.
Return the first and last positions as 0-based indices.
Q94. Maze with N Doors and 1 Key Problem Statement
You are given an N x N maze where some cells have doors, and you have a key that can be used only once to open a door. Determine if there exists a path from the top...read more
Determine if there exists a path from the top-left cell to the bottom-right cell of a maze with N doors and 1 key.
Use depth-first search (DFS) or breadth-first search (BFS) to explore possible paths through the maze.
Keep track of the cells visited and use the key only once to open doors.
Check if the bottom-right cell is reachable after traversing the maze.
Handle edge cases such as the top-left and bottom-right cells having doors.
Return 'YES' if reachable, 'NO' otherwise.
Q95. Path Counting in Directed Graph
Given a directed graph with a specified number of vertices V
and edges E
, your task is to calculate the total number of distinct paths from a given source node S
to all other no...read more
Calculate total number of distinct paths from a given source node to all other nodes in a directed graph.
Use dynamic programming to keep track of the number of paths from the source node to each node.
Consider the modulo operation to handle large numbers efficiently.
Start by initializing the number of paths from the source node to itself as 1.
Iterate through all edges and update the number of paths for each destination node.
Return the total number of distinct paths modulo 10^9...read more
Q96. Given a BST containing distinct integers, and a number ‘X’, find all pairs of integers in the BST whose sum is equal to ‘X’.
Find pairs of integers in a BST whose sum is equal to a given number.
Traverse the BST and store the values in a hash set.
For each node, check if (X - node.value) exists in the hash set.
If yes, add the pair (node.value, X - node.value) to the result.
Continue traversal until all nodes are processed.
Q97. Find Missing Number In String Problem Statement
You have a sequence of consecutive nonnegative integers. By appending all integers end-to-end, you formed a string S
without any separators. During this process, ...read more
Given a string of consecutive nonnegative integers with one missing number, find the missing integer.
Iterate through the string and check for missing numbers by comparing adjacent integers
Calculate the sum of the original sequence and the sum of the integers in the string to find the missing number
Handle cases where there are multiple missing numbers or the string is invalid
Q98. Kth Largest Number in a Stream Problem Statement
Design a data structure that can handle an infinite stream of numbers and efficiently return the k-th largest number at any given time.
Explanation:
You will be ...read more
Design a data structure to efficiently return the k-th largest number from an infinite stream of numbers.
Implement a max heap to store the numbers in the stream.
Keep the heap size limited to k to efficiently find the k-th largest number.
Update the heap when adding new numbers or querying for the k-th largest number.
Q99. String Rearrangement Problem Statement
You are given a string of lowercase characters. The objective is to rearrange (reorder) the string so that no two adjacent characters are identical.
Return the rearranged ...read more
Given a string of lowercase characters, rearrange it so that no two adjacent characters are identical. Return the rearranged string or 'NO SOLUTION'.
Iterate through the string and count the frequency of each character.
Sort the characters based on their frequency in non-increasing order.
Place the characters with highest frequency first, alternating with other characters.
If there are more than half of the characters with the same frequency, 'NO SOLUTION' is returned.
Q100. Problem Statement: Find the Number of States
You are given ‘n’ cities, some of which are connected by bidirectional roads. You also have an ‘n x n’ matrix ‘roads’, where if city ‘i’ and city ‘j’ are connected b...read more
Find the number of states of cities connected by roads in a matrix.
Iterate through each city and perform depth-first search to find connected cities.
Use a visited array to keep track of visited cities.
Increment state count whenever a new state is found.
More about working at Amazon
Top HR Questions asked in PLRC
Interview Process at PLRC
Top Software Developer Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month