SDE - Intern D.E.Shaw interview experience | Anonymous

Interview rounds

Round

Medium

Online Coding Test

Duration90 Minutes

Interview date16 Jul 2020

Coding problem3

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.

1. Count Ways To Reach The N-th Stairs

Moderate

30m average time

80% success

0/80

Asked in companies

You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair.

Each time, you can climb either one step or two steps.

You are supposed to return the number of distinct ways you can climb from the 0th step to the Nth step.

Note:

Note: Since the number of ways can be very large, return the answer modulo 1000000007.

Example :

N=3

We can climb one step at a time i.e. {(0, 1) ,(1, 2),(2,3)} or we can climb the first two-step and then one step i.e. {(0,2),(1, 3)} or we can climb first one step and then two step i.e. {(0,1), (1,3)}.

Problem approach

Approach :

Our intuition is : How can we reach “currStep” step in taking one step or two steps:

1) We can take the one-step from (currStep-1)th step or,
2) We can take the two steps from (currStep-2)th step.

So the total number of ways to reach “currStep” will be the sum of the total number of ways to reach at (currStep-1)th and the total number of ways to reach (currStep-2)th step.

Let dp[currStep] define the total number of ways to reach “currStep” from the 0th. So,

dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]

The base case will be :
1) If we have 0 stairs to climb then the number of distinct ways to climb will be 1 (we are already at Nth stair that’s the way)

2) If we have only 1 stair to climb then the number of distinct ways to climb will be 1, i.e. one step from the beginning.

TC : O(N), where N = number of stairs
SC : O(N)

Try solving now

2. Water

Easy

15m average time

85% success

0/40

Asked in companies

You are given an array 'ARR' of positive integers, each of which represents the number of liters of water in that particular bucket, we have to make the liters of water in every bucket equal.

We are allowed to do two types of operations any number of times:

1. We can altogether remove a bucket from the sequence

2. We can draw some water from a bucket

We have to tell the minimum number of liters removed to make all buckets have the same amount of water.

For example:

Given ‘N’ = 4 and ‘ARR’ = [1, 1, 2, 2].
The answer will be 2, i.e., if we chose that all buckets should have 1 unit of water, we will have to throw 1 unit of water from buckets 3 and 4. Hence 2.

Problem approach

Approach :

1) Sort the array(waters array) in descending order.

2) Assuming every bucket as a candidate finds the minimum amount of water needs to be removed. The result will be a minimum amount of water, among that.

3) Every bucket which is on the left of the current bucket has more water than a current bucket, and every bucket which is on the right of the current bucket has less water than an existing bucket.

4) For every ‘i’ we will keep track of the minimum water to be removed in a variable ‘res’.

5) For every bucket, we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).

6) Amount of water removed can be calculated using (totalWater - arr[i]*(i+1)).
res = min(res, (totalWater - arr[i]*(i+1))).

7) Return the final res.

TC : O( N * log(N) ), where N = size of the array
SC : O(1)

Try solving now

3. Set Bits

Easy

0/40

Asked in companies

Write a program to count the number of 1's in the binary representation of an integer.

Problem approach

Approach :
1) Here we are converting the number into binary, and during the conversion, we are checking the remainder part.
2) If it is 1, then we increment the value of count by 1.

TC : O(log(N)), where N = given integer
SC : O(1)

Try solving now

Round

Medium

Video Call

Duration60 Minutes

Interview date16 Jul 2020

Coding problem4

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.

1. Candies

Moderate

10m average time

90% success

0/80

Asked in companies

Prateek is a kindergarten teacher. He wants to give some candies to the children in his class. All the children stand in a line and each of them has a grade according to his or her performance in the class. Prateek wants to give at least one candy to each child. If two children are standing adjacent to each other, then the one with the higher rating must get more candies than the other. Prateek wants to minimize the total number of candies he must buy.

Given an array 'STUDENTS' of size 'N' that contains the grades for each student, your task is to find what is the minimum number of candies Prateek must buy so that he can distribute them among his students according to the criteria given above.

Example :

Given students' ratings : [5, 8, 1, 5, 9, 4]. 
He gives the students candy in the following minimal amounts : [1, 2, 1, 2, 3, 1]. He must buy a minimum of 10 candies.

Note :

1. If two students having the same grade are standing next to each other, they may receive the same number of candies.
2. Every student must get at least a candy.

