سوالاتی که از من در مصاحبه‌های توسعه‌دهنده Frontend پرسیده شد (بخش ۲)

سلام، امیدوارم که خوب باشید و ایام به کام باشه. اگرم نیست، به کامش کنید :)
بریم سراغ بخش دوم سوالات مصاحبه (بخش اول رو از این لینک میتونید مطالعه کنید).
این بخش ترکیبی از سوالات عملی و live code جاوااسکریپت و الگوریتم و حل مسئله هست.
سوال اول تا نهم به این صورت بود که از من خواسته شد توی یک ادیتور آنلاین مشخص شده (که قابلیت اجرا نداشت) کد ها رو بنویسم. همزمان لازم بود که بلند بلند فکر کنم تا مصاحبه کننده در جریان مسیر فکریم قرار بگیره. همزمان راهنمایی هم میکردن و یا نظرشون رو میگفتن یا سوال میپرسیدن باز :) پس اینکه کدها بدون خطا باشه خیلی مهم نبود، بیشتر راه حلی که مطرح میکردی مهم بود.
سوال ۱۰ مربوط به یک مصاحبه دیگه هست که الگوریتم و ساختمان داده مد نظر بوده و کد رو باید تو یک ادیتور آنلاین که قابلیت اجرا داره پیاده میکردم.
دو سوال آخر هم، حل مسئله هستن و صرفا راه حل شفاهی رو میخواستن.

خب، بریم سراغ سوالات:

۱- تابعی بنویس که با گرفتن دو تا دنباله در ورودی، تشخیص بده که دنباله دوم، آیا زیردنباله ای از دنباله اول هست یا نه؟ خروجی باید به صورت true یا false باشه.
به طور مثال دنباله های زیر رو داریم:

// inputs
[8, 4 , 9 , 1 , 18 , 23]
[9, 18, 23]

// output
true

// inputs
[8, 4 , 1 , 18 , 23]
[9, 18, 23]

// output
false

پاسخ:
(پاسخ من به این سوال، کد زیر بوده. شاید راه بهتری هم براش موجود باشه)

function findSub(arr1, arr2) {
    let i=0
    let j=0
    while(i< arr1.length && j< arr2.length) {
        const el1 = arr1[i]
        const el2 = arr2[j]

        if(el1 === el2) {
            j++
            i++
        } else {
            i++
        }
    }

    return j === arr2.length
}

۲- تابعی بنویس که با گرفتن یک رشته، پرتکرار ترین توکن رو برگردونه.
ورودی و خروجی این تابع باید به این صورت باشه:

// input
'book in book of library in book'

// output
book

پاسخ:
(پاسخ من به این سوال، کد زیر بوده. شاید راه بهتری هم براش موجود باشه)

function find(str) {
    const words = str.split(' ')
    const obj = {}
    words.map((item) => {        
        if(obj[item]) { 
            obj[item] = obj[item] + 1 
        } else {
            obj[item] = 1
        }
    })

    const myarr = Object.values(obj)
    const maxIndex = findMax(myarr)
    const properties = Object.keys(obj)

    return properties[maxIndex]
}

function findMax(arr) {
    let maxIndex  = 0
    let max = 0

    arr.map((item, index) => {
        if(item > max) {
            maxIndex = index
            max = item
        }
    })

    return maxIndex 
}

۳- تفاوت دو متد زیر چیه؟ و خروجی هر کدوم چیه؟

[1, 5 , 7 , 10].map(_=>_%2 == 0)
[1, 5, 7, 10, 12].filter((_) => _ % 2 == 0)

پاسخ: خروجی به صورت زیر هست:

[ false, false, false, true ]
[ 10, 12 ]

۴- این سوال در ادامه سوال قبل هست و از من خواستن که متد map آرایه ها رو بازنویسی کنم.
پاسخ:

Array.prototype.map2 = function(callback) {
  const arr = []

  for (let i = 0; i < this.length; i++) {
    arr.push(callback(this[i], i))
  }
  return arr
}

