ویرگول
ورودثبت نام
سهراب خان‌بدر | Sohrab Khanbadr
سهراب خان‌بدر | Sohrab Khanbadrچیزی مثبت بگو، و چیز مثبت خواهی دید." — جیم تامپسون من کیستم ؟ من کجا هستم ؟ من چه میخواهم ؟
سهراب خان‌بدر | Sohrab Khanbadr
سهراب خان‌بدر | Sohrab Khanbadr
خواندن ۲ دقیقه·۱ سال پیش

🚖 مسأله مصاحبه Uber - شماره 1206

🚖 مسأله مصاحبه 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).

برای بررسی سازگاری:

  1. باید موقعیت نسبی هر نقطه را در یک سیستم مختصات دوبعدی (x,y) مدل کنیم.

    • N = +y

    • S = -y

    • E = +x

    • W = -x

  2. هر قاعده، یک معادله یا نابرابری روی مختصات اضافه می‌کند.

  3. اگر تضاد پیدا شود (مثلاً همزمان می‌گوید 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]

۰
۰
سهراب خان‌بدر | Sohrab Khanbadr
سهراب خان‌بدر | Sohrab Khanbadr
چیزی مثبت بگو، و چیز مثبت خواهی دید." — جیم تامپسون من کیستم ؟ من کجا هستم ؟ من چه میخواهم ؟
شاید از این پست‌ها خوشتان بیاید