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

100+ ApexGig Interview Questions and Answers

Updated 18 Sep 2024
Popular Designations

Q1. Fish Eater Problem Statement

In a river where water flows from left to right, there is a sequence of 'N' fishes each having different sizes and speeds. The sizes of these fishes are provided in an array called ...read more

Ans.

Given a river with fishes of different sizes and speeds, determine how many fishes survive after encounters.

  • Iterate through the array of fishes and simulate encounters between fishes to determine survivors

  • Use a stack to keep track of surviving fishes

  • Compare sizes of fishes to determine which fish eats the other

View 1 answer

Q2. First Missing Positive Problem Statement

You are provided with an integer array ARR of length 'N'. Your objective is to determine the first missing positive integer using linear time and constant space. This me...read more

Ans.

The task is to find the lowest positive integer that does not exist in the given array of integers.

  • Iterate through the array and mark the positive integers as visited using the array indices.

  • Iterate through the marked array and return the index of the first unmarked element.

  • If all positive integers are marked, return the length of the array + 1 as the missing positive integer.

Add your answer

Q3. Container with Most Water Problem Statement

Given a sequence of 'N' space-separated non-negative integers A[1], A[2], ..., A[i], ..., A[n], where each number in the sequence represents the height of a line draw...read more

Ans.

Given a sequence of non-negative integers representing the height of lines on a cartesian plane, find two lines that form a container with the maximum area of water.

  • Use two pointers approach to find the maximum area

  • Start with the widest container and gradually move the pointers towards each other

  • Calculate the area at each step and update the maximum area

  • The area is calculated as the minimum height of the two lines multiplied by the distance between them

Add your answer

Q4. Pair Sum Problem Statement

You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to find and return a list of all pairs of elements where each sum of a pair equals 'S'.

Note:

Each pa...read more

Ans.

Given an array and a target sum, find all pairs of elements in the array that add up to the target sum.

  • Create an empty list to store the pairs

  • Iterate through the array and for each element, check if there is a complement (target sum minus the current element) in the array

  • If a complement is found, add the pair (current element, complement) to the list

  • Sort the list of pairs in non-decreasing order of their first value

  • If two pairs have the same first value, sort them based on th...read more

Add your answer
Discover ApexGig interview dos and don'ts from real experiences

Q5. Frequency in a Sorted Array Problem Statement

Given a sorted array ARR and a number X, your task is to determine the count of occurrences of X within ARR.

Note:

  • If X is not found in the array, return 0.
  • The ar...read more
Ans.

The task is to count the number of occurrences of a given number in a sorted array.

  • Use binary search to find the first and last occurrence of the given number in the array.

  • Subtract the indices of the first and last occurrence to get the count.

  • Handle the case when the number is not found in the array.

Add your answer

Q6. Kth Smallest and Largest Element Problem Statement

You are provided with an array 'Arr' containing 'N' distinct integers and a positive integer 'K'. Your task is to find the Kth smallest and Kth largest element...read more

Ans.

Find the Kth smallest and largest elements in an array.

  • Sort the array and return the Kth element for smallest and (N-K+1)th element for largest.

  • Use a priority queue to efficiently find the Kth smallest and largest elements.

  • Handle edge cases where K is equal to 1 or N.

Add your answer
Are these interview questions helpful?

Q7. Longest Increasing Subsequence Problem Statement

Given an array of integers with 'N' elements, determine the length of the longest subsequence where each element is greater than the previous element. This subse...read more

Ans.

The task is to find the length of the longest increasing subsequence in a given array.

  • Iterate through the array and keep track of the longest increasing subsequence length at each index.

  • Use dynamic programming to store the lengths of increasing subsequences ending at each index.

  • Return the maximum length from the dynamic programming array.

Add your answer

Q8. Minimum Travel Cost Problem

You are given a country called 'Ninjaland' with 'N' states, numbered from 1 to 'N'. These states are connected by 'M' bidirectional roads, each with a specified travel cost. The aim ...read more

Ans.

The task is to select 'N' - 1 roads in a country with 'N' states, such that the tourist bus can travel to every state at least once at minimum cost.

  • The problem can be solved using a minimum spanning tree algorithm, such as Kruskal's algorithm or Prim's algorithm.

  • Create a graph representation of the country using the given roads and their costs.

  • Apply the minimum spanning tree algorithm to find the minimum cost roads that connect all the states.

  • Print the selected roads and thei...read more

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

Q9. Valid Sudoku Problem Statement

You are given a 9 X 9 2D matrix named MATRIX which contains some cells filled with digits (1 to 9) and some cells left empty (denoted by 0).

Your task is to determine if there is ...read more

Ans.

The task is to determine if a given 9x9 matrix can be filled with digits 1-9 to form a valid Sudoku solution.

  • Iterate through each cell in the matrix.

  • For each empty cell, try filling it with a digit from 1-9 and check if it satisfies the Sudoku conditions.

  • Use helper functions to check if the digit is valid in the current row, column, and sub-matrix.

  • If a valid digit is found, recursively fill the next empty cell.

  • If all cells are filled and the Sudoku conditions are satisfied, r...read more

Add your answer

Q10. Flip Bits Problem Explanation

Given an array of integers ARR of size N, consisting of 0s and 1s, you need to select a sub-array and flip its bits. Your task is to return the maximum count of 1s that can be obta...read more

Ans.

Given an array of 0s and 1s, find the maximum count of 1s by flipping a sub-array at most once.

  • Iterate through the array and keep track of the maximum count of 1s obtained by flipping a sub-array.

  • Consider flipping a sub-array only when it results in increasing the count of 1s.

  • Update the maximum count of 1s as you iterate through the array.

  • Return the maximum count of 1s obtained after considering all possible sub-arrays.

Add your answer

Q11. Count Inversions Problem Statement

Given an integer array ARR of size N, your task is to find the total number of inversions that exist in the array.

An inversion is defined for a pair of integers in the array ...read more

Ans.

The task is to count the number of inversions in an array.

  • Iterate through the array and for each element, compare it with all the elements that come after it.

  • If the current element is greater than any of the elements that come after it, increment the inversion count.

  • Return the inversion count as the result.

Add your answer

Q12. Missing Number in Concatenated Sequence

You were given a sequence of consecutive nonnegative integers but missed one while appending them to create a string S. Your task is to identify the missing integer from ...read more