نکته۱: چون map آرایه اصلی (در اینجا this) رو تغییر نمیده، پس ما هم نباید آرایه اصلی رو تغییر بدیم و باید از آرایه جدید (arr) استفاده کنیم.
نکته۲: برای نوشتن این متد باید از normal function استفاده کنیم و اگر از arrow function استفاده کنیم، متدمون درست کار نمیکنه. چون this توی arrow function ها از اسکوپی که توش تعریف شدن، ارث برده میشه و به instance آرایه مون اشاره نمیکنه. در حالی که this توی normal function همون آبجکتی هست که داره اون متد رو کال میکنه، در نتیجه به instance آرایه دسترسی داریم. اگر کامل متوجه نشدید، تفاوت this توی normal function و arrow function رو بخونید (توی سری اول سوالات بهش پرداختیم).

۵- سوال بعدی به این صورت بود که گفتن بین این دو تا console.log زیر، کدی بنویس که باعث بشه console.log دوم دو ثانیه بعد از اولی چاپ بشه.

console.log('A')
...
console.log('B')

پاسخ:
با ترکیب setTimeout و Promise میتونیم این کار رو انجام بدیم.
توی سری سوالات قبلی(اینجا، سوال ۱۶)، به این مسئله اشاره شد که await به تنهایی روی setTimeout تاثیری نداره، چرا که setTimeout, پرامیسی برنمیگردونه. پس خودمون باید یه پرامیس بنویسیم (تابع f1)
از اونجایی که await فقط توی یک تابع async قابل استفاده هست، پس کل تابع f1 رو توی یک تابع async دیگه به اسم testFunc کال میکنیم.

const testFunc = async () => {
  console.log('A')
  const f1 = async () => {
      return new Promise(resolve => {
          setTimeout(() => {
              resolve(1)
          }, 2000)
      })  
  }
  await f1()
  console.log('B')
}
testFunc()

۶- خروجی هر یک از توابع a, b و c چیست؟

function a(){
  function x(){
    var num = 10;
  }
  x();
  console.log(num)
}
a();

function b(){
  function x(){
    let num = 10;
  }
  x();
  console.log(num)
}
b();

function c(){
  function x(){
     num = 10;
  }
  x();
  console.log(num)
}
c();

پاسخ:
خروجی تابع a
ReferenceError: num is not defined
هست. چون متغیر num با var تعریف شده و var هم function scope هست، پس num فقط توی a قابل دسترسیه و خارج اون ناشناخته است.

خروجی تابع b هم
ReferenceError: num is not defined
هست. به همون دلیل مشابه. چون block scope ,let هست، پس num خارج تابع b قابل دسترسی نیست.

خروجی تابع c اما ۱۰ هست. چون متغیر num با let, var یا const تعریف نشده پس تبدیل به متغیر global میشه و همه جا هم قابل دسترسیه.

۷- کد تابع generateNumber رو بنویس به نحوی که خروجی اون به صورت زیر باشه (هر بار که تابع رو کال میکنیم، خروجی یک واحد افزایش پیدا میکنه):

generateNumber() //1
generateNumber() //2
generateNumber() //3

پاسخ:
تو این سوال به صورت غیرمستقیم از شما درباره closure ها پرسش شده و تابع generateNumber یک نمونه از کاربردهای closure هست.

const gn = () => {
    let count = 1
    return () => count++
}

const generateNumber = gn()

console.log(generateNumber())
console.log(generateNumber())
console.log(generateNumber()) 

۸- فرض کنید apiای داریم که هر بار که کال میشه، یک url رو برمیگردونه. بدین صورت:

const url = 'https://xyz.com/getNextUrl'
const res =  Get(url)

بار اول این api رو کال میکنیم و res رو میگیریم. سپس Get(res.data) رو کال میکنیم و res2 رو میگیریم و سپس Get(res2.data) رو کال میکنیم و res3 رو میگیریم. این فرآیند رو یک بار با استفاده از async/await و یک بار با استفاده از promise ها بنویس.
پاسخ:
روش اول، با استفاده از async/await:

