
DE Shaw


100+ DE Shaw Interview Questions and Answers
Q1. Tower Building Problem Statement
Given an array 'ARR' of 'N' cubes, you need to construct towers such that each cube can either be placed on top of an existing tower or start a new one. The restriction is that ...read more
The task is to determine the minimum number of towers needed to stack cubes in a specific order.
Iterate through the array of cubes and maintain a stack to keep track of towers.
For each cube, check if it can be placed on an existing tower or start a new one.
Update the stack based on the cube's size and count the number of towers needed.
Return the minimum number of towers required.
Example: For input N = 3, ARR = [3, 2, 1], the output should be 1.
Q2. Rabbit Jumping Problem
Consider 'n' carrots numbered from 1 to 'n' and 'k' rabbits. Each rabbit jumps to carrots only at multiples of its respective jumping factor Aj (i.e., Aj, 2Aj, 3Aj, ...), for all rabbits ...read more
Calculate uneaten carrots by rabbits with specific jumping factors.
Iterate through each carrot and check if any rabbit jumps on it.
Use the jumping factors to determine which carrots will be eaten.
Subtract the eaten carrots from the total to get the uneaten carrots.
Q3. Pretty JSON Formatting Problem
You're provided with a string 'STR' that represents a JSON object. Your task is to return an array of strings representing JSON objects, formatted with proper indentation based on...read more
The task is to format a JSON object string with proper indentation based on specific rules.
Iterate through the string character by character and keep track of the indentation level.
Use a stack to keep track of opening and closing braces to determine the indentation level.
Insert four spaces or a tab (' ') for each level of indentation.
Handle commas to represent new lines in the output array of strings.
Q4. MegaPrime Numbers Problem Statement
Given two integers Left
and Right
, determine the count of 'megaprime' numbers within the inclusive range from 'Left' to 'Right'. A 'megaprime' number is a prime number where ...read more
Q5. Coin Game Problem Statement
Wong wants to borrow money from Dr. Strange, who insists Wong must win a coin game first. The game involves two players taking turns to remove one coin from either end of a row of co...read more
Given an array of coin values, determine the maximum value Wong can obtain by playing a coin game against Dr. Strange.
Wong plays first and can remove one coin from either end of the array on each turn.
The game ends when no coins are left, and the player with the highest total value wins.
Consider different scenarios like having an odd or even number of coins in the array.
Q6. Number Pattern Generator
To arrange a high-security meeting, tables are set up for delegates and security personnel. There are N
rows of tables. The first row has one table, the second row has two tables, and s...read more
Generate a pattern of guest and security personnel distributions across tables for a given number of rows.
Iterate through each row from 1 to N
For each row, print the pattern based on the number of guests and security personnel at each table
Tables on each end of a row are reserved for security personnel
Q7. Maximum Number from Linked List Problem Statement
Given a linked list where each node contains a single digit, your task is to construct the largest possible number using these digits.
Objective:
Print the maxi...read more
To find the maximum number that can be formed using the digits present in a linked list.
Traverse the linked list and store the digits in an array
Sort the array in descending order
Concatenate the sorted array elements to form the maximum number
Q8. Money Saving in Bank Problem
Harshit wants to save up money for his first car by depositing money daily in the Ninja bank with a specific increment strategy.
Starting with 1 rupee on the first Monday, the amoun...read more
Calculate the total money accumulated by Harshit in Ninja bank after N days with a specific increment strategy.
Start with 1 rupee on the first Monday and increase by 1 rupee each day from Tuesday to Sunday.
Each new Monday starts with an additional rupee more than the previous Monday's deposit.
Calculate the total amount of money accumulated after N days for each test case.
Example: For N = 2, total amount is 3 rupees; for N = 5, total amount is 15 rupees.
Q9. K Most Frequent Elements Problem Statement
Given an integer array ARR
and an integer K
, identify the K
most frequent elements within ARR
. Return these elements sorted in ascending order.
Example:
Input:
ARR = [...read more
Identify K most frequent elements in an array and return them sorted in ascending order.
Use a hashmap to store the frequency of each element in the array.
Sort the elements based on their frequency in descending order.
Return the first K elements from the sorted list.
Q10. Stock Investment Problem Statement
You are given the prices of a particular stock over 'N' consecutive days. Your task is to find the maximum profit that can be obtained by completing at most two transactions. ...read more
Find the maximum profit that can be obtained by completing at most two transactions of buying and selling a stock.
Iterate through the array of stock prices and calculate the maximum profit that can be obtained by completing at most two transactions.
Keep track of the maximum profit that can be obtained by selling the stock on each day after buying it on a previous day.
Consider all possible combinations of two transactions to find the maximum profit.
Return the maximum profit fo...read more
Q11. Minimum Removals Problem Statement
Given an array ARR
of size N
and an integer K
, determine the minimum number of elements that must be removed from the array so that the difference between the maximum and mini...read more
The problem involves finding the minimum number of elements to remove from an array so that the difference between the maximum and minimum element is less than or equal to a given value.
Iterate through the array and keep track of the minimum and maximum elements.
Calculate the difference between the maximum and minimum elements.
If the difference is greater than the given value, increment the count of elements to remove.
Return the count of elements to remove as the result.
Q12. K Max Sum Combinations Problem Statement
Given two arrays/lists A
and B
, each of size N
, and an integer K
, you need to determine the K
maximum and valid sum combinations from all possible combinations of sums g...read more
The problem involves finding the K maximum sum combinations from two arrays by adding one element from each array.
Iterate through all possible sum combinations of elements from arrays A and B.
Store the sums in a max heap to keep track of the K maximum sums.
Pop the top K elements from the max heap to get the K maximum sum combinations.
Q13. Majority Element - II Problem Statement
You are given an array ARR
of integers of length N
. Your task is to find all the elements that occur strictly more than floor(N/3)
times in the given array.
Input:
The fi...read more
Q14. LCS of Three Strings Problem Statement
Given three strings A, B, and C, determine the length of the longest common subsequence present in all three strings.
Explanation:
A subsequence is derived by deleting som...read more
Find the length of the longest common subsequence among three strings.
Use dynamic programming to solve this problem efficiently.
Create a 3D array to store the lengths of common subsequences.
Iterate through the strings to fill the array and find the longest common subsequence length.
Q15. Minimum Steps for a Knight to Reach Target
Given a square chessboard of size 'N x N', determine the minimum number of moves a Knight requires to reach a specified target position from its initial position.
Expl...read more
Calculate the minimum number of moves a Knight requires to reach a specified target position on a chessboard.
Implement a function that calculates the minimum number of moves for a Knight to reach the target position on an NxN chessboard.
Consider the possible movements of a Knight on a chessboard (2 squares in one direction and 1 square in a perpendicular direction).
Use breadth-first search (BFS) algorithm to find the shortest path from the Knight's starting position to the ta...read more
Evaluate Reverse Polish Notation Problem Statement
You are provided with an arithmetic expression in Reverse Polish Notation represented as an array EXP
. Your task is to calculate the value of this expression.
Evaluate arithmetic expression in Reverse Polish Notation using stack.
Use a stack to keep track of operands and perform operations when encountering an operator.
Iterate through the array of strings and push operands onto the stack, perform operation when an operator is encountered.
Handle division using modular division to avoid floating point precision issues.
Return the final result modulo 10^9 + 7 as specified in the constraints.
Q17. Minimum Sum in Matrix Problem Statement
You are given a 2D matrix 'ARR' of size 'N x 3' with integers, where 'N' is the number of rows. Your task is to compute the smallest sum achievable by selecting one eleme...read more
Find the smallest sum achievable by selecting one element from each row of a matrix, following certain constraints.
Iterate through each row and find the minimum element that can be selected without violating the constraints
Keep track of the selected elements to avoid selecting elements directly below them in the next row
Sum up the selected elements to get the smallest possible sum
Q18. Conquering the Best Kingdom Problem Statement
Aragorn, an influential ruler, aspires to expand his power by conquering more kingdoms. There are 'N' kingdoms numbered from 0 to N-1, forming a tree structure. The...read more
Given a tree structure of kingdoms, determine if it's possible to conquer more kingdoms than Aragorn by strategically choosing the starting kingdom.
Start at the kingdom adjacent to Aragorn's initial kingdom
Choose the kingdom that allows you to capture the most number of kingdoms in subsequent turns
Consider the tree structure to plan your conquest strategically
Q19. Count Smaller People on Right
You are provided with an array called HEIGHT
that contains the heights of 'N' people standing in a queue. For each person in the array, compute the number of individuals on their r...read more
Count the number of people to the right with a smaller height for each person in a queue.
Iterate through the array from right to left and maintain a sorted list of heights encountered so far.
Use binary search to find the position where the current height should be inserted in the sorted list.
The count of smaller people to the right for each person can be calculated based on the index of insertion in the sorted list.
Q20. Gas Station Tour Problem
You are presented with a circular track consisting of several petrol pumps. Each petrol pump is indexed from 0 to N-1 and offers certain attributes:
- The quantity of petrol available at...read more
Find the first petrol pump from which a truck can start its journey and complete the circle.
Iterate through each petrol pump and calculate the remaining petrol after reaching the next pump.
If the remaining petrol is negative at any point, reset the starting point to the next pump.
If the total remaining petrol at the end is non-negative, return the starting point as the answer.
Q21. Water Equalization Problem Statement
You are provided with an array ARR
of positive integers. Each integer represents the number of liters of water in a bucket. The goal is to make the liters of water in every ...read more
Given an array of water buckets, find the minimum liters of water to remove to make all buckets equal.
Iterate through the array to find the maximum frequency of a water amount
Calculate the total liters to be removed by subtracting the maximum frequency from the total number of buckets
Return the total liters to be removed as the answer
Q22. Minimum Number of Taps to Water the Garden
Given a garden that extends along a one-dimensional x-axis from point 0 to point N, your task is to determine the minimum number of taps needed to water the entire gar...read more
Find the minimum number of taps needed to water the entire garden using given tap ranges.
Iterate over taps and update the farthest point each tap can reach.
Use a greedy approach to select the tap that can water the farthest point.
If a tap can't water any point, return -1.
Example: For ranges = [3, 4, 1, 1, 0, 0], tap at position 1 can water the entire garden.
Q23. Problem Statement: Sibling Nodes
You are provided with a Binary Tree consisting of 'N' nodes, where each node holds an integer value. Your objective is to identify and list all nodes that do not possess a sibli...read more
Identify and list nodes in a Binary Tree without siblings.
Traverse the Binary Tree in level order and keep track of nodes without siblings.
Check if each node has a sibling by comparing with its parent's other child.
Output the values of nodes without siblings in ascending order.
Q24. Dijkstra's Algorithm for Shortest Path
Given an undirected graph with 'V' vertices labeled from 0 to V-1 and 'E' edges. Each edge has a weight that represents the distance between two nodes 'X' and 'Y'.
Your ta...read more
Dijkstra's algorithm is used to find the shortest path distances from a source node to all other vertices in a graph.
Dijkstra's algorithm is a greedy algorithm that finds the shortest path from a source node to all other nodes in a graph.
It uses a priority queue to select the node with the smallest distance and relaxes its neighbors.
The algorithm maintains a distance array to keep track of the shortest distances from the source node.
If a node is unreachable, the distance is s...read more
Q25. LCA in a Binary Search Tree
You are given a binary search tree (BST) containing N nodes. Additionally, you have references to two nodes, P and Q, within this BST.
Your task is to determine the Lowest Common Anc...read more
Find the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST).
Traverse the BST from the root node to find the LCA of nodes P and Q.
Compare the values of nodes P and Q with the current node's value to determine the LCA.
If both nodes are on the same side of the current node, move to that side; otherwise, the current node is the LCA.
Handle cases where one node is the ancestor of the other node.
Example: For input 2 3 and BST 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -...read more
Q26. Phone Directory Search Directory
You are given a list/array of strings representing the contacts in a phone directory. The task is to perform a search based on a query string 'str' and return all contacts that ...read more
Implement a phone directory search feature to suggest contacts based on a given prefix query string.
Iterate through the contact list to find contacts with the prefix matching the query string.
Display suggestions as the user types each character of the query.
Handle cases where no suggestions are found for a particular prefix by printing 'No suggestions found'.
Q27. 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
Q28. Find Triplets with Given Sum Problem Statement
Given an array ARR
consisting of N
integers, your task is to identify all distinct triplets within the array that sum up to a given integer K
.
Explanation:
An arra...read more
The task is to find all distinct triplets in an array that sum up to a given integer.
Iterate through the array and use nested loops to find all possible triplets.
Use a set to store unique triplets and avoid duplicates.
Check if the sum of the triplet equals the target sum.
Return the list of valid triplets or -1 if no such triplet exists.
Q29. Find Magic Index in Sorted Array
Given a sorted array A consisting of N integers, your task is to find the magic index in the given array, where the magic index is defined as an index i such that A[i] = i.
Exam...read more
Find the magic index in a sorted array where A[i] = i.
Use binary search to efficiently find the magic index in the sorted array.
Check the middle element of the array and compare it with its index to determine the direction to search.
Repeat the process on the left or right half of the array until the magic index is found or no more elements to search.
Q30. Jump Game Problem Statement
In this problem, you are given an array ARR
consisting of N
integers. Your task is to determine the minimum number of jumps required to reach the last index of the array N - 1
. At an...read more
Q31. Alien Dictionary Problem Statement
You are provided with a sorted dictionary (by lexical order) in an alien language. Your task is to determine the character order of the alien language from this dictionary. Th...read more
Q32. Peak Element Finder
For a given array of integers arr
, identify the peak element. A peak element is an element that is greater than its neighboring elements. Specifically, if arr[i]
is the peak, then both arr[i...read more
Find the peak element in an array of integers.
Iterate through the array and check if the current element is greater than its neighbors.
Handle edge cases for the first and last elements of the array.
Return the peak element found.
Q33. Buy and Sell Stock Problem Statement
Imagine you are Harshad Mehta's friend, and you have been given the stock prices of a particular company for the next 'N' days. You can perform up to two buy-and-sell transa...read more
The task is to determine the maximum profit that can be achieved by performing up to two buy-and-sell transactions on a given set of stock prices.
Iterate through the stock prices to find the maximum profit that can be achieved by buying and selling stocks at different points.
Keep track of the maximum profit after the first transaction and the maximum profit overall after the second transaction.
Consider edge cases where no profit can be made or where only one transaction is po...read more
Q34. 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
Q35. Longest Increasing Path in a 2D Matrix Problem Statement
Given a matrix of non-negative integers of size 'N x M', where 'N' and 'M' denote the number of rows and columns respectively, find the length of the lon...read more
Find the length of the longest increasing path in a 2D matrix by moving in four directions.
Use dynamic programming to keep track of the longest increasing path starting from each cell.
Explore all four directions from each cell and recursively find the longest increasing path.
Optimize the solution by storing the length of the longest increasing path starting from each cell.
Q36. Binary Tree Mirror Conversion Problem
Given a binary tree, your task is to convert it into its mirror tree.
A binary tree is a data structure where each parent node has at most two children.
The mirror of a bin...read more
Convert a binary tree into its mirror tree by interchanging left and right children of non-leaf nodes.
Traverse the binary tree in postorder fashion and swap the left and right children of each non-leaf node.
Use recursion to solve the problem efficiently.
Remember to handle null child nodes represented by -1 in the input.
Q37. Maximum Sum Subarray Problem Statement
Given an array of integers, find the maximum sum of any contiguous subarray within the array.
Example:
Input:
array = [34, -50, 42, 14, -5, 86]
Output:
137
Explanation:
Th...read more
Find the maximum sum of any contiguous subarray within an array in O(N) time complexity.
Iterate through the array and keep track of the maximum sum of subarrays encountered so far
At each index, decide whether to include the current element in the subarray or start a new subarray
Update the maximum sum if a new maximum is found
Example: For array [34, -50, 42, 14, -5, 86], the maximum sum subarray is [42, 14, -5, 86] with sum 137
Q38. Minimum Number of Platforms Problem
Your task is to determine the minimum number of platforms required at a railway station so that no train has to wait.
Explanation:
Given two arrays:
AT
- representing the ar...read more
Determine the minimum number of platforms needed at a railway station so that no train has to wait.
Sort the arrival and departure times arrays in ascending order.
Initialize two pointers for arrival and departure times, and a variable to keep track of the maximum number of platforms needed.
Increment the platform count when a train arrives and decrement when a train departs.
Update the maximum platform count as needed.
Return the maximum platform count as the minimum number of pl...read more
Q39. Minimum Fountains Activation Problem
In this problem, you have a one-dimensional garden of length 'N'. Each position from 0 to 'N' has a fountain that can provide water to the garden up to a certain range. Thus...read more
Find the minimum number of fountains to activate to water the entire garden.
Iterate through the array to find the coverage of each fountain.
Keep track of the farthest coverage reached by each activated fountain.
Activate the fountain that covers the farthest distance not yet covered.
Repeat until the entire garden is watered.
Q40. Is Binary Heap Tree Problem Statement
You are given a binary tree of integers. Your task is to determine if it is a binary heap tree or not.
Input:
The first line of input contains an integer ‘T’ denoting the n...read more
Q41. Find the Largest BST Subtree in a Given Binary Tree
Your task is to determine the size of the largest subtree of a given binary tree which is also a Binary Search Tree (BST).
BST Definition:
- The left subtree o...read more
Find the size of the largest subtree in a binary tree that is also a Binary Search Tree (BST).
Traverse the binary tree in a bottom-up manner to check if each subtree is a BST.
Keep track of the size of the largest BST subtree encountered so far.
Use the properties of a BST to determine if a subtree is a valid BST.
Consider edge cases such as empty tree or single node tree.
Example: For input 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, the output should be 3.
Q42. Delete a Node from a Linked List
You are provided with a linked list of integers. Your task is to implement a function that deletes a node located at a specified position 'POS'.
Input:
The first line contains a...read more
Implement a function to delete a node from a linked list at a specified position.
Traverse the linked list to find the node at the specified position.
Update the pointers of the previous and next nodes to skip the node to be deleted.
Handle cases where the position is at the beginning or end of the linked list.
Ensure to free the memory of the deleted node to avoid memory leaks.
Q43. Check if Binary Search Tree (BST)
Given a binary tree with 'N' nodes, verify whether this tree is a Binary Search Tree (BST). Return true if it is a BST and false otherwise.
Definition:
A Binary Search Tree (BS...read more
Verify if a given binary tree is a Binary Search Tree (BST) or not.
Check if the left subtree of a node contains only nodes with values less than the node's value.
Check if the right subtree of a node contains only nodes with values greater than the node's value.
Ensure that both the left and right subtrees are also binary search trees.
Return true if the tree is a BST, false otherwise.
Handle cases with duplicate elements in either subtree.
Q44. Two cops and a robber are located on opposite corners of a cube and move along its edges. They all move at the same rate. Is it possible for the cops to catch the robber. [Each of the 3 people can see each othe...
read moreNo, it is not possible for the cops to catch the robber.
The robber can always stay equidistant from the cops by moving along the diagonal of the cube.
The cops can never cut off the robber's path without colliding with each other.
This problem is known as the '3 Cops and a Robber' problem in graph theory.
Q45. Reverse Linked List Problem Statement
Given a singly linked list of integers, return the head of the reversed linked list.
Example:
Initial linked list: 1 -> 2 -> 3 -> 4 -> NULL
Reversed linked list: 4 -> 3 -> 2...read more
Reverse a singly linked list of integers and return the head of the reversed linked list.
Iterate through the linked list and reverse the pointers to point to the previous node instead of the next node.
Use three pointers to keep track of the current, previous, and next nodes while reversing the linked list.
Update the head of the reversed linked list as the last node encountered during the reversal process.
Q46. Ways to Arrange Balls Problem
You are given 'a' balls of type 'A', 'b' balls of type 'B', and 'c' balls of type 'C'. Determine the total number of ways to arrange these balls in a straight line so that no two a...read more
The problem involves arranging balls of different types in a straight line without having two adjacent balls of the same type.
Use recursion to try all possible arrangements while keeping track of the previous ball type.
Handle edge cases where one or more types of balls have a count of 0.
Consider using dynamic programming to optimize the solution by storing intermediate results.
For the given example input (2 1 1), the output is 6 as there are 6 valid arrangements.
For the input...read more
Q47. Ways To Make Coin Change
Given an infinite supply of coins of varying denominations, determine the total number of ways to make change for a specified value using these coins. If it's not possible to make the c...read more
The task is to find the total number of ways to make change for a specified value using given denominations.
Use dynamic programming to solve this problem efficiently.
Create a 2D array to store the number of ways to make change for each value up to the specified value.
Iterate through each denomination and update the array accordingly.
The final answer will be stored in the last cell of the array.
Example: For N=3, D=[1, 2, 3], V=4, the output is 4 as explained in the example.
Q48. Longest Common Subsequence of Three Strings
Given three strings A, B, and C, the task is to determine the length of the longest common subsequence across these three strings.
Explanation:
A subsequence of a str...read more
Find the length of the longest common subsequence among three strings.
Use dynamic programming to solve this problem efficiently.
Create a 3D array to store the lengths of common subsequences.
Iterate through the strings to fill the array and find the longest common subsequence length.
Q49. Best Time To Buy and Sell Stock Problem Statement
You are given an array 'PRICES' of 'N' integers, where 'PRICES[i]' represents the price of a certain stock on the i-th day. An integer 'K' is also provided, ind...read more
The task is to determine the maximum profit achievable with at most K transactions by buying and selling stocks.
Iterate through the array and keep track of the minimum price to buy and maximum profit for each transaction.
Use dynamic programming to store the maximum profit at each day with each possible number of transactions.
Consider edge cases like when K is 0 or when the array is empty.
Example: For input N = 6, PRICES = [3, 2, 6, 5, 0, 3], K = 2, the output would be 7.
Q50. Find the Lone Set Bit
Your task is to identify the position of the only '1' bit in the binary representation of a given non-negative integer N
. The representation contains exactly one '1' and the rest are '0's....read more
Find the position of the only '1' bit in the binary representation of a given non-negative integer.
Iterate through the bits of the integer to find the position of the lone '1' bit.
Use bitwise operations to check if there is exactly one '1' bit in the binary representation.
Return the position of the lone '1' bit or -1 if there isn't exactly one '1'.
Q51. Next Higher and Previous Lower Number with Same Number of Set Bits
Given a positive integer n
, the task is to find the next smallest integer and the previous largest integer that contain the exact same number o...read more
Find next smallest and previous largest integers with same number of set bits as given integer.
Count the number of set bits in the given integer using bitwise operations.
For next smallest integer, find the next number with same number of set bits by iterating through numbers greater than the given integer.
For previous largest integer, find the previous number with same number of set bits by iterating through numbers smaller than the given integer.
Q52. Pythagorean Triplets Detection
Determine if an array contains a Pythagorean triplet by checking whether there are three integers x, y, and z such that x2 + y2 = z2 within the array.
Input:
The first line contai...read more
Detect if an array contains a Pythagorean triplet by checking if x^2 + y^2 = z^2.
Iterate through all possible triplets of numbers in the array and check if they form a Pythagorean triplet.
Use a nested loop to generate all possible combinations of three numbers from the array.
Check if the sum of squares of two numbers is equal to the square of the third number.
Q53. Longest Increasing Subsequence Problem Statement
Given 'N' students standing in a row with specific heights, your task is to find the length of the longest strictly increasing subsequence of their heights, ensu...read more
Find the length of the longest strictly increasing subsequence of heights of students in a row.
Iterate through the heights array and for each student, find the length of the longest increasing subsequence ending at that student.
Use dynamic programming to keep track of the longest increasing subsequence length for each student.
Return the maximum length found in the dynamic programming array as the result.
Example: For heights [10, 20, 10, 30, 40], the longest increasing subsequ...read more
Q54. 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
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 add it to the result array
If no negative integer is found in a window, add 0 to the result array
Q55. Candies Distribution Problem Statement
Prateek is a kindergarten teacher with a mission to distribute candies to students based on their performance. Each student must get at least one candy, and if two student...read more
The task is to distribute candies to students based on their performance while minimizing the total candies distributed.
Create an array to store the minimum candies required for each student.
Iterate through the students' ratings array to determine the minimum candies needed based on the adjacent ratings.
Consider both left-to-right and right-to-left passes to ensure fair distribution.
Calculate the total candies required by summing up the values in the array.
Example: For rating...read more
Q56. Validate Binary Search Tree (BST)
You are given a binary tree with 'N' integer nodes. Your task is to determine whether this binary tree is a Binary Search Tree (BST).
BST Definition:
A Binary Search Tree (BST)...read more
Validate if a given binary tree is a Binary Search Tree (BST) or not.
Check if the left subtree of a node contains only nodes with data less than the node's data
Check if the right subtree of a node contains only nodes with data greater than the node's data
Recursively check if both left and right subtrees are also binary search trees
Q57. Validate BST Problem Statement
Given a binary tree with N
nodes, determine whether the tree is a Binary Search Tree (BST). If it is a BST, return true
; otherwise, return false
.
A binary search tree (BST) is a b...read more
Validate if a binary tree is a Binary Search Tree (BST) or not.
Check if the left subtree of a node contains only nodes with data less than the node's data.
Check if the right subtree of a node contains only nodes with data greater than the node's data.
Ensure that both the left and right subtrees are also binary search trees.
Traverse the tree in an inorder manner and check if the elements are in sorted order.
Use recursion to validate each node and its subtrees.
Q58. Find the Missing Number in an Arithmetic Progression
You are given a sorted array consisting of ‘N’ distinct integers, forming a nearly complete Arithmetic Progression, except for one missing element. Your task...read more
Q59. Find the Duplicate Number Problem Statement
Given an integer array 'ARR' of size 'N' containing numbers from 0 to (N - 2). Each number appears at least once, and there is one number that appears twice. Your tas...read more
Find the duplicate number in an array of integers from 0 to (N-2).
Iterate through the array and keep track of the count of each number using a hashmap.
Return the number with a count greater than 1 as the duplicate number.
Alternatively, use Floyd's Tortoise and Hare algorithm to find the duplicate number in O(N) time and O(1) space.
Q60. In some tournament 139 teams have participated. Tournament is knock out. what is the number of matches to choose the champion to be held?
139 teams in a knock-out tournament, find the number of matches to choose the champion.
In a knock-out tournament, each team plays only one match per round.
The number of matches required to choose the champion is one less than the number of teams.
Therefore, the number of matches required is 138.
Q61. 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
The problem involves counting 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 where N=0 and N=1 separately.
Consider using modulo operation to avoid overflow when dealing with large numbers.
Q62. Union and Intersection of Two Arrays
Given two arrays 'A' and 'B' of size 'N' and 'M' respectively, both sorted in non-decreasing order, find the intersection of these two arrays.
The intersection of two arrays...read more
Yes, we can solve this problem using a time complexity of O(max(N, M)) by using a two-pointer approach.
Use two pointers to iterate through both arrays simultaneously.
Compare the elements at the pointers and move the pointers accordingly to find the intersection.
This approach ensures linear time complexity based on the size of the larger array.
Q63. Candy Distribution Problem Statement
Prateek, a kindergarten teacher, needs to distribute candies to his class. Each child has a performance grade, and all students stand in a line.
The rules for distributing c...read more
Calculate the minimum number of candies needed to distribute to students based on their performance grades.
Create an array to store the minimum candies needed for each student.
Iterate through the students' ratings from left to right, comparing each student with the previous one to determine the candy count.
Iterate through the students' ratings from right to left, comparing each student with the next one to ensure the correct candy count.
Sum up the total candies needed for all...read more
Q64. 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
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
Q65. Binary Ones Count Problem
Develop a program to determine the number of '1's in the binary form of a given integer.
Input:
The input consists of a single line containing an integer N.
Output:
The output should b...read more
Count the number of '1's in the binary form of a given integer.
Convert the given integer to binary representation
Count the number of '1's in the binary representation
Return the count of '1's as output
Q66. Equalize Water in Buckets
You are provided with an array, ARR
, of positive integers. Each integer represents the number of liters of water in a bucket. The goal is to make the water volume in each bucket equal ...read more
Find the minimum amount of water to be removed to equalize water in buckets.
Iterate through the array to find the average water level.
Calculate the total amount of water that needs to be removed to equalize the buckets.
Keep track of the excess water in each bucket and sum them up to get the final result.
Q67. Inorder Traversal of Binary Tree Without Recursion
Given a Binary Tree consisting of 'N' nodes with integer values, your task is to perform an In-Order traversal of the tree without using recursion.
Input:
The ...read more
Implement in-order traversal of a binary tree without recursion.
Use a stack to simulate the recursive in-order traversal process.
Start with the root node and keep traversing left until reaching a null node, pushing nodes onto the stack.
Pop nodes from the stack, print the value, and move to the right child if it exists.
Continue this process until the stack is empty and all nodes have been visited.
Diamond Problem is a common issue in multiple inheritance in C++ where a class inherits from two classes that have a common base class.
Diamond Problem occurs when a class inherits from two classes that have a common base class, leading to ambiguity in accessing members.
It can be resolved in C++ using virtual inheritance, where the common base class is inherited virtually to avoid duplicate copies of base class members.
Example: class A is inherited by classes B and C, and clas...read more
Garbage collection in OOP refers to automatic memory management by deallocating memory of objects no longer in use.
Garbage collection is a process of automatically reclaiming memory occupied by objects that are no longer in use.
It helps prevent memory leaks and ensures efficient memory usage.
Languages like Java, C#, and Python have built-in garbage collection mechanisms.
Garbage collection can be done using different algorithms like mark and sweep, reference counting, and gene...read more
Internal fragmentation occurs when memory is allocated in fixed-size blocks, leading to wasted space within a block. External fragmentation occurs when free memory is fragmented into small chunks, making it difficult to allocate contiguous blocks.
Internal fragmentation is caused by allocating fixed-size blocks of memory, leading to wasted space within a block.
External fragmentation occurs when free memory is fragmented into small chunks, making it difficult to allocate contig...read more
Q71. What is the difference between default and copy constructor?
Default constructor is provided by the compiler if no constructor is defined. Copy constructor creates a new object by copying an existing object.
Default constructor initializes member variables to default values.
Copy constructor creates a new object with the same values as an existing object.
Default constructor is called automatically by the compiler if no constructor is defined.
Copy constructor is called when an object is passed by value or when a new object is initialized ...read more
Q72. What is the difference between primary key and unique key?
Primary key uniquely identifies a record in a table, while unique key ensures that all values in a column are distinct.
Primary key can't have null values, while unique key can have one null value.
A table can have only one primary key, but multiple unique keys.
Primary key is used as a foreign key in other tables, while unique key is not.
Example: Primary key - employee ID, Unique key - email address.
Q73. What is the difference between Truncate and Delete?
Truncate removes all data from a table while Delete removes specific data from a table.
Truncate is faster than Delete as it doesn't log individual row deletions.
Truncate resets the identity of the table while Delete doesn't.
Truncate can't be rolled back while Delete can be.
Truncate doesn't fire triggers while Delete does.
Processes are instances of programs in execution, while threads are smaller units within a process that can execute independently.
Processes are independent entities that contain program code, data, and resources.
Threads are lightweight units within a process that share the same resources but can execute independently.
Processes have their own memory space, while threads share the same memory space.
Processes communicate with each other through inter-process communication mechan...read more
Default Constructor is a constructor that is automatically called when an object is created without any arguments. Copy Constructor is used to create a new object as a copy of an existing object.
Default Constructor has no parameters, while Copy Constructor takes an object of the same class as a parameter.
Default Constructor initializes the object with default values, while Copy Constructor creates a new object with the same values as the existing object.
Example: Default Const...read more
Use one wire to measure 30 minutes, then ignite the other wire at one end and the middle point to measure 15 minutes.
Ignite one wire at both ends and the other wire at one end. The first wire will burn out in 30 minutes.
At the same time, ignite the second wire at one end and the middle point. It will take 15 minutes for the fire to reach the middle point from one end.
When the first wire burns out, ignite the other end of the second wire. It will take another 15 minutes for th...read more
Q77. Write an algorithm to find the absolute max subsequence of an array containing both positive and negative numbers in O(n) time ?
Algorithm to find absolute max subsequence of an array with positive and negative numbers in O(n) time.
Initialize max_so_far and max_ending_here as 0
Loop through the array and for each element, add it to max_ending_here
If max_ending_here becomes negative, reset it to 0
If max_ending_here is greater than max_so_far, update max_so_far
Return max_so_far
Q78. Design a class which has director, HOD, Professor and students. They all are reporting to their respective heads. I have to display the hierarchy structure of the information in a Site
Design a class hierarchy for director, HOD, Professor and students reporting to their respective heads.
Create a base class for all employees with common attributes and methods
Create derived classes for director, HOD, Professor and students
Implement reporting hierarchy using pointers or references
Display hierarchy structure on the site using a tree or graph
Consider adding additional attributes and methods as needed
Abstract class can have both abstract and non-abstract methods, while interface can only have abstract methods.
Abstract class can have constructor, member variables, and methods with implementation.
Interface can only have abstract methods and constants.
A class can implement multiple interfaces but can only extend one abstract class.
Example: Abstract class - Animal with abstract method 'eat' and non-abstract method 'sleep'. Interface - Flyable with method 'fly'.
Primary Key uniquely identifies each record in a table, while Unique Key ensures that all values in a column are distinct.
Primary Key does not allow NULL values, while Unique Key allows one NULL value.
A table can have only one Primary Key, but multiple Unique Keys.
Primary Key is automatically indexed, while Unique Key may or may not be indexed.
Primary Key is used to establish relationships between tables, while Unique Key is used to enforce data integrity.
Example: In a table ...read more
Q81. What is the difference between C and C++?
C++ is an extension of C with object-oriented programming features.
C++ supports classes and objects while C does not.
C++ has better support for polymorphism and inheritance.
C++ has a standard template library (STL) which C does not have.
C++ allows function overloading while C does not.
C++ has exception handling while C does not.
System calls provide a way for user-level processes to interact with the operating system kernel.
System calls allow user programs to request services from the operating system.
They provide a secure and controlled way for applications to access system resources.
System calls enable processes to perform tasks such as file operations, network communication, and process management.
Examples of system calls include open(), read(), write(), fork(), and exec().
DDL is used to define the structure of database objects, while DML is used to manipulate data within those objects.
DDL is used to create, modify, and delete database objects like tables, indexes, etc.
DML is used to insert, update, delete, and retrieve data from database tables.
DDL statements include CREATE, ALTER, DROP, TRUNCATE, etc.
DML statements include INSERT, UPDATE, DELETE, SELECT, etc.
Q84. Find the next largest int of a given int such that it has same number of 1′s in binary?
Find the next largest int with same number of 1's in binary.
Count the number of 1's in the binary representation of the given int.
Increment the given int until a number with the same number of 1's is found.
Return the next largest int with same number of 1's.
Q85. What is the difference between DML and DLL?
DML is Data Manipulation Language used to manipulate data in a database. DLL is Data Definition Language used to define database schema.
DML is used to insert, update, delete data in a database.
DLL is used to create, alter, drop database objects like tables, views, indexes.
DML statements include INSERT, UPDATE, DELETE.
DLL statements include CREATE, ALTER, DROP.
DML affects data in a database, DLL affects the structure of a database.
Q86. What is the difference between DBMS and RDBMs?
DBMS is a software system to manage databases while RDBMS is a type of DBMS that uses a relational model.
DBMS stands for Database Management System while RDBMS stands for Relational Database Management System.
DBMS can manage any type of database while RDBMS uses a relational model to manage data.
DBMS does not enforce any specific data model while RDBMS enforces a relational data model.
Examples of DBMS include MongoDB, Cassandra, and Redis while examples of RDBMS include MySQL...read more
Q87. task schedular from leetcode second is : N piles of coins diffrent length you can add or remove one coin from a pile adding cost c1 and removing cost c2 find minimum cost such that height of n piles equals
Find minimum cost to make heights of N piles of coins equal by adding or removing one coin from a pile with different costs.
Use dynamic programming to keep track of the minimum cost for each pile height.
Consider the cost of adding and removing coins from each pile.
Iterate through all possible combinations of adding and removing coins to find the minimum cost.
Different types of semaphores include binary semaphores, counting semaphores, and mutex semaphores.
Binary semaphores: Can only have two states - 0 or 1. Used for mutual exclusion.
Counting semaphores: Can have multiple states. Used for resource allocation and synchronization.
Mutex semaphores: Similar to binary semaphores but with additional features like priority inheritance and deletion safety.
Q89. Given an array eliminate the duplicates and print it. Linear time complexity?
Eliminate duplicates in an array of strings and print it in linear time complexity.
Use a hash set to keep track of unique elements
Iterate through the array and add non-duplicate elements to the hash set
Print the hash set elements to get the final array
Q90. Mention any five operating systems which have been derived from UNIX
Five operating systems derived from UNIX are...
Linux
macOS
Solaris
FreeBSD
Android
Inheritance is a concept in object-oriented programming where a class inherits properties and behaviors from another class.
Allows for code reusability by creating a new class based on an existing class
Child class inherits attributes and methods of the parent class
Can have multiple levels of inheritance (e.g. grandparent, parent, child classes)
Example: class Dog extends Animal, where Dog inherits properties and methods from Animal class
Normalization in database management systems aims to reduce data redundancy, improve data integrity, and optimize database performance.
Eliminate data redundancy by breaking down data into smaller tables
Reduce update anomalies by ensuring data is stored in a logical and consistent manner
Improve data integrity by enforcing referential integrity constraints
Optimize database performance by reducing the amount of redundant data stored
The select() system call is used in Unix-like operating systems to monitor multiple file descriptors for activity.
select() allows a program to wait for multiple I/O operations to complete on multiple file descriptors.
It takes three sets of file descriptors as arguments - readfds, writefds, and errorfds.
The function will block until an activity is detected on one of the file descriptors or until a timeout occurs.
select() is commonly used in networking applications to handle mu...read more
Q94. do you think the era of social media influencers is short lived?
No, social media influencers are here to stay.
Social media has become an integral part of our lives and will continue to be so.
Influencers have a huge impact on consumer behavior and brand marketing.
The industry is constantly evolving and adapting to changes.
Influencers are diversifying their content and expanding their reach.
Brands are investing more in influencer marketing than ever before.
Examples: Kylie Jenner, PewDiePie, Huda Kattan, etc.
Q95. What is the purpose of Normalisation?
Normalisation is the process of organizing data in a database to reduce redundancy and improve data integrity.
Normalisation helps to eliminate data redundancy and inconsistencies
It ensures that each piece of data is stored in only one place
It helps to improve data integrity and accuracy
It makes it easier to maintain and update the database
There are different levels of normalisation, each with its own set of rules and guidelines
Q96. How would I defend myself if I were to get caught for having downloaded torrents?
Defending oneself for downloading torrents
Explain that downloading torrents is illegal but common
Admit to the mistake and show remorse
Explain that you were not aware of the consequences
Promise to delete all downloaded content and not repeat the mistake
Offer to pay any fines or penalties
Consult a lawyer for legal advice
SQL query to find the employee with the nth highest salary
Use the ORDER BY clause to sort salaries in descending order
Use the LIMIT clause to select the nth highest salary
Join the employee table with the salary table to get the employee details
Static loading is done at compile time while dynamic loading is done at runtime in operating systems.
Static loading involves loading all the necessary libraries and dependencies at compile time.
Dynamic loading involves loading libraries and dependencies at runtime when they are needed.
Static loading is faster but consumes more memory, while dynamic loading is slower but more memory efficient.
Examples of static loading include C/C++ programs, while examples of dynamic loading ...read more
The types of access modifiers in C++ are public, private, and protected.
Public: accessible from outside the class
Private: only accessible within the class
Protected: accessible within the class and its subclasses
Q100. What are class access modifiers?
Class access modifiers are keywords used to control the visibility and accessibility of class members.
There are four access modifiers in Java: public, private, protected, and default
Public members can be accessed from anywhere
Private members can only be accessed within the same class
Protected members can be accessed within the same class, subclasses, and same package
Default members can be accessed within the same package
More about working at DE Shaw

Top HR Questions asked in DE Shaw
Interview Process at DE Shaw

Top Interview Questions from Similar Companies








Reviews
Interviews
Salaries
Users/Month