Ans.

The task is to find the missing number in a string of consecutive nonnegative integers.

  • Iterate through the string and check if each substring can form a valid number

  • If a substring forms a valid number, check if it is consecutive with the previous number

  • If a substring does not form a valid number or is not consecutive, it is the missing number

  • Handle edge cases such as multiple missing numbers or all numbers already present

Add your answer

Q13. Simplify Directory Path Problem Statement

You are provided with a directory path in Unix-style notation, and your task is to simplify it according to given rules.

In a Unix-style file system:

  • A dot (.) refers ...read more
Ans.

The task is to simplify a given Unix-style directory path and determine the final destination.

  • Replace multiple slashes with a single slash

  • Handle dot (.) by ignoring it

  • Handle double dot (..) by removing the previous directory from the path

  • Ensure the simplified path starts with a slash and does not have a trailing slash

Add your answer

Q14. Anagram Pairs Verification Problem

Your task is to determine if two given strings are anagrams of each other. Two strings are considered anagrams if you can rearrange the letters of one string to form the other...read more

Ans.

The task is to determine whether two given strings form an anagram pair or not.

  • Anagrams are words or names that can be formed by rearranging the letters of another word

  • Check if the two strings have the same characters with the same frequency

  • Convert the strings to character arrays and sort them

  • Compare the sorted arrays to check if they are equal

Add your answer

Q15. Subsequences of String Problem Statement

You are provided with a string 'STR' that consists of lowercase English letters ranging from 'a' to 'z'. Your task is to determine all non-empty possible subsequences of...read more

Ans.

Generate all possible subsequences of a given string.

  • Use recursion to generate all possible subsequences by including or excluding each character in the string.

  • Maintain the order of characters while generating subsequences.

  • Handle base cases where the string is empty or has only one character.

  • Store the generated subsequences in an array of strings.

Add your answer

Q16. Clone Linked List with Random Pointer Problem Statement

Given a linked list where each node has two pointers: one pointing to the next node and another which can point randomly to any node in the list or null, ...read more

Ans.

Cloning a linked list with random pointers by creating new nodes rather than copying references.

  • Create a deep copy of the linked list by iterating through the original list and creating new nodes with the same values.

  • Update the random pointers of the new nodes by mapping the original node's random pointer index to the corresponding new node.

  • Ensure the cloned linked list is an exact copy of the original by validating the values and random pointers.

  • The cloning process can be ac...read more

Add your answer

Q17. Matrix Median Problem Statement

You are provided with a matrix containing 'N' rows and 'M' columns filled with integers. Each row is sorted in non-decreasing order. Your task is to find the overall median of th...read more

Ans.

Find the overall median of a matrix with sorted rows.

  • Merge all elements of the matrix into a single sorted array

  • Calculate the median of the merged array

  • Handle odd number of elements by directly finding the middle element

Add your answer

Q18. Count Triplets in a Sorted Doubly Linked List

You are provided with an integer X and a non-decreasing sorted doubly linked list consisting of distinct nodes.

Your task is to find and return the count of triplet...read more

Ans.

Count triplets in a sorted doubly linked list that sum up to a given value.

  • Iterate through the list and for each node, find pairs that sum up to X-nodeValue.

  • Use two pointers approach to find pairs efficiently.

  • Keep track of count of triplets found while iterating through the list.

View 1 answer

Q19. Chocolate Distribution Problem

You are given an array/list CHOCOLATES of size 'N', where each element represents the number of chocolates in a packet. Your task is to distribute these chocolates among 'M' stude...read more

Ans.

Distribute chocolates among students to minimize difference between largest and smallest packets.

  • Sort the array of chocolates packets.

  • Use sliding window technique to find the minimum difference between packets distributed to students.

  • Return the minimum difference as the output.

Add your answer

Q20. Subtree of Another Tree Problem Statement

Given two binary trees, T and S, determine whether S is a subtree of T. The tree S should have the same structure and node values as a subtree of T.

Explanation:

A subt...read more

Ans.

Given two binary trees T and S, determine if S is a subtree of T with the same structure and node values.

  • Traverse both trees and check if S is a subtree of T at each node

  • Use recursion to compare subtrees

  • Handle edge cases like empty trees or null nodes

Add your answer

Q21. Triplet Count in a Sorted Doubly Linked List Problem

Count the number of triplets in a sorted doubly linked list such that their sum equals a given integer 'X'. The list is composed of distinct node values.

Exp...read more

Ans.

Count the number of triplets in a sorted doubly linked list such that their sum equals a given integer 'X'.

  • Iterate through the linked list and for each node, use two pointers to find the other two nodes that sum up to 'X'.

  • Keep track of the count of triplets found while traversing the list.

  • Return the final count of triplets that sum up to 'X'.

Add your answer

Q22. Number of Islands Problem Statement

You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in this ma...read more

Ans.

The task is to find the number of islands present in a 2-dimensional array filled with ones and zeroes.

  • Iterate through each cell in the array

  • If the cell is land (1) and not visited, perform a depth-first search to find all connected land cells

  • Increment the count of islands for each connected component found

Add your answer

Q23. Sort Linked List Based on Actual Values

Given a Singly Linked List of integers that are sorted based on their absolute values, the task is to sort the linked list based on the actual values.

The absolute value ...read more

Ans.

Sort a Singly Linked List based on actual values instead of absolute values.

  • Traverse the linked list and store the nodes in an array.

  • Sort the array based on the actual values of the nodes.

  • Reconstruct the linked list using the sorted array.

Add your answer

Q24. Ninja's Jump Task

The Ninja has been given a challenge by his master to reach the last stone. These stones are represented as an array of numbers. The Ninja can jump using either odd-numbered or even-numbered j...read more

Ans.

Find the number of starting indices from which a Ninja can reach the last stone by following specific jump rules.

  • Iterate through the array and keep track of the indices that satisfy the jump rules.

  • Use dynamic programming to efficiently determine the number of starting indices.

  • Consider odd and even jumps separately to handle the different conditions.

  • Example: For the input [10, 13, 12, 14, 15], the Ninja can start at indices 0 and 1 to reach the last stone.

Add your answer

Q25. The Celebrity Problem