async function fetchUrls() {
  try {
    const url = 'https://xyz.com/getNextUrl';
    const res = await Get(url);
    const res2 = await Get(res.data);
    const res3 = await Get(res2.data);
  } catch (error) {
    console.error(error);
  }
}

روش دوم، با استفاده از promiseها:

function fetchUrls() {
  const url = 'https://xyz.com/getNextUrl';
  Get(url)
    .then((res) =>
      Get(res.data)
        .then((res2) =>
          Get(res2.data)
            .then((res3) => console.log(res3))
            .catch((err3) => console.log(err3)),
        )
        .catch((err2) => console.log(err2)),
    )
    .catch((err) => console.log(err));
}

۹- سوال بعدی در ادامه سوال قبل هست. توی روش های بالا به صورت سریال ریکوئست ها رو ارسال کردیم. حالا اگه بخوایم به صورت موازی ریکوئست ها رو ارسال کنیم، چیکار باید کرد؟
نکته: ماهیت داده ها تو سوال بالا جوریه که کلا سریال هست و موازی نمیشه هندلش کرد، چون حتما باید ریسپانس ریکوئست قبل بیاد و ما url جدید رو دریافت کنیم تا بتونیم ریکوئست بعدی رو بزنیم. منظور سوال، اینه که به صورت کلی چه طور میشه promise ها رو موازی هندل کرد (نه فقط توی این مورد خاص)
پاسخ:
از متدهای Promise.all یا Promise.allSettled میتونیم برای ارسال موازی چند promise استفاده کنیم. تفاوت این دو متد در این هست که توی Promise.all اگه فقط یکی از پرامیسهای پاس داده شده با خطا مواجه بشه، خروجی پرامیس نهایی rejected خواهد بود اما Promise.allSettled, آرایهای از پرامیسها رو به عنوان ورودی میگیره و زمانی fulfilled میشه که همهٔ پرامیسها Settle بشن. منظور از Settle شدن یعنی کار پرامیس تموم بشه (فارغ از اینکه نتیجه پرامیس چی باشه. یعنی fulfilled یا rejected اهمیتی نداره.) [ref]

const res =  Get(url)
const res2 =  Get(res.data)
const res3 =  Get(res2.data)

const myRes = Promise.allSettled([res, res2, res3])

۱۰- لیستی از اعداد داریم و میخوایم همه دو تا اعدادی که مجموعشون برابر k میشن رو پیدا کنیم(بدون استفاده از حافظه کمکی). چه راه حلی رو پیشنهاد میکنی برای حل این مسئله؟ پیچیدگی زمانی و مکانی اش رو هم تحلیل کن.
پاسخ:
بخش اول سوال توضیح راه حل پیشنهادی به صورت شفاهی هست. خب چون گفته شده که از حافظه کمکی نمیشه استفاده کرد، این یعنی از objectها یا hash map مجاز نیستیم استفاده کنیم.
راه حل پیشنهادی من این بود که در مرحله اول، اعداد رو مرتب کنیم (با مرتبه زمانی O(nlogn)). یه توضیح مختصر هم دادم درباره اینکه الگوریتم های مرتب سازی بهینه از این مرتبه زمانی هستند(مثل merge sort و quick sort و ...) بعد از مرتب کردن آرایه، میتونیم با استفاده از binary search که از مرتبه زمانی O(logn) هست، مسئله رو حل کنیم. یک بار یک لوپ روی کل آرایه بزنیم (از مرتبه زمانی O(n))، توی هر تکرار هم با استفاده از باینری سرچ، چک کنیم که آیا مکمل این عدد، توی آرایه (از آیتم فعلی به بعد) وجود داره یا نه. این خودش از مرتبه O(nlogn) میشه. در مجموع یه O(nlogn) برای مرتب سازی و یه O(nlogn) هم برای سرچ داشتیم، پس پیچیدگی زمانی نهایی همون O(nlogn) هست. پیچیدگی مکانی هم O(1) هست.
بعد از این مرحله که توضیح راه حل بود، مصاحبه کننده خواست که الگوریتم binary search رو پیاده سازی کنم. این کد رو توی یک ادیتور که قابلیت اجرا داشت باید مینوشتم و خروجی چک میشد که درست هست یا نه.

این لینک همه راه حل های موجود برای این سوال رو از ساده ترین تا بهینه ترین رو توضیح داده. البته سوالش یه کوچولو متفاوته و خواسته شده که true یا false برگردونده شه (اگر دو تا آیتمی مجموعشون k شد -> true، یا اگه هیچ دو آیتمی مجموعشون k نشد -> false). ولی راه حل همونه. کد باینری سرچ هم به زبان های مختلف از جمله جاوااسکریپت رو داره.

دو سوال بعدی فقط حل مسئله هست و به پیاده سازی نیاز نداشت.

۱۱- یک لیست پیوندی یک طرفه داریم و ده عنصر آخر لیست رو میخواهیم. از چه الگوریتم یا ساختمان داده ای برای حل این مسئله استفاده میکنی؟
پاسخ:
یک راه حل ساده برای این سوال میتونه این باشه که یک queue با اندازه ۱۰ رو در نظر بگیریم و یک بار لوپ بزنیم روی لیست پیوندیمون و هر بار آیتم جدید رو پوش کنیم به queue. وقتی ظرفیت queue پر بشه، قدیمی ترین آیتم، پاپ میشه. در نتیجه همیشه ۱۰ تا عنصر آخر رو توی queue داریم. پیچیدگی مکانی این راه حل از مرتبه (10)θ هست. اما با θ(1) هم میتونیم این مسئله رو حل کنیم:
راه دیگه اینه که میتونیم فقط یک عنصر رو در یک متغیر نگه داریم. چرا که از هر عنصر، میتونیم ده تای بعدیش رو پیدا کنیم. پس باید فقط عنصر ده تا مونده به آخر رو توی یک متغیر نگه داریم. در نتیجه یک لوپ روی لیست پیوندیمون میزنیم. توی ده تکرار اول، همه عناصر، جزو ده تای آخر هستند. به عنصر ۱۱ از لیست پیوندی که رسیدیم، عنصر اول رو در متغیر نگه داری میکنیم. به عنصر ۱۲ که رسیدیم، اگه عنصر آخر لیست پیوندی نبود، پس عنصر دوم رو توی متغیرمون نگه داری میکنیم و تکرارهای بعدی هم به همین ترتیب تا برسیم به عنصر آخر لیست. وقتی لوپ تموم بشه، عنصر ده تا مونده به آخر رو توی متغیرمون داریم.

۱۲- از اعداد ۱ تا n رو داریم. میخوایم چک کنیم که عدد تکراری توی این ها نباشه(یا به عبارت دیگه n تا عدد داریم و میخوایم چک کنیم که عدد تکراری توشون نباشه و همه incremental باشن ). چه راه حلی رو پیشنهاد میکنی؟
پاسخ:
راه اول: چون اعداد incremental هستن، پس جمعشون باید برابر n(n+1)/2باشه. اگه عدد تکراری توی این ها باشه، دیگه جمعشون برابر n(n+1)/2نمیشه.
راه دوم: از یک آبجکت استفاده میکنیم و یک لوپ روی اعداد میزنیم. تو هر تکرار اگر آیتم توی آبجکت نبود(پراپرتی برای اون عدد ست نشده بود)، obj[n] رو برابر ۱ یا مقدار دیگه قرار میدیم. اما اگر توش بود، پس یعنی عنصر تکراری داریم.
راه سوم: استفاده از Set هست. چون آیتم تکراری به Set نمیشه پوش کرد، پس اگر اعداد رو ریختیم توی Set و طولش همون n بود پس یعنی عدد تکراری توش نبوده. در غیر اینصورت آیتم تکراری داشتیم.

خب، این سری سوالات هم تموم شد. توی سری بعدی، انشالله میریم سراغ سوالات react :)

منابع:

https://ditty.ir/posts/promise-static-methods/5kP7n#promise-all
https://www.geeksforgeeks.org/check-if-pair-with-given-sum-exists-in-array/