12 months ago

Akshat Agrawal • 20

Navi Mumbai

Adobe visited our campus for Product intern role. The process comprised of two parts: 1) Online Assessment 2) Technical interview

Round 1 Online Assessment (Duration: 1hr) : There were two sections: 1) Section A (1 X 5 Marks): This section had 5 MCQ problems based on probability and combinatorics. 2) Section B (10 X 2 Marks): This section had 2 Coding Problems.

Problem 1: https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/

Problem 2: Find the minimum cost of constructing a string which consists of only 4 distinct characters, such that no two consecutive characters are same. Given a matrix of size n x 4 where ith row entry shows cost of all 4 characters at ith position in the string.

I was able to solve both the problems so i got shortlisted for the interview. 12 Students were shortlisted after online assessment.

Round 2 Interview (Duration: 45-50 min):

The interview was conducted on Teams. The interview started with my introduction. He then asked me to explain my project. I explained it thoroughly and also included the tech stack I used. Then he asked some few questions regarding the project like why did you implement it this way, then he suggested another way and asked me if I could implement it another way. He asked me what problems could come if we implement it this way. After some more discussion on the project he asked what programming languages I use and how proficient I am in each language. He also asked what subjects I have studied till now, then the next questions were based on this.

He first asked me if I knew about the diamond problem in OOPS. Then asked me to explain the problem and how it can be fixed. He then asked about runtime polymorphism and asked the implementation behind it. He then asked what is the critical section problem and asked me to write some pseudocode explaining the problem. Also asked about smart pointers and virtual table.

At the end he asked a simple puzzle, There is a river and there are two sides, Side A and Side B. Side A has some cities and Side B has some cities, we cannot connect a city in Side A to another city in Side A, similarly we cannot connect a city in Side B to another city in Side B, but we can move from a city in side A to a city in side B and vice-versa. We need to find out the minimum number of bridges that need to be constructed such that we can move from every city to every city. I was able to explain my approach to him by giving an example.

At the end, I asked about the work culture at work and tech stacks used. Then he wrapped up the call. Most surprising part of the interview was he didn't ask any DSA questions from me.

2 were selected after the interview and I was one of them.

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to Problem 2

Analysis

The problem can be solved simply using dynamic programming. Let dp[i][j] denote the minimum cost of creating a string of length i which ends with the character j (1 ≤ j ≤ 4). We can then use the following dp transition to calculate the dp:

• dp[i][j] = min(dp[i-1][k] + cost[i-1][k]) ∀ 1 ≤ k ≤ 4, k ≠ j.

The final answer is min(dp[n][k]) ∀ 1 ≤ k ≤ 4 . Thus we can solve the problem in a time complexity of O(16*N) and a space complexity of O(1).

Code (C++)

#include<bits/stdc++.h>
using namespace std;
const int inf = INT_MAX;
int main()
{
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        vector<int> dp(4), ndp(4,inf); for(int i=0; i<4; i++) cin>>dp[i];
        for(int i=1; i<n; i++)
        {
            for(int j=0; j<4; j++)
            {
                int cost; cin>>cost;
                for(int k=0; k<4; k++)
                {
                    if(j!=k) ndp[j] = min(ndp[j], dp[k] + cost);
                }
            }
            dp = ndp;
            ndp.assign(ndp.size(),inf);
        }
        cout<<*min_element(dp.begin(),dp.end())<<"\n";
    }
}