Imagine there are 'N' people at a party, each assigned a unique ID from 0 to N-1. A celebrity at the party is a person who is known by everyone but knows no one else.

Problem Statement:

Yo...read more

Ans.

Identify the celebrity at a party where one person knows everyone but is not known by anyone.

  • Use a two-pointer approach to eliminate non-celebrity candidates.

  • Start with two pointers at the beginning and end of the party.

  • If A knows B, A cannot be the celebrity; move A to B.

  • If A does not know B, B cannot be the celebrity; move B to A.

  • Repeat until only one person remains; check if this person is known by everyone.

  • Return the ID of the celebrity or -1 if none exists.

Add your answer

Q26. Reachable Nodes Problem Statement

You are provided with a graph containing 'N' nodes and 'M' unidirectional edges. Your task is to determine the number of nodes that can be reached from each node 'i', where 0 <...read more

Ans.

The task is to determine the number of nodes that can be reached from each node in a graph.

  • Create an adjacency list to represent the graph.

  • Use Depth First Search (DFS) to traverse the graph and count reachable nodes from each node.

  • Initialize a count array to store the number of reachable nodes for each node.

  • Update the count array while traversing the graph using DFS.

  • Output the count array for each test case.

Add your answer

Q27. Maximum of All Subarrays of Size K

You are provided with an array A containing N integers. Your task is to determine the maximum element in every contiguous subarray of size K as you move from left to right thr...read more

Ans.

Find maximum element in every contiguous subarray of size K in an array.

  • Iterate through the array and maintain a deque to store the indices of elements in decreasing order.

  • Remove indices from the deque that are outside the current window of size K.

  • The front of the deque will always have the index of the maximum element in the current window.

Add your answer

Q28. Flip Bit to Win Problem Statement

You are given a task to help ninjas maximize their practice area in a dense forest represented by a sequence of trees (1s) and empty places (0s) in the binary representation of...read more

Ans.

Given an integer representing a binary sequence, find the maximum consecutive ones by flipping one bit.

  • Iterate through the binary representation of the integer to find the longest sequence of ones.

  • Track the positions of zeros to determine where to flip a bit for maximizing consecutive ones.

  • Update the count of consecutive ones after flipping a zero to one.

  • Return the maximum length of consecutive ones obtained by flipping one bit.

Add your answer

Q29. Saving Money Problem Statement

Ninja is adventurous and loves traveling while being mindful of his expenses. Given a set of 'N' stations connected by 'M' trains, each train starting from station 'A' and reachin...read more

Ans.

Given a set of stations connected by trains, find the cheapest fare from a source to a destination with a maximum number of stops allowed.

  • Iterate through all possible routes with up to 'K' stops using a graph traversal algorithm like DFS or BFS.

  • Keep track of the cost for each route and return the minimum cost found.

  • If no route is found within the maximum stops allowed, return '-1'.

Add your answer

Q30. Find the Row with the Maximum Number of 1's

You are given a non-empty grid MAT with 'N' rows and 'M' columns, where each element is either 0 or 1. All rows are sorted in ascending order.

Your task is to determi...read more

Ans.

Find the row with the maximum number of 1's in a grid of 0's and 1's.

  • Iterate through each row of the grid and count the number of 1's in each row.

  • Keep track of the row index with the maximum number of 1's seen so far.

  • Return the index of the row with the maximum number of 1's.

Add your answer

Q31. Knight Probability in Chessboard

Calculate the probability that a knight remains on an N x N chessboard after making K moves. Initially, the knight is placed at a given position on the board. It can move in any...read more

Ans.

Calculate the probability that a knight remains on an N x N chessboard after making K moves.

  • Use dynamic programming to calculate the probability of the knight staying on the board after each move.

  • Consider all possible moves the knight can make from its current position.

  • Keep track of the probabilities at each position on the board after each move.

  • Normalize the probabilities at the end to get the final result accurate to six decimal places.

Add your answer

Q32. Favourite Operation - Problem Statement

Ninja has studied the bitwise operations ‘AND’ and ‘XOR’. He received an assignment that involves these operations and needs help to complete it efficiently before the de...read more

Ans.

Calculate bitwise 'AND' and 'XOR' of subarrays of size at most K in an array efficiently.

  • Iterate through all subarrays of size at most K and calculate bitwise 'AND'.

  • Calculate the 'XOR' of all the bitwise 'AND' results to get the final output.

  • Optimize the solution to handle large input sizes efficiently.

Add your answer

Q33. Critical Connection Problem Statement

In a network with 'N' system nodes, identified from 0 to N-1, and 'M' connections, determine all critical connections. A connection is critical if its removal disrupts the ...read more

Ans.

Implement a function to find critical connections in a network with system nodes and connections.

  • Create an adjacency list to represent the network connections.

  • Use Tarjan's algorithm to find critical connections in the network.

  • Output the count of critical connections and the pairs of nodes involved.

  • Handle multiple test cases efficiently.

  • Ensure that the removal of a critical connection disrupts network connectivity.

Add your answer

Q34. Rotting Oranges Problem Statement

You are given a grid containing oranges where each cell of the grid can contain one of the three integer values:

  • 0 - representing an empty cell
  • 1 - representing a fresh orange...read more
Ans.

Find minimum time to rot all fresh oranges in a grid if adjacent to rotten oranges.

  • Use Breadth First Search (BFS) to simulate the rotting process of oranges.

  • Keep track of the time taken to rot all fresh oranges.

  • Return -1 if there are fresh oranges left after simulation.

  • Handle edge cases like empty grid or no fresh oranges present.

Add your answer

Q35. Reverse Linked List Problem Statement

Given a Singly Linked List of integers, your task is to reverse the Linked List by altering the links between the nodes.

Input:

The first line of input is an integer T, rep...read more
Ans.

Reverse a singly linked list by altering the links between nodes.

  • Iterate through the linked list and reverse the links between nodes

  • Use three pointers to keep track of the previous, current, and next nodes

  • Update the links while traversing the list to reverse it

  • Return the head of the reversed linked list

Add your answer

Q36. Squares of a Sorted Array Problem Statement

You are given an array/list ARR consisting of N integers. Your task is to generate a new array/list containing the squares of each element in ARR, with the resulting ...read more

Ans.

Given an array of integers, generate a new array with the squares of each element sorted in increasing order.

  • Iterate through the array and square each element

  • Sort the squared elements in increasing order

  • Return the sorted array