Problem approach

Approach :

1) Create an array (say, ‘CANDIES’) to store candies for each student and initialise it with 1.

2) Run a loop from 1 to ‘N’ (say, iterator ‘i’), if ‘STUDENTS’[i] is less than ‘STUDENTS’[i - 1] :
Update ‘CANDIES’[i] to ‘CANDIES’[i] + ‘CANDIES’[i - 1]

3) Run a loop from ‘N’ - 2 to 0 (say, iterator ‘i’), if ‘STUDENTS’[i] is greater than ‘STUDENTS’[i + 1] and ‘CANDIES’[i] is smaller than ‘CANDIES’[i + 1] + 1:
Update ‘CANDIES’[i] to ‘CANDIES’[i] + ‘CANDIES’[i + 1]

4) Create a variable (say, ‘ANS’) to store total number of candies required and initialise it to 0.

5) Run a loop from 0 to ‘N’ (say, iterator ‘i’) and add ‘CANDIES’[i] to ‘ANS’.

6) Finally, return ‘ANS’.

TC : O(N), where N = size of the array
SC : O(N)

Try solving now

2. Validate BST

Moderate

25m average time

0/80

Asked in companies

You have been given a binary tree of integers with N number of nodes. Your task is to check if that input tree is a BST (Binary Search Tree) or not.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Example :

Answer :

Level 1: 

All the nodes in the left subtree of 4 (2, 1, 3) are smaller 
than 4, all the nodes in the right subtree of the 4 (5) are 
larger than 4.

Level 2 :

For node 2:
All the nodes in the left subtree of 2 (1) are smaller than 
2, all the nodes in the right subtree of the 2 (3) are larger than 2.
For node 5:
The left and right subtrees for node 5 are empty.

Level 3:

For node 1:
The left and right subtrees for node 1 are empty.
For node 3:
The left and right subtrees for node 3 are empty.

Because all the nodes follow the property of a binary search tree, the above tree is a binary search tree.

Problem approach

Approach (Using Inorder Traversal) :

1) If an inorder traversal is performed on a binary search tree, then the elements are in ascending order.

2) While performing the traversal, keep track of the previous node and the current node.

3) If the previous node is greater than the current node, then the binary tree is definitely not a binary search tree.

4) For all nodes, if the previous node is smaller than the current node, then the traversal is in ascending order, return true.

TC : O(N), where N = number of nodes in the Binary Tree
SC : O(N)

Try solving now

3. Puzzle

Two wire burning puzzle.

Problem approach

If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly
half the original time, i.e. 30 minutes to burn completely.

1) 0 minutes – Light stick 1 on both sides and stick 2 on one side.
2) 30 minutes – Stick 1 will be burnt out. Light the other end of stick 2.
3) 45 minutes – Stick 2 will be burnt out. Thus 45 minutes is completely measured.

4. Puzzle

Mislabeled Jars :
There are 3 jars, namely, A, B, C. All of them are mislabeled. Following are the labels of each of the jars:

A: Candies
B: Sweets
C: Candies and Sweets (mixed in a random proportion)

You can put your hand in a jar and pick only one eatable at a time. Tell the minimum number of eatable(s) that
has/have to be picked in order to label the jars correctly.

Problem approach

Answer : 1 pick of an eatable is required to correctly label the Jars.

Approach :
1) Pick only one eatable from jar C. Suppose the eatable is a candy, then the jar C contains candies only(because all
the jars were mislabeled).

2) Now, since the jar C has candies only, Jar B can contain sweets or mixture. But, jar B can contain only the mixture
because its label reads “sweets” which is wrong.

3) Therefore, Jar A contains sweets. Thus the correct labels are :
A : Sweets.
B : Candies and Sweets.
C : Candies.

Round

Easy

HR Round

Duration30 Minutes

Interview date16 Jul 2020

Coding problem1

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.

1. Basic HR Questions

Why should we hire you ?
What are your expectations from the company?
How was your overall interview experience?
What are your strengths and weakness according to you?
Where do you see yourself in the next 5 years?

Problem approach

Tip 1 : The cross questioning can go intense some time, think before you speak.

Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.

Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round,
like what are the projects currently the company is investing, which team you are mentoring. How all is the work
environment etc.

Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical
questions. No coding in most of the cases but some discussions over the design can surely happen.