UKG | OA | ROUND |2025 | FEB

Round 1

Questions: You are given a list of products, where each product has a name, price, and weight. Your task is to determine how many duplicate products are in the list. A duplicate product is defined as a product that has the same name, price, and weight as another product in the list.

Function Signature

public static int numDuplicates(List name, List price, List weight)

Parameters:

• name: A list of strings where name[i] represents the name of the product at index i.
• price: A list of integers where price[i] represents the price of the product at index i.
• weight: A list of integers where weight[i] represents the weight of the product at index i.

Returns: An integer denoting the number of duplicate products in the list.

Constraints 1 ≤ n ≤ 10^5 1 ≤ price[i], weight[i] ≤ 1000 name[i] consists of lowercase English letters (a-z) and has at most 10 characters.

Example 1 Input

name = ["ball", "box", "ball", "ball", "box"]
price = [2, 2, 2, 2, 2]
weight = [1, 2, 1, 1, 3]

Output

2

Explanation "ball" at indices [0, 2, 3] have the same attributes (name = "ball", price = 2, weight = 1), so there are 2 duplicates. "box" at indices [1, 4] have different weights, so they are unique.

Example 2 Input

name = ["ball", "box", "lamp", "brick", "pump"]
price = [2, 2, 2, 2, 2]
weight = [2, 2, 2, 2, 2]

Output

0

Explanation Each product has unique attributes, so there are no duplicates.

Solution

import java.util.*;

public class Result {
    public static int numDuplicates(List<String> name, List<Integer> price, List<Integer> weight) {
        Map<String, Integer> productCount = new HashMap<>();
        int duplicates = 0;

        for (int i = 0; i < name.size(); i++) {
            String productKey = name.get(i) + "," + price.get(i) + "," + weight.get(i);
            productCount.put(productKey, productCount.getOrDefault(productKey, 0) + 1);
        }

        for (int count : productCount.values()) {
            if (count > 1) {
                duplicates += (count - 1); // Count only the extra occurrences
            }
        }

        return duplicates;
    }

    public static void main(String[] args) {
        List<String> name = Arrays.asList("ball", "box", "ball", "ball", "box");
        List<Integer> price = Arrays.asList(2, 2, 2, 2, 2);
        List<Integer> weight = Arrays.asList(1, 2, 1, 1, 3);

        System.out.println(numDuplicates(name, price, weight)); // Output: 2
    }
}

Complexity Analysis

• Time Complexity: O(n), since we iterate through the list once to store product attributes in a HashMap and another pass to count duplicates.
• Space Complexity: O(n), as we store unique product keys in the HashMap.

Candidate's Approach

The candidate utilized a HashMap to count occurrences of each unique product defined by its name, price, and weight. The approach involved creating a unique key for each product and incrementing its count in the map. Finally, the candidate calculated duplicates by checking counts greater than one.

Interviewer's Feedback

The interviewer appreciated the efficient use of a HashMap for counting duplicates and noted that the solution was clear and well-structured. They suggested considering edge cases in future implementations.

---

Round 2

Questions: You are given an undirected tree with tree_nodes nodes, numbered from 0 to tree_nodes - 1, and rooted at node 0. Each node initially has a binary value (0 or 1) given by the array initial[], and an expected binary value given by the array expected[].

You can perform the following operation any number of times:

Pick a node u and flip its value along with all nodes v in the subtree of u where v % 2 == u % 2. Flipping a value means toggling between 0 and 1.

Find the minimum number of operations needed so that the final binary values match expected[].

Example 1 Input

tree_nodes = 4
tree_from = [0, 0, 1]
tree_to = [1, 2, 3]
initial = [1, 1, 0, 1]
expected = [0, 1, 1, 0]

Output

2

Explanation Pick node 0 and flip it → initial = [0, 1, 1, 1] Pick node 3 and flip it → initial = [0, 1, 1, 0] (matches expected)

Example 2 Input

tree_nodes = 5
tree_from = [0, 1, 0, 1]
tree_to = [1, 2, 3, 4]
initial = [1, 0, 1, 1, 0]
expected = [1, 1, 0, 1, 1]

Output

3

Approach

• Build the Tree: Construct an adjacency list from tree_from and tree_to.
• Use DFS Traversal: Start DFS from the root node (0) while tracking flipEven and flipOdd states.
• Track Flips Efficiently: Maintain flipEven and flipOdd to track the effect of previous flips at even and odd depth levels. If a node’s flipped value does not match expected[], perform a flip and propagate it down.

Optimized DFS Solution (Java)

import java.util.*;

public class Result {
    public static int getMinimumOperations(int treeNodes, List<Integer> treeFrom, List<Integer> treeTo, 
                                           List<Integer> initial, List<Integer> expected) {
        // Step 1: Build the Tree as an Adjacency List
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < treeNodes; i++) {
            tree.add(new ArrayList<>());
        }
        for (int i = 0; i < treeFrom.size(); i++) {
            tree.get(treeFrom.get(i)).add(treeTo.get(i));
            tree.get(treeTo.get(i)).add(treeFrom.get(i)); // Since it's an undirected tree
        }

        // Step 2: DFS to Find Minimum Flips
        boolean[] visited = new boolean[treeNodes];
        return dfs(0, -1, 0, 0, tree, visited, initial, expected);
    }

    private static int dfs(int node, int parent, int flipEven, int flipOdd, 
                           List<List<Integer>> tree, boolean[] visited, 
                           List<Integer> initial, List<Integer> expected) {
        visited[node] = true;
        int flips = 0;

        // Determine the effective value of this node after previous flips
        int currentValue = initial.get(node);
        if (node % 2 == 0) {
            currentValue ^= flipEven;
        } else {
            currentValue ^= flipOdd;
        }

        // If the value does not match expected, we flip it
        if (currentValue != expected.get(node)) {
            flips++;
            // Propagate flip
            if (node % 2 == 0) {
                flipEven ^= 1;
            } else {
                flipOdd ^= 1;
            }
        }

        // Traverse children
        for (int child : tree.get(node)) {
            if (child != parent) {  // Avoid revisiting the parent
                flips += dfs(child, node, flipEven, flipOdd, tree, visited, initial, expected);
            }
        }

        return flips;
    }

    // Sample test case
    public static void main(String[] args) {
        List<Integer> treeFrom = Arrays.asList(0, 0, 1);
        List<Integer> treeTo = Arrays.asList(1, 2, 3);
        List<Integer> initial = Arrays.asList(1, 1, 0, 1);
        List<Integer> expected = Arrays.asList(0, 1, 1, 0);
        int treeNodes = 4;

        System.out.println(getMinimumOperations(treeNodes, treeFrom, treeTo, initial, expected)); // Output: 2
    }
}

Complexity Analysis

• Building the tree: O(N)
• DFS traversal: O(N)
• Total Complexity: O(N), where N = tree_nodes

Candidate's Approach

The candidate constructed an adjacency list to represent the tree and implemented a DFS traversal to determine the minimum number of flips required. They maintained two states for flips (even and odd) to optimize the flipping process and ensure efficient propagation of changes.

Interviewer's Feedback

The interviewer commended the candidate for their clear understanding of tree traversal and efficient state management. They recommended further exploration of edge cases in tree structures.

---

Round 3

Questions: You are working on a Git repository located at: 📂 /home/ubuntu/1792024-git-excluding-specific-files-and-directories

Your task is to modify the repository's tracking behavior so that:

• The .env file is no longer tracked by Git.
• The cache/ directory (and all files within it) is no longer tracked by Git.

These files should remain in the local filesystem but should not be included in future commits. After making these changes, commit the update with the message: 📜 "Exclude from tracking"

Push the commit to the remote repository.

Expected Outputs

• Git Status Output (git status)

On branch master  
Your branch is up to date with 'origin/master'.  
nothing to commit, working tree clean  

• Tracked Files Output (git ls-files)

.gitignore  
README.md  
core.module  
modules/a.module  
modules/b.module  

• Untracked Files Output (git ls-files --other)

.env  
cache/a.cache  
cache/b.cache  
cache/something.else  

• Local File Presence (ls -al .env cache/*)

-rw-r--r-- 1 ubuntu ubuntu 52 Jun 9 09:22 .env  
-rw-rw-r-- 1 ubuntu ubuntu 11 Jun 9 09:20 cache/a.cache  
-rw-rw-r-- 1 ubuntu ubuntu 20 Jun 9 09:20 cache/b.cache  
-rw-rw-r-- 1 ubuntu ubuntu 25 Jun 9 09:20 cache/something.else  

• Git Log (git log --name-status)

commit 8eccc904ff32a87fa184a6da3edd82bab1ccfeb3 (HEAD -> master, origin/master)  
Author: Hacker Developer <hacker.developer@hackercompany.com>  
Date: Sun Jun 9 09:28:37 2024 +0000  

    Exclude from tracking  

D .env  
A .gitignore  
D cache/a.cache  
D cache/b.cache  
D cache/something.else  

How Would You Solve This? What are the best Git commands to achieve this while ensuring that the .env file and cache/ directory remain in the local project but are no longer tracked by Git?

Candidate's Approach

The candidate suggested using the following Git commands:

1. Create or update a .gitignore file to include .env and cache/.
2. Use git rm --cached .env to stop tracking the .env file.
3. Use git rm --cached -r cache/ to stop tracking the cache directory and its contents.
4. Commit the changes with the message "Exclude from tracking".
5. Push the commit to the remote repository.

Interviewer's Feedback

The interviewer was impressed with the candidate's understanding of Git commands and their ability to manage file tracking effectively. They encouraged the candidate to continue practicing Git operations for better proficiency.

---