Add your answer

Q37. Valid String Problem Statement

Given a string S consisting solely of the characters '(', ')', and '*', determine if it is a valid string.

Definition of Valid String:

1. Every left parenthesis '(' must have a co...read more
Ans.

Determine if a given string consisting of '(' , ')' and '*' is valid based on certain rules.

  • Iterate through the string and keep track of the count of left parentheses, right parentheses, and stars.

  • Use a stack to keep track of the positions of left parentheses.

  • If at any point the count of right parentheses exceeds the count of left parentheses + stars, the string is invalid.

  • If the stack is not empty at the end, the string is invalid.

  • Otherwise, the string is valid.

Add your answer

Q38. Convert a Binary Tree to its Sum Tree

Given a binary tree of integers, convert it to a sum tree where each node is replaced by the sum of the values of its left and right subtrees. Set leaf nodes to zero.

Input...read more

Ans.

Convert a binary tree to a sum tree by replacing each node with the sum of its left and right subtrees.

  • Traverse the tree in postorder fashion.

  • For each node, calculate the sum of its left and right subtrees and update the node's value.

  • Set leaf nodes to zero.

  • Return the level order traversal of the modified tree.

Add your answer

Q39. Return in Row Wave Form Problem Statement

You are provided with a 2D array having dimensions 'N*M'. Your task is to traverse the elements row-wise and return a single-dimensional array which stores these elemen...read more

Ans.

Traverse a 2D array row-wise and return elements in a wave pattern.

  • Traverse the 2D array row-wise and store elements alternately in a wave pattern.

  • For each row, store elements from left to right for odd rows and from right to left for even rows.

  • Return the final 1D array representing the wave pattern of elements.

Add your answer

Q40. 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 on the board.

  • Keep track of visited cells and the number of dice throws required to reach each cell.

  • Consider the presence of snakes and ladders while calculating the next possible moves.

  • Return -1 if the last cell is unreachable.

Add your answer

Q41. Longest Substring with At Most K Distinct Characters

Given a string S of length N and an integer K, find the length of the longest substring that contains at most K distinct characters.

Input:

The first line co...read more
Ans.

Find the length of the longest substring with at most K distinct characters in a given string.

  • Use a sliding window approach to keep track of the characters and their counts within the window.

  • Maintain a hashmap to store the characters and their frequencies.

  • Update the window size and characters count as you iterate through the string.

  • Return the maximum window size encountered for each test case.

Add your answer

Q42. Circular Array Loop Problem Statement

Given a circular array ARR of size N consisting of positive and negative integers, determine if there is a cycle present in the array. You can make movements based on the v...read more

Ans.

Determine if a circular array has a cycle present, following specific movement rules.

  • Iterate through the array and check for cycles following the given movement rules.

  • Keep track of visited indices to detect cycles.

  • Handle both clockwise and counterclockwise movements separately.

  • Return 'True' if a cycle is found, 'False' otherwise.

Add your answer

Q43. Word Break Problem Statement

You are given a list of N strings called A. Your task is to determine whether you can form a given target string by combining one or more strings from A.

The strings from A can be u...read more

Ans.

Given a list of strings, determine if a target string can be formed by combining one or more strings from the list.

  • Iterate through all possible combinations of strings from the list to form the target string.

  • Use recursion to try different combinations of strings.

  • Check if the current combination forms the target string.

  • Return true if a valid combination is found, otherwise return false.

Add your answer

Q44. LRU Cache Design Question

Design a data structure for a Least Recently Used (LRU) cache that supports the following operations:

1. get(key) - Return the value of the key if it exists in the cache; otherwise, re...read more

Ans.

Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.

  • Use a combination of a doubly linked list and a hashmap to efficiently implement the LRU cache.

  • Maintain a doubly linked list to keep track of the order of keys based on their recent usage.

  • Use a hashmap to store key-value pairs for quick access and update operations.

  • When a key is accessed or updated, move it to the front of the linked list to mark it as the mos...read more

Add your answer

Q45. Find First Repeated Character in a String

Given a string 'STR' composed of lowercase English letters, identify the character that repeats first in terms of its initial occurrence.

Example:

Input:
STR = "abccba"...read more
Ans.

Find the first repeated character in a given string of lowercase English letters.

  • Iterate through the string and keep track of characters seen so far.

  • Return the first character that repeats, not just the first repeating character.

  • If no repeating character is found, return '%'.

Add your answer

Q46. 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 determine if it's a palindrome.

Add your answer

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

Calculate total unique paths from top-left to bottom-right corner of a matrix by moving only right or down.

  • Use dynamic programming to solve the problem efficiently.

  • Create a 2D array to store the number of unique paths for each cell.

  • Initialize the first row and first column with 1 as there is only one way to reach them.

  • For each cell (i, j), the number of unique paths is the sum of paths from the cell above and the cell to the left.

  • Return the value in the bottom-right corner of...read more

Add your answer

Q48. Count Ways to Reach the N-th Stair Problem Statement

You are provided with a number of stairs, and initially, you are located at the 0th stair. You need to reach the Nth stair, and you can climb one or two step...read more

Ans.

The problem involves finding the number of distinct ways to climb N stairs by taking 1 or 2 steps at a time.

  • Use dynamic programming to solve the problem efficiently.

  • The number of ways to reach the Nth stair is the sum of the number of ways to reach the (N-1)th stair and the (N-2)th stair.

  • Handle base cases for N=0 and N=1 separately.

  • Apply modulo operation to avoid overflow while calculating the result.

  • Consider using memoization to optimize the solution by storing intermediate ...read more

Add your answer

Q49. Minimum Cost to Cross a Grid

You are given a 2D grid consisting of 'N' rows and 'M' columns. Each cell in the grid has a certain cost associated with passing through it. Your goal is to find the minimum cost to...read more

Ans.

Find the minimum cost to travel from top-left to bottom-right corner of a grid.

  • Use dynamic programming to keep track of minimum cost to reach each cell.

  • Start from top-left corner and iterate through the grid to calculate minimum cost.

  • Consider all possible movements (UP, DOWN, LEFT, RIGHT) while staying within grid boundaries.

  • Update the cost for each cell by considering the minimum cost of reaching adjacent cells.

  • The final answer will be the cost to reach the bottom-right corn...read more

