Question

Atlassian | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-8

Answer 1

The online assessment included 15 MCQs related to Operating Systems and Computer Networking. One problem (also MCQ) was more like a server load problem to calculate approx. time taken to upload and download files. 

 

1. 

 

Test cases -

 

•  

  Input - N=2 rollMax=[1,2,1,2,1,2] Output - 33 (Since {11}, {33}, {55} are not allowed. So 6 * 6 - 3 )

   

•  

  Input - N=3 rollMax=[1,1,1,1,1,1] Output - 150 (6 * 5 * 5)
  Constraints - N<= 1e5 and rollMax[i]<=50

Answer 2

JAVA SOLUTION
// "static void main" must be defined in a public class.
public class Main {
    private static int M = 1000000007;
    public static void main(String[] args) {
        System.out.println("Hello World!");
        int n =2;
        int[] rollMax={1,2,1,2,1,2};
        // int[] rollMax={1,1,1,1,1,1};
        
        System.out.println(dieSimulator(n, rollMax));
    }
    private static Map<Integer, Integer> map = new HashMap<>();
    private static int dieSimulator( int n , int[] dice) {
        if( n == 0 )
            return 1;
        int result = 0;
        for( int i =0; i < 6; i++) {
            if( dice[i] == 0 )
                continue;
            dice[i] -= 1;
            result += dieSimulator(n-1, dice);
            dice[i] += 1;
            result %= M;
        }
        return result;
    }
}

Answer 3

for(int i=0;i<6;i++)
	dp[1][i]=1;
for(int i=2;i<=n;i++)
{
	int sum=0;
	for(int j=0;j<6;j++)
		sum+=dp[i-1][j];
	for(int j=0;j<6;j++)
	{
		dp[i][j]=sum-dp[i-1][j];
		for(int k=i-1;k>=1 && i-k < arr[j];k--)
		{
			dp[i][j]+=dp[k][j];
		}
	}
}
int ans=0;
for(int i=0;i<6;i++)
	ans+=dp[n][i];
cout<<ans;

Answer 4

similar ques 

https://leetcode.com/problems/dice-roll-simulation/

Solution in max 50 * 6 * N time for 1st question using dynamic programming, dp[d][i] gives the number of sequences that in the last i rolls we have dice=d, and the previous one was not d, so the run's length was exactly "i".

 

int rollDice(int N,vector<int> rollMax){
    
    if(N==0)return 1;
    
#define M 1000000007
    
    vector<vector<int>>dp(6);
    for(int i=0;i<6;i++){
        dp[i]=vector<int>(rollMax[i]+2,0);
        dp[i][1]=1;
    }
    
    for(int numroll=2;numroll<=N;numroll++){
        int total=0;
        int p_sum[6];
        for(int d=0;d<6;d++){
            int partsum=0;
            for(int i=0;i<=rollMax[d];i++)partsum=(partsum+dp[d][i])%M;
            p_sum[d]=partsum;
            total=(total+partsum)%M;
        }
        
        for(int d=0;d<6;d++){
            for(int i=rollMax[d];i>1;i--)dp[d][i]=dp[d][i-1];
            int res=(total-p_sum[d])%M;
            if(res<0)res+=M;
            dp[d][1]=res;
        }
    }

    int ans=0;
    for(int d=0;d<6;d++)for(int i=1;i<=rollMax[d];i++)ans=(ans+dp[d][i])%M;
    return ans;
}
    
    
int main(void){
    
    cout<<rollDice(2,{1,2,1,2,1,2})<<endl;
    cout<<rollDice(3,{1,1,1,1,1,1})<<endl;
    
    return 0;
}