🚖 مسأله مصاحبه Uber
ما یک سری قواعد مکانی داریم که رابطه بین نقاط را مشخص میکنند.
A NE B → یعنی نقطه A شمالشرق نقطه B است.
A SW C → یعنی نقطه A جنوبغرب نقطه C است.
🔍 هدف: بررسی کنیم که آیا کل این قواعد با هم سازگار (consistent) هستند یا نه.
📌 نمونهها
A N B B NE C C N A
❌ معتبر نیست، چون در این صورت A باید هم شمال C باشد و هم جنوب C.
A NW B A N B
✅ معتبر است، چون هر دو شرط با هم سازگار هستند.
💡 ایده حل (تفکر الگوریتمی)
این مسأله شباهت زیادی به گراف و سازگاری قیود دارد.
هر نقطه → یک رأس (node) در گراف.
هر قانون → یک یال (edge) با رابطهی نسبی جهتدار (N, S, E, W).
برای بررسی سازگاری:
باید موقعیت نسبی هر نقطه را در یک سیستم مختصات دوبعدی (x,y) مدل کنیم.
N = +y
S = -y
E = +x
W = -x
هر قاعده، یک معادله یا نابرابری روی مختصات اضافه میکند.
اگر تضاد پیدا شود (مثلاً همزمان میگوید A بالاتر از B و پایینتر از B)، مجموعه معتبر نیست.
🔎 پیادهسازی خطبهخط (Python)
def validate_rules(rules): # نگاشت جهتها به بردارهای مختصات direction_map = { "N": (0, 1), "S": (0, -1), "E": (1, 0), "W": (-1, 0), "NE": (1, 1), "NW": (-1, 1), "SE": (1, -1), "SW": (-1, -1) } # گراف قیود: برای هر نقطه مجموعه روابطش from collections import defaultdict constraints = defaultdict(list) # اضافه کردن قیود for a, d, b in rules: dx, dy = direction_map[d] constraints[a].append((b, dx, dy)) constraints[b].append((a, -dx, -dy)) # رابطه معکوس # DFS با بررسی سازگاری positions = {} # مختصات هر نقطه def dfs(node, x, y): if node in positions: return positions[node] == (x, y) positions[node] = (x, y) for neigh, dx, dy in constraints[node]: if not dfs(neigh, x - dx, y - dy): return False return True # بررسی همه نقاط for node in constraints: if node not in positions: if not dfs(node, 0, 0): return False return True
✨ توضیح حرفهای خطبهخط
direction_map : هر جهت را به یک بردار (dx, dy) نگاشت میکنیم.
مثلا NE → (1,1) یعنی یک گام به شرق و یک گام به شمال.
constraints : گرافی میسازیم که در آن هر یال نشاندهنده رابطه مکانی بین دو نقطه است.
dfs(node, x, y) : با پیمایش عمقی، برای هر نقطه یک مختصات فرضی میگذاریم. اگر قبلاً مختصات داشت و تناقض پیدا شد، مجموعه نامعتبر است.
در پایان: اگر هیچ تناقضی پیدا نشد → قواعد معتبر هستند.
✅ خروجی نهایی
مثال اول (نامعتبر):
rules = [("A", "N", "B"), ("B", "NE", "C"), ("C", "N", "A")] print(validate_rules(rules)) # False
مثال دوم (معتبر):
rules = [("A", "NW", "B"), ("A", "N", "B")] print(validate_rules(rules)) # True
📌 این مسأله قدرت شما در مدلسازی ریاضی از مسأله کلامی را میسنجد؛ چیزی که دقیقاً در مصاحبههای Uber و شرکتهای مشابه به دنبال آن هستند.
Daily Coding Problem: Problem #1206 [[Hard]