Add your answer

Q50. Maximum Sum of Non-Adjacent Nodes in a Binary Tree

Given a binary tree with integer values assigned to each node, select nodes such that their sum is maximum, ensuring no two adjacent nodes are picked.

Input:

T...read more
Ans.

Find the maximum sum of non-adjacent nodes in a binary tree.

  • Use dynamic programming to keep track of the maximum sum at each node considering whether to include or exclude the current node.

  • Recursively traverse the binary tree while keeping track of the maximum sum of non-adjacent nodes.

  • Consider the scenarios where the current node is included in the sum or excluded from the sum to calculate the maximum possible sum.

Add your answer

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

Given a binary tree, return the bottom view of the tree when viewed from left to right.

  • Calculate the horizontal distance of each node relative to the root.

  • For each horizontal distance, keep track of the bottom-most node.

  • If two nodes share the same horizontal distance, choose the deeper node.

  • Return the sequence of bottom view nodes from left to right.

Add your answer

Q52. Square Root with Decimal Precision Problem Statement

You are provided with two integers, 'N' and 'D'. Your objective is to determine the square root of the number 'N' with a precision up to 'D' decimal places. ...read more

Ans.

Implement a function to find the square root of a number with a given precision up to a specified number of decimal places.

  • Implement a function that takes two integers N and D as input and returns the square root of N with precision up to D decimal places.

  • Use mathematical algorithms like Newton's method or binary search to approximate the square root with the desired precision.

  • Ensure that the difference between the computed result and the true square root is less than 10^(-D)...read more

Add your answer

Q53. Bridges in a Graph Problem Statement

In an undirected graph consisting of V vertices and E edges, your task is to identify all the bridges within the graph. A bridge is an edge which, when removed, results in t...read more

Ans.

Identify bridges in an undirected graph by finding edges that, when removed, increase the number of connected components.

  • Use depth-first search (DFS) to find bridges in the graph.

  • Keep track of discovery time and low time for each vertex during DFS.

  • An edge (u, v) is a bridge if low[v] > disc[u].

  • Sort and print the bridge pairs in ascending order of vertices.

  • Example: If the input graph has vertices 0, 1, 2, 3, 4 and edges (0, 1), (1, 2), (2, 3), (3, 4), (0, 4), then the bridge i...read more

Add your answer

Q54. Amazing Strings Problem Statement

Determine if the third string contains all the characters from both the first and second strings in any order. If so, return "YES"; otherwise, return "NO".

Input:

Line 1: First...read more
Ans.

Check if the third string contains all characters from the first and second strings in any order.

  • Create a frequency map for characters in the first and second strings.

  • Check if the frequency of characters in the third string matches the frequency map of the first and second strings.

  • Return 'YES' if all characters are present in the third string, otherwise return 'NO'.

Add your answer

Q55. Sort Array by Set Bit Count

You have an array of N positive integers. Your goal is to sort this array in descending order based on the number of set bits in the binary representation of each integer.

In other w...read more

Ans.

Sort array of positive integers based on set bit count in descending order.

  • Count set bits for each integer using bitwise operations.

  • Implement a custom comparator function to sort the array based on set bit count.

  • Handle cases where integers have the same set bit count by retaining their original order.

Add your answer

Q56. Product Of Array Except Self Problem Statement

You are provided with an integer array ARR of size N. You need to return an array PRODUCT such that PRODUCT[i] equals the product of all the elements of ARR except...read more

Ans.

Return an array of products of all elements in an array except the current element.

  • Iterate through the array twice to calculate the product of all elements to the left and right of each element.

  • Use two arrays to store the products of elements to the left and right of each element.

  • Multiply the corresponding elements from the left and right product arrays to get the final product array.

Add your answer

Q57. Count Set Bits Problem Statement

Given a positive integer N, compute the total number of '1's in the binary representation of all numbers from 1 to N. Return this count modulo 1e9+7 because the result can be ve...read more

Ans.

Count the total number of set bits in the binary representation of numbers from 1 to N modulo 1e9+7.

  • Use bitwise operations to count the set bits in each number from 1 to N.

  • Consider using dynamic programming to optimize the solution.

  • Remember to return the count modulo 1e9+7 to handle large results.

Add your answer

Q58. Find Pair with Maximum GCD in an Array

Given an array of positive integers, your task is to find the GCD (Greatest Common Divisor) of a pair of elements such that it is the maximum among all possible pairs. The...read more

Ans.

Find the pair with the maximum GCD in an array of positive integers.

  • Iterate through all pairs of elements in the array.

  • Calculate the GCD of each pair using Euclidean algorithm.

  • Keep track of the maximum GCD found so far.

  • Return the maximum GCD value.

Add your answer

Q59. Maximum Product Subarray Problem Statement

Given an array of integers, determine the contiguous subarray that produces the maximum product of its elements.

Explanation:

A subarray can be derived from the origin...read more

Ans.

Find the contiguous subarray with the maximum product of elements in an array.

  • Iterate through the array and keep track of the maximum and minimum product ending at each index.

  • Update the maximum product by taking the maximum of current element, current element * previous maximum, and current element * previous minimum.

  • Update the minimum product by taking the minimum of current element, current element * previous maximum, and current element * previous minimum.

  • Return the maximu...read more

Add your answer

Q60. First Negative Integer in Every Window of Size K

Given an array of integers 'ARR' and an integer 'K', determine the first negative integer in every contiguous subarray (or window) of size 'K'. If a window does ...read more

Ans.

Find the first negative integer in every window of size K in an array.

  • Iterate through the array using a sliding window approach of size K

  • For each window, find the first negative integer and output it, if none exists output 0

  • Handle edge cases where window size is greater than array size

Add your answer

Q61. Transform BST to Greater Sum Tree

Given a Binary Search Tree (BST) of integers, the task is to convert it into a greater sum tree. In this transformation, each node's value is replaced by the sum of values of a...read more

Ans.

Convert a Binary Search Tree into a Greater Sum Tree by replacing each node's value with the sum of values of all nodes greater than the current node.

  • Traverse the BST in reverse inorder (right, root, left) to visit nodes in descending order.

  • Keep track of the sum of visited nodes and update each node's value with this sum.

  • Recursively apply the above steps to all nodes in the BST.

  • Example: For the given BST, the transformed tree will have values 139, 137, 130, 119, 104, 75, 40, ...read more

