سخت‌ترین سؤالات مصاحبه‌‌های کدنویسی FAANG

به نظر می‌رسد سؤالات مصاحبه‌‌های کدنویسی هر روز سخت‌تر می‌شوند و آماده‌سازی برای آن‌ها کار ساده‌ای نیست. هیچ محدودیتی برای نوع سؤالاتی که ممکن است در مصاحبه از شما پرسیده شود، وجود ندارد و بسیاری از آن‌ها آسان نیستند. بنابراین بسیار مهم است که خود را برای مصاحبه کدنویسی آماده کنید. در این مقاله پنج مورد از سخت‌ترین سؤالات مطرح شده در مصاحبه‌های کدنویسی FAANG (Facebook, Amazon, Apple, Netflix, Google) همراه با نکاتی را در‌مورد نحوه آماده‌سازی برای مصاحبه آورده شده است.

نحوه طراحی Garbage Collector

مسئله Garbage Collector به‌عنوان یک مسئله بسیار مشکل شناخته شده است. Garbage Collection موضوعی است که اکثر افراد در مدرسه با آن آشنا نمی‌شوند و فهم مطالب آموزشی مربوط به آن نیز بسیار دشوار است. یادگیری Garbage Collection شامل تئوری‌های بسیاری است، بنابراین فهم آن می‌تواند دشوار و گیج‌کننده باشد. صرف‌نظر از اینکه با چه زبانی کار می‌کنید، بسیار مهم است که زیر‌و‌بم زبان مورد‌نظر را بدانید تا بتوانید به بهترین نحو این مسئله را حل کنید.

هنگام حل این مسئله از پرسیدن سؤال از مصاحبه‌کننده نترسید. به یاد داشته باشید که مصاحبه‌کننده آنجاست تا به شما کمک کند. مصاحبه‌کنندگان معمولاً اطلاعات کمی به شما می‌دهند تا به شما در جهت درست حل مسئله کمک کند.

توجه: سؤالات Garbage Collection در مصاحبه‌های پیشرفته جاوا رایج است، اما دانستن آن‌ها برای سایر زبان‌های برنامه‌نویسی نیز مهم است.

مسئله حداقل تعداد سکه لازم برای یک مقدار مشخص

این مسئله معمولاً در مصاحبه‌های فیس‌بوک و آمازون دیده می‌شود. به شما سکه‌هایی با ارزش‌های مختلف و یک مبلغ کل داده می‌شود. شما باید یک تابع بنویسید که کمترین تعداد سکه مورد‌نیاز برای تشکیل این مقدار را محاسبه کند و اگر نمی‌تواند با هر ترکیبی از سکه‌ها به مقدار مشخص‌شده برسد، 1- را برگرداند.

در اینجا سه روشی که می‌توانید از آن‌ها برای حل این مسئله استفاده کنید، ارائه شده است:

• جستجوی فراگیر (Brute force)
• برنامه‌نویسی پویا از بالا به پایین با Memoization
• برنامه‌نویسی پویا از پایین به بالا با جدول‌سازی

بیایید به برنامه‌نویسی پویا از پایین به بالا با راه‌حل جدول‌بندی در سی‌پلاس‌پلاس نگاهی بیندازیم:

#include <iostream>

using namespace std;

int countChange(int denoms[], int denomsLength, int amount) {
  // Edge cases
  if(amount <= 0 || denomsLength <= 0)
    return 0;

  int i, j, x, y;

  // We need n+1 rows as the table 
  // is constructed in bottom up 
  // manner using the base case 0 
  // value case (n = 0) 
  int lookupTable[amount + 1][denomsLength];

  // Fill the entries for 0 
  // value case (n = 0) 
  for (i = 0; i < denomsLength; i++)
    lookupTable[0][i] = 1;

  // Fill rest of the table entries 
  // in bottom up manner 
  for (i = 1; i < amount + 1; i++) {
    for (j = 0; j < denomsLength; j++) {
      // Count of solutions including denoms[j] 
      x = (i - denoms[j] >= 0) ? lookupTable[i - denoms[j]][j] : 0;

      // Count of solutions excluding denoms[j] 
      y = (j >= 1) ? lookupTable[i][j - 1] : 0;

      // total count 
      lookupTable[i][j] = x + y;
    }
  }
  return lookupTable[amount][denomsLength - 1];
}

