سوالات مصاحبه فنی PHP برای استخدام برنامه‌نویسان
PHP Interview Questions
همانطور که می دانید بسیاری از شرکت ها برای استخدام برنامه نویس دست به انجام مصاحبه های فنی می زنند. در این نوع مصاحبه ها به شما چند سوال داده می شود و از شما خواسته می شود که به آن سوال ها پاسخ بدهید. توجه کنید که مصاحبه های فنی از مصاحبه های عادی جدا هستند چرا که مصاحبه های عادی معمولا برای شناخت بهتر شما و رزومه شما انجام می شوند در حالی که مصاحبه های فنی برای تست کردن مهارت شما طراحی شده اند. با اینکه در ایران تمام شرکت ها چنین مصاحبه هایی را انجام نمی دهند اما بهتر است با این دسته از سوالات آشنا شوید تا علاوه بر بالا بردن دانش خود، شانس استخدام خود را نیز ارتقاء دهید.
سطح مقاله: این مقاله جزء مقالات تکمیلی در حوزه مهارت PHP است و برای افرادی طراحی شده است که به طور کامل با زبان PHP آشنا هستند، بنابراین مطالعه آن را برای افراد مبتدی توصیه نمی کنم. همچنین در بخش دوم این مقاله به سراغ سوالات الگوریتمی می رویم بنابراین باید با مفاهیم داده ساختار ها نیز آشنا باشید.
ما در این مقاله از سوالات بسیار ساده مانند تعریف بلوک های PHP شروع کرده و به سوالات پیچیده مانند الگوریتم ها می رسیم. در واقع کل این مقاله به دو بخش تقسیم می شود: سوالات عمومی و سوالات الگوریتمی. سعی کنید بدون نگاه کردن به پاسخ، خودتان به این سوالات پاسخ بدهید و سپس پاسخ خود را با جواب صحیح مقایسه کنید تا فرآیند یادگیری شما بهتر باشد.
۱. اجرای PHP از command line
سوال: چطور می توانیم یک اسکریپت PHP را از command line یا terminal یک سیستم اجرا کنیم؟
پاسخ: PHP command line interface که همان CLI برای زبان PHP است به ما اجازه می دهد در ترمینال دستوری مانند php script.php را اجرا کنیم. با انجام این کار فایل script.php اجرا خواهد شد. برای دسترسی و ورود به shell زبان PHP نیز از دستور php -a استفاده می کنیم.
۲. باز کردن و بستن یک بلوک PHP
سوال: ساده ترین راه های تعریف یک بلوک کد PHP چیست؟
پاسخ: راه استاندارد و کامل به شکل زیر است:
<?php [ --- PHP code---- ] ?>
اما راه خلاصه ای برای کد های کوتاه PHP نیز وجود دارد که به شکل زیر است:
<? [--- PHP code ---] ?>
در نهایت اگر بخواهیم محتوا را مستقیما echo کنیم باید از علامت = استفاده کنیم:
<?= the data to be echoed in browser ?>
۳. ارث بری چندگانه در PHP
سوال: آیا در زبان PHP ارث بری چندگانه یا multiple inheritance ممکن است؟
پاسخ: خیر. زبان PHP فقط از single inheritance پشتیبانی می کند که یعنی هر کلاس فرزند می تواند فقط و فقط یک کلاس پدر داشته باشد.
۴. کلاس و متدهای final
سوال: کلاس ها و متدهایی که با کلیدواژه final مشخص شده اند، چه خاصیتی دارند؟
پاسخ: کلیدواژه final که در نسخه پنجم PHP اضافه شده است به معنی «نهایی» می باشد بنابراین اگر کلاسی final باشد دیگر قابلیت extend شدن ندارد و متدهای final نیز نمی توانند بازنویسی یا ویرایش شوند.
۵. مقایسه اشیاء
سوال: چطور می توانیم در زبان PHP دو شیء را با هم مقایسه کنیم؟
پاسخ: اپراتور == برای مقایسه دو شیء استفاده می شود و دو موضوع را مقایسه می کند: اولا دو شیء از یک کلاس ساخته شده باشند و دوما attribute ها و مقادیر یکسانی داشته باشند. اپراتور === نیز می تواند دو شیء را از نظر یکسان بودن عینی (دو شیء یکی باشند نه اینکه مقدار یکسانی داشته باشند) بررسی کند.
۶. تفاوت include و require
سوال: در صورتی که بخواهیم یک اسکریپت را وارد اسکریپت دیگری کنیم دو دستور include و require به ذهن می رسد. تفاوت این دو چیست؟ نسخه های include_once و require_once چطور؟
پاسخ: اگر عملیات وارد کردن اسکریپت با require انجام شود و فایل مورد نظر پیدا نشود یک fatal error خواهیم داشت و کل برنامه متوقف می شود در صورتی که include تنها یک warning (هشدار) را پرتاب می کند اما اجرای اسکریپت ادامه پیدا می کند. require_once نیز دقیقا مانندrequire است با این تفاوت که قبل از وارد کردن اسکریپت، بررسی می کند که آیا اسکریپت قبلا وارد شده است یا خیر تا دوباره و بی جهت اسکریپت را وارد نکند. این مسئله برای include_once نیز صحیح است.
۷. زمان اجرای بی نهایت
سوال: PHP به صورت پیش فرض محدودیتی را برای زمان اجرای اسکریپت ها در نظر می گیرد. چطور می توان این زمان را نامحدود کنیم؟
پاسخ: برای جلوگیری از بروز خطای maximum execution time exceeded (طولانی شدن اجرای اسکریپت) می توانیم از تابع (0)set_time_limit در ابتدای فایل php استفاده کرده یا این خصوصیت را در php.ini تنظیم کنیم. البته باید در نظر داشت که این کار می تواند سرور ما را به شدت درگیر کند و توصیه نمی شود.
۸. پاس دادن متغیر با ارجاع
سوال: چطور می توانیم در PHP به جای پاس دادن یک متغیر، آن را با ارجاع (by reference) پاس بدهیم؟
پاسخ: برای انجام این کار باید از علامت & در کنار آن استفاده کنید. مثال:
$var1 = &$var2
۹. GLOBALS$ چیست؟
سوال: GLOBALS$ در زبان PHP چیست؟
پاسخ: GLOBALS$ یک آرایه متناظر است که به تمام متغیر های تعریف شده در scope سراسری دسترسی دارد.
۱۰. انواع خطا ها در PHP
سوال: انواع خطا ها در زبان PHP را توضیح بدهید.
پاسخ: سه دسته خطا در زبان PHP وجود دارد. نوع اول notice (ملاحظه) ها هستند که از کمترین اهمیت برخوردار هستند و به ما می گویند که چیزی در هنگام اجرای اسکریپت با خطا روبرو شده است، مثلا متغیری تعریف نشده داشته ایم. نوع دوم warning (هشدار) ها هستند که از اهمیت بیشتری برخوردارند و به ما می گویند که مشکل جدی تری در برنامه داشته ایم (مثلا include فایل مورد نظرش را پیدا نکرده است) اما اجرای اسکریپت متوقف نمی شود. دسته سوم fatal error ها یا خطاهای مهلک هستند که به طور کامل اجرای اسکریپت را متوقف می کنند مانند یک دستور require که نتواند فایل مورد نظرش را پیدا کند.
۱۱. تفاوت بین const و define
سوال: چه تفاوتی بین const و define وجود دارد؟
پاسخ: const و define هر دو یک کار را انجام می دهند و آن هم تعریف ثابت ها است اما const این کار را در هنگام compile time (کامپایل شدن کد قبل از اجرا) و define این کار را در هنگام runtime (اجرا شدن کد) انجام می دهد. همچنین تا نسخه ۵.۳ از زبانPHP استفاده از const در global scope مجاز نبود
۱۲. کلاس stdClass
سوال: در زبان PHP کلاسی به نام stdClass وجود دارد. این کلاس چیست و چه کاری را بر عهده دارد؟
پاسخ: کلاس stdClass یک کلاس عمومی و خالی است که معمولا هنگام تبدیل انواع داده دیگر به اشیاء مورد استفاده قرار می گیرد. باید توجه داشت که stdClass کلاس پایه اشیاء در PHP نیست. ما می توانیم این مسئله را به شکل زیر اثبات کنیم:
class Foo{}
$foo = new Foo();
echo ($foo instanceof stdClass)?'Y':'N'; // outputs 'N'
از stdClass معمولا برای اشیاء ناشناس و خصوصیات پویا و غیره استفاده می شود.
۱۳. تفاوت بین isset و array_key_exists
سوال: با ذکر مثال، تفاوت بین توابع isset و array_key_exists را توضیح بدهید.
پاسخ: تابع array_key_exists وجود یک کلید در یک آرایه را بررسی می کند و اگر خود آرایه وجود نداشته باشد هشدار می دهد. از طرفی isset مسئول بررسی وجود یک کلید یا متغیر است و شرطش این است که null نباشد. اگر خود آرایه وجود نداشته باشد isset هشدار نمی دهد.
$a = array('key1' => 'Foo Bar', 'key2' => null);
isset($a['key1']); // true
array_key_exists('key1', $a); // true
isset($a['key2']); // false
array_key_exists('key2', $a); // true
۱۴. تشخیص آرایه های متناظر
سوال: روشی ارائه کنید که با استفاده از آن بتوان آرایه های متناظر را تشخیص داد.
پاسخ: اگر فقط یکی از کلیدهای آرایه رشته باشد، آرایه ما حتما متناظر است بنابراین:
function has_string_keys(array $array) {
return count(array_filter(array_keys($array), 'is_string')) > 0;
}
۱۵. تفاوت بین error و exception
سوال: چه تفاوتی بین خطا (error) و استثناء (exception) وجود دارد؟
پاسخ: exception ها مربوط به خود برنامه هستند در حالی که خطا ها مربوط به محیطی می باشند که در برنامه در آن اجرا می شود. اگر خطایی به وجود بیاید هیچ راه حلی نداریم و اجرای اسکریپت متوقف می شود اما با استفاده از بلوک های try & catch می توانید exception ها را مدیریت کنید و نیازی به توقف اسکریپت نمی باشد.
۱۶. فراخوانی تابع با ارجاع
سوال: با ذکر مثال، فراخوانی تابع با ارجاع (function call by reference) را توضیح بدهید.
پاسخ: اگر فراخوانی تابعی دارای ارجاع به یک متغیر باشد با تغییر آن متغیر در بدنه تابع، خود متغیر در بیرون تابع نیز تغییر می کند. این کار با علامت & انجام می شود:
function adder(&$str2) {
$str2 .= 'Call By Reference';
}
$str = 'This is ';
adder($str);
echo $str;
در کد بالا یک متغیر سراسری به نام str را داریم که محتوایش به شکل This is می باشد. از طرفی تابع adder یک رشته دیگر به شکل Call by reference را به هر رشته ای که به عنوان آرگومان پاس داده شود اضافه می کند. با اجرای کد بالا نتیجه This is Call By Reference را دریافت می کنیم بنابراین متغیر سراسری str ویرایش شده است.
۱۷. کلاس singleton
سوال: با هر روشی که دوست دارید یک کلاس singleton را تعریف کنید (محتوای کلاس مهم نیست).
پاسخ: معماری singleton یعنی از هر کلاس فقط یک نمونه (instance) ساخته شود بنابراین هر کلاسی که این قاعده را رعایت کند یک کلاس singleton است. مثال:
/**
* Singleton class
*
*/
final class UserFactory {
/**
* Call this method to get singleton
*
* @return UserFactory
*/
public static
function Instance() {
static $inst = null;
if ($inst === null) {
$inst = new UserFactory();
}
return $inst;
}
/**
* Private ctor so nobody else can instantiate it
*
*/
private
function __construct() {
}
}
این کلاس ابتدا بررسی می کند که inst$ در آن null باشد و آنگاه یک نمونه جدید می سازد در غیر این صورت نمونه قبلی ساخته شده را برمی گرداند. با این حساب برای استفاده از آن می گوییم:
$fact = UserFactory::Instance(); $fact2 = UserFactory::Instance();
اما کد زیر به شما خطا می دهد:
$fact = new UserFactory()
۱۸. متدهای کلاس exception
سوال: متدهای مهم کلاس exception در PHP را نام ببرید و به صورت مختصر در مورد هر کدام توضیح بدهید.
پاسخ: کلاس exception همان کلاسی است که وظیفه مدیریت exception ها را بر عهده دارد. متدهای مهم آن نیز به شرح زیر هستند:
- ()getMessage: پیام exception را دریافت می کند.
- ()getCode: کد exception را دریافت می کند.
- ()getFile: نام فایل منبع exception را دریافت می کند.
- ()getLine: خط exception را دریافت می کند.
- ()getTrace: آرایه ()backtrace را دریافت می کند.
- ()getTraceAsString: مانند مورد قبلی است اما آن را به شکل رشته دریافت می کند.
- ()Exception::__toString: کل exception را به صورت رشته دریافت می کند.
۱۸. تفاوت array_map و array_walk و array_filter
سوال: تفاوت بین array_map و array_walk و array_filter را توضیح بدهید.
پاسخ: تابع array_walk یک تابع تعریف شده توسط ما را گرفته و آن را روی تک تک اعضای آرایه اعمال می کند. تابع array_map نیز همین کار را انجام می دهد با این تفاوت که به جای ویرایش آرایه اصلی، یک آرایه جدید را برمی گرداند. تابع array_filter نیز به جای ویرایش عناصر، یک شرط را تعیین می کند و آن شرط را برای تک تک اعضای آرایه بررسی می کند. اگر شرط برای هر عضوی صادق نباشد، آن عضو از آرایه حذف می شود.
۱۹. حل کد stdClass
سوال: به نظر شما با اجرای کد زیر چه نتیجه ای برایمان چاپ می شود؟
$a = new stdClass(); $a->foo = "bar"; $b = clone $a; var_dump($a === $b);
پاسخ: همانطور که توضیح داده بودیم، stdClass یک کلاس خالی است بنابراین می توانیم هر چیزی را درون آن قرار بدهیم. من خصوصیت foo را به آن اضافه کرده ام و مقدارش را bar گذاشته ام. در مرحله سوم آن را clone (کپی) کرده ایم و سپس آن را به کپی خودش مقایسه کرده ایم. نتیجه var_dump به شکل زیر خواهد بود:
bool(false)
چرا؟ به دلیل اینکه دو نمونه از یک کلاس با اپراتور === برابر نیستند و جزئیات متفاوتی دارند.
۲۰. مقایسه رشته ای
سوال: به نظر شما با اجرای کد زیر چه نتیجه ای برگردانده می شود:
$something = 0;
echo ('password123' == $something) ? 'true' : 'false';
پاسخ: هیچ گاه نباید برای مقایسه رشته ها از اپراتور == استفاده کنیم. در کد بالا عدد صفر و رشته password123 مقایسه می شوند و عدد صفر به رشته تبدیل می شود. این رفتار به صورت خودکار اتفاق می افتد.
۲۱. اندازه گیری زمان اجرای اسکریپت
سوال: چطور می توانیم زمان اجرای یک اسکریپت یا قسمتی از کد هایمان در یک اسکریپت را اندازه گیری کنیم؟
پاسخ: راه های مختلفی برای انجام این کار وجود دارد. به طور مثال تابع microtime و تابع hrtime از توابع مشهور برای انجام این کار هستند. وب سایت رسمی PHP پیشنهاد می کند برای اندازه گیری سرعت اسکریپت از hrtime استفاده کنید. یک مثال ساده:
$start = microtime(true);
for ($i = 0; $i < 10000; ++$i) {
// do something
}
$total = microtime(true) - $start;
echo $total;
۲۲. ادغام اشیاء
سوال: چطور می توانیم دو شیء در زبان PHP را در هم ادغام کنیم؟
پاسخ: ساده ترین راه این است که اشیاء را به آرایه تبدیل کنیم، سپس دو آرایه را با متد array_merge در هم ادغام کنیم و در نهایت نتیجه را دوباره به یک شیء تبدیل کنیم:
$obj_merged = (object) array_merge((array) $obj1, (array) $obj2);
۲۳. اپراتور سفینه فضایی
سوال: اپراتور سفینه فضایی (spaceshipt operator) در زبان PHP چه مسئولیتی دارد؟
پاسخ: این اپراتور که به شکل <=> است از نسخه ۷ زبان PHP ارائه شد. این اپراتور بین دو مقدار مقایسه انجام می دهد به طوری که:
- اگر هر دو مقدار یکسان باشند عدد 0 برگردانده می شود.
- اگر مقدار سمت چپ اپراتور بزرگتر باشد عدد 1 برگردانده می شود.
- اگر مقدار سمت راست اپراتور بزرگتر باشد عدد 1- برگردانده می شود.
به مثال زیر توجه کنید:
//Comparing Integers echo 1 <=> 1; //output 0 echo 3 <=> 4; //output -1 echo 4 <=> 3; //output 1 //String Comparison echo "x" <=> "x"; //output 0 echo "x" <=> "y"; //output -1 echo "y" <=> "x"; //output 1
۲۴. closure ها
سوال: closure در زبان PHP چیست؟ چه هنگامی از کلمه use در آن ها استفاده می کنیم؟
پاسخ: closure به زبان ساده توابعی هستند که بدون نیاز به نام گذاری ساخته می شوند. مثل زیر استفاده از یک closure را در تابع array_walk نمایش می دهد:
<?php
$array = array('Ruby', 'PHP', 'JavaScript', 'HTML');
array_walk($array, function(&$v, $k) {
$v = $v . ' - Programming Language';
});
print_r($array);
البته پیچیده ترین حالت استفاده از closure ها مربوط به زمانی است که closure ها می توانند از متغیر های scope پدرشان استفاده کنند. برای این کار باید از دستور use استفاده کنید که ساختار زیر را دارد:
function() use ($variable) { /* code */ }
به طور مثال:
<?php
$param = 'John!';
function sayHello()
{
$param = 'Michael!';
$func = function() use ($param)
{
echo 'Hi, I am ' . $param;
};
$func();
}
sayHello();
با اجرای این کد نتیجه I am Michael را دریافت می کنید. چرا؟ به دلیل اینکه closure بالا از scope پدرش استفاده می کند که همان تابع sayHello می باشد و با scope سراسری کاری ندارد.
چند سوال الگوریتمی
از این بخش مقاله به بعد وارد حل الگوریتم و سوالات پیچیده تر می شویم. از آنجایی که سوالات این بخش معمولا پیچیده است، پس از بیان هر سوال بخشی خواهم نوشت که خودش سه قسمت Input و Output و Why را خواهد داشت. بخش Input مثالی از داده های ورودی به کدی است که شما باید بنویسید و بخش Output نتیجه خروجی از کد های نوشته شده توسط شما است. نهایتا بخش why نیز دلیل و رابطه بخش Input و Output را توضیح می دهد. من این موضوع را در سوال اول توضیح خواهم داد اما از آن به بعد خودتان باید بدانید که سوالات الگوریتم چطور کار می کنند.
همچنین در نظر داشته باشید که روش های مختلفی برای حل سوالات الگوریتمی وجود دارد و هر سوال شاید ده راه حل مختلف داشته باشد. تا زمانی که کد شما output (جواب) صحیح را پاس می دهد یعنی روش شما نیز درست است و لزومی ندارد حتما با روش من مطابقت داشته باشد.
۲۵. الگوریتم: مشکل two sum
سوال: با فرض وجود آرایه ای از اعداد صحیح به نام nums و عدد صحیحی به نام target، ایندکس های دو عدد را به نحوی برگردانید که مجموعشان برابر با target باشد. شما نمی توانید از یک عنصر دو بار استفاده کنید اما ترتیب برگرداندن عناصر اهمیتی ندارد. به طور مثال:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Why: nums[0] + nums[1] == 9
بخش Input به ما یک داده مثالی را به عنوان ورودی می دهد. توجه داشته باشید که این فقط یک داده مثالی است و کد هایتان باید با داده های دیگر نیز کار کنند. target (هدف) ما عدد ۹ است. بخش Output ایندکس های صفر و یک را نشان می دهد. چرا؟ توضیح این مسئله را در بخش why می بینیم: به دلیل اینکه جمع اعضایی با ایندکس صفر و ایندکس یک از آرایه nums برابر هدف (عدد ۹) می باشد.
برای شروع از کد زیر استفاده کنید:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
}
}
پاسخ: برای حل این سوال ابتدا باید صورت سوال را به دقت بخوانید و قسمت توضیحات سوال را نیز مطالعه کنید تا دقیقا متوجه آن بشوید. سوالات الگوریتمی به دلیل پیچیدگی شان نیاز به تمرکز بالا روی صورت سوال دارند. در مرحله اول باید هر عضو را از target کم کنیم و نتیجه را با اعداد دیگر موجود در nums مقایسه کنیم تا مشخص شود کدام دو عدد با هم target را می سازند. با این حساب به یک شیء یا آرایه دیگر نیاز داریم تا ایندکس ها را نیز در نظر بگیریم. من ابتدا کد آماده را برایتان قرار می دهم و سپس آن را خط به خط تحلیل می کنیم:
<?php
class Solution
{
function twoSum($nums, $target)
{
$map = [];
for ($i = 0; $i < count($nums); $i++) {
$map[$nums[$i]] = $i;
}
for ($i = 0; $i < count($nums); $i++) {
$complement = $target - $nums[$i];
if (array_key_exists($complement, $map) && $map[$complement] != $i) {
return [$i, $map[$complement]];
}
}
throw new Error("No two sum solution");
}
}
$sol = new Solution();
print_r($sol->twoSum([2, 7, 11, 15], 9));
من در ابتدا یک آرایه به نام map را تعریف کرده ام. ما با استفاده از یک حلقه for روی آرایه nums گردش کرده و آن را به صورت برعکس شده درون map گذاشته ایم. منظورم از برعکس شده این است که جای ایندکس ها و مقادیر در map برعکس و بدین شکل است:
Array ( [2] => 0 [7] => 1 [11] => 2 [15] => 3 )
در مرحله بعدی یک حلقه دیگر داریم که کار اصلی را انجام می دهد. در این حلقه متغیری به نام complement وجود دارد. complement به معنی متمم یا تمام کننده است. یعنی چه؟ یعنی اگر عدد اول در nums را از target کم کنیم (در دور اول حلقه، ۹ منهای ۲) عدد متمم را می گیریم (۷). این عدد اگر با عدد اول جمع بشود حاصل target خواهد شد. با این حساب ابتدا complement را حساب کرده ایم، سپس با تابع array_key_exists بررسی می کنیم تا این complement درون کلید های map (آرایه وارونه شده nums) وجود داشته باشد. مثلا اگر ۹ را منهای ۱۱ (عدد سوم nums) کنیم، نتیجه عددی منفی می شود و طبیعتا عدد منفی در ایندکس نداریم بنابراین حتما باید وجود complement درون آرایه map را بررسی کنیم. شرط مهم دیگر این است که مقدار متناظر با complement از آرایه map (یا ایندکس nums) برابر با نوبت گردش فعلی در آرایه (i$) نباشد. اگر این شرط ها برقرار بود یعنی به نتیجه رسیده ایم بنابراین آرایه نهایی را برمی گردانیم. در غیر این صورت نیز یک خطا پرتاب کرده ایم که جمع هیچ کدام از این اعداد برابر با target نمی شود.
با اجرای کد بالا نتیجه زیر را می گیریم:
Array ( [0] => 0 [1] => 1 )
بنابراین اعداد 0 و 1 برایمان برگردانده شده اند که پاسخ صحیح است.
همانطور که گفتم روش های مختلفی برای حل سوالات الگوریتمی وجود دارد. برای نشان دادن این موضوع به شما این سوال را با روش دیگری نیز حل می کنیم. فرض کنید این کار را بدون کلاس ها و فقط در یک تابع انجام بدهیم:
<?php
function twoSum(array $nums, int $target): array
{
foreach ($nums as $key => $val) {
$nextKey = array_search(($target - $val), $nums);
if ($nextKey) {
return [$key, $nextKey];
}
}
return [];
}
print_r(twoSum([7, 2, 11, 15], 9));
همانطور که می بینید این روش بسیار خلاصه تر است. در ابتدا با استفاده از حلقه foreach روی آرایه nums گردش کرده ایم. در مرحله بعدی تابع array_search را داریم؛ این تابع به دنبال یک مقدار خاص در یک آرایه می گردد و اگر آن را پیدا کند، ایندکس آن مقدار را برمی گرداند و اگر چیزی پیدا نکند false را برمی گرداند. با این حساب من complement را به عنوان آرگومان اول پاس داده ام. در گردش اول target منهای value می شود ۹ منهای ۷ که عدد ۲ را به ما می دهد. حالا array_search بررسی می کند که آیا مقدار ۲ درون آرایه nums وجود دارد؟ پاسخ مثبت است بنابراین ایندکس آن را به ما برمی گرداند که همان 1 می باشد. حالا می گوییم اگر این ایندکس پیدا شده است و false نیست باید این دو کلید (کلید فعلی در گردش و کلید بعدی) را پیدا کنیم. نتیجه این کد باز هم مانند قبل است:
Array ( [0] => 0 [1] => 1 )
بنابراین راه حل ها زیاد و متعدد هستند. مهم این است که به راه حل اصلی برسید.
۲۶. الگوریتم: مشکل Add Two Numbers
سوال: فرض کنید دو لیست پیوندی (linked list) در قالب دو عدد به شما داده شده است و اعداد آن منفی نبوده اما برعکس چیده شده اند. دو عدد را جمع زده و به عنوان لیست پیوندی برگردانید. فرض مسئله این است که هیچ کدام از اعداد به غیر از عدد صفر با 0 شروع نمی شود.
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Why: 342 + 465 = 807
همانطور که می بینید ما l1 یا list 1 و l2 یا list 2 را داریم و هر دو نیز یک آرایه هستند (لیست های پیوندی را شبیه سازی کرده ایم). زمانی که این دو را به کد های شما بدهیم باید آرایه [7,0,8] برایمان برگردانده شود. چرا؟ ما گفتیم ترتیب عداد برعکس است بنابراین آرایه [2,4,3] به جای عدد ۲۴۳ برابر با عدد ۳۴۲ خواهد بود (حالت برعکس). این کار را برای آرایه دیگر نیز انجام داده و اعداد را جمع می زنیم. نهایتا عدد ۸۰۷ را به دست می آوریم و زمانی که آن را برعکس کنیم عدد ۷۰۸ به دست می آید.
در صورتی که ساختار لینک های پیوندی را یادتان رفته است، به ساختار زیر نگاهی بیندازید:
// تعریف لیست های پیوندی
class ListNode
{
public $val = 0;
public $next = null;
function __construct($val = 0, $next = null)
{
$this->val = $val;
$this->next = $next;
}
}
پاسخ: شاید در نگاه اول پاسخ دادن به این سوال ساده به نظر برسد اما اگر با داده ساختار لیست های پیوندی آشنا نباشید این سوال بسیار سخت خواهد بود. در ابتدا مثل همیشه صورت سوال را چند بار بخوانید تا متوجه شوید که دقیقا چه چیزی از شما خواسته شده است. در صورت سوال گفته شده است که هیچ کدام از لیست های پیوندی ما خالی نیستند. یعنی چه؟ ما قرار است دو عدد را جمع بزنیم X + Y = Z بنابراین خالی نبودن آن ها یعنی X و Y هر دو وجود دارند و ممکن نیست وجود نداشته باشند.
نکته بعدی در مورد برعکس بودن ترتیب ارقام است. شاید فکر کنید این موضوع برای ما مشکل است اما اتفاقا کار ما را راحت می کند چرا که جمع زدن اعداد از یکان (سمت راست) شروع می شود و سپس به دهگان و صدگان می رسد. همه ما این موضوع را در دبستان یاد گرفتیم. همچنین ما مثال بالا را دیدیم که در آن هر دو عدد سه رقمی بودند اما شاید یکی از اعداد ما چهار رقمی یا بیشتر باشد. آنگاه چطور؟ شاید یکی از اعداد دو رقمی باشد! آنگاه چطور؟ بیایید مثال زیر را در نظر بگیریم:
5 6 4 2 4 3 3
حالا که می دانیم اعداد برعکس شده اند، مطمئن هستیم که ۵ در عدد اول و ۲ در عدد دوم یکان محسوب می شوند بنابراین انجام این عملیات بسیار ساده است:
5 6 4 2 4 3 3 ---------------------------------- 7 0 8 3
در این بخش به یاد داشته باشید که جمع 6 و 4 برابر با 10 است بنابراین صفر را گذشته ایم و دهگان (۱) را به بخش بعدی برده ایم تا با 4 و 3 جمع شود. در انگلیسی به دهگان منتقل شده carry می گوییم. با توضیحاتی که دادم بهتر است شروع به کدنویسی کنیم:
<?php
// تعریف لیست های پیوندی
class ListNode
{
public $val = 0;
public $next = null;
function __construct($val)
{
$this->val = $val;
}
}
class Solution
{
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
}
}
از آنجایی که سوال به ما می گوید هیچ کدام از اعداد نمی توانند خالی باشند و همچنین می خواهیم کارمان را ساده تر و راحت تر کنیم، من مقدار اولیه هر node را با صفر شروع کرده ام (این کار را در تعریف ListNode انجام داده ایم). در مرحله بعدی در کلاس Solution یک متد به نام addTwoNumbers را داریم. dummy یک node اولیه است که از کلاس ListNode ساخته شده است و می خواهیم کارمان را با آن شروع کنیم. curr$ نیز مخفف current (به معنی «فعلی») است و همان pointer یا نشانگر ما است که به dummy اشاره می کند. چرا dummy؟ ما در ابتدا می خواهیم اعداد جدید را به این لیست پیوندی اضافه کنیم.
در مرحله بعدی باید بین این node ها گردش کنیم تا زمانی که یکی از آن ها null شود یا به زبان ساده تر دیگر عددی نداشته باشد:
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
while ($l1 != null || $l2 != null) {
}
}
ما می دانیم که یکی از آن ها در یکی از گردش های این حلقه null می شود بنابراین باید اعدادشان را در هر گردش از آن ها بگیریم. من از d1 (مخفف digit 1 یا عدد ۱) برای اعداد l1 (لیست پیوندی اول) و از d2 برای اعداد l2 استفاده می کنم:
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
while ($l1 != null || $l2 != null) {
$d1 = ($l1 != null) ? $l1->val : 0;
$d2 = ($l2 != null) ? $l2->val : 0;
}
}
من در این کد گفته ام اگر l1 برابر با null نباشد، مقدار d1 برابر ست با l1->value یا همان مقدار l1 در آن لحظه و در غیر این صورت مقدار d1 برابر است با صفر! چرا صفر؟ به دلیل اینکه گفتیم Node ها نمی توانند خالی باشند. آیا حالا می توانیم این دو را جمع بزنیم؟ خیر! اگر یادتان باشد ممکن است یک carry داشته باشیم، یعنی جمع دو عدد ۱۰ یا بیشتر بشود بنابراین مجبور شویم دهگان را به اعداد بعدی منتقل کنیم. برای اینکه بتوانیم carry را زیر نظر داشته باشیم باید آن را در قالب یک متغیر تعریف کنیم:
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
$carry = 0;
while ($l1 != null || $l2 != null) {
$d1 = ($l1 != null) ? $l1->val : 0;
$d2 = ($l2 != null) ? $l2->val : 0;
}
}
طبیعتا در ابتدا carry صفر است چرا که هنوز عملیات جمع را شروع نکرده ایم. حالا می توانیم دو عدد را با هم جمع کنیم:
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
$carry = 0;
while ($l1 != null || $l2 != null) {
$d1 = ($l1 != null) ? $l1->val : 0;
$d2 = ($l2 != null) ? $l2->val : 0;
$sum = $d1 + $d2 + $carry;
}
}
یادتان باشد که d1 و d2 دو رقم از کل اعداد لیست پیوندی هستند یا به زبان فنی تر d1 و d2 مقادیر هر node هستند بنابراین برای جمع زدن آن ها می توانیم به سادگی carry را نیز اضافه کنیم. مثال قبلی ما را یادتان است؟
5 6 4 2 4 3 3 ---------------------------------- 7 0 8 3
در این حالت اعداد ۵ و ۶ و ۴ در هر گردش یک d1 و اعداد ۲ و ۴ و ۳ و ۳ نیز در هر گردش یک d2 محسوب می شوند. به همین خاطر است که carry را مستقیما به آن اضافه کرده ایم اما الان کد ما مشکلی دارد. اگر مقدار sum$ بیشتر از ۱۰ بشود و خودش یک carry دیگر بسازد چطور؟ برای حل این مشکل باید carry را از آن خارج کنیم. چطور؟ راه های مختلفی برای جدا کردن دهگان از یک عدد وجود دارد. در زبان PHP می توانیم به سادگی از تابع intval استفاده کنیم که مقدار غیر اعشاری را برایمان برمی گرداند:
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
$carry = 0;
while ($l1 != null || $l2 != null) {
$d1 = ($l1 != null) ? $l1->val : 0;
$d2 = ($l2 != null) ? $l2->val : 0;
$sum = $d1 + $d2 + $carry;
$carry = intval($sum / 10);
}
}
حالا مقدار carry را در متغیر carry داریم. اگر sum بزرگتر از ۱۰ باشد carry برابر با دهگان خواهد بود و اگر کوچکتر از ۱۰ باشد دهگانی وجود ندارد بنابراین carry برابر 0 می شود که صحیح است. در مرحله بعدی باید carry را از sum جدا کنیم تا عدد یکان را داشته باشیم. مثلا با اضافه کردن ۴ و ۶ عدد ۱۰ را می گیریم اما می دانیم که در عملیات جمع نمی توانیم ۱۰ را مستقیما بنویسیم بلکه 0 را می گذاریم و ۱ را به اعداد بعد منتقل می کنیم. در حال حاضر ما آن 0 یا یکانِ sum را می خواهیم تا با آن یک node جدید بسازیم:
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
$carry = 0;
while ($l1 != null || $l2 != null) {
$d1 = ($l1 != null) ? $l1->val : 0;
$d2 = ($l2 != null) ? $l2->val : 0;
$sum = $d1 + $d2 + $carry;
$carry = intval($sum / 10);
$curr->next = new ListNode($sum % 10);
}
}
همانطور که می دانید اپراتور % باقی مانده تقسیم بر ۱۰ را برمی گرداند که همان یکان ما می شود. curr->next به node بعدی اشاره می کند و این طرز ساخت یک node در لیست های پیوندی است که باید از قبل با آن آشنا باشید. پس از انجام این کار باید pointer یا همان نشانگر خودمان (متغیر current) را به روز رسانی کنیم تا به node جدید اشاره کند:
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
$carry = 0;
while ($l1 != null || $l2 != null) {
// دریافت یک رقم از لیست های پیوندی
$d1 = ($l1 != null) ? $l1->val : 0;
$d2 = ($l2 != null) ? $l2->val : 0;
// محاسبه عدد جدید
$sum = $d1 + $d2 + $carry;
$carry = intval($sum / 10);
$curr->next = new ListNode($sum % 10);
// به روز رسانی نشانگرها در لیست های پیوندی
$curr = $curr->next;
if ($l1 != null) $l1 = $l1->next;
if ($l2 != null) $l2 = $l2->next;
}
}
حالا که نشانگرهایمان به روز رسانی شدند، این حلقه یک بار دیگر برای node های بعدی نیز تکرار می شود تا زمانی که l1 یا l2 به null برسد (دیگر node نداشته باشند). شاید بگویید کارمان تمام شده است و حالا باید dummy.next را برگردانیم اما هنوز مشکلی وجود دارد. اگر دو عدد آخر ۸ و ۷ بودند و نتیجه بیشتر از ۱۰ شد چطور؟ آنگاه یک carry خواهیم داشت که در آخر محاسبه نشده است! برای حل این مشکل آخرین carry را نیز به عنوان یک node جدید به لیست هایمان اضافه می کنیم:
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
$carry = 0;
while ($l1 != null || $l2 != null) {
// دریافت یک رقم از لیست های پیوندی
$d1 = ($l1 != null) ? $l1->val : 0;
$d2 = ($l2 != null) ? $l2->val : 0;
// محاسبه عدد جدید
$sum = $d1 + $d2 + $carry;
$carry = intval($sum / 10);
$curr->next = new ListNode($sum % 10);
// به روز رسانی نشانگرها در لیست های پیوندی
$curr = $curr->next;
if ($l1 != null) $l1 = $l1->next;
if ($l2 != null) $l2 = $l2->next;
}
if ($carry > 0) {
$curr->next = new ListNode($carry);
}
return $dummy->next;
}
من یک شرط نهایی را به متدمان اضافه کرده ام که اگر carry از صفر بزرگ تر بود باید آن را به صورت یک node جداگانه اضافه کرده و سپس dummy->next را اضافه کرده ایم. البته در نظر داشته باشید که ما می توانیم به جای اضافه کردن یک شرط جداگانه در انتهای این متد، این شرط را در همان while نیز مشخص کنیم:
class Solution
{
function addTwoNumbers($l1, $l2)
{
$dummy = new ListNode(0);
$curr = $dummy;
$carry = 0;
while ($l1 != null || $l2 != null || $carry) {
// دریافت یک رقم از لیست های پیوندی
$d1 = ($l1 != null) ? $l1->val : 0;
$d2 = ($l2 != null) ? $l2->val : 0;
// محاسبه عدد جدید
$sum = $d1 + $d2 + $carry;
$carry = intval($sum / 10);
$curr->next = new ListNode($sum % 10);
// به روز رسانی نشانگرها در لیست های پیوندی
$curr = $curr->next;
if ($l1 != null) $l1 = $l1->next;
if ($l2 != null) $l2 = $l2->next;
}
return $dummy->next;
}
}
هر دو کد نتیجه مورد نظر را به شما می دهند.
۲۷. الگوریتم: مشکل Palindrome Number
سوال: فرض کنید عددی به نام X داشته باشیم. متدی بنویسید تا اگر X پالیندروم (palindrome) بود مقدار true و در غیر این صورت false را برگرداند. پالیندروم یا «قرینه خوان» یا «وارونه خوان» به اعدادی گفته می شود که خواندن آن ها از هر دو طرف یکسان است (به طور مثال ۱۲۱ از هر دو طرف ۱۲۱ است اما اگر ۱۲۳ را برعکس بخوانید به عدد ۳۲۱ می رسید بنابراین پالیندروم نیست).
Input: x = 121 Output: true Why: از هر دو طرف یکی است Input: x = -121 Output: false Why: -121 != 121-
یک قدم فراتر: در صورتی که حل سوال برایتان آسان است، سعی کنید بدون تبدیل کردن عدد به رشته به آن پاسخ بدهید.
پاسخ: سطح این سوال آسان است بنابراین با کمی فکر کردن باید بتوانید خودتان به آن پاسخ بدهید. مثال اول که واضح است اما در مثال دوم باید توجه کنید که ۱۲۱- (منفی ۱۲۱) با -۱۲۱ یکی نیست چرا که دومی (-۱۲۱) اصلا عدد نیست و در ریاضی چنین چیزی نداریم. بلکه به عنوان یک قانون کلی می توان گفت که هیچ عدد صحیح منفی پالیندروم نیست. چرا؟ به دلیل اینکه برعکس شده آن مانند مثال ۱۲۱- تبدیل به یک عدد غلط می شود. برای حل این مسئله روش های متعددی وجود دارد. در بخش «یک قدم فراتر» توضیح داده شده است که سعی کنید این کار را بدون تبدیل به رشته انجام بدهید. من ابتدا آن را با تبدیل به رشته انجام داده و سپس بدون تبدیل به رشته انجام می دهم.
قدم اول این است که اعداد منفی را بدون هیچ محاسبه ای برگردانیم:
class Solution
{
function isPalindrome($x)
{
if ($x < 0) return false;
}
}
چرا چنین کاری را کرده ایم؟ به دلیل اینکه اعداد منفی هیچ گاه نمی توانند پالیندروم باشند (بالاتر توضیح دادیم). از این بخش به بعد کارمان بسیار ساده خواهد بود چرا که زبان PHP توابع آماده بسیار زیادی را دارد بنابراین می گوییم:
class Solution
{
function isPalindrome($x)
{
if ($x < 0) return false;
$array_form = str_split((string) $x);
$reversed_array = array_reverse($array_form);
$reversed_number = (int) implode($reversed_array);
return $x === $reversed_number;
}
}
من ابتدا عدد دریافت شده (x$) را به یک رشته تبدیل کرده ام. به این کار type casting یا type juggling گفته می شود. سپس آن را به تابع str_split داده ام. این تابع یک رشته را گرفته و آن را به صورت یک آرایه برمی گرداند. ما این آرایه را در array_form ذخیره کرده ایم. در مرحله بعدی آرایه array_reverse را صدا زده ایم که کارش برعکس کردن ترتیب اعضای یک آرایه است و array_form را به آن پاس داده ایم. با این کار آرایه برعکس شده را در reversed_array خواهیم داشت. در مرحله بعدی از تابع implode استفاده کرده ایم که یک آرایه را به یک رشته تبدیل می کند و سپس دوباره با type juggling آن رشته را به عدد (int) تبدیل کرده ایم تا reversed_number یا عدد برعکس شده را به دست بیاوریم. در نهایت عدد اولیه (x$) را به این عدد برعکس شده مقایسه کرده و نتیجه اش را return کرده ایم. به همین سادگی سوال را حل کرده ایم!
از آنجایی که حل سوال بدین شکل (تبدیل به رشته) بسیار آسان است، بیایید یک بار بدون کمک گرفتن از رشته ها آن را حل کنیم تا چالش برانگیز تر شود. حتما همه شما نیز با من موافق هستید که برای تعیین پالیندروم بودن یک عدد باید آن را به نوعی برعکس کنیم بنابراین بیایید تلاشمان را روی برعکس کردن اعداد بگذریم (بدون استفاده از رشته ها). من راه حل را یک بار از طریق فرمول آن به طور تئوری توضیح می دهم و سپس شروع به کدنویسی می کنیم.
فرض کنید عدد ۴۹ را داشته باشیم و حالا بخواهیم آن را برعکس کنیم. ما برای چنین حالتی دو ستون را در ذهنمان فرض می کنیم که یکی عدد برعکس شده و دیگری عدد فعلی است. ما همیشه عدد برعکس شده را با 0 شروع می کنیم:
Reversed current 0 49
اولین قدم این است که آخرین عدد (۹) باید تبدیل به اولین عدد شود. برای این کار می توان ۴۹ را بر ۱۰ تقسیم کرد و باقی مانده آن تقسیم را به دست آورد که همان عدد ۹ می باشد. در مرحله بعدی عدد 0 از ستون reversed (برعکس شده) را گرفته و در ۱۰ ضرب می کنیم که باز همان 0 می شود. در مرحله بعدی نتیجه این ضرب (0) و باقی مانده تقسیم (۹) را با هم جمع می کنیم. این فرآیند، اولین رقم برعکس شده را به ما می دهد:
Reversed current 0 49 9
حالا که از ۹ استفاده کرده ایم باید آن را از ستون current حذف کنیم. چطور؟ ۴۹ را بر ۱۰ تقسیم می کنیم و نتیجه (۴.۹) را به پایین گِرد می کنیم که به ما ۴ را می دهد:
Reversed current 0 49 9 4
این فرمول کلی برای برعکس کردن اعداد است. حالا باید به سراغ عدد ۴ برویم و آن را در ستون reversed قرار بدهیم بنابراین همین فرمول را دوباره تکرار می کنیم. باقی مانده تقسیم ۴ بر ۱۰ برابر است با ۴. در مرحله بعدی ۹ را در ۱۰ ضرب می کنیم که ۹۰ را به ما می دهد. نهایتا ۹۰ را با ۴ (باقی مانده تقسیم) جمع می زنیم تا ۹۴ به دست بیاید. با اینکه به عدد برعکس شده رسیده ایم اما هنوز کارمان تمام نشده است و باید فرمول را کامل کنیم. مرحله آخر تقسیم ۴ بر ۱۰ (نتیجه: ۰.۴) و گِرد کردن آن به پایین است که برابر با 0 می شود:
Reversed current 0 49 9 4 94 0
زمانی که به 0 در ستون current برسیم مطمئن می شویم که فرآیند تمام شده است.
اگر بخواهیم همین توضیحات را در قالب کد انجام بدهیم، به چنین نتیجه ای می رسیم:
class Solution
{
function isPalindrome($x)
{
if ($x < 0) return false;
$original_number = $x;
$reversed_number = 0;
while ($x > 0) {
$reversed_number = ($reversed_number * 10) + ($x % 10);
$x = floor($x / 10);
}
return $original_number == $reversed_number;
}
}
همانطور که می بینید من در ابتدا مقدار پاس داده شده به تابع (x$) را در متغیری به نام original_number ذخیره کرده ام. در مرحله بعدی متغیری به نام reversed_number را داریم که همان عدد برعکس شده می باشد اما برایتان توضیح دادم که همیشه با 0 شروع می کنیم بنابراین مقدارش را در ابتدا روی 0 گذاشته ام. حالا یک حلقه while را ایجاد کرده ایم؛ درون این حلقه همان فرمولی که گفتم را پیاده سازی کرده ام. یعنی رقم اول را در ۱۰ ضرب کرده و آن را با باقی مانده تقسیم عدد اصلی بر ۱۰ جمع می کنیم، سپس x$ را نیز بر ۱۰ تقسیم کرده و آن را به پایین گِرد کرده ایم. این اتفاق تا زمانی می افتد که x برابر صفر شود (شرط حلقه). نهایتا عدد اصلی و عدد برعکس شده را مقایسه می کنیم.
همانطور که گفتم راه های مختلفی برای حل یک سوال وجود دارد. مثلا می توانستیم از حلقه for نیز استفاده کنیم که روش پیشرفته تری است:
class Solution
{
function isPalindrome($x)
{
if ($x < 0) return false;
$i = 0;
$reversed = 0;
$original = $x;
for ($i = 10; $x > 0; $x = intval($x / 10)) {
$reversed *= 10;
$reversed += $x % $i;
}
return $reversed == $original;
}
}
این دقیقا همان مراحلی است که قبلا توضیح دادم با این تفاوت که ساختار حلقه و دستورات استفاده شده کمی متفاوت است.
امیدوارم از نمونه مصاحبه PHP و سوالات استخدام برنامه نویس PHP با پاسخ های مطرح شده استفاده کرده باشید. سوالات مربوط به الگوریتم بسیار زیاد هستند و نمی توانیم تمام آن ها را در این مقاله بررسی کنیم اما سعی کرده ایم با این چند بررسی، نحوه کلی حل آن ها را به شما نشان بدهم.
در این قسمت، به پرسش‌های تخصصی شما درباره‌ی محتوای مقاله پاسخ داده نمی‌شود. سوالات خود را اینجا بپرسید.