Add your answer

Q62. Sorted Linked List to Balanced BST Problem Statement

Given a singly linked list where nodes contain values in increasing order, your task is to convert it into a Balanced Binary Search Tree (BST) using the same...read more

Ans.

Convert a sorted linked list into a Balanced Binary Search Tree (BST) using the same data values.

  • Create a function to convert the linked list to an array for easier manipulation.

  • Implement a function to build a Balanced BST from the array recursively.

  • Ensure the height difference of the subtrees is no more than 1 for each node.

  • Use level order traversal to output the values of the BST nodes.

  • Handle NULL nodes by representing them with -1 in the output.

Add your answer

Q63. Fishmonger Toll Optimization Problem

A fishmonger needs to transport goods from a port to a market, crossing multiple states each requiring a toll. The goal is to minimize the toll costs while ensuring the jour...read more

Ans.

The Fishmonger Toll Optimization Problem involves minimizing toll costs while ensuring timely delivery of goods from a port to a market.

  • Given 'N' states and a time limit 'M', find the smallest toll amount to reach the market from the port within the given time.

  • Use dynamic programming to solve the problem efficiently.

  • Consider both time and toll matrices to calculate the minimum toll cost.

  • Return -1 if it is not possible to reach the market within the given time limit.

Add your answer

Q64. Character Formation Check

Determine if the second string STR2 can be constructed using characters from the first string STR1. Both strings may include any characters.

Input:

The first line contains an integer T...read more
Ans.

Check if second string can be formed using characters from the first string.

  • Iterate through each character in STR2 and check if it exists in STR1.

  • Use a hashmap to store the frequency of characters in STR1 for efficient lookup.

  • Return 'YES' if all characters in STR2 are found in STR1, otherwise return 'NO'.

Add your answer

Q65. Problem Statement: Sorted Subsequence of Size 3

Given an array composed of N elements, your task is to identify a subsequence with exactly three elements where these elements maintain a strictly increasing orde...read more

Ans.

Identify a subsequence of size 3 with strictly increasing order in an array.

  • Iterate through the array and keep track of the smallest and second smallest elements encountered so far.

  • If a third element greater than both is found, return the subsequence.

  • Handle edge cases where no valid subsequence exists.

Add your answer

Q66. Next Smaller Element Problem Statement

You are provided with an array of integers ARR of length N. Your task is to determine the next smaller element for each array element.

Explanation:

The Next Smaller Elemen...read more

Ans.

Given an array of integers, find the next smaller element for each element in the array.

  • Iterate through the array from right to left and use a stack to keep track of elements.

  • Pop elements from the stack until a smaller element is found or the stack is empty.

  • If no smaller element is found, output -1 for that element.

Add your answer

Q67. Find All Pairs Adding Up to Target

Given an array of integers ARR of length N and an integer Target, your task is to return all pairs of elements such that they add up to the Target.

Input:

The first line conta...read more
Ans.

Given an array of integers and a target, find all pairs of elements that add up to the target.

  • Iterate through the array and for each element, check if the difference between the target and the element exists in a hash set.

  • If it exists, then print the pair (element, target-element), else add the element to the hash set.

  • If no pair is found, print (-1, -1).

Add your answer

Q68. Connect Ropes with Minimum Cost

Given 'N' ropes, each having different lengths, your task is to connect these ropes into one single rope. The cost to connect two particular ropes is equal to the sum of their le...read more

Ans.

Connect ropes with different lengths into one single rope with minimum cost by merging the smallest ropes first.

  • Sort the lengths of ropes in ascending order.

  • Merge the two smallest ropes at each step to minimize cost.

  • Keep track of the total cost as you merge the ropes.

  • Repeat the merging process until all ropes are connected.

  • Return the total cost as the minimum cost to connect all ropes.

Add your answer

Q69. Langford Pairing Problem Statement

Given a positive integer N, you are required to generate a list of integers of size 2N such that it contains all the integers from 1 to N, both included, twice. These integers...read more

Ans.

Generate Langford pairing for given N, return 'Valid' if correct, 'Invalid' if not.

  • Generate a list of integers of size 2N with all integers from 1 to N twice.

  • Arrange integers according to Langford pairing rules.

  • Return 'Valid' if pairing is correct, 'Invalid' if not.

  • If no valid pairing possible, return list with only -1 element.

Add your answer

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

  • Create a dummy node to start the merged list

  • Compare the nodes of both lists and link them accordingly

  • Move the pointer to the next node in the merged list

  • Handle cases where one list is empty or both lists are empty

  • Time complexity: O(n), Space complexity: O(1)

Add your answer

Q71. Add Two Numbers as Linked Lists

You are given two singly linked lists, where each list represents a positive number without any leading zeros.

Your task is to add these two numbers and return the sum as a linke...read more

Ans.

Add two numbers represented as linked lists and return the sum as a linked list.

  • Traverse both linked lists simultaneously while adding corresponding nodes and carry over the sum if needed

  • Handle cases where one linked list is longer than the other by adding remaining nodes with carry

  • Create a new linked list to store the sum and return its head node

Add your answer

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

Determine if it is feasible to complete all courses with given prerequisites.

  • Create a graph representation of the courses and prerequisites.

  • Check for cycles in the graph using topological sorting.

  • If there are no cycles, all courses can be completed.

  • Example: For N=2 and prerequisites=[[1, 2]], output is 'Yes'.

Add your answer

Q73. Flatten BST to a Sorted List

The objective is to transform a given Binary Search Tree (BST) into a right-skewed BST, effectively flattening it into a sorted list. In the resulting structure, every node's left c...read more

Ans.

Transform a Binary Search Tree into a right-skewed BST, flattening it into a sorted list.

  • Implement a function to flatten the BST into a sorted list by linking nodes through right children.

  • Traverse the BST in-order and adjust the pointers to create the right-skewed structure.

  • Ensure that every node's left child is NULL in the resulting flattened BST.

  • Output the values of nodes in the skewed BST in level order for each test case.

  • Handle cases where nodes are NULL (-1) appropriatel...read more

Add your answer

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

Q75. Find Missing Number In String Problem Statement

You have a sequence of consecutive nonnegative integers. By appending all integers end-to-end, you formed a string S without any separators. During this process, ...read more

Ans.

Find the missing number in a string of consecutive nonnegative integers.

  • Iterate through the string to find the missing number by checking the consecutive integers.

  • If there is more than one missing number, all integers are present, or the string is invalid, return -1.

  • Handle cases where the missing number is at the beginning or end of the string.

  • Consider edge cases such as single-digit strings or strings with leading zeros.

Add your answer

Q76. Dice Throws Problem Statement

You are given D dice, each having F faces numbered from 1 to F. The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up numbers e...read more

Ans.

The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up numbers equals the given 'target' sum.

  • Use dynamic programming to solve the problem efficiently.

  • Create a 2D array to store the number of ways to reach each sum with each dice.

  • Iterate through the dice and sum values to fill up the array.

  • Return the result modulo 10^9 + 7.

  • Optimize the solution to use no more than O(S) extra space by using rolling arrays.

Add your answer

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

  • Explore all possible directions ('U', 'D', 'L', 'R') from each cell.

  • Terminate the search when the destination cell is reached.

  • Return the list of valid paths sorted in alphabetical order.

Add your answer

Q78. Check if Two Trees are Mirror

Given two arbitrary binary trees, your task is to determine whether these two trees are mirrors of each other.

Explanation:

Two trees are considered mirror of each other if:

  • The r...read more
Ans.

Check if two binary trees are mirrors of each other based on specific criteria.

  • Compare the roots of both trees.

  • Check if the left subtree of the first tree is the mirror of the right subtree of the second tree.

  • Verify if the right subtree of the first tree is the mirror of the left subtree of the second tree.

Add your answer

Q79. Sub Matrices With Sum Zero Problem Statement

You are provided with a square matrix 'MAT' of order N. Your task is to determine the number of non-empty sub-matrices where the sum of all elements within the sub-m...read more

Ans.

Count the number of sub-matrices with sum zero in a square matrix.

  • Iterate over all possible sub-matrices and calculate the sum of elements within each sub-matrix.

  • Use a hashmap to store the prefix sum of rows or columns to efficiently calculate the sum of sub-matrices.

  • Check for sub-matrices with sum zero and increment the count accordingly.

  • Return the total count of sub-matrices with sum zero.

Add your answer

Q80. Unique Element In Sorted Array

Nobita wants to impress Shizuka by correctly guessing her lucky number. Shizuka provides a sorted list where every number appears twice, except for her lucky number, which appears...read more

Ans.

Find the unique element in a sorted array where all other elements appear twice.

  • Iterate through the array and XOR all elements to find the unique element.

  • Use a hash set to keep track of elements and find the unique one.

  • Sort the array and check adjacent elements to find the unique one.

Add your answer

Q81. Find Duplicate in Array Problem Statement

You are provided with an array of integers 'ARR' consisting of 'N' elements. Each integer is within the range [1, N-1], and the array contains exactly one duplicated el...read more

Ans.

Identify the duplicate element in an array of integers.

  • Iterate through the array and keep track of the frequency of each element using a hashmap.

  • Return the element with a frequency greater than 1 as the duplicate.

  • Time complexity can be optimized to O(N) using Floyd's Tortoise and Hare algorithm.

  • Example: For input [3, 1, 3, 4, 2], the output should be 3.

Add your answer

Q82. Kevin and his Fruits Problem Statement

Kevin has 'N' buckets, each consisting of a certain number of fruits. Kevin wants to eat at least 'M' fruits. He is looking to set a marker as high as possible such that i...read more

Ans.

Find the marker value needed for Kevin to eat at least 'M' fruits from 'N' buckets.

  • Iterate through each bucket and calculate the difference between the number of fruits and the marker value needed to reach 'M'.

  • Update the marker value to be the maximum of the current marker value and the difference calculated in the previous step.

  • Return the final marker value as the output.

Add your answer

Q83. Longest Decreasing Subsequence Problem Statement

Given an array/list of integers ARR consisting of N integers, your task is to determine the length of the longest decreasing subsequence.

Explanation:

A subseque...read more

Ans.

Find the length of the longest decreasing subsequence in an array of integers.

  • Use dynamic programming to keep track of the longest decreasing subsequence ending at each index.

  • Initialize an array to store the length of the longest decreasing subsequence ending at each index.

  • Iterate through the array and update the length of the longest decreasing subsequence for each element.

  • Return the maximum value in the array as the length of the longest decreasing subsequence.

Add your answer

Q84. 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 path in a matrix from top row to bottom row by moving down or diagonally.

  • Use dynamic programming to keep track of maximum sum at each cell.

  • At each cell, the maximum sum is the current cell value plus the maximum of the three possible previous cells.

  • Iterate through the matrix row by row and update the maximum sum at each cell.

  • Return the maximum sum found in the last row as the result.

Add your answer

Q85. Subset Check Problem Statement

Determine if one array is a subset of another given two integer arrays ARR1 and ARR2 of lengths 'N' and 'M' respectively.

Return True if ARR2 is a subset of ARR1, otherwise return...read more

Ans.

Check if one array is a subset of another array.

  • Iterate through elements of ARR2 and check if each element is present in ARR1.

  • Use a set data structure to efficiently check for element presence.

  • Return true if all elements of ARR2 are found in ARR1, otherwise return false.

Add your answer

Q86. Counting Distinct Elements in Every K-Sized Window

Given an array ARR of size N and an integer K, determine the number of distinct elements in every K-sized window of the array. A 'K' sized window is defined as...read more

Ans.

Implement a function to count distinct elements in every K-sized window of an array.

  • Use a sliding window approach to keep track of distinct elements in each window

  • Use a hashmap to store the frequency of elements in the current window

  • Update the hashmap as you slide the window to the right and maintain the count of distinct elements

  • Return the count of distinct elements for each window as an array

Add your answer

Q87. Search in a Row-wise and Column-wise Sorted Matrix Problem Statement

You are given an N * N matrix of integers where each row and each column is sorted in increasing order. Your task is to find the position of ...read more

Ans.

Given a sorted N * N matrix, find the position of a target integer 'X'.

  • Iterate over each row and column to search for the target integer 'X'.

  • Utilize the sorted nature of the matrix to optimize the search process.

  • Return the position of 'X' if found, else return '-1 -1'.

