Add office photos
Engaged Employer

Amazon

4.1
based on 25.2k Reviews
Video summary
Proud winner of ABECA 2024 - AmbitionBox Employee Choice Awards
Filter interviews by

300+ TECHNOLOGICS GLOBAL Pvt Ltd, Bangalore India Interview Questions and Answers

Updated 27 Dec 2024
Popular Designations

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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.

Add your answer
Discover TECHNOLOGICS GLOBAL Pvt Ltd, Bangalore India interview dos and don'ts from real experiences

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer
Are these interview questions helpful?

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer
Share interview questions and help millions of jobseekers 🌟

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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
Ans.

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.

Add your answer

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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
Ans.

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

Add your answer

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

Ans.

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

Add your answer

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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 more
Ans.

To 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

Add your answer

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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
Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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
Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

Q136. Mean, Median, and Mode Problem Statement

Given an integer array ARR of size N, you need to compute the following three statistical measures:

  1. Mean: Implement the function mean() to calculate the mean of the arr...read more
Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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.

Ans.

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)]

Add your answer

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

Ans.

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.

View 1 answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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 more
Ans.

Merge 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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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].

Add your answer

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
Ans.

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

Add your answer

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
Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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

Add your answer

Q183. In question 2 when there are ‘n’ in the String whose position shouldn’t get affected during the swapping process

Ans.

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

View 1 answer

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
Ans.

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.

Add your answer

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

Ans.

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.

Add your answer

Q186. Print the level order traversal of the binary tree in the spiral form

Ans.

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

View 3 more answers

Q187. A String was given with a lot of words in it and I had to reverse all the words

Ans.

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

View 3 more answers

Q188. Minimum number of squares whose sum equals to given number n.

Ans.

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.

Add your answer

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

Ans.

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

Add your answer
Q190. What are the differences between static and dynamic memory allocation?
Ans.

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

Add your answer
Q191. How do you find the maximum difference between a node and its descendant in the same path in a binary tree?
Ans.

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

Add your answer
Q192. How would you assess your basic communication skills and confidence?
Ans.

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.

View 1 answer
Q193. What are the ACID properties in database management systems, and how does memory management work in this context?
Ans.

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

Add your answer

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

Ans.

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.

Add your answer

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

Ans.

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.

Add your answer
Q196. How can you find a Minimum Spanning Tree (MST) from a given graph using Kruskal’s algorithm?
Ans.

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.

Add your answer

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

Ans.

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

Add your answer

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?

Ans.

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

Add your answer

Q199. Given Two sorted array of size size n each. Find the Kth largest element in these two array (Expected Time Complexity Log(n))

Ans.

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.

Add your answer

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)

Ans.

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

Add your answer
1
2
3
4

More about working at Amazon

Top Rated Mega Company - 2024
Top Rated Company for Women - 2024
Top Rated Internet/Product Company - 2024
Contribute & help others!
Write a review
Share interview
Contribute salary
Add office photos

Interview Process at TECHNOLOGICS GLOBAL Pvt Ltd, Bangalore India

based on 119 interviews
5 Interview rounds
Coding Test Round - 1
Coding Test Round - 2
Video Call Round - 1
Video Call Round - 2
Video Call Round - 3
View more
Interview Tips & Stories
Ace your next interview with expert advice and inspiring stories

Top Software Developer Interview Questions from Similar Companies

3.7
 • 107 Interview Questions
3.8
 • 40 Interview Questions
4.0
 • 35 Interview Questions
3.7
 • 33 Interview Questions
3.6
 • 14 Interview Questions
3.5
 • 11 Interview Questions
View all
Share an Interview
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
75 Lakh+

Reviews

5 Lakh+

Interviews

4 Crore+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter