Amazon
300+ TECHNOLOGICS GLOBAL Pvt Ltd, Bangalore India Interview Questions and Answers
Q101. Spiral Order Traversal of a Binary Tree
Given a binary tree with N
nodes, your task is to output the Spiral Order traversal of the binary tree.
Input:
The input consists of a single line containing elements of ...read more
Implement a function to return the spiral order traversal of a binary tree.
Traverse the binary tree level by level, alternating between left to right and right to left.
Use a queue to keep track of nodes at each level.
Append nodes to the result list in the order they are visited.
Q102. 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.
Q103. Clone a Linked List with Random Pointers Problem Statement
Given a linked list where each node contains two pointers: the first points to the next node in sequence, and the second is a random pointer that can p...read more
Clone a linked list with random pointers by creating deep copy of the original list without duplicating references.
Create a deep copy of the linked list by instantiating new nodes for each node in the original list.
Ensure that the random pointers in the cloned list point to the corresponding nodes in the new list.
Do not duplicate references to original nodes while creating the clone.
Implement the function to clone the linked list without using additional space.
Verify that the...read more
Q104. Family Structure Problem Statement
Aakash belongs to a unique family structure where every male member (M) has a male child first followed by a female child, and every female member (F) has a female child first...read more
Determine the gender of the Kth child in the Nth generation based on a unique family structure.
Every male member has a male child first followed by a female child, and every female member has a female child first followed by a male child.
Given generation number N and position of the child K, determine the gender of the Kth child in the Nth generation.
Output 'Male' if the child is male, otherwise 'Female'.
Start the family tree from the male member, Aakash.
Q105. Largest Rectangle in Histogram Problem Statement
You are given an array/list HEIGHTS
of length N
, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.
Your t...read more
Find the area of the largest rectangle that can be formed within the bounds of a given histogram.
Iterate through the histogram bars and maintain a stack to keep track of increasing heights.
Calculate the area of the rectangle formed by each bar as the smallest height in the stack times the width.
Update the maximum area found so far and return it as the result.
Q106. Merge Two Sorted Linked Lists Problem Statement
You are provided with two sorted linked lists. Your task is to merge them into a single sorted linked list and return the head of the combined linked list.
Input:...read more
Merge two sorted linked lists into a single sorted linked list without using additional space beyond constant space complexity.
Create a dummy node to start the merged list
Iterate through both linked lists and compare nodes to merge them in sorted order
Update the next pointers accordingly
Handle cases where one list is empty or both lists are empty
Return the head of the merged linked list
Q107. Pythagorean Triplet Detection
Determine whether an array contains a Pythagorean triplet. A Pythagorean triplet exists if there are three integers x, y, z such that x2 + y2 = z2 within the array.
Input:
The firs...read more
Detect if an array contains a Pythagorean triplet.
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 in the array.
Check if the sum of squares of two numbers is equal to the square of the third number.
Q108. Find the Next Smaller Palindrome
You are provided with a number N
, expressed as a string S
, which is a palindrome. The task is to determine the largest number strictly less than N
that is also a palindrome.
Exa...read more
Find the largest palindrome number strictly less than the given palindrome number.
Iterate from the middle towards the start of the number and copy the digits to the left side to create the next smaller palindrome.
Handle cases where the middle digit is not 0 by decrementing it and mirroring the left side to the right side.
If the number is all 9s, change the first and last digits to 1 and fill the middle with 0s.
Q109. Longest Common Subsequence Problem Statement
Given two strings, S
and T
with respective lengths M
and N
, your task is to determine the length of their longest common subsequence.
A subsequence is a sequence tha...read more
Find the length of the longest common subsequence between two given strings.
Use dynamic programming to solve this problem efficiently.
Create a 2D array to store the lengths of common subsequences.
Iterate through the strings to fill the array and find the longest common subsequence length.
Q110. Group Anagrams Problem Statement
Given an array or list of strings called inputStr
, your task is to return the strings grouped as anagrams. Each group should contain strings that are anagrams of one another.
An...read more
Group anagrams in an array of strings based on their characters.
Iterate through the array of strings and sort each string to group anagrams together.
Use a hashmap to store the sorted string as key and the list of anagrams as value.
Return the values of the hashmap as the grouped anagrams.
Q111. Number of Islands Problem Statement
You are given a non-empty grid that consists of only 0s and 1s. Your task is to determine the number of islands in this grid.
An island is defined as a group of 1s (represent...read more
Count the number of islands in a grid of 0s and 1s connected horizontally, vertically, or diagonally.
Iterate through the grid and perform depth-first search (DFS) to mark visited land cells and count islands
Use a visited array to keep track of visited cells to avoid double counting
Check all neighboring cells (horizontally, vertically, and diagonally) of a land cell during DFS
Increment island count whenever a new island is encountered
Q112. Is Binary Heap Tree Problem Statement
You are given a binary tree of integers. Your task is to determine if it is a binary heap tree or not.
Input:
The first line of input contains an integer ‘T’ denoting the n...read more
Determine if a given binary tree is a binary heap tree or not based on certain properties.
Check if the binary tree is a complete binary tree where every level, except the last level, is completely filled and the last level is as far left as possible.
Ensure that every parent node is greater than all its children nodes, forming a max-heap.
If any node does not have a left or right child, it should be represented as -1 in the input.
Q113. Biggest Number Formation Problem
Your task is to construct the largest number possible by concatenating each of the provided positive integers in the array exactly once.
Input:
Integer T denoting the number of ...read more
Construct the largest number by concatenating positive integers in the array exactly once.
Sort the array of integers in a way that the concatenation of the numbers forms the largest possible number.
Use a custom comparator function to sort the numbers based on their concatenation value.
Join the sorted array elements to form the final largest number.
Q114. Infix to Postfix Conversion Problem Statement
You are given a string EXP
that represents a valid infix expression. Your task is to convert this infix expression into its corresponding postfix expression.
In inf...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 (* and / before + and -).
Handle parentheses by pushing them onto the stack and popping when necessary.
Q115. Level Order Traversal Problem Statement
Given a binary tree of integers, return the level order traversal of the binary tree.
Input:
The first line contains an integer 'T', representing the number of test cases...read more
Return the level order traversal of a binary tree given in level order with null nodes represented by -1.
Create a queue to store nodes for level order traversal
Start with the root node and enqueue it
While the queue is not empty, dequeue a node, print its value, and enqueue its children
Repeat until all nodes are traversed in level order
Q116. Bottom View of Binary Tree
Given a binary tree, determine and return its bottom view when viewed from left to right. Assume that each child of a node is positioned at a 45-degree angle from its parent.
Nodes in...read more
Return the bottom view of a binary tree when viewed from left to right.
Traverse the tree in level order and keep track of the horizontal distance and depth of each node
For each horizontal distance, update the node in the map if it is deeper than the current node
Return the values of the map in sorted order of horizontal distance
Q117. Special Binary Tree Verification
Determine whether a given binary tree is 'special'. A binary tree is defined as 'special' if every node either has zero or two children.
Example:
Input:
3
5 1
6 2 0 8
-1 -1 7 4 -1 ...read more
Check if a binary tree is 'special' if every node has zero or two children.
Traverse the binary tree and check if each non-leaf node has exactly two children.
Use a recursive approach to check each node's children.
Handle NULL nodes represented by -1 in the input.
Q118. Optimize Memory Usage Problem Statement
Alex wants to maximize the use of 'K' memory spaces on his computer. He has 'N' different document downloads, each with unique memory usage, and 'M' computer games, each ...read more
Maximize memory usage by pairing downloads and games within memory limit 'K'.
Sort the downloads and games in descending order.
Iterate through the sorted arrays to find the optimal pairs within memory limit 'K'.
Return the indices of the selected download and game pairs.
Q119. Given 2 integers a and b, the sequence which will be formed is a, b, a+b, a+2b…. i.e Current element = sum of the previous 2 elements. So now given a number k, how to figure out if it lies in the sequence or no...
read moreTo check if a number k lies in a sequence formed by adding previous 2 elements, start with a=0 and b=1 and iterate until k is found or exceeded.
Start with a=0 and b=1
Iterate through the sequence until k is found or exceeded
If k is found, return true. If exceeded, return false
Q120. Duplicate Integer in Array
Given an array ARR
of size N
, containing each number between 1 and N-1
at least once, identify the single integer that appears twice.
Input:
The first line contains an integer, 'T', r...read more
Identify the duplicate integer in an array containing numbers between 1 and N-1.
Iterate through the array and keep track of the frequency of each number using a hashmap.
Return the number with a frequency greater than 1 as the duplicate integer.
Time complexity can be optimized to O(N) using Floyd's Tortoise and Hare algorithm.
Example: For input [1, 2, 3, 4, 4], the output should be 4.
Q121. Ninja and Binary String Problem Statement
Ninja has a binary string S
of size N
given by his friend. The task is to determine if it's possible to sort the binary string S
in decreasing order by removing any num...read more
Determine if a binary string can be sorted in decreasing order by removing non-adjacent characters.
Check if the count of '1's in the string is equal to the length of the string, as it can be sorted in decreasing order by removing non-adjacent characters.
If the count of '1's is not equal to the length of the string, check if the string can be rearranged to form a decreasing order by removing non-adjacent characters.
Consider edge cases like all '0's or all '1's in the string.
Q122. 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
Q123. Snake and Ladder Problem Statement
Given a 'Snake and Ladder' board with N rows and N columns, where positions are numbered from 1 to (N*N) starting from the bottom left, alternating direction each row, find th...read more
Find the minimum number of dice throws required to reach the last cell on a 'Snake and Ladder' board.
Use Breadth First Search (BFS) algorithm to find the shortest path from the starting cell to the last cell.
Maintain a queue to keep track of the cells to be visited next.
Consider the effect of snakes and ladders on the movement of the player.
Return the minimum number of dice throws required to reach the last cell, or -1 if unreachable.
Q124. Subarray With Given Sum Problem Statement
Given an array ARR
of N integers and an integer S, determine if there exists a contiguous subarray within the array with a sum equal to S. If such a subarray exists, re...read more
Given an array of integers and a target sum, find a contiguous subarray with the sum equal to the target.
Iterate through the array while keeping track of the current sum and start index.
Use a hashmap to store the cumulative sum and its corresponding index.
If the current sum - target sum exists in the hashmap, a subarray with the target sum is found.
Return the start index and current index as the end index of the subarray.
Q125. 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.
Iterate through each denomination and update the array accordingly.
The final answer will be the value at the last cell of the array.
Q126. Clone a Linked List with Random Pointers
Given a linked list where each node contains two pointers: one pointing to the next node and another random pointer that can point to any node within the list (or be nul...read more
Create a deep copy of a linked list with random pointers.
Iterate through the original linked list and create a new node for each node in the list.
Store the mapping of original nodes to new nodes in a hashmap to handle random pointers.
Update the random pointers of new nodes based on the mapping stored in the hashmap.
Return the head of the copied linked list.
Q127. Sort Linked List Problem Statement
You are given a linked list of N
nodes where each node contains values 0, 1, and 2 exclusively. Your task is to sort the linked list.
Input:
The first line contains an integer...read more
Sort a linked list containing values 0, 1, and 2 exclusively.
Use three pointers to keep track of nodes with values 0, 1, and 2 separately.
Traverse the linked list and move nodes to their respective positions based on their values.
Finally, concatenate the three lists in the order 0 -> 1 -> 2 to get the sorted linked list.
Q128. Maximum Path Sum in a Matrix
Given an N*M matrix filled with integer numbers, determine the maximum sum that can be obtained from a path starting from any cell in the first row to any cell in the last row.
You ...read more
Find the maximum sum that can be obtained from a path in a matrix from the first row to the last row.
Use dynamic programming to keep track of the maximum sum at each cell.
Consider moving down, down-left, and down-right to calculate the maximum sum.
Start from the second row and update the values based on the maximum sum from the row above.
At the end, find the maximum sum in the last row to get the final result.
Q129. Merge Two Sorted Linked Lists
Given two sorted linked lists, your task is to merge them into a single sorted linked list. Return the head of the newly combined list.
Note:
The given linked lists may or may not ...read more
Merge two sorted linked lists into a single sorted linked list.
Create a dummy node to start the merged list
Compare nodes from both lists and add the smaller one to the merged list
Move the pointer of the merged list and the list with the smaller node
Handle cases where one list is exhausted before the other
Return the head of the merged list
Q130. String Compression Problem Statement
Implement a program that performs basic string compression. When a character is consecutively repeated more than once, replace the consecutive duplicates with the count of r...read more
Implement a program to compress a string by replacing consecutive duplicates with the count of repetitions.
Iterate through the string and keep track of consecutive characters and their counts.
Replace consecutive duplicates with the count of repetitions.
Ensure the count of repetitions is ≤ 9.
Return the compressed string.
Q131. K Most Frequent Words Problem Statement
Given an array or list WORDS
of 'N' non-empty words and an integer 'K', identify the 'K' most frequent words and return them sorted by their frequency, in descending orde...read more
Identify the K most frequent words in a list, sorted by frequency and lexicographical order.
Use a hashmap to store word frequencies
Use a min heap to keep track of K most frequent words
Sort the heap based on frequency and lexicographical order
Q132. K Closest Points to Origin Problem Statement
Your house is located at the origin (0,0) of a 2-D plane. There are N
neighbors living at different points on the plane. Your goal is to visit exactly K
neighbors wh...read more
Find the K closest points to the origin in a 2-D plane using Euclidean Distance.
Calculate the Euclidean Distance of each point from the origin
Sort the points based on their distances from the origin
Return the first K points as the closest points
Q133. LCA of Binary Tree Problem Statement
You are given a binary tree consisting of distinct integers and two nodes, X
and Y
. Your task is to find and return the Lowest Common Ancestor (LCA) of these two nodes.
The ...read more
Find the Lowest Common Ancestor (LCA) of two nodes in a binary tree.
Traverse the binary tree to find the paths from the root to nodes X and Y.
Compare the paths to find the last common node, which is the LCA.
Handle cases where one node is an ancestor of the other.
Consider edge cases like when X or Y is the root node.
Implement a recursive or iterative solution to find the LCA efficiently.
Q134. Ninja and Binary Tree Challenge
Implement a binary tree class from scratch. You are required to handle three types of queries on the binary tree:
- ‘I’ ‘VAL’: Insert a node with value 'VAL' into the binary tree....read more
Implement a binary tree class from scratch to handle insert, delete, and random retrieval queries.
Create a binary tree class with insert and delete methods.
Implement a method to randomly retrieve a node from the tree.
Ensure equal chance of selection for each node during random retrieval.
Handle different types of queries ('I', 'D', 'R') on the binary tree.
Return the value of the randomly chosen node for each test case.
Q135. Bridge in Graph Problem Statement
Given an undirected graph with V vertices and E edges, your task is to find all the bridges in this graph. A bridge is an edge that, when removed, increases the number of conne...read more
Find all the bridges in an undirected graph.
Use Tarjan's algorithm to find bridges in the graph.
A bridge is an edge whose removal increases the number of connected components.
Check for bridges by removing each edge and checking the number of connected components.
Return the edges that are bridges in non-decreasing order.
Q136. Mean, Median, and Mode Problem Statement
Given an integer array ARR
of size N
, you need to compute the following three statistical measures:
- Mean: Implement the function
mean()
to calculate the mean of the arr...read more
Implement functions to calculate mean, median, and mode of an integer array.
Calculate mean by summing all elements and dividing by total count
Calculate median by sorting array and finding middle element(s)
Calculate mode by finding element with highest frequency
Q137. String Ka Khel Problem Statement
Ninja is creating a new game ‘String Ka Khel’ for his gaming shop. In this game, players are given ‘N’ strings. The objective is to find the maximum length of strings that can b...read more
Compute the maximum length of a string that can be formed by joining given strings based on a condition.
Iterate through each string and store the count of strings ending with 'R' and 'B'.
Check if there are any strings ending with 'R' and 'B' that can be combined to form a longer string.
Return the maximum length of the string that can be formed or 0 if no combination is possible.
Q138. All Prime Numbers Less Than or Equal to N
Given a positive integer N
, your task is to return all the prime numbers less than or equal to N
.
Note:
1) A prime number is a number that has only two factors: 1 and t...read more
Return all prime numbers less than or equal to a given positive integer N.
Iterate from 2 to N and check if each number is prime using a helper function.
A number is prime if it is not divisible by any number from 2 to its square root.
Return the prime numbers in increasing order for each test case.
Q139. Construct Tree from Preorder Traversal
Given a list of integers pre[]
of size n
, representing the preorder traversal of a special binary tree where each node has 0 or 2 children, and a boolean array isLeaf[]
in...read more
Construct a binary tree from preorder traversal and leaf node information.
Create a binary tree using preorder traversal and leaf node information.
Use a stack to keep track of nodes and their children.
Handle leaf nodes appropriately to construct the tree.
Traverse the preorder list to construct the binary tree.
Q140. Minimum Sum in Matrix Problem Statement
You are given a 2D matrix 'ARR' of size 'N x 3' with integers, where 'N' is the number of rows. Your task is to compute the smallest sum achievable by selecting one eleme...read more
Find the smallest sum achievable by selecting one element from each row of a 2D matrix, following certain constraints.
Iterate through each row and find the minimum element that does not violate the constraints.
Keep track of the minimum sum achieved by selecting elements from each row.
Avoid selecting elements directly beneath previously selected elements.
Q141. Minimum Number of Swaps to Achieve K-Periodic String
Given a string S
of length N
, an array A
of length M
consisting of lowercase letters, and a positive integer K
, determine the minimum number of swaps require...read more
The minimum number of swaps required to make a string K-periodic by replacing characters with elements from an array.
Iterate through the string and check if each character matches the character K positions ahead.
Count the number of characters that need to be swapped to make the string K-periodic.
Use the array elements to swap characters in the string.
Return the total number of swaps needed for each test case.
Q142. Next Greater Number Problem Statement
Given a string S
which represents a number, determine the smallest number strictly greater than the original number composed of the same digits. Each digit's frequency from...read more
Given a number represented as a string, find the smallest number greater than the original with the same set of digits.
Iterate from right to left to find the first digit that can be swapped with a larger digit to make the number greater.
Swap this digit with the smallest digit to its right that is larger than it.
Sort the digits to the right of the swapped digit in ascending order to get the smallest number greater than the original.
If no such number exists, return -1.
Example: ...read more
Q143. Zig-Zag Array Rearrangement
You are provided with an array of distinct elements, and your task is to rearrange the array elements in a zig-zag manner. Specifically, for every odd index i
, the element ARR[i]
sho...read more
Rearrange array elements in a zig-zag manner where every odd index element is greater than its neighbors.
Iterate through the array and swap elements to satisfy the zig-zag condition.
Ensure that for every odd index i, ARR[i] > ARR[i-1] and ARR[i] > ARR[i+1].
Multiple correct answers may exist for a given array.
Q144. Intersection of Linked List Problem
You are provided with two singly linked lists containing integers, where both lists converge at some node belonging to a third linked list.
Your task is to determine the data...read more
Find the node where two linked lists merge, return -1 if no merging occurs.
Traverse both lists to find their lengths and the difference in lengths
Move the pointer of the longer list by the difference in lengths
Traverse both lists simultaneously until they meet at the merging point
Q145. Edit Distance Problem Statement
Given two strings S
and T
with lengths N
and M
respectively, your task is to find the "Edit Distance" between these strings.
The Edit Distance is defined as the minimum number of...read more
The task is to find the minimum number of operations required to convert one string into another using delete, replace, and insert operations.
Use dynamic programming to solve the problem efficiently.
Create a 2D array to store the edit distances between substrings of the two input strings.
Fill up the array based on the minimum of three possible operations: insert, delete, or replace.
The final answer will be the value at the bottom right corner of the array.
Example: For strings...read more
Q146. Check If Linked List Is Palindrome
Given a singly linked list of integers, determine if the linked list is a palindrome.
Explanation:
A linked list is considered a palindrome if it reads the same forwards and b...read more
Check if a given singly linked list of integers is a palindrome or not.
Traverse the linked list to find the middle element using slow and fast pointers.
Reverse the second half of the linked list.
Compare the first half with the reversed second half to check for palindrome.
Handle odd and even length linked lists separately.
Example: For input 1 2 1 -1, the linked list is a palindrome.
Q147. Rotate Matrix to the Right
You are provided with a matrix MAT
of size 'N' * 'M', where 'N' is the number of rows and 'M' is the number of columns. Your task is to rotate the matrix to the right 'K' times, where...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 the edge cases where 'K' is greater than the number of columns
Q148. 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.
Recursively try moving in all directions (up, down, left, right) until reaching the destination.
Return the list of valid paths sorted in alphabetical order.
Q149. Robot Delivery Path Problem
You are tasked with directing a robot from the top-left corner of an N*N matrix to a specified point (x, y), delivering a parcel. The robot is restricted to move only on flat areas (...read more
Determine if a robot can reach a specified destination in a matrix by moving only downwards or rightwards.
Start at (0,0) and move towards the destination (x, y) only downwards or rightwards.
Check if the path is clear (1) and avoid obstacles (0) while staying within matrix boundaries.
Return true if the robot can reach the destination, false otherwise.
Example: For input matrix [[1, 0, 1], [1, 1, 1], [1, 1, 5]] with destination (2, 2), the output is true.
Q150. BST Iterator Problem Statement
You are tasked with implementing a class BSTIterator
, which is designed to traverse a Binary Search Tree (BST) in the inorder manner. The class must support the following operatio...read more
Implement a BSTIterator class to traverse a Binary Search Tree in inorder manner.
Implement a constructor to initialize the iterator with the root of the BST.
Implement next() and hasNext() methods to traverse the BST in inorder.
Implement prev() and hasPrev() methods to access the previous element in the inorder traversal.
Use level-order traversal format to represent the tree input.
Output the inorder traversal of the binary search tree for each test case.
Q151. 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
Calculate the distance between two nodes in a binary tree.
Traverse the tree to find the paths from the root to each node
Find the lowest common ancestor of the two nodes
Calculate the distance by adding the distances from the LCA to each node
Q152. Reverse Linked List in Groups of K
You are provided with a linked list containing 'N' nodes and an integer 'K'. The task is to reverse the linked list in groups of size K, which means reversing the nodes in eac...read more
Reverse a linked list in groups of size K by reversing nodes in each group.
Iterate through the linked list in groups of size K
Reverse each group of nodes
Handle cases where the last group may not have K elements
Q153. Trapping Rain Water Problem Statement
You are given a long type array/list ARR
of size N
, representing an elevation map. The value ARR[i]
denotes the elevation of the ith
bar. Your task is to determine the tota...read more
Calculate the total amount of rainwater that can be trapped between given elevations in an array.
Iterate through the array and calculate the maximum height on the left and right of each bar.
Calculate the amount of water that can be trapped at each bar by taking the minimum of the maximum heights on the left and right.
Sum up the trapped water at each bar to get the total trapped water for the entire array.
Q154. Search in a 2D Matrix-II Problem Statement
Given a 2-D matrix of dimensions N x M
where each row is sorted in non-decreasing order and each column is sorted in non-decreasing order. You are also given an intege...read more
Given a 2D matrix with sorted rows and columns, determine if a given integer is present in the matrix.
Iterate through the matrix starting from the top right corner or bottom left corner to efficiently search for the target integer.
Use the sorted property of rows and columns to eliminate rows or columns based on the comparison with the target integer.
If the target integer is greater than the current element, move down in the matrix. If it is smaller, move left.
Continue this pr...read more
Q155. Group Anagrams Together
Given an array/list of strings STR_LIST
, group the anagrams together and return each group as a list of strings. Each group must contain strings that are anagrams of each other.
Example:...read more
Group anagrams together in a list of strings.
Iterate through the list of strings and sort each string to group anagrams together.
Use a hashmap to store the sorted string as key and the original string as value.
Return the values of the hashmap as the grouped anagrams.
Q156. Total Unique Paths Problem Statement
You are located at point ‘A’, the top-left corner of an M x N matrix, and your target is point ‘B’, the bottom-right corner of the same matrix. Your task is to calculate the...read more
The task is to calculate the total number of unique paths from the top-left to 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 the first row and column.
For each cell (i, j), the number of unique paths is the sum of the paths...read more
Q157. Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals.
Merge overlapping time intervals into mutually exclusive intervals.
Sort the intervals based on their start time.
Iterate through the intervals and merge overlapping intervals.
Output the mutually exclusive intervals.
Example: [(1,3), (2,6), (8,10), (15,18)] -> [(1,6), (8,10), (15,18)]
Q158. Maximum of all subarrays of size k(Expected Time Complexity O(N). Input : arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6} k = 3 Output : 3 3 4 5 5 5 6
Find the maximum element in each subarray of size k in a given array.
Iterate through the array from index 0 to n-k.
For each subarray of size k, find the maximum element.
Store the maximum elements in a separate array.
Return the array of maximum elements.
Q159. Find Maximum Element Between Two Nodes in a BST
Given a Binary Search Tree (BST) and two integers, NODE1 and NODE2, determine the maximum element found in the path between NODE1 and NODE2.
Explanation:
A Binary...read more
Find the maximum element between two nodes in a Binary Search Tree (BST) path.
Traverse the BST to find the path between NODE1 and NODE2.
Keep track of the maximum element encountered in the path.
Return the maximum element found, or -1 if NODE1 or NODE2 are not in the BST or no elements exist between them.
Q160. Convert a Binary Search Tree (BST) to a Greater Sum Tree
Given a Binary Search Tree of integers, transform it into a Greater Sum Tree where each node's value is replaced with the sum of all node values greater ...read more
Convert a Binary Search Tree to a Greater Sum Tree by replacing each node's value with the sum of all node values greater than the current node's value.
Traverse the BST in reverse inorder (right, root, left) to visit nodes in descending order.
Keep track of the running sum of visited nodes and update each node's value with this sum.
Modify the BST in place without creating a new tree.
Example: Input BST: 4 1 6 0 2 5 7 -1 -1 -1 3 -1 -1 -1 -1. Output Greater Sum Tree: 26 30 21 36 ...read more
Q161. Validate Binary Search Tree (BST)
You are given a binary tree with 'N' integer nodes. Your task is to determine whether this binary tree is a Binary Search Tree (BST).
BST Definition:
A Binary Search Tree (BST)...read more
Validate if a given binary tree is a Binary Search Tree (BST) or not.
Check if the left subtree of a node contains only nodes with data less than the node's data.
Check if the right subtree of a node contains only nodes with data greater than the node's data.
Recursively check if both the left and right subtrees are also binary search trees.
Example: For a node with data 4, left subtree nodes (2, 1, 3) are smaller and right subtree node (5) is larger.
Q162. Flatten a Linked List
You are provided with a linked list of 'N' nodes. Each node contains two pointers: NEXT
, pointing to the next node in the list, and CHILD
, pointing to a linked list. Each child linked list...read more
Flatten a linked list of sorted child linked lists into a single sorted linked list.
Traverse the linked list and maintain a priority queue to keep track of the next smallest element.
Merge the child linked lists into the priority queue while traversing the main linked list.
Pop elements from the priority queue to create the final flattened linked list.
Q163. 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.
Use binary search to find the pivot point where the array is rotated.
Based on the pivot point, apply binary search on the appropriate half of the array.
Return the index of the integer if found, else return -1.
Q164. Merge Two Balanced BSTs
Given two balanced binary search trees (BSTs) of integers, with 'N' and 'M' nodes respectively, your task is to merge these two BSTs into a single balanced BST and return the root node o...read more
Merge two balanced BSTs into a single balanced BST and return the root node of the new balanced BST.
Create inorder traversals of both BSTs
Merge the two inorder traversals into a single sorted array
Build a new balanced BST from the sorted array
Q165. Given two array , one of size m+n and contains m element and other position are empty , 2nd array is of size n and contains n element. both array are sorted , now merge the second array to first one such that t...
read moreMerge two sorted arrays into one sorted array with expected time complexity of (m+n).
Use a two-pointer approach to compare elements from both arrays and merge them into the first array.
Start comparing elements from the end of both arrays and place the larger element at the end of the first array.
Continue this process until all elements from the second array are merged into the first array.
Q166. Height of Binary Tree
You are provided with the Inorder and Level Order traversals of a Binary Tree composed of integers. Your goal is to determine the height of this Binary Tree without actually constructing i...read more
Calculate the height of a Binary Tree using Inorder and Level Order traversals without constructing the tree.
Use the properties of Inorder and Level Order traversals to determine the height of the Binary Tree.
The height of a Binary Tree is the number of edges on the longest path from the root to a leaf node.
Consider edge cases like a single node tree or empty tree while calculating the height.
Q167. 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 given binary tree is a Binary Search Tree (BST) or not.
Check if the left subtree of a node contains only nodes with data less than the node's data.
Check 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 an inorder manner and check if the elements are in sorted order.
Use recursion to validate each node in the tree.
Q168. Convert BST to Greater Sum Tree
Given a Binary Search Tree (BST) of integers, your task is to convert it into a greater sum tree. In the greater sum tree, each node's value should be replaced with the sum of al...read more
Convert a Binary Search Tree into a Greater Sum Tree by replacing each node's value with the sum of all nodes' values greater than the current node's value.
Traverse the BST in reverse inorder (right, root, left) to visit nodes in descending order.
Keep track of the running sum of visited nodes' values and update each node's value with this sum.
Recursively apply the above steps to all nodes in the BST.
Example: For input BST [4, 1, 6, 0, 2, 5, 7], the output Greater Sum Tree wil...read more
Q169. Word Search Problem Statement
Given a matrix of characters with dimensions N
* M
, you need to process 'Q'
queries. For each query, you are given a word 'W'
and you must determine if you can form word 'W'
by sel...read more
Given a matrix of characters, determine if a word can be formed by selecting adjacent characters.
Parse input to get matrix dimensions, characters, and queries
For each query, search for the word in the matrix by checking adjacent characters
Output '1' if word is present, '0' if not
Q170. Ninja's Pattern with Powers of 2
Ninja, who loves playing with numbers, sets out to arrange numbers within 'N' rows. The unique arrangement follows these rules: the first row contains 1 number, the second row c...read more
Generate a pattern of numbers in rows following a specific sequence based on powers of 2.
Start with 1 number in the first row, 2 numbers in the second row, 4 numbers in the third row, and so on based on powers of 2.
Fill the pattern with numbers in increasing sequence from 1 to 9, recycling back to 1 after reaching 9.
Output the pattern for a given number 'N' of rows.
Example: For N = 4, the pattern would be 1, 23, 4567, 89123456.
Q171. Problem: Pair Sum in a Binary Search Tree
Given a Binary Search Tree (BST) and an integer 'S', your task is to find all pairs of nodes within the BST that total to 'S' and return these pairs. If no such pair ex...read more
Find pairs of nodes in a BST that sum up to a given value 'S'.
Traverse the BST in-order to get a sorted list of nodes.
Use two pointers approach to find pairs with sum 'S'.
Keep track of visited nodes to avoid using the same node twice in a pair.
Q172. Max Element in the Path in a Binary Search Tree
Given a Binary Search Tree (BST) and two integers, NODE1 and NODE2, determine the maximum element found along the path from NODE1 to NODE2.
The binary search tree...read more
Find the maximum element in the path from NODE1 to NODE2 in a Binary Search Tree.
Traverse the BST from NODE1 to NODE2 while keeping track of the maximum element encountered.
If NODE1 or NODE2 does not exist in the BST, return -1.
The path does not include the values of NODE1 and NODE2 themselves, except when no intermediary nodes exist.
Q173. Palindrome Partitioning Problem Statement
You are given a string S
. Your task is to partition S
such that every substring of the partition is a palindrome. Your objective is to return all possible palindrome pa...read more
Given a string, partition it into palindromes and return all possible configurations.
Use backtracking to generate all possible palindrome partitions
Check if each substring is a palindrome before adding it to the partition
Return all valid partitions as an array of strings
Q174. Longest Substring Without Repeating Characters Problem Statement
Given a string S
of length L
, determine the length of the longest substring that contains no repeating characters.
Example:
Input:
"abacb"
Output...read more
Find the length of the longest substring without repeating characters in a given string.
Use a sliding window approach to keep track of the longest substring without repeating characters.
Use a hashmap to store the index of each character as it appears in the string.
Update the start index of the window when a repeating character is found.
Calculate the maximum length of the window as you iterate through the string.
Return the maximum length as the result.
Q175. Missing Numbers Problem Statement
You are provided with an array called ARR
, consisting of distinct positive integers. Your task is to identify all the numbers that fall within the range of the smallest and lar...read more
Identify missing numbers within the range of smallest and largest elements in an array.
Find the smallest and largest elements in the array.
Generate a list of numbers within the range of smallest and largest elements.
Remove the numbers that are present in the array to get the missing numbers.
Sort and return the missing numbers.
Q176. Course Schedule Problem Statement
You are enrolled as a student and must complete N
courses, numbered from 1 to N, to earn your degree.
Some courses have prerequisites, which means that to take course i
, you mu...read more
Check if it is feasible to complete all courses with prerequisites.
Create a graph representing the prerequisites with courses as nodes and edges as prerequisites.
Perform a topological sort on the graph to check if there is a cycle (if there is, then it's not feasible to complete all courses).
If there is no cycle, then it is feasible to complete all courses.
Q177. BFS in Graph Problem Statement
You are given an undirected and disconnected graph G(V, E)
having V
vertices numbered from 0
to V-1
and E
edges. Your task is to print its BFS traversal starting from the 0th vert...read more
BFS traversal of an undirected and disconnected graph starting from vertex 0.
Start BFS traversal from vertex 0 and visit all connected nodes in sorted order.
Use a queue to keep track of nodes to visit next.
Keep a visited array to avoid revisiting nodes.
Print the BFS traversal path as the nodes are visited.
Example: For input V=5, E=4 and edges 0-1, 0-2, 1-3, 2-4, the BFS traversal will be [0, 1, 2, 3, 4].
Q178. Calculate Sum of Proper Divisors
Given a natural number N
, return the sum of all its proper divisors.
A proper divisor of Y
is defined as a number X
such that X < Y
and Y % X = 0
.
Example:
Input:
T = 2
N = 6
N = ...read more
Calculate the sum of proper divisors of a given natural number.
Iterate from 1 to sqrt(N) and check for divisors
If a divisor is found, add it to the sum and also add N/divisor if it is not the same as divisor
Return the sum as the result
Q179. Left View of a Binary Tree Problem Statement
Given a binary tree, your task is to print the left view of the tree.
Example:
Input:
The input will be in level order form, with node values separated by a space. U...read more
Print the left view of a binary tree given in level order form.
Traverse the tree level by level and print the first node encountered at each level
Use a queue to perform level order traversal
Keep track of the level while traversing the tree
Q180. Paths in a Matrix Problem Statement
Given an 'M x N' matrix, print all the possible paths from the top-left corner to the bottom-right corner. You can only move either right (from (i,j) to (i,j+1)) or down (fro...read more
Print all possible paths from top-left to bottom-right in a matrix by moving only right or down.
Use backtracking to explore all possible paths from top-left to bottom-right in the matrix.
At each cell, recursively explore moving right and down until reaching the bottom-right corner.
Keep track of the current path and add it to the result when reaching the destination.
Q181. Binary Search Tree Iterator Problem Statement
Design and implement a class BSTIterator
to perform an in-order traversal over a Binary Search Tree (BST). Your implementation should include the following methods:...read more
Design and implement a class BSTIterator to perform in-order traversal over a Binary Search Tree (BST).
Implement a parameterized constructor to initialize the iterator with the root of the BST.
Implement a method 'next()' to return the next smallest element in in-order traversal.
Implement a method 'hasNext()' to check if there exists a next smallest element in traversal.
Ensure the output is the in-order traversal of the BST using the iterator.
Q182. First Non-Repeating Character Problem Statement
You are given a string consisting of English alphabet characters. Your task is to identify and return the first character in the string that does not repeat. If e...read more
Identify and return the first non-repeating character in a string, or the first character if all characters repeat.
Iterate through the string to count the frequency of each character
Iterate through the string again to find the first character with frequency 1
If no such character is found, return the first character of the string
Q183. In question 2 when there are ‘n’ in the String whose position shouldn’t get affected during the swapping process
Explaining how to handle 'n' in a string during swapping process
Identify the positions of 'n' in the string
Exclude those positions from the swapping process
Use a temporary variable to swap the characters
Ensure the swapped characters are not 'n'
Return the modified string
Q184. 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 of the numbers.
Keep the two heaps balanced by ensuring the size difference is at most 1.
If the total number of elements is odd, the median is the top element of the larger heap. If even, average the tops of both heaps.
Update the heaps as new elements are added to the stream.
Q185. Remove Duplicates from a Sorted Linked List
Your friend has homework to complete. Help him by removing duplicates from a sorted linked list.
You are given the 'Head' of a sorted linked list. Modify the list to ...read more
Remove duplicates from a sorted linked list without adjacent duplicates.
Traverse the linked list while comparing current and next nodes.
If they are equal, skip the next node by updating the current node's next pointer.
Repeat until the end of the list is reached.
Q186. Print the level order traversal of the binary tree in the spiral form
Print the level order traversal of binary tree in spiral form
Perform level order traversal of the binary tree
Alternate the direction of traversal for each level
Use a stack to reverse the order of nodes in each level
Print the nodes in the order of traversal
Q187. A String was given with a lot of words in it and I had to reverse all the words
Reverse all the words in a given string
Split the string into an array of words
Loop through the array and reverse each word
Join the reversed words back into a string
Q188. Minimum number of squares whose sum equals to given number n.
Find the minimum number of squares whose sum equals to a given number n.
Use dynamic programming to solve the problem efficiently.
Start with finding the square root of n and check if it is a perfect square.
If not, then try to find the minimum number of squares required for the remaining number.
Repeat the process until the remaining number becomes 0.
Return the minimum number of squares required for the given number n.
Q189. Given a n-ary tree. Devise an algo which determines the position at which the 3rd B is present from the given index in constant time complexity
The algorithm finds the position of the 3rd occurrence of 'B' in an n-ary tree from a given index in constant time complexity.
Traverse the n-ary tree using a depth-first search (DFS) algorithm
Keep track of the count of 'B' occurrences
When the count reaches 3, return the current position
If the end of the tree is reached before the 3rd 'B', return -1
Static memory allocation is done at compile time, while dynamic memory allocation is done at runtime.
Static memory allocation is fixed in size and allocated on the stack, while dynamic memory allocation can change in size and is allocated on the heap.
Static memory allocation is determined at compile time, while dynamic memory allocation is determined at runtime.
Static memory allocation is less flexible but faster, while dynamic memory allocation is more flexible but slower.
Ex...read more
To find the maximum difference between a node and its descendant in the same path in a binary tree, we can perform a depth-first search while keeping track of the minimum value encountered so far.
Perform a depth-first search on the binary tree, keeping track of the minimum value encountered so far in the path.
At each node, calculate the difference between the current node value and the minimum value encountered so far in the path.
Update the maximum difference found so far if ...read more
I would rate my basic communication skills as strong and my confidence as high.
I have experience effectively communicating with team members and stakeholders.
I am comfortable presenting my ideas and discussing technical concepts.
I actively seek feedback to improve my communication skills.
I have successfully led meetings and discussions on project requirements.
ACID properties ensure database transactions are processed reliably. Memory management involves allocating and deallocating memory efficiently.
ACID properties: Atomicity, Consistency, Isolation, Durability
Atomicity ensures that either all operations in a transaction are completed successfully or none are
Consistency ensures that the database remains in a valid state before and after the transaction
Isolation ensures that transactions are executed independently without interfere...read more
Q194. Given a dictionary with limited words. Check if the string given to you is a composite of two words which are already present in the dictionary
Check if a given string is a composite of two words from a limited dictionary.
Create a hash set of all the words in the dictionary.
Iterate through all possible pairs of substrings in the given string.
Check if both substrings are present in the hash set.
If yes, return true. Else, return false.
Q195. Given a string of alphabet of at most 5 characters. Write a function which returns a unique number for each string with O(1) space
Function to return unique number for each string of at most 5 characters with O(1) space.
Use a hash function to map each string to a unique number.
Ensure that the hash function has a constant time complexity.
Use a fixed-size array to store the hash values for each string.
Kruskal's algorithm finds MST by sorting edges, adding smallest edge that doesn't create a cycle, repeat until all vertices are connected.
Sort all edges in non-decreasing order of their weights.
Initialize an empty graph to store the MST.
Iterate through sorted edges and add the smallest edge that doesn't create a cycle in the MST.
Repeat until all vertices are connected in the MST.
Q197. make copy of a linked list which has two pointer one point to next node and other one point to arbitrary node in linked list
To make a copy of a linked list with two pointers, iterate through the original list and create a new node for each element.
Iterate through the original linked list
Create a new node for each element
Set the 'next' pointer of each new node
Set the 'arbitrary' pointer of each new node
Q198. Given a bt and a 2d matrix M. where M[i,j]=1 if i is ancessostor of j. Initially all elements of M is set to zero. Feed this matrix?
The question asks how to feed a 2D matrix with values based on the given binary tree.
Traverse the binary tree and for each node, update the corresponding row in the matrix
Use a recursive function to update the matrix values
Start with the root node and recursively update its descendants
Set M[i, j] to 1 if node i is an ancestor of node j
Repeat the process for all nodes in the binary tree
Q199. Given Two sorted array of size size n each. Find the Kth largest element in these two array (Expected Time Complexity Log(n))
To find the Kth largest element in two sorted arrays, we can use the merge step of merge sort algorithm.
Merge the two arrays into a single sorted array using a modified merge sort algorithm.
Return the Kth element from the merged array.
Q200. Convert a binary tree to a DLL such that a next node for DLL is selected in a top down order in zig-zag manner. O(n) space was allowed, but not O(2n)
Convert binary tree to DLL in zig-zag order with O(n) space
Traverse the tree in level order using a queue
For each level, alternate between left-to-right and right-to-left order
Create a DLL using the nodes in the order they are visited
Return the head of the DLL
More about working at Amazon
Top HR Questions asked in TECHNOLOGICS GLOBAL Pvt Ltd, Bangalore India
Interview Process at TECHNOLOGICS GLOBAL Pvt Ltd, Bangalore India
Top Software Developer Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month