DE shaw Online Assessement
I have recently given Online Assessement Test for Summer Internship in DE Shaw company,the questions were medium-to-hard level problems in hackerrank platform.
Duration of the test was 95 minutes and time distribution was 25 minutes for 1st question,35 minutes each for other two questions.
You have to solve the particular question in that allotted time only,time will not carry forward to other two sections.
For example: You solved first question in just 15 minutes and total time for the first question was of 25 minutes then remaining 10 minutes you have to wait for the opening of the 2nd section and closing of the first section and same rule is applied over the other two sections also.
Questions with explanation
All three question's are given below with explanation try to solve these problems and also post the solution in comment of this discussion so that others can take benefit from it:-
Q1)
Given an array products of size n and an integer k (k>=n) you have select to k products from it and each product you have to select atleast 1.
suppose you select a product t times then discount you will get on this product will be disc=products[i]*pow(2,t-1).
You want maximum discounts by selecting k products from it with atleast 1 product each.
Instead of adding all the discounts from the products you have to take OR operation.
For example:-
Products=[12,2,13,6] and k=7 then one way I can select is :-
1st product 2 times then discount=nums[0]pow(2,2-1)=122=24,
2nd product 1 times and discount will be= nums[1]*pow(2,1-1)=nums[i]=2,
3rd product 2 times and discount will be= nums[2]pow(2,2-1)=132=26
and 4th product 2 times then discount will be =nums[3]pow(2,2-1)=62=12
total discount= 24 | 2 | 26 | 12
finally you have to maximize the total discount.
Q2)
Given an array pixel of size n where ith pixel is pixel[i], An image is clear if the array pixel has a padding of some number of 0s (possibly none) in the prefix and the suffix and the non-zero part in the array pixel say from index i to index j,starts from pixel[i]=1 ,strictly increases for some k in steps of 1 and then strictly decreases in steps of 1 such that pixel[j]=1.
For example the pixel arrays [0, 0, 1, 2, 3, 2, 1], [1, 2, 1], [1], [0, 0, 0, 1, 2, 3, 4, 3, 2, 1, 0] are clear.
In a single operation you can reduce any pixel value by 1.
Given n pixels of an image and an array pixel find the minimum number of operations required to make the array pixel clear.
Q3)
Given a matrix nm and a vector Thres of size m you can choose any two row(i,j) i may or may not equal to j and check for every k: 0 to m-1 if
max(matrix[i][k],matrix[j][k])>=Thres[k] then pair(i,j) is good. Return total number of good pairs. This can solve using Brute Force method with time complexity **O(nm*m)** but this will give TLE try to optimize it.
Guide for internships
If you solve these three questions then its fine, but you failed then please solve questions related to DP and hashing in LeetCode as much as possible.