مهم‌ترین سوالات مصاحبه برنامه نویسی اندروید

سید ایوب کوکبی دوشنبه ۹ اردیبهشت ۱۳۹۸
مهم‌ترین سوالات مصاحبه برنامه نویسی اندروید

یکی از مهم‌ترین مراحل هر مصاحبۀ شغلی، سوالات تخصصی آن است. آقای Amit Shekhar تعدادی از مهم‌ترین سوالاتی مصاحبه برنامه نویسی اندروید که طی سال‌ها تجربه گردآوری شده را به همراه پاسخ کوتاه در گیت‌هاب منتشر کرده‌اند که ما بخشی از آن را در اینجا ترجمه کرده‌ایم.

الگوریتم و ساختمان داده

سطح سوالات این بخش معمولاً به شرکتی که برای آن اپلای کرده‌اید برمی‌گردد. مثلاً شرکتی که محصولاتش مبتنی بر هوش مصنوعی و بینایی ماشینی است قطعاً سوالات الگورتیمی پربارتری خواهد داشت و شرکتی که در حیطۀ ذخیرۀ داده‌ها فعالیت می‌کند، بیشتر به الگوریتم‌های ذخیره‌سازی و پردازش داده اهمیت می‌دهد. حتی سطح کاری و سابقۀ فعالیت شرکت‌ها نیز در این امر دخیل هستند.

آرایه (Array)

آرایه، گروهی از داده‌های هم نوع است که به شکل خانه‌هایی پشت‌سرهم در حافظه ذخیره شده و با ایندکس هر خانه می‌توان به دادۀ ذخیره شده در آن خانه دسترسی داشت. آرایه‌ها می‌توانند یک بعدی یا چند بعدی باشند. آرایۀ یک بعدی ساده‌ترین و البته رایج‌ترین ساختار داده‌ای است. در زبان جاوا آرایۀ چند بعدی به آرایه‌ای از آرایه‌ها گفته می‌شود؛ یعنی آرایه‌ای که هر یک از خانه‌های آن حاوی یک آرایۀ دیگر است. مثلاً [۵][۱۰]int یعنی ابتدا اندیس ۱۰ را پیدا کن، داخل آن یک آرایه هست، حالا داده‌ای که در اندیس ۵ آن وجود دارد را به من بده.

لیست پیوندی(Linked List)

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

لیست پیوندی دو طرفه (Doubly Linked List)

لیست پیوندی دو طرفه یا لیست دو پیوندی بر مبنای لیست پیوندی معمولی است با این تفاوت که به جای یک اشاره‌گر دارای دو اشاره‌گر در هر نود است. یک اشاره‌گر به نود قبلی و یک اشاره‌گر به نود بعدی. اینجا نیزگره head و tail داریم. اشاره‌گر بعدی در گرۀ head به اولین گره در لیست پیوندی اشاره دارد و در گرۀ پایانی به null. البته اگر اشارۀ گر بعدی در گرۀ آخر به اولین گره اشاره کند به چنین ساختاری، لیست دوپیوندی حلقوی گفته می‌شود. لیست‌های پیوندی دو طرفه، ساختار داده‌ای رایجی برای پیمایش دو طرفه بین داده‌هاست.

پشته (Stack)

پشته یک ساختمان دادۀ LIFO یا Last In First out است؛ یعنی آخرین آیتمی که وارد پشته می‌شود، اولین آیتمی است که از آن خارج می‌شود. پشته دقیقاً مثل قرار دادن بشقاب‌ها روی هم است. آخرین بشقابی که بالاتر گذاشته‌اید، اولی بشقابی است که بر میدارید. اضافه کردن یک عنصر به پشته push و برداشتن یک عنصر از آن pop گفته می‌شود. همچنین به برداشتن آخرین عنصر پشته بدون حذف آن top گفته می‌شود. رایج‌ترین روش پیاده‌سازی پشته، استفاده از لیست پیوندی است. آرایه و وکتور هم از دیگر روش‌های پیاده‌سازی پشته هستند که هر کدام مزایا و معایب خاص خود را دارند.

