Samsung Research Institute

Details

Job Status

Internship Only

Criteria

Round 1

18/10/23

There were 3 coding questions to be solved in 80 min, everyone got 3 questions from a pool of questions.

Coding Questions

1. Christmas Gifts: There are N chocolates and M toys, a gift box can have either X chocolates and Y toys or X toys and Y chocolates.

   Find the maximum number of gift boxes that can be made.

int solve(int n, int m, int x, int y) {
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));

    auto dfs = [&] (auto self, int i, int j) {
        if (min(i, j) < 0) {
            return -1;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int left = self(self, i - x, j - y);
        int right = self(self, i - y, j - x);

        return dp[i][j] = 1 + max(right, left);
    };
    
    return dfs(dfs, n, m);
}

2. Hamiltonian Circuits: Given an undirected graph, return the total number of unique hamiltonian circuits.

   Note: An hamiltonian circuit is a path in which each node in the graph is visited once except for the source node which is visited twice.

• GFG

3. Worms: Given some number of worms and some number of interactions amongst the worms, figure out whether these interactions are valid or not.

   A worm can be a male or female. A valid interaction is when a male worm interacts with the female worm and vice versa.

   For the given set of interactions, figure out if it is a valid set of interactions or an invalid set of interactions.

   Ex:

   3 (worms) 3 (interactions)
   1 2
   2 3
   1 3
   
   This is invalid as 1 interacts with 2 and 3 but 2 interacts with 3, there is no possible combination of genders where this is valid.