DE Shaw Software Developer Intern Interview Questions, Process, and Tips

Round duration - 75 minutes
Round difficulty - Medium

2 coding questions

Q1. 
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 ...read more
Ans. 
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
Answered by AI
Add your answer
Q2. 
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 link...read more
Ans. 
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.
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

Q1. 
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)...read more
Ans. 
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 recursio
Answered by AI
Add your answer

Round duration - 75 minutes
Round difficulty - Easy

Smooth platform of Hackerrank.
Nice user interface.

Q1. 
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 link...read more
Ans. 
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.

• Update the head of the reversed linked list as the last node encountered.

• Ensure to handle edge cases like empty list or single node list.

• Time complexity should be O(N) and space complexity should be O(1).
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

It was conducted in the evening at around 7:00 p.m.
The hackerrank environment is clearly the best for conducting coding exams as it provides a decent interface for debugging and testing purposes.
There were 3 questions- 1 of easy level and 2 of medium level.

Q1. 
Pythagorean Triplets Detection
Determine if an array contains a Pythagorean triplet by checking whether there are three integers x, y, and z such that x² + y² = z² within the array.
Input:
The first lin...read more
Ans. 
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.
Answered by AI
Add your answer
Q2. 
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...read more
Ans. 
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 o...read more
Answered by AI
Add your answer
Q3. 
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 ...read more
Ans. 
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.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

The round was conducted on CodePair platform which provides a IDE along with a video call for interviews.
There were 2 interviewers and both were friendly.
I was first asked about the various subjects I have studied in my curriculum. Then I was asked about my favourite programming language to which I answered Python.
After this, they asked various confusing questions based on function calling, argument passing and pass by object reference concept in Python. 
Then they asked about the implementation of dictionary in Python and wanted me to design one with the help of lists(arrays) and optimize its search, add and delete operations. (Could be done with hashing and probing).
Then they asked questions from subjects like Computer Architecture and Theory of Computation (Basic questions were asked so you should just remember the key topics in the subject).

Q1. 
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 co...read more
Ans. 
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.
Answered by AI
Add your answer

Round duration - 75 minutes
Round difficulty - Hard

It was a coding round on Hackerrank.

Q1. 
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)...read more
Ans. 
Validate if a binary tree is a Binary Search Tree (BST) based on given properties.
• Check if the left subtree of a node contains only nodes with data less than the node's data.

• Verify 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 level order form and compare the elements to validate if
Answered by AI
Add your answer
Q2. 
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 link...read more
Ans. 
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 create the reversed linked list.

• Use three pointers to keep track of the current, previous, and next nodes while reversing the linked list.

• Ensure to update the head of the reversed linked list at the end.

• Example: Input: 1 -> 2 -> 3 -> 4 -> NULL, Output: 4 ->
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Medium

This round had 3 coding questions to be solved under 90 minutes. I found the questions to be of Easy to Medium level of difficulty and anyone who has practised enough from LeetCode or CodeStudio would be able to pass this round.

Q1. 
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 tw...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 mem...read more
Answered by AI
Add your answer
Q2. 
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 ...read more
Ans. 
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
Answered by AI
Add your answer
Q3. 
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 outpu...read more
Ans. 
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
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

In this round, the interviewer asked me 2 coding questions in which I was expected to first explain my approach with proper complexity analysis and then code up the solution. These questions were then followed by 2 puzzles to check my overall aptitude.

Q1. 
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 s...read more
Ans. 
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...read more
Answered by AI
Add your answer
Q2. 
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 Tr...read more
Ans. 
Validate if a given binary tree is a Binary Search Tree (BST) or not.
• Check if the left subtree of a node contains only nodes with data less than the node's data

• Check if the right subtree of a node contains only nodes with data greater than the node's data

• Recursively check if both left and right subtrees are also binary search trees
Answered by AI
Add your answer
Q3. You have two wires of different lengths that are both capable of burning for exactly one hour when ignited at both ends. How can you measure a time interval of 45 minutes using these two wires?
Add your answer

Round duration - 30 Minutes
Round difficulty - Easy

This was a Technical Cum HR round where I was first asked some basic SQL related concepts and then we discussed
about my expectations from the company , learnings and growth in the forthcomig years. I would suggest be honest and
try to communicate your thoughts properly in these type of rounds to maximise your chances of getting selected.

Round duration - 95 Minutes
Round difficulty - Easy

The complete test was Audio and Video Proctored. 
The test was divided into 3 sections:
1) Aptitude: (14 MCQs in 28 minutes)
2) Technical: (12 MCQs in 17 minutes) 
3) coding: (2 questions - first in 20 minutes, second in 30 minutes)

Q1. 
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 ...read more
Ans. 
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.
Answered by AI
Add your answer
Q2. 
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 b...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
Answered by AI
Add your answer