Glean's 2-Part Snack Bar Grid Question

Glean dresses a classic grid search in office comedy: get from your desk to a snack bar, then do it quietly enough that the noise never reaches a boss. It is two breadth-first searches with a twist that catches people who conflate reachability with noise. Here is the full question, Java for both parts, and a detailed rubric.

The question

Part 1 · Reach a snack bar

Plain BFS from the desk over passable cells, treating walls and bosses as blocked. Return true the moment you step onto a snack bar.

import java.util.*;

class Office {
    static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};

    boolean canReachSnack(char[][] g) {
        int[] start = find(g, 'D');
        boolean[][] seen = new boolean[g.length][g[0].length];
        Deque<int[]> q = new ArrayDeque<>();
        q.add(start); seen[start[0]][start[1]] = true;
        while (!q.isEmpty()) {
            int[] c = q.poll();
            if (g[c[0]][c[1]] == 'S') return true;
            for (int[] d : DIRS) {
                int r = c[0] + d[0], col = c[1] + d[1];
                if (!inBounds(g, r, col) || seen[r][col]) continue;
                if (g[r][col] == '#' || g[r][col] == 'B') continue;   // walls and bosses block movement
                seen[r][col] = true; q.add(new int[]{r, col});
            }
        }
        return false;
    }

    private int[] find(char[][] g, char target) {
        for (int r = 0; r < g.length; r++)
            for (int c = 0; c < g[0].length; c++)
                if (g[r][c] == target) return new int[]{r, c};
        return null;
    }
    private boolean inBounds(char[][] g, int r, int c) {
        return r >= 0 && r < g.length && c >= 0 && c < g[0].length;
    }
}

Part 2 · Grab it quietly

Two different searches, and conflating them is the mistake. Movement avoids walls and bosses. Noise is a separate bounded BFS from the snack cell, over non-wall cells (walls block noise), out to distance K; if it reaches a boss, that snack is too loud. A snack works if you can reach it and its noise touches no boss. Because the grid does not change, being able to reach the snack means you can return.

boolean canSnackQuietly(char[][] g, int K) {
    int[] desk = find(g, 'D');
    boolean[][] reachable = reachable(g, desk);          // cells you can walk to
    for (int r = 0; r < g.length; r++)
        for (int c = 0; c < g[0].length; c++)
            if (g[r][c] == 'S' && reachable[r][c] && !noiseHitsBoss(g, r, c, K))
                return true;                              // reachable AND quiet
    return false;
}

private boolean[][] reachable(char[][] g, int[] start) {
    boolean[][] seen = new boolean[g.length][g[0].length];
    Deque<int[]> q = new ArrayDeque<>();
    q.add(start); seen[start[0]][start[1]] = true;
    while (!q.isEmpty()) {
        int[] c = q.poll();
        for (int[] d : DIRS) {
            int r = c[0] + d[0], col = c[1] + d[1];
            if (!inBounds(g, r, col) || seen[r][col]) continue;
            if (g[r][col] == '#' || g[r][col] == 'B') continue;
            seen[r][col] = true; q.add(new int[]{r, col});
        }
    }
    return seen;
}

// Bounded BFS of the noise: walls block it, a boss within K steps is disturbed.
private boolean noiseHitsBoss(char[][] g, int sr, int sc, int K) {
    boolean[][] seen = new boolean[g.length][g[0].length];
    Deque<int[]> q = new ArrayDeque<>();
    q.add(new int[]{sr, sc, 0}); seen[sr][sc] = true;
    while (!q.isEmpty()) {
        int[] c = q.poll();
        if (g[c[0]][c[1]] == 'B') return true;            // noise reached a boss
        if (c[2] == K) continue;                          // noise fades after K steps
        for (int[] d : DIRS) {
            int r = c[0] + d[0], col = c[1] + d[1];
            if (!inBounds(g, r, col) || seen[r][col]) continue;
            if (g[r][col] == '#') continue;               // walls block noise; bosses do not
            seen[r][col] = true; q.add(new int[]{r, col, c[2] + 1});
        }
    }
    return false;
}

The two searches differ on purpose: movement treats a boss as an obstacle, noise treats a boss as a target to avoid disturbing. Walls block both. Mixing them up is the single most common failure here.

How Glean scores it

Glean interview FAQ