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.