Add your answer

Q88. 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 in a spiral order, alternating between left to right and right to left.

  • Use a queue to keep track of nodes at each level and a flag to switch direction.

  • Handle null nodes appropriately to maintain the spiral order traversal.

  • Example: Input: 1 2 3 -1 -1 4 5, Output: 1 3 2 4 5

Add your answer

Q89. Find Row With Maximum 1's in a Sorted 2D Matrix

You are provided with a 2D matrix containing only the integers 0 or 1. The matrix has dimensions N x M, and each row is sorted in non-decreasing order. Your objec...read more

Ans.

Find the row with the maximum number of 1's in a sorted 2D matrix.

  • Iterate through each row of the matrix and count the number of 1's in each row.

  • Keep track of the row index with the maximum number of 1's encountered so far.

  • Return the index of the row with the maximum number of 1's.

  • If multiple rows have the same number of 1's, return the row with the smallest index.

Add your answer

Q90. N Queens Problem

Given an integer N, find all possible placements of N queens on an N x N chessboard such that no two queens threaten each other.

Explanation:

A queen can attack another queen if they are in the...read more

Ans.

The N Queens Problem involves finding all possible placements of N queens on an N x N chessboard without threatening each other.

  • Use backtracking algorithm to explore all possible configurations.

  • Keep track of rows, columns, and diagonals to ensure queens do not threaten each other.

  • Generate all valid configurations and print them as specified in the output format.

Add your answer

Q91. Time to Burn Tree Problem

You are given a binary tree consisting of 'N' unique nodes and a start node where the burning will commence. The task is to calculate the time in minutes required to completely burn th...read more

Ans.

Calculate the time in minutes required to completely burn a binary tree starting from a given node.

  • Start burning from the given node and spread fire to adjacent nodes each minute

  • Track the time taken for each node to burn and return the maximum time taken

  • Use a queue to keep track of nodes to be burned next

Add your answer

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

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

  • Time complexity can be optimized to O(N) using a stack-based approach.

Add your answer

Q93. Longest Palindromic Substring Problem Statement

You are provided with a string STR of length N. The goal is to identify the longest palindromic substring within this string. In cases where multiple palindromic ...read more

Ans.

Given a string, find the longest palindromic substring, prioritizing the one with the smallest start index.

  • Iterate through each character in the string and expand around it to find palindromes

  • Keep track of the longest palindrome found so far

  • Return the longest palindromic substring with the smallest start index

Add your answer

Q94. Count Distinct Palindromic Substrings

Given a string STR, your task is to determine the total number of palindromic substrings present in the string.

Input:

The first line contains an integer 't', representing ...read more
Ans.

Count the total number of palindromic substrings in a given string.

  • Iterate through each character in the string and expand around it to find palindromic substrings.

  • Keep track of the count of palindromic substrings found.

  • Consider both odd and even length palindromes while expanding around each character.

Add your answer

Q95. Data Structure with Insert, Delete, and GetRandom Operations

Design a data structure that supports four operations: insert an element, remove an element, search for an element, and get a random element. Each op...read more

Ans.

Design a data structure supporting insert, delete, search, and getRandom operations in constant time.

  • Use a combination of hashmap and array to achieve O(1) time complexity for each operation.

  • For insert operation, check if element exists in hashmap, if not add to array and hashmap.

  • For remove operation, check if element exists in hashmap, if yes, remove from array and hashmap.

  • For search operation, check if element exists in hashmap.

  • For getRandom operation, generate a random ind...read more

Add your answer

Q96. Maximal AND Subsequences Problem

Given an array consisting of N integers, your task is to determine how many k-element subsequences of the given array exist where the bitwise AND of the subsequence's elements i...read more

Ans.

Find the maximal AND value and count of subsequences in an array.

  • Iterate through all possible k-element subsequences and calculate their AND value.

  • Track the maximal AND value and count of subsequences achieving this value.

  • Return the maximal AND value and count modulo 1000000007.

Add your answer

Q97. LRU Cache Implementation

Design and implement a Least Recently Used (LRU) cache data structure, which supports the following operations:

  • get(key) - Return the value of the key if it exists in the cache, otherw...read more
Ans.

Implement a Least Recently Used (LRU) cache data structure with get and put operations.

  • Use a combination of a hashmap and a doubly linked list to efficiently implement the LRU cache.

  • Keep track of the least recently used item and update it accordingly when inserting new items.

  • Ensure to handle the capacity constraint by evicting the least recently used item when the cache is full.

  • For get operation, return the value of the key if it exists, otherwise return -1.

Add your answer

Q98. Power Set Generation

Given a sorted array of 'N' integers, your task is to generate the power set for this array. Each subset of this power set should be individually sorted.

A power set of a set 'ARR' is the s...read more

Ans.

Generate power set of sorted array of integers with individually sorted subsets.

  • Use recursion to generate all possible subsets by including or excluding each element.

  • Sort each subset before adding it to the power set.

  • Handle base case when all elements have been considered.

  • Time complexity can be exponential due to 2^N subsets being generated.

Add your answer

Q99. Position of Right Most Set Bit

Given a number 'N', the task is to determine the position of the rightmost set bit in its binary representation.

Example:

Input:
If N = 10, which has binary representation 1010
Ou...read more
Ans.

Find the position of the rightmost set bit in a given number's binary representation.

  • Convert the number to binary representation.

  • Find the position of the rightmost set bit by counting from the right.

  • Return the position as output.

Add your answer

Q100. Prerequisite Task Completion Verification

Given a positive integer 'N', representing the number of tasks, and a list of dependency pairs, determine if it is possible to complete all tasks considering these prer...read more

Ans.

Given tasks and dependencies, determine if all tasks can be completed based on prerequisites.

  • Create a graph representation of tasks and dependencies.

  • Use topological sorting to check if there is a cycle in the graph.

  • Return 'Yes' if no cycle is found, 'No' otherwise.

Add your answer
1
2

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 ApexGig

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

Top Software Developer Intern Interview Questions from Similar Companies

3.5
 • 50 Interview Questions
4.0
 • 21 Interview Questions
3.6
 • 14 Interview Questions
3.4
 • 13 Interview Questions
4.2
 • 12 Interview Questions
3.7
 • 10 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
70 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