### sru_31's blog

By sru_31, history, 7 weeks ago, 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.  Comments (27)
 » Auto comment: topic has been updated by sru_31 (previous revision, new revision, compare).
 » Auto comment: topic has been updated by sru_31 (previous revision, new revision, compare).
 » Auto comment: topic has been updated by sru_31 (previous revision, new revision, compare).
 » Can you give more details for the third question?
•  » » If you're asking about the constraints , 1<=n<=1000 1<=m<=1000 -1000<=arr[i]<=1000
•  » » » Thanks
 » 7 weeks ago, # | ← Rev. 2 →   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 statesdp[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]
 » 7 weeks ago, # | ← Rev. 2 →   1.) Brute force works2.) 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
•  » » can you provide code also please
•  » » » int ans=0; while(true){ int cnt=0; for(int i=0;i
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   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?
•  » » » 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?
•  » » » » Reducing each element to 0. 1. Then returning the maximum number of steps it took to reduce any one element. (OR) 2. Returning the total number of steps it took to reduce all elements. Which one of these methods were you explaining?
 » 7 weeks ago, # | ← Rev. 2 →   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.
 » 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
 » For the first problem, if : s = abz, v = {z, abz}. Who will the winner in this case?
•  » » z will be the winner as idx['z'] > idx['a'].
•  » » » ah okay thanks.
 » 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)
 » 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$
 » 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.
 » 7 weeks ago, # | ← Rev. 2 →   for the second problem let's define step[i] as the number of steps to reduce final_array[i] into 0 using the following steps : if final_array[i] is odd decrement it by 1 if final_array[i] is even divide by 2 now the final answer will be the maximum value of step[i] for all i in 1...n Time Complexity : O(n*max(final_array))
 » Stupid CGPA criteria :'(
 » Can first sum be done using sorting by comparators? If so can anybody tell the code pls
 » 7 weeks ago, # | ← Rev. 2 →   Was this on-campus? Also was it for intern role ?
•  » » Yes , it was on campus and it was an internship opportunity
 » 7 weeks ago, # | ← Rev. 2 →   For Second Question : 4 lines of code will do `int mx = 0; int ans = 0; for(int x: array) { ans+=__builtin_popcount(x); mx = maxi(mx, log2(x)); } cout<