100+ Amazon Software Developer Intern Interview Questions and Answers for Freshers

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

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.

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

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

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.

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.

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.

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

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

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.

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.

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

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

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

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.

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

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.

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

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.

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

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

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

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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

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.

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.

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.

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.

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

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 '%'.

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

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

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.

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

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

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

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.

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

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.

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

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

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.

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.

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.

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

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.

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.

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

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.

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

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.

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.

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.

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

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

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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

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.

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.

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.

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

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.

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

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.

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.

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

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.

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.