// Driver Code 
int main() { 
  int denoms[4] = {25,10,5,1};
  cout << countChange(denoms, 4, 10) << endl;
}

برای هر تکرار حلقه داخلی، راه‌حل را با denoms[j] به دست می‌آوریم و آن را در x ذخیره می‌کنیم. همچنین راه‌حل را بدون denoms[j] به دست می‌آوریم و آن را در y ذخیره می‌کنیم. با انجام این کار، می‌توانیم به راه‌حل‌های قبلی ارجاع دهیم و از محاسبات تکراری جلوگیری کنیم.

برای هر سکه تنها دو احتمال وجود دارد: در نظر گرفتن یا حذف آن. می‌دانیم که اگر سکه denoms[j] بزرگتر از amount باشد، x بر روی 0 تنظیم می‌شود؛ زیرا در نظر گرفتن آن غیرممکن است.

پیچیدگی زمانی O(amount×denomsLength) است که تعداد تکرارهای حلقه for است.

توجه: هر یک از این سه روش شامل پیچیدگی زمانی است و درک پیچیدگی زمانی یک عامل مهم برای موفقیت در حل این مسئله است.

مسئله غذا خوردن فیلسوف‌ها (multithreading)

مسئله غذا خوردن فیلسوف‌ها معمولاً در طراحی الگوریتم هم‌زمان برای نشان دادن مسائل مربوط به همگام‌سازی و تکنیک‌های حل آن‌ها استفاده می‌شود. این مسئله بیان می‌کند که پنج فیلسوف دور یک میز دایره‌ای نشسته‌اند. فیلسوفان باید به‌صورت متناوب فکر کنند و بخورند. هر فیلسوف یک کاسه غذا در جلوی خود دارد و برای خوردن نیاز به یک چنگال در هر دست دارد. با این حال تنها پنج چنگال در دسترس است. شما باید راه‌حلی را طراحی کنید که در آن هر فیلسوف بتواند غذای خود را بدون ایجاد deadlock بخورد.

معمولاً توسعه‌دهندگان این موضوع را نادیده می‌گیرند که این مسئله در‌مورد یک سناریوی واقعی نیست، بلکه انواع مسائلی که ممکن است در اجرای برنامه‌های چند‌نخی و یا مدیریت سهل‌انگارانه قفل‌ها با آن‌ها مواجه شوید را نشان می‌دهد. این مسئله شما را مجبور می‌کند تا به کارآمدترین روش در‌مورد محدودیت‌ها و تنظیم مناسب برای انجام این کار فکر کنید.

برای آمادگی برای این سؤال باید در همگام‌سازی، کنترل هم‌زمان و سمافورها عمیق‌تر شوید.

در ادامه دو راه ممکن برای حل این مسئله ارائه شده است:

• محدود کردن فیلسوفانی که در آستانه غذا خوردن هستند
• تنظیم دوباره برداشتن چنگال

بیایید به راه‌حل تنظیم دوباره برداشتن چنگال در جاوا نگاهی بیندازیم:

public class DiningPhilosophers2 {

    private static Random random = new Random(System.currentTimeMillis());

    private Semaphore[] forks = new Semaphore[5];

    public DiningPhilosophers2() {
        forks[0] = new Semaphore(1);
        forks[1] = new Semaphore(1);
        forks[2] = new Semaphore(1);
        forks[3] = new Semaphore(1);
        forks[4] = new Semaphore(1);
    }

    public void lifecycleOfPhilosopher(int id) throws InterruptedException {

        while (true) {
            contemplate();
            eat(id);
        }
    }

    void contemplate() throws InterruptedException {
        Thread.sleep(random.nextInt(500));
    }

    void eat(int id) throws InterruptedException {

        // We randomly selected the philosopher with
        // id 3 as left-handed. All others must be
        // right-handed to avoid a deadlock.
        if (id == 3) {
            acquireForkLeftHanded(3);
        } else {
            acquireForkForRightHanded(id);
        }

        System.out.println("Philosopher " + id + " is eating");
        forks[id].release();
        forks[(id + 1) % 5].release();
    }

    void acquireForkForRightHanded(int id) throws InterruptedException {
        forks[id].acquire();
        forks[(id + 1) % 5].acquire();
    }

    // Left-handed philosopher picks the left fork first and then
    // the right one.
    void acquireForkLeftHanded(int id) throws InterruptedException {
        forks[(id + 1) % 5].acquire();
        forks[id].acquire();
    }
}

در این راه‌حل، شما هر یک از فیلسوفان را مجبور می‌کنید تا ابتدا چنگال چپ را به جای چنگال راست بردارند. فرقی نمی‌کند که ابتدا کدام فیلسوف را انتخاب کنید و او را مجبور کنید که چنگال چپ خود را بردارد. در این راه‌حل، ما فیلسوف با id = 3 را به عنوان فیلسوف چپ‌دست خود انتخاب کرده‌ایم.

چرا باید از این روش‌های برنامه‌نویسی استفاده کرد؟

هنگام یادگیری برنامه‌نویسی، شما معمولاً برخی از بهترین روش‌ها را یاد می‌گیرید. بهترین توسعه‌دهندگان روش‌های خاصی را در فرایند کدنویسی خود پیاده‌سازی می‌کنند که به آن‌ها کمک می‌کند تا مطمئن شوند که کد آن‌ها از نظر عملکرد و ظاهر به بهترین شکل ممکن است.

پس از سال‌ها تجربه در برنامه‌نویسی، روش‌هایی که باید از آن‌ها اجتناب کنید و روش‌هایی که باید از آن‌ها استفاده کنید را می‌دانید. ممکن است شما یک تصور کلی از اینکه چرا برخی روش‌ها بهتر از بقیه هستند داشته باشید، اما وقتی زمان آن است که دلیل آن را توضیح دهید، دچار مشکل می‌شوید.

چند نمونه از بهترین روش‌ها عبارت‌اند از:

• کامنت‌گذاری در کد
• شناسایی و حذف کدهای تکراری
• گروه‌بندی بر اساس ویژگی‌ها در React
• اجتناب از ساختارهای پنهان در Ruby

بهترین راه آماده‌سازی برای این سؤالات این است که روش‌های مفید و قابل‌اجتناب و استدلال پشت آن‌ها را یادآوری و به خاطر بسپارید. به یاد داشته باشید که در طول مصاحبه می‌توانید در‌مورد این سؤالات با مصاحبه‌کننده صحبت کنید.

پیاده‌سازی کش LRU

با وجود اینکه سؤال پیاده‌سازی حافظه کش LRU (Least Recently Used) چندان متداول نیست، در برخی مصاحبه‌های گوگل، مایکروسافت و آمازون مطرح شده است. این سؤال از شما می‌خواهد که عمیق‌تر فکر کنید و دو یا چند ساختار داده موجود را با هم ترکیب کنید.

مهم است که مسئله را به آرامی بخوانید و مطمئن شوید که متوجه شده‌اید از شما چه خواسته شده است. این سؤالات معمولاً از شما می‌خواهند که چند کار را انجام دهید. هنگامی که مسئله را به‌طور کامل مطالعه کردید، می‌توانید از مصاحبه‌کننده بخواهید تا تأیید کند که در مسیر درستی حرکت می‌کنید یا خیر.

قبل از اقدام به حل این نوع مسائل، باید بدانید که حافظه پنهان (cache) چیست. LRU یک استراتژی ذخیره‌سازی پنهان رایج است که اصول حذف عناصر را برای ایجاد فضا در هنگام پر شدن حافظه پنهان تعریف می‌کند. این بدان معناست که ابتدا موارد کمتر‌استفاده‌شده را دور می‌اندازد.

مراحل بعدی آماده‌سازی برای مصاحبه

سؤالاتی که در این مقاله به آن‌ها پرداخته شد، تنها تعدادی از سؤالات دشوار برنامه‌نویسی مصاحبه‌ها هستند. این سؤالات دشوار به نظر می‌رسند و حتی می‌توانند با‌تجربه‌ترین توسعه‌دهندگان را نیز دچار مشکل کنند. در ادامه تعدادی از مسائل دشوارتر که در مصاحبه‌های کدنویسی مطرح می‌شوند، آورده شده است:

• پیدا کردن میانه از یک جریان داده
• جستجو در آرایه مرتب‌شده‌ی چرخش‌یافته
• حداقل تعداد حرکات اسب در صفحه شطرنج