صف (Queue)

صف یک ساختمان دادۀ FIFO یا First In First Out است؛ یعنی اولین دادۀ ورودی، اولین دادۀ خروجی است؛ مثل یک صف نانوایی. آدم‌ها به ته صف اضافه می‌شوند و از سر صف خارج می‌شوند. بنابراین آخرین کسی که وارد صف شده، آخرین کسی است که نان را دریافت می‌کند و اولین کسی که وارد صف شده، نخستین فردی است که نان می‌گیرد. در واقع ورودی و خروجی از هم متمایز هستند.

صف اولویت‌دار (Priority Queue)

صف معمولی مبتنی بر روش فیفو است یعنی همۀ اعضای صف به ترتیب ورود در صف قرار می‌گیرند؛ بنابراین اولین ورودی، اولین خروجی است. اما در صف اولویت‌دار، هر داده اولویتی دارد؛ البته این اولویت منحصر به فرد نیست. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی پیدا می‌کند. سیستم‌عامل نیز برای مدیریت پردازش‌ها به وفور از صف‌های اولویت‌دار استفاده می‌کند.

درخت دودویی (Binary Tree)

درخت باینری یا دودویی ساختمان داده‌ای است که هر گره در آن حداکثر دو گره فرزند دارد که فرزند راست و چپ نامیده می‌شوند. در این درخت، درجۀ هر گره حداکثر می‌تواند ۲ باشد. از درخت‌های دودویی برای پیاده‌سازی درخت جستجوی دودویی و انبوه دودویی و همچنین برای جستجوی کارآمد و مرتب‌سازی داده‌ها استفاده می‌شود.

بخوانید  آموزش زبان کاتلین – درس 19 (Getter و Setter)

درخت جستجوی دودویی (Binary Search Tree)

درخت جستجوی دودویی یا به اختصار BST نوع خاصی درخت دودویی است که درخت دودویی مرتب هم نامیده می‌شود.

جدول هش (Hash Table) یا نقشۀ هش (Hash Map)

جدول هش یا جدول درهم‌سازی، نوعی ساختمان داده است که مقادیر ذخیره شده در آن توسط یک تابع درهم‌ساز با کلیدهای ویژه‌ای مرتبط می‌شود تا کاربر بتواند با سرعت بالایی دادۀ مورد نظرش را بیابد. در این ساختمان داده، اضافه کردن دادۀ جدید نیز با سرعت بالایی صورت می‌گیرد.

الگوریتم‌های مرتب‌سازی

استفاده از الگوریتم‌های کارآمد برای مرتب‌سازی داده‌ها و انتخاب ساختمان دادۀ مناسب جهت پیاده‌سازی این الگوریتم‌ها در هر برنامه‌ای ضروری است چرا که یکی از موضوعات مهم در بحث پرفرمنس همین الگوریتم‌های مرتب‌سازی هستند. کارایی یک الگوریتم در علوم کامپیوتر با Big O سنجیده می‌شود. بهترین الگوریتم‌ها معمولاً عملیات اصلی را با پیچیدگی (O(n log n یا حتی (O(log n انجام می‌دهند. حتی بعضی از الکوریتم‌ها عملیات خاصی را با (O(1 انجام می‌دهند (به عنوان مثال عمل درج در HashTable). خوشبختانه O بزرگ بسیاری از الگوریتم‌ها در اینترنت موجود است و نیازی به مصاحبۀ مجدد نیست.

مرتب‌سازی حبابی (Bubble Sort)

مرتب‌سازی حبابی یکی از ساده‌ترین و البته ناکارآمدترین الگوریتم‌های مرتب‌سازی است. در این الگوریتم فهرست ورودی پشت سر هم پیمایش می‌شود تا هر بار عناصر کنار هم را با هم مقایسه و در صورت نیاز در جایگاه درست خود قرار گیرند. این کار تا جایی ادامه پیدا می‌کند که هیچ جابه‌جایی دیگری در فهرست رخ ندهد. در این روش، با اولین گذر اطمینان حاصل می‌شود که حداقل یک عنصر در جایگاه درست خود قرار گرفته است. مرتب‌سازی حبابی در لیست‌های به شدت نامرتب کارایی خوبی ندارد طوری که پیچیدگی زمانی آن به (O(n^2 هم خواهد رسید. اما یکی از مزیت‎های این الگوریتم پیچیدگی فضایی خوبی آن است چون هر بار فقط دو عنصر با هم مقایسه می‌شوند؛ بنابراین نیازی به حافظۀ زیاد برای اجرای الگوریتم ندارد.

مرتب‌سازی انتخابی (Selection Sort)

مرتب‌سازی انتخابی، یکی دیگر از الگوریتم‌های ساده و ناکارآمد مرتب‌سازی داده‌هاست. در این الگوریتم ابتدا کوچکترین عدد با اولین عدد جا به جا می‌شود. سپس دومین عدد کوچک‌تر با عنصر دوم جا‌به‌جا می‌شود. این کار مادامی که لیست اعداد به پایان نرسیده باشد ادامه می‌یابد. در واقع هر بار لیستی از اعداد مرتب شده داریم که عدد جدید را در جایگاه مناسب آن لیست قرار می‌دهیم. در شرایطی که اعداد خیلی به هم ریخته و نامرتب باشند و نیاز به مرتب‌سازی زیادی باشد، تعداد مقایسه‌ها و جابه‌جایی‌ها بالا رفته و کارآمدی این روش را به (O(n^2 می‌رساند که مطلوب نیست.

مرتب‌سازی ادغامی (Merge Sort)

پیچدگی زمانی این روش n log n است و نسبتاً روش پایداری محسوب می‌شود. در مرتب‌سازی ادغامی لیست بزرگ اعداد به صورت بازگشتی به لیست‌های کوچکتری شکسته شده، سپس هر لیست به صورت مجزا مرتب‌سازی می‌شود. سپس این لیست‌ها مجددا با سایر لیست‌ها ادغام می‌شود تا به لیست مرتب نهایی برسیم. این روش سرعت مرتب‌سازی را بالا می‌برد ولی پیچیدگی فضایی را افزایش خواهد داد. البته با حجم ذخیره‌سازی امروز چندان جای نگرانی نیست.

مرتب‌سازی سریع (Quick Sort)

مرتب‌سازی سریع، یکی از بهینه‌ترین و سریع‌ترین الگوریتم‌های مرتب‌سازی‌ است که در صورت پیاده‌سازی درست، عملکرد بسیار خوبی خواهد داشت. این الگوریتم نیز همانند روش ادغامی در دسته‌بندی الگوریتم‌های «تفرقه و حکومت» قرار می‌گیرد. در مرتب‌سازی سریع ابتدا یک عنصر محوری انتخاب و سپس عناصر بزرگتر و کوچکتر از آن در دو آرایۀ چپ و راست تقسیم می‌شوند. به لحاظ آماری، انتخاب تصادفی عنصر محوری باعث می‌شود تا الگوریتم به سمت پیچیدگی زمانی بدترین حالت کشیده نشود. سپس همین کار برای آرایه‌های چپ و راست به صورت بازگشتی تکرار شده تا به آرایۀ مرتب نهایی برسیم. پیچیدگی زمانی این الگوریتم در صورت پیاده‌سازی درست در حالت میانگین n log n و در بدترین حالت n^2 است. ولی پیچیدگی فضایی آن در بدترین شرایط ممکن (O(1 خواهد بود.

الگوریتم‌های مرتب‌سازی فراوان دیگری هم وجود دارند که اینجا فرصت بیان همۀ آن‌ها نیست. توصیه می‌کنیم هرچه بیشتر ذهن خود را با این الگوریتم‌ها آشنا کنید تا بفهمید در پسِ آن‌ها چه روش‌ها و استراتژی‌هایی نهفته است. در یک مصاحبۀ برنامه نویسی، هر چه بیشتر با الگوریتم‌ها آشنا باشید ذهن بازتری برای پاسخ به سوالات خواهید داشت و مصاحبه‌گر نیز به دانش الگوریتمی بالای شما بهای بیشتری می‌دهد.

بخوانید  آشنایی با الگوهای طراحی Observer در اندروید

برای تکمیل این بخش چند مورد دیگر را هم فهرست وار بیان می‌کنیم تا در فرصت لازم دربارۀ آن‌ها تحقیق کنید:

هستۀ اصلی جاوا

شی‌گرایی (OOP)

مفهوم شی‌گرایی را توضیح دهید
شی گرایی (OOP سرنام Object-Oriented Programming) یک متدولوژی محبوب جهت ساخت برنامه با استفاده از کلاس‌ها، اشیاء، ارث‌بری، پلی‌مورفیسیم (چند ریختی)، کپسوله‌سازی و انتزاع (abstraction) است.

تفاوت بین کلاس‌های abstract و اینترفیس چیست؟

  • کلاس abstract هم حاوی متدهای واقعی و هم امضای متدها (یعنی بدون پیاده‌سازی) است. متد abstract باید توسط یک زیرکلاس abstrct پیاده‌سازی شود. کلاس abstract را نمی‌توان نمونه‌سازی کرد یا به عبارتی نمی‌توان از روی آن شی‌ای ساخت. برای استفاده از این کلاس فقط باید extend کرد؛
  • اینترفیس مثل یک قرارداد عمل می‌کند. هر کلاسی که این قرارداد را پیاده‌سازی کند زبان مشترک هم را خواهند فهمید. هر اینترفیس فقط امضای متدها (نام متد، پارامترها و نوع بازگشتی) را تعریف می‌کند و کاری به پیاده‌سازی آن ندارد. هر زیرکلاس با توجه به ماهیت خود می‌تواند پیاده‌سازی لازم برای آن متد را ارائه دهد. اینترفیس در بحث الگوهای طراحی کاربردهای فراوانی دارد.

فرق بین method overloading و overriding چیست؟

  • Method Overloading قابلیتی است که در زمان کامپایل اتفاق می‌افتد. در این روش می‌توان چندین متد هم‌نام ولی با پارامترها متفاوت (چه در نام، چه در تعداد) و در برخی از زبان‌ها حتی متفاوت در نوع بازگشتی متد، تعریف کرد. اما Override قابلیتی است که در زمان اجرا اتفاق می‌افتد و کارش این است که یک کلاس فرزند می‌تواند یکی از متدهای کلاس والد را پیاده‌سازی مجدد کند تا در زمان اجرا به جای پیاده‌سازی پدر، پیاده‌سازی فرزند به کار گرفته شود؛
  • متدهای استاتیک می‌توانند overload شوند ولی نمی‌توانند override شوند. حتی اگر متد استاتیک یکسانی در کلاس فرزند تعریف کنید هیچ کاری انجام نمی‌دهد چون مرجع انتخاب متد استاتیک، کلاس رفرنس است نه آبجکت ساخته شده از آن کلاس. مثلاً به این کد نگاه کنید:
public class Animal {
    public static void testClassMethod() {
        System.out.println("The static method in Animal");
    }

    public void testInstanceMethod() {
        System.out.println("The instance method in Animal");
    }
}

public class Cat extends Animal {
    public static void testClassMethod() {
        System.out.println("The static method in Cat");
    }

    public void testInstanceMethod() {
        System.out.println("The instance method in Cat");
    }

    public static void main(String[] args) {
        Cat myCat = new Cat();
        myCat.testClassMethod();
        Animal myAnimal = myCat;
        myAnimal.testClassMethod();
        myAnimal.testInstanceMethod();
    }
}
Will output:

The static method in Cat    // testClassMethod() is called from "Cat" reference

The static method in Animal // testClassMethod() is called from "Animal" reference,
                            // ignoring actual object inside it (Cat)

The instance method in Cat  // testInstanceMethod() is called from "Animal" reference,
                            // but from "Cat" object underneath

اولین تفاوت اینجاست که overloading در یک کلاس انجام می‌شود ولی برای override به دو کلاس پدر و فرزند نیاز داریم. Overriding دربارۀ پیاده‌سازی خاص یکی از متدهای پدر در کلاس فرزند صحبت می‌کند. فرق بعدی این دو سرعت اجرای آن‌هاست. overload در زمان کامپایل اتفاق می‌افتد ولی override در زمان اجرا، بنابراین در overriding رانتایم برنامه کند می‌شود.

متدهای private و final می‌توانند overload شوند ولی قابلیت override شدن ندارند. این یعنی یک کلاس می‌تواند بیش از یک متد private/final با نام یکسان داشته باشد ولی کلاس فرزند حق override کردن آن متدها را ندارد.

نوع برگشتی متد در عملیات overloading زبان جاوا تفاوتی در آن‌ها ایجاد نمی‌کند یعنی نمی‌توان صِرف تغییر نوع بازگشتی متد، نسخۀ جدیدی از آن متد ایجاد کرد. حتماً باید در پارامترها تغییراتی ایجاد کنید. اما در بحث overriding، کلاس فرزند می‌تواند نوع برگشتی متد override شده را تغییر دهد مادامی که در سلسلۀ ارث‌بری آن قرار داشته باشد. مثلاً اگر متد override در کلاس والد نوع برگشتی Number داشته باشد، کلاس فرزند می‌تواند در نسخۀ override شده، هر نوع برگشتی دیگری که کلاس Number را اکستند کرده انتخاب کند ولی نه بالاتر از آن. مثلاً از Object که در سلسلۀ ارث‌بری بالاتر از Number قرار می‌گیرد نمی‌توانیم استفاده کنیم.

بخوانید  ساخت اپلیکیشن با بودجه محدود

آرگومان‌ها در هنگام اورلود کردن متدها باید متفاوت باشند ولی هنگام اوراید کردن باید یکسان باشند. همچنین تمرین خوبی است که هنگام اوراید کردن متدها از انوتیشن Override@ استفاده کنید تا کامپایلر بتواند به شما اطلاع دهد که آیا متد فرزند متد والد را اوراید کرده است یا نه.

فرق بین iterator و enumerator در جاوا چیست؟

تفاوت بین access modifier ها چیست؟ در زبان جاوا ۴ نوع اکسس مودیفایر هست (به ترتیب از محدودترین به عمومی‌ترین):

  • خصوصی (private): متغیرها، متدها، سازنده‌ها یا کلاس‌های داخلی فقط برای کلاسی که در آن تعریف شده‌اند و متدهای داخل آن کلاس قابل رؤیت هستند. این مودیفایر بیشترین استفاده را در زبان جاوا دارد. در واقع این مودیفایر روش خوبی برای پیاده‌سازی مفهوم کپسوله‌سازی است؛ یعنی کاری کنیم که پیاده‌سازی داخلی یک کلاس را از دید مصرف کننده‌ها مخفی کنیم. مکانیزم دسترسی به متغیرهای یک کلاس از طریق getter و setter چیزی است که با کمک این مودیفایر امکان‌پذیر است. یا مثال دیگر، متد سازنده در سینگلتون با این مودیفایر علامت‌گذاری شده تا اشتباهاً از نمونه‌سازی سهوی جلوگیری شود؛
  • محافظت شده (protected): این مودیفایر را می‌توان برای متغیرها، متدها، سازنده‌ها به کار برد معنی‌اش این است که فقط زیرکلاس‌ها و کلاس‌های داخل یک پکیج اجازۀ دسترسی به اعضای protected را می‌دهد؛
  • پیش‌فرض (default): کلیدواژه‌ای برای این حالت وجود ندارد. هر وقت هیچ مودیفایری استفاده نمی‌کنید ، دیفالت در نظر گرفته خواهد شد. معنی‌اش این است که به کلاس‌ها و متدهای داخل یک پکیج اجازۀ دسترسی به اعضای دیفالت را خواهد داد؛
  • عمومی (public): این مودیفایر به صورت گسترده‌ای برای کلاس‌ها، متغیرها، سازنده‌ها و متدها استفاده می‌شود تا از داخل هر کلاس و متدی به آن‌ها دسترسی داشته باشیم. هیچ وقت برای سهولت کار خود همه جا از این مودیفایر استفاده نکنید چون اصل کپسوله‌سازی را با مشکل مواجه خواهید کرد و بعدها مدیریت کد برای خودِ شما هم سخت می‌شود. از مودیفایر public دقیقاً زمانی استفاده کنید که این دسترسی گسترده واقعاً ضروری است.

آیا یک اینترفیس می‌تواند اینترفیس دیگری را پیاده‌سازی کند؟
بله نه‌تنها یک بلکه هر تعداد اینترفیس دیگر را می‌تواند پیاده‌سازی کند ولی به جای extend حتماً باید از implement استفاده کند.

پلی‌مورفیسم یا چندریختی (Polymorphism) چیست؟ و همچنین ارث‌بری؟

  • چندریختی در جاوا دو نوع است: چند ریختی زمان کامپایل (static binding) و چند ریختی زمان اجرا (dynamic binding). متد اورلودینگ نمونه‌ای از چندریختی استاتیک و متد اورایدینگ مثالی از چندریختی داینامیک است. مثال مهم دیگر، چگونگی ارجاع کلاس والد به کلاس فرزند است. در حقیقت، هر آبجکتی که بیشتر از یک رابطۀ IS-A روی آن صدق کند ماهیتی چندریختی دارد. مثلاً کلاس Animal را فرض کنید. Cat یک زیرکلاس از Animal است. بنابراین همۀ کلاس‌های Cat ضمن اینکه Cat هستند یک کلاس Animal هم هستند.
  • ارث‌بری به فرایند دریافت خصوصیت‌ها (متدها و فیلدها) از یک نفر دیگر گفته می‌شود. مثلاً هر دو کلاس Cat و Lion خصوصیات مشترک کلاس Animal را به ارث می‌برند. به کلاسی که از آن ارث می‌بریم کلاس مبنا، کلاس والد و گاهی کلاس پدر یا کلاس مادر گفته می‌شود و به کلاسی که مشتق شده کلاس فرزند، کلاس مشتق شده یا derived class گفته می‌شود. در ارث‌بری یا inheritance از کلیدواژۀ extends استفاده می‌شود که بارها در کدهای جاوا دیده‌اید:
class Super {
   .....
   .....
}
class Sub extends Super {
   .....
   .....
}

ارث‌بری چندگانه در کلاس‌ها و اینترفیس‌های جاوا چیست؟

الگوی طراحی چیست؟
الگوهای طراحی راهکارهای همه‌پسندی برای مشکلات رایج نرم‌افزاری هستند. این الگوها در دسته‌بندی‌های تکوینی (Creational)، ساختاری (Structural) و رفتاری (Behavioral) طبقه‌بندی می‌شوند. در دسته‌بندی تکوینی الگوی Builder, Factory, Singleton, Monostate Fluent Interface Pattern مهم‌تر هستند. در ساختاری‌ها Adapter, Decorator و Facade و نهایتاً الگوهای مهم رفتاری شامل زنجیرۀ مسئولیت‌ها، iterator و الگوی استراتژی است. مثلاً الگوی سینگلتون، راهکار خوبی برای جلوگیری از ساخت چندین نمونه از یک کلاس است. مثلاً زمانی که بخواهیم کاربر فقط یک نسخه از برنامه را اجرا کند از این الگو استفاده می‌کنیم.

کالکشن و جنریک‌ها

فرق بین Arrays و ArrayLists
فرق بین Hashset و TreeSet
تفاوت بین HashMap و Set
تفاوت بین Stack و Queue

بقیه سوالات را می‌توانید در صفحۀ گیت‌هاب مطالعه کنید.

دیدگاه شما :

بدون دیدگاه

    هنوز دیدگاهی ارسال نشده است.

عضویت در خبرنامه

عضویت در خبرنامه برای عضویت در خبرنامه پیامکی، عدد 1 را به شماره 30005563 پیامک کنید.