DSA Interview problems

amazon.md

Problem

There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in.For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

Return a list of groups such that each person i is in a group of size groupSizes[i].

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3] Output: [[5],[0,1,2],[3,4,6]] Explanation: The first group is [5]. The size is 1, and groupSizes[5] = 1. The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3. The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3. Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2] Output: [[1],[0,5],[2,3,4]]

Constraints:

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n

Solution

def find_groups(groupSizes):
    groups = {}
    result = []
    for i in range(0, len(groupSizes)):
        group_size = groupSizes[i]
        
        if group_size not in groups:
            groups[group_size] = []

        groups[group_size].append(i)
        
    
        if len(groups[group_size]) == group_size:
            result.append(groups[group_size])
            groups[group_size] = []

    return result

print(find_groups([2,1,3,3,3,2]))
print(find_groups([3,3,3,3,3,1,3]))

anagram.md

Problem Statement: The WordQuest Swipe Challenge

In the WordQuest championship, you’ve swiped the string s = "wolkdre" on your keyboard, hoping to form a valid word from a given list of legendary words: ["word", "world", "wonder", "west"]. Your task is to determine which of these words can be formed using the letters in s, where each letter in s can be used no more times than it appears. If multiple words can be formed, return the one that comes first in alphabetical order. If no word can be formed, return "-1".

Input: A string s (e.g., "wolkdre") representing the swiped letters. A list of target words (e.g., ["word", "world", "wonder", "west"]).

Output: A string representing the first valid word in alphabetical order that can be formed from the letters in s. If no word can be formed, return "-1".

Constraints:

• The string s contains only lowercase English letters.
• Each letter in s can be used only as many times as it appears.
• The target words contain only lowercase English letters.
• If multiple words are valid, return the one that is first in alphabetical order.

Example:

Input: s = "wolkdre", target = ["word", "world", "wonder", "west"] Output: "word" Explanation:

Letters in s: w, o, l, k, d, r, e (each appears once). "word" (w, o, r, d): All letters present → Valid. "world" (w, o, r, l, d): All letters present → Valid. "wonder" (w, o, n, d, e, r): Missing 'n' → Invalid. "west" (w, e, s, t): Missing 's' and 't' → Invalid.

Valid words: ["word", "world"]. Alphabetical order: ["word", "world"] → Return "word".

Input: s = "root", target = ["cat", "door"] Output: "-1"

Explanation: No word can formed from "root"

Task: Implement the validWord method to check which target words can be formed from s, returning the lexicographically smallest valid word or "-1" if none are valid.

javaimport java.util.List;

public class SwipeWordQuest {
    
    public static String validWord(String s, List<String> target) {
        // Your code here
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read the swipe string
        System.out.println("Enter the swipe string:");
        String str = scanner.nextLine().trim();

        // Read the target words (space-separated)
        System.out.println("Enter the target words (space-separated):");
        String[] targetArray = scanner.nextLine().trim().split("\\s+");
        List<String> targets = Arrays.asList(targetArray);

        // Output the result
        System.out.println(validWord(str, targets));

        scanner.close();
    }
}

workday.md

Problem

Based on your description, I'll assume this is a HackerRank-style problem involving N processes (likely numbered from 1 to N) with a mapping where each process i has a "to" value (e.g., a directed edge to another process or a resource). The task is to validate Q queries, where each query likely asks if a path exists from process A to process B (or if the mapping allows B to be reached from A), i.e., checking for reachability in a directed graph. If a query is valid (path exists), output "Yes"; else "No".

Approach

• Model as a Graph: Treat processes as nodes (1 to N). The mappings are directed edges (from → to).

• Build Adjacency List: Use a list of lists to represent the graph.

• Reachability Check: For each query, perform a DFS (Depth-First Search) from the "from" process to see if the "to" process is reachable. To optimize for multiple queries, we can precompute transitive closure using Floyd-Warshall (O(N³)), but since N is small (assume N ≤ 100), it's fine. For larger N, DFS per query (O(N + M) per query, where M is edges) is also okay.

• Input Format Assumption:

  • First line: N M (N processes, M mappings)

  • Next M lines: from to (directed edge)

  • Next line: Q (number of queries)

  • Next Q lines: A B (validate if path from A to B exists)

  • Output: For each query, "Yes" or "No" on a new line.

Sample Input

4 3
1 2
2 3
1 4
2
1 3
4 2

Sample output

Yes
No

Explanation: From 1 → 3 (via 1→2→3): Yes. From 4 → 2: No path.

Solution

import java.util.*;

public class Main {
    // BFS to check if target is reachable from start
    static boolean bfs(ArrayList<Integer>[] graph, int start, int target, int N) {
        boolean[] visited = new boolean[N + 1]; // 1-indexed
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            if (current == target) {
                return true;
            }
            for (int neighbor : graph[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Read N and M
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        
        // Initialize adjacency list (1-indexed)
        @SuppressWarnings("unchecked")
        ArrayList<Integer>[] graph = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // Read M mappings
        for (int i = 0; i < M; i++) {
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            graph[from].add(to);
        }
        
        // Read Q queries
        int Q = scanner.nextInt();
        String[] results = new String[Q];
        
        // Process each query
        for (int i = 0; i < Q; i++) {
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            
            // Validate process IDs
            if (A < 1 || A > N || B < 1 || B > N) {
                results[i] = "No";
            } else {
                // Run BFS
                results[i] = bfs(graph, A, B, N) ? "Yes" : "No";
            }
        }
        
        // Output results
        for (String result : results) {
            System.out.println(result);
        }
        
        scanner.close();
    }
}