You are given a set of locations L laid out on a 2D grid (rows and columns) and a list of relational clues of the forms: ( 1) X is north/south/east/west of Y; ( 2) X is adjacent/not-adjacent to Y; ( 3) X cannot be in row r or column c; ( 4) Exactly one of {A, B, C} is adjacent to D. Assume the clues are consistent and determine the unique location (row, column) of a target person P or report that no unique solution exists. Design an algorithm to solve this constraint-satisfaction problem, describe the data structures you will use, analyze time/space complexity, and provide pseudocode.

This question evaluates the ability to model and reason about constraint-satisfaction on a 2D grid, including logical inference with directional and adjacency relations, combinatorial placement constraints, and determination of uniqueness.

How do I approach Statistics & Math interview questions?

Statistics & Math questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master statistics & math interviews.

What difficulty level is this interview question?

This is a hard difficulty Statistics & Math question, commonly asked during Take-home Project rounds at MathWorks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at MathWorks during technical interviews.

Deduce position from logic clues | MathWorks Interview Question

Constraint-Satisfaction on a 2D Grid with Relational Clues

Context

You are given a rectangular grid with R rows and C columns. A set of named entities (people) must each occupy exactly one distinct grid cell. A set of relational clues constrain where entities may be placed. Your goal is to determine whether the location (row, column) of a particular target person P is uniquely determined by the clues. If so, return that unique location; otherwise report that no unique solution exists.

Assumptions and definitions:

Rows are indexed 1..R (1 is the northernmost/top row) and columns 1..C (1 is the westernmost/left column).
A cell is identified by (r, c).
Adjacency means 4-neighborhood: two cells are adjacent if their Manhattan distance is 1 (i.e., share a side).
Directional relation "X is north of Y" means same column and row(X) < row(Y); similarly for south (>), east (same row, col(X) > col(Y)), west (<).
All entities occupy distinct cells unless otherwise stated.

Clue Types

You may receive any combination of the following clues:

Directional: X is north/south/east/west of Y
Adjacency: X is adjacent/not-adjacent to Y
Unary bans: X cannot be in row r or column c
Exactly-one adjacency: Exactly one of {A, B, C} is adjacent to D

Clues are guaranteed to be mutually consistent (at least one full placement exists), but may or may not uniquely determine P's location.

Task

Design an algorithm to:

Determine the unique location (row, column) of target P if implied by the clues; otherwise report that no unique solution exists.
Describe data structures you will use.
Analyze time and space complexity.
Provide clear pseudocode.

Input (conceptual): R, C; set of entities E; target P ∈ E; list of clues of the types above.

Output: Either the unique (row, column) for P, or a statement that P is not uniquely determined.

Context

Assumptions and definitions:

Rows are indexed 1..R (1 is the northernmost/top row) and columns 1..C (1 is the westernmost/left column).

A cell is identified by (r, c).

Adjacency means 4-neighborhood: two cells are adjacent if their Manhattan distance is 1 (i.e., share a side).

Directional relation "X is north of Y" means same column and row(X) < row(Y); similarly for south (>), east (same row, col(X) > col(Y)), west (<).

All entities occupy distinct cells unless otherwise stated.

Clue Types

You may receive any combination of the following clues:

Directional: X is north/south/east/west of Y

Adjacency: X is adjacent/not-adjacent to Y

Unary bans: X cannot be in row r or column c

Exactly-one adjacency: Exactly one of {A, B, C} is adjacent to D

Clues are guaranteed to be mutually consistent (at least one full placement exists), but may or may not uniquely determine P's location.

Task

Design an algorithm to:

Determine the unique location (row, column) of target P if implied by the clues; otherwise report that no unique solution exists.

Describe data structures you will use.

Analyze time and space complexity.

Provide clear pseudocode.

Input (conceptual): R, C; set of entities E; target P ∈ E; list of clues of the types above.

Output: Either the unique (row, column) for P, or a statement that P is not uniquely determined.

Deduce position from logic clues

Quick Overview

Constraint-Satisfaction on a 2D Grid with Relational Clues

Context

Clue Types

Task

Solution

Comments (0)

Deduce position from logic clues

Quick Overview

Constraint-Satisfaction on a 2D Grid with Relational Clues

Context

Clue Types

Task

Solution

Comments (0)