sru_31's blog

By sru_31, history, 7 weeks 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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sru_31 (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sru_31 (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sru_31 (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you give more details for the third question?

»
7 weeks 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]

»
7 weeks 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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you provide code also please

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      int ans=0;
      while(true){
          int cnt=0;
          for(int i=0;i<n;i++){if(arr[i]%2==1){arr[i]-=1;ans++;}if(arr[i]==0)cnt++;}
          if(cnt==n)return ans;
          for(int i=0;i<n;i++){arr[i]/=2;}
          ans++;
      }
  • »
    »
    7 weeks 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?

    • »
      »
      »
      7 weeks 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?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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   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.

»
7 weeks 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

»
7 weeks 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?

»
7 weeks 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)

»
7 weeks 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$$$

»
7 weeks 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.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :

  1. if final_array[i] is odd decrement it by 1

  2. 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))

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Stupid CGPA criteria :'(

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can first sum be done using sorting by comparators? If so can anybody tell the code pls

»
7 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes , it was on campus and it was an internship opportunity

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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<<ans+mx;

Explanation: (Going in reverse direction) Note that divide operation can be done even on element 0. So we will have to perform this operation on the largest number log no. of times ( max log value )

And for the odd number part. This operation is performed on individual numbers. This is simply the count of set bits in the number.

WHY? { consider 11 in binary is 1 0 1 1 Now, every time we right shift it (div by 2) how many times will 1 appear on 0th position is the number of times it will appear as an odd number. }