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

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