sru_31's blog

DESHAW Online Coding Test
By sru_31, history, 3 years ago, In English

Today we had Deshaw online coding test, 1st question had 25 mins time limit, 2nd and 3rd have 35 mins time limit.

Q1: You are given a vector of strings v and a string s.

Length of s= 26.

1<=v.size()<=2*(1e4);

max_length of string<=100

All strings in v may or may not have the same length. string s contains only lowercase English alphabets. All the characters in the string s are in the increasing order of value of the character.Let's say s="abfde" , it means value of 'a'< value of 'b'<value of 'f' <value of 'd' and so on. Now there's a competition going on, let's say v={"ab","abdf","abe"} in the first round every string uses the character "a" and as all the strings provide same value they proceed to the next round, in the second round every string uses char "b" and proceed to third round, Now in third round string "ab" gets eliminated because it doesn't have any character left, now if we compare the third character of strings {"abdf","abe"}, value of 'e'>value of 'd' (in the string s), so the string "abe" wins.

Goal=> To find the final winner amongst all the strings in vector v;

Q2: You are given an final state array of length n;

1<=n<=1e6;

0<=arr[i]<=1e9;

Let's say n=4; The initial state of the array is having only zeroes at every index. Here we took n=4 so , initial state =[0,0,0,0], let's say n was 3 then initial state would've been [0,0,0]. The final state of the array is given in the question. Now we are working with the initial state of the array:

In each move you can : 1.Increase the value of any element by 1,
2. Double the values of all the elements of the array.

Goal => To find the minimum moves to reach the final state of the array from the initial state. For example let's say final state =[1,4] initial state =[0,0] -> [0,1]-> [0,2] -> [0,4]->[1,4]
Min no of steps =4.

Q3 . You are given two arrays named fruits, vegetables.

1<=m<=1000

1<=n<=1000

-1000<=arr[i]<=1000

1<=fruits.size()<=m

1<=vegetables.size()<=n;

Every day customers buy fruits and vegetables, here there's a rule that customers must buy the same number of fruits and vegetables. It is guaranteed that at least one customer buys fruit and a vegetable. Let's say customer buys fruits {f1,f3,f4} and vegetables {v1,v2,v5} profit is calculated as f1*v1+f2*v2+f4*v5. Example : fruits {-6,-2} vegetables{ -1,-4} Here the maximum profit is (-6)*(-4) =24, now you might say that (-6)*(-4)+(-2)*(-1) =26 is the maximum profit but here there's a condition that order should be followed.

Goal => Find maximum profit that can be obtained such that at least one fruit and one vegetable is included.

Ps: I wrote the blog for the first time, please correct me if you find any mistake.

  • Vote: I like it
  • +22
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you give more details for the third question?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

for solving the third question you can use dp similar to lcs. Let dp[i][j] be storing the ans ie to problem of fruits[0:i] and veg[0:j] Here either you can pair the fruits[i] with veg[j] and get an amount of fruits[i]*veg[j] or you can choose not to pair and get ans from previous calculated states
dp[i][j]=max(dp[i-1][j-1]+fruits[i]*veg[j],dp[i-1][j],dp[i][j-1]). And finally the actual ans would be stored at dp[fruits.length-1][veg.length-1]

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

1.) Brute force works

2.) Lets start from the end, while each element in the array is divisible by 2, divide it by 2. [ this wont be too many times since 1e9 the maximum element in the array, is just below 2^30. ] After this we have to treat every element separately which is the absolute difference from 0.

3.) Seems like n^2 DP

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    In 2.) First, making all odd values even, and then dividing all the values by 2. Performing the above two steps until all the values become 0. Wouldn't this give the minimum number of moves since we are trying to reduce each element as much as possible at every step?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, you are right. What if we try to solve the problem individually for every element, and return the max as the global answer?

      For example [1,4], to convert 1 to 0 we need 1 op. to convert 4 to 0, we need 4->2->1->0, so final answer is 4. Does this work?

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I participated in this Round and gave one of my worst performance, was able to solve only last problem. Last problem is dp like finding LCS. I was stuck at A for 15-20 minute out of 25 minutes alloted at first problem finding compilation errors because I was not returning output properly.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For the $$$2^{nd}$$$ I think the answer should be $$$(no\,of \,positive\,a[i]+ max_{i=0}^{n}(h[i])+\sum_{i=0}^{n} a[i] - \sum_{i=0}^{n} 2^{h[i]})$$$, where $$$h[i]$$$ is the highest set bit of $$$a[i].$$$

$$$3^{rd}$$$ is classic dp LCS

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the first problem, if : s = abz, v = {z, abz}. Who will the winner in this case?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    z will be the winner as idx['z'] > idx['a'].

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the second one. First we can create an auxilarry array aux. For each i, what we will do is divide l[i] by 2 and check if l[i] is odd or not. if odd then aux[i]+=1 till l[i] becomes 0.

And then we have to find the maximum times l[i] has to be divided by 2 to get 0 for each i. Lets call it times. The answer will be times + sum(aux)

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For second question consider 2 parameters for each element $$$x[i]$$$ and $$$y[i]$$$. $$$x[i]$$$ is the number of subtraction and $$$y[i]$$$ is the number of division by $$$2$$$. if $$$a[i]$$$ is even divide by $$$2$$$ and increment $$$y[i]$$$ , if it is odd subtract $$$1$$$ and increment $$$x[i]$$$. The final answer is

$$$\sum_{i=1}^{n} x[i] $$$ + max of all $$$y[i]$$$ from $$$1$$$ to $$$n$$$

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For the first problem, I had an approach but idk about its correctness.

Test Case:
v = {"ab","abdf","abe"}

Approach:
1. Take the first string as winner = "ab".
2. Compare current winner with second string according to the rules, "abdf" > "ab", so winner = "abdf".
3. Repeat step 2 for each string.

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Stupid CGPA criteria :'(

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Was this on-campus? Also was it for intern role ?

→ Reply