Question

D.E Shaw IIT Madras Round 1 | OA Coding Questions and Solutions | Set - 17| 2022

Answer 1

Q2. Assume you are playing the game Mortal Kombat. If you have h health and d damage, and you have k opponents whose health and damage are stored in separate arrays, find the maximum coins u can earn in the game (killing a person with m health gives you m coins, and the opponents are against you only)
Q3. Give two numbers n and k, find the number of binary strings of length n which contain <= k zeroes after every 1 in the string.

Answer 2

Posting questions without test cases doesn't help anyone!
1st one is fairly straightforward :-)

vector<string>m;
void dfs(int i,int j,char ch,int len){

   for(int k=j;k<j+len;k++){
      m[i][k]=ch;
   }

   for(int k=j;k<j+len;k++){
     m[i+len-1][k]=ch;
   }
   for(int k=i+1;k<i+len-1;k++){
    m[k][j]=ch;
    m[k][j+len-1]=ch;
   }

}

void solve(){

    int n;
    cin>>n;
    string s= string(2*n,'*');
    for(int i=0;i<2*n;i++){
      m.push_back(s);
    }
    int i=0;
    int j=0;
    int len=2*n;
    for(char ch='a'+n-1; ch>='a';ch-- ){
        dfs(i,j,ch,len);
        len-=2;
        i++;
        j++;
    }
    for(auto x:m){
        cout<<x<<endl;
    }
}

Q2 is 2D knap-sack.
Q3 is DP.

 

Q2 assume max number of enemies<100, and there are times when you can't earn any coins (when their health/damage is too high )
Q3 no such constraints, but if ans is too big, give the remainder post division by 7+10^9