پیمایش معکوس
Reverse Traversalپیمایش معکوس یک الگوریتم از دسته لیست‌های پیوندی است. این الگوریتم Linked List به‌جای index از referenceها عبور می‌کند؛ بنابراین ترتیب تغییر pointer/reference مهم‌ترین بخش correctness است.
اول این مفهوم را در ذهن نگه دار
پیمایش معکوس یک الگوریتم از دسته لیست‌های پیوندی است. این الگوریتم Linked List به‌جای index از referenceها عبور می‌کند؛ بنابراین ترتیب تغییر pointer/reference مهم‌ترین بخش correctness است.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم پیمایش معکوس ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع Varies by implementation / input constraints است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
اگر قرار است link عوض شود next را قبلش ذخیره کن.
current/previous را با ترتیب درست جلو ببر.
لیست خالی و تکNode را جدا بررسی کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای پیمایش معکوس هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی مسئله مستقیماً روی linkهای Nodeها تعریف شده مناسب است.
کجا معمولاً اشتباه می‌کنیم؟
- با overwrite کردن next ادامه لیست را گم نکن.
- edge case مربوط به null را مدیریت کن.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای پیمایش معکوس در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی Varies by implementation / input constraints و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
پیمایش معکوس چه مسئله‌ای را حل می‌کند؟
پیمایش معکوس یک الگوریتم از دسته لیست‌های پیوندی است. این الگوریتم Linked List به‌جای index از referenceها عبور می‌کند؛ بنابراین ترتیب تغییر pointer/reference مهم‌ترین بخش correctness است.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
با overwrite کردن next ادامه لیست را گم نکن.