NUHMAN.com

💡 Problem Statement

You are given two arrays of store names representing routes planned for two people:

java

Array 1 = {"storea", "storeg", "storek", "storel"};
Array 2 = {"storea", "storel", "storep", "storeg"};

Each person must visit one store at each time index (i.e., both people act simultaneously), and no store should be visited by both people at any point.

🎯 Goal

Assign the stores to each person such that:

• At each time slot, one person takes one store from the two arrays.
• No person visits the same store twice.
• No store is visited by both people at any point.

We will solve this using recursive backtracking in Java.

🛠️ Java Recursive Solution

java

import java.util.HashSet;
import java.util.Set;

public class StoreVisit {

    public static void main(String[] args) {
        String[] array1 = {"storea", "storeg", "storek", "storel"};
        String[] array2 = {"storea", "storel", "storep", "storeg"};
        
        Set<String> person1 = new HashSet<>();
        Set<String> person2 = new HashSet<>();

        boolean isPossible = findOptimalVisit(array1, array2, 0, person1, person2);

        if (isPossible) {
            System.out.println("✅ Person 1 visits: " + person1);
            System.out.println("✅ Person 2 visits: " + person2);
        } else {
            System.out.println("❌ No valid assignment possible without overlap.");
        }
    }

    public static boolean findOptimalVisit(String[] array1, String[] array2, int index,
                                           Set<String> person1, Set<String> person2) {
        // ✅ Base case: All slots processed
        if (index == array1.length) {
            return true;
        }

        String store1 = array1[index];
        String store2 = array2[index];

        // ➤ Try assigning store1 to person1 and store2 to person2
        if (!person1.contains(store1) && !person2.contains(store2) && !store1.equals(store2)) {
            person1.add(store1);
            person2.add(store2);
            if (findOptimalVisit(array1, array2, index + 1, person1, person2)) {
                return true;
            }
            person1.remove(store1);
            person2.remove(store2);
        }

        // ➤ Try swapping: store2 to person1 and store1 to person2
        if (!person1.contains(store2) && !person2.contains(store1) && !store1.equals(store2)) {
            person1.add(store2);
            person2.add(store1);
            if (findOptimalVisit(array1, array2, index + 1, person1, person2)) {
                return true;
            }
            person1.remove(store2);
            person2.remove(store1);
        }

        // ❌ No valid combination for this index
        return false;
    }
}

🔍 How It Works

ComponentRoleSet<String>Keeps track of stores visited by each person to avoid overlap.indexIndicates the current time slot being evaluated.Base CaseIf all indices are processed, return true.Recursive StepTry assigning stores to persons; backtrack if needed.

🧪 Example Output

less

✅ Person 1 visits: [storek, storea]
✅ Person 2 visits: [storel, storeg]

The exact set order may vary due to HashSet, but you’ll see that all visited stores are unique and assigned without conflict.

✨ Benefits of This Approach

✅ Conflict-Free Assignments

✅ Handles Swaps Automatically

✅ Backtracking to Explore All Combinations

✅ No Duplicates for Either Person

📘 Enhancements & Interview Follow-ups

• 🔁 Convert to iterative DP or memoized recursion for performance boost.
• 📦 Return a list of all possible valid combinations, not just one.
• 🚶‍♂️ Add distance/cost for path optimization (like traveling salesman problem).