بررسی پرسش ها و پاسخ های مصاحبه شغلی برای یک موقعیت توسعه دهنده جاوا. قسمت 9

برنامه نویس بودن کار آسانی نیست. همیشه چیز جدیدی برای یادگیری وجود دارد. و مانند هر تلاش دیگری، دشوارترین کار شروع کردن است، برداشتن اولین قدم به سوی هدفتان. اما از آنجایی که قبلاً اینجا هستید و این مقاله را می خوانید، مرحله اول را تکمیل کرده اید. این بدان معنی است که اکنون باید عمداً به سمت هدف خود حرکت کنید، بدون اینکه سرعت خود را کاهش دهید یا به طرفین منحرف شوید. من فرض می کنم هدف شما این است که یک توسعه دهنده جاوا شوید یا اگر قبلاً یک توسعه دهنده هستید، دانش خود را تقویت کنید. اگر چنین است، بیایید به بررسی لیست گسترده ای از سوالات مصاحبه توسعه دهندگان جاوا ادامه دهیم. بیا ادامه بدهیم!

مجموعه ها

84. در مورد تکرار کننده ها و نحوه استفاده از آنها بگویید

مجموعه ها یک موضوع مورد علاقه در هر مصاحبه توسعه دهنده جاوا است. هنگام پاسخ به سؤالات مربوط به سلسله مراتب مجموعه، نامزدها اغلب می گویند که با رابط مجموعه شروع می شود . اما این طوری نیست. رابط دیگری در یک سطح بالاتر وجود دارد: تکرارپذیر . این رابط از متد iterator() تشکیل شده است که به شما امکان می دهد به شی Iterator برای مجموعه فعلی دسترسی داشته باشید. و این شی Iterator دقیقا چیست ؟ شی Iterator توانایی حرکت در یک مجموعه و تکرار بر روی عناصر آن را فراهم می کند و کاربر نیازی به دانستن جزئیات پیاده سازی خاص مجموعه ندارد. به عبارت دیگر، نوعی اشاره به عناصر مجموعه است، گویی در درون یکی از آنها را زیر نظر می گیرد. تکرار کننده روش هایی مانند:

• hasNext() - اگر تکرار عنصر دیگری داشته باشد، true را برمی‌گرداند (این روش به شما امکان می‌دهد بدانید چه زمانی به پایان مجموعه رسیدید).

• next() - مورد بعدی را در تکرار برمی گرداند. اگر یکی نباشد، یک NoSuchElementException پرتاب می شود. این بدان معناست که قبل از استفاده از این روش، بهتر است از متد hasNext() استفاده کنید تا مطمئن شوید عنصر بعدی وجود دارد.

• remove() — آخرین عنصر دریافتی را با استفاده از متد next() از مجموعه حذف می کند . اگر next() هرگز فراخوانی نشده باشد، فراخوانی remove() باعث می شود که یک IllegalStateException پرتاب شود.

• forEachRemaining(<Consumer>) - عمل تصویب شده را روی هر عنصر مجموعه اجرا می کند (این روش در جاوا 8 ظاهر شد).

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

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

کنسول موارد زیر را نمایش می دهد: این بدان معنی است که عناصر با موفقیت حذف شدند. هنگامی که یک تکرار کننده دریافت کردید، می توانید از روشی برای نمایش تمام عناصر روی صفحه استفاده کنید:

iterator.forEachRemaining(x -> System.out.print(x));

اما وقتی این کار را انجام دهیم، تکرار کننده برای استفاده بیشتر نامناسب می شود: کل لیست را طی کرده است، و یک تکرار کننده معمولی هیچ روشی برای تکرار به عقب ندارد. و این باعث می شود که بحث خوبی در بحث LinkedList ایجاد شود، به ویژه، متد listIterator() آن ، که نوع پیشرفته ای از تکرارکننده را برمی گرداند: ListIterator . این نوع علاوه بر روش های تکرار کننده معمولی (استاندارد) دارای موارد زیر است:

• add(<Element>) - یک عنصر جدید به لیست اضافه می کند.

• hasPrevious() - اگر عنصری قبل از عنصر بعدی باشد (اگر عنصر قبلی وجود داشته باشد) true را برمی گرداند.

• nextIndex() - شاخص عنصر بعدی را برمی گرداند.

• previous() - عنصر قبلی (یکی قبل از عنصر بعدی) را برمی گرداند.

• previousIndex شاخص عنصر قبلی را برمی گرداند.

• set(<Element>) - جایگزین آخرین عنصر بازگشتی توسط next() یا previous() می شود .

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

85. چه سلسله مراتبی در مجموعه Java Framework وجود دارد؟

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

• مجموعه یک رابط است که یک مجموعه را توصیف می کند، یک ساختار داده ای که شامل عناصر منحصر به فرد (غیر تکراری) نامرتب است. این رابط پیاده سازی استاندارد دارد: TreeSet ، HashSet و LinkedHashSet .

• لیست یک رابط است که ساختار داده ای را توصیف می کند که دنباله ای مرتب از اشیاء را ذخیره می کند. اشیاء در یک لیست را می توان با فهرست آنها در لیست درج و حذف کرد (مانند یک آرایه، اما با تغییر اندازه پویا). این رابط پیاده سازی استاندارد نیز دارد: ArrayList ، Vector ( منسوخ شده و در واقع استفاده نشده است )، و LinkedList .

• Queue رابطی است که یک ساختار داده را توصیف می کند که موارد را در صف First In First Out (FIFO) ذخیره می کند . این رابط پیاده‌سازی‌های استاندارد زیر را دارد: LinkedList (درست است، Queue را نیز پیاده‌سازی می‌کند ) و PriotityQueue .

سلسله مراتب مجموعه دوم ، سلسله مراتب نقشه است که ساختار زیر را دارد: این سلسله مراتب مجموعه هیچ تقسیم بندی به زیر مجموعه ها ندارد (زیرا سلسله مراتب نقشه خود چیزی شبیه به یک مجموعه فرعی است که به تنهایی جدا می ایستد). پیاده‌سازی استاندارد Map عبارتند از : Hashtable (منسوخ شده)، LinkedHashMap و TreeMap . در عمل، هنگامی که مردم در مورد مجموعه ها می پرسند ، معمولاً منظور هر دو سلسله مراتب است.

86. ساختار داخلی ArrayList چیست؟

ArrayList مانند یک آرایه است، اما می تواند به صورت پویا گسترش یابد . معنی آن چیست؟ در زیر هود، ArrayList از یک آرایه معمولی استفاده می کند، یعنی عناصر خود را در یک آرایه داخلی ذخیره می کند که اندازه پیش فرض آن 10 سلول است. پس از پر شدن آرایه داخلی، یک آرایه جدید ایجاد می شود. اندازه آرایه جدید با این فرمول تعیین می شود:

<size of the current array> * 3 / 2 + 1

بنابراین، اگر اندازه آرایه ما 10 باشد، اندازه آرایه جدید خواهد بود: 10 * 3 / 2 + 1 = 16. سپس تمام مقادیر آرایه اصلی (قدیمی) با استفاده از داخلی در آن کپی می شوند. متد System.arraycopy() و آرایه اصلی حذف می شود. به طور خلاصه، ArrayList اینگونه است که تغییر اندازه پویا را پیاده سازی می کند. بیایید محبوب‌ترین روش‌های ArrayList را در نظر بگیریم : 1. add(<Element>) - یک عنصر را به انتهای آرایه (در آخرین سلول خالی) اضافه می‌کند، پس از اینکه ابتدا بررسی کرد که آیا یک سلول موجود در آرایه وجود دارد یا خیر. اگر نه، یک آرایه جدید ایجاد می شود و عناصر در آن کپی می شوند. پیچیدگی زمانی این عملیات O(1) است. یک روش مشابه add(<Index>, <Elelement>) وجود دارد . یک عنصر را نه به انتهای لیست (آرایه)، بلکه به سلول خاصی که با شاخصی که به عنوان آرگومان وارد شده است، اضافه می کند. در این مورد، پیچیدگی زمانی بسته به جایی که اضافه می‌کنید متفاوت خواهد بود:

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

یعنی پیچیدگی زمانی این روش از O(1) تا O(N) بسته به جایی که عنصر درج شده است، متغیر است. 2. set(<Index>, <Element>) - یک عنصر را در موقعیت مشخص شده در لیست می نویسد. اگر عنصری از قبل در آن موقعیت وجود داشته باشد، روش آن را بازنویسی می کند. پیچیدگی زمانی این عملیات O(1) است، زیرا شامل هیچ عملیات شیفتی نمی شود: ما فقط از ایندکس برای محاسبه آدرس سلول در آرایه که دارای پیچیدگی O(1) است استفاده می کنیم و سپس عنصر جدید را می نویسیم. . 3. remove(<index>) - یک عنصر را با شاخص آن در آرایه داخلی حذف می کند. هنگام حذف آیتمی که در انتهای لیست نیست، تمام موارد سمت راست مورد حذف شده باید یک سلول به چپ منتقل شوند تا شکاف حاصل از حذف بسته شود. بر این اساس، پیچیدگی زمانی مانند add(<Index>, <Element>) خواهد بود که یک عنصر در وسط اضافه شود: O(N/2). پس از همه، شما باید نیمی از عناصر را یک سلول به سمت چپ منتقل کنید. و اگر در مورد آغاز صحبت می کنیم، O(N). یا اگر در پایان، O(1)، زیرا نیازی به جابجایی چیزی ندارید.

87. ساختار داخلی LinkedList چیست؟

یک ArrayList حاوی عناصری در آرایه داخلی است، اما یک LinkedList آنها را در یک لیست دارای پیوند دوگانه ذخیره می کند. این بدان معنی است که هر عنصر حاوی پیوندی به عنصر قبلی و عنصر بعدی است . عنصر اول به عنصر قبلی پیوند نمی خورد (در نهایت، اولین عنصر است). همچنین به عنوان سر لیست در نظر گرفته می شود و شی LinkedList یک ارجاع مستقیم به آن دارد. به طور مشابه، آخرین عنصر عنصر بعدی را ندارد، زیرا دم لیست است. شی LinkedList نیز مستقیماً به آن ارجاع می دهد. این بدان معنی است که پیچیدگی زمانی دسترسی به سر یا دم یک لیست O(1) است. در ArrayList ، اگر لیست بزرگ شود، آرایه داخلی رشد می کند. در اینجا همه چیز ساده تر است: افزودن یک مرجع به سادگی تغییر چند پیوند است. بیایید به برخی از متدهای LinkedList که بیشترین استفاده را می‌کنند نگاهی بیاندازیم : 1. add(<Element>) - یک عنصر را به انتهای لیست اضافه می‌کند، یعنی بعد از آخرین عنصر (5)، پیوندی به عنصر جدید به عنوان بعدی اضافه می‌شود. . مرجع قبلی در عنصر جدید به عنصر (5) اشاره می کند که اکنون در لیست قبل از آن قرار دارد. پیچیدگی زمانی این عملیات O(1) است، زیرا ما فقط به پیوند به آخرین عنصر نیاز داریم، و همانطور که به یاد دارید، شی LinkedList یک ارجاع مستقیم به دم دارد و دسترسی به آن دارای حداقل پیچیدگی زمانی ثابت است. 2. add(<Index>, <Element>) - یک عنصر را به فهرست اضافه می کند. هنگام اضافه کردن یک عنصر، فرض کنید، در وسط یک لیست، این روش ابتدا روی عناصر از سر و دم (در هر دو جهت) تکرار می شود تا جایی که مکان مورد نظر پیدا شود. اگر عنصری را بین عنصر سوم و چهارم (در تصویر بالا) اضافه کنیم، پیوند بعدی عنصر سوم به عنصر جدید اشاره خواهد کرد. و قبلی عنصر جدید اضافه شده به عنصر سوم اشاره می کند. به نوبه خود، پیوند قبلی عنصر چهارم قدیمی اکنون به عنصر جدید اشاره خواهد کرد و پیوند بعدی عنصر جدید به عنصر چهارم جدید اشاره خواهد کرد: پیچیدگی زمانی این روش به شاخص عنصر جدید بستگی دارد:

• اگر به سر یا دم نزدیک باشد، عملیات به O(1) نزدیک می شود، زیرا عملاً نیازی به تکرار بر روی عناصر نخواهد بود.
• اگر نزدیک به وسط باشد، O(N/2) خواهیم داشت، زیرا این روش از سر و دم به طور همزمان جستجو می کند تا عنصر مورد نظر پیدا شود.

3. set(<Index>, <Element>) - یک عنصر را در موقعیت مشخص شده در لیست می نویسد. پیچیدگی زمانی این عملیات از O(1) تا O(N/2) متغیر خواهد بود، باز هم بسته به نزدیک بودن عنصر جدید به سر، دم یا وسط. 4. remove(<index>) - یک عنصر را از لیست حذف می کند و آن را طوری می سازد که عنصر قبل از حذف شده ( قبلی ) اکنون به عنصر بعد از حذف شده ( بعدی ) اشاره می کند. و بالعکس، یعنی عنصر بعد از حذف شده اکنون به عنصر قبل از حذف شده اشاره می کند: این فرآیند برعکس اضافه کردن با شاخص است ( add(<Index>, <Element>) ).

88. ساختار داخلی HashMap چیست؟

این ممکن است یکی از پرطرفدارترین سوالات مصاحبه ای باشد که باید از نامزدهای توسعه دهنده جاوا پرسیده شود. HashMap با جفت های کلید-مقدار کار می کند . چگونه آنها در داخل خود HashMap ذخیره می شوند ؟ HashMap دارای یک آرایه داخلی از گره ها است :

Node<K,V>[] table

به‌طور پیش‌فرض، اندازه آرایه 16 است و هر بار که با عناصر پر می‌شود، دو برابر می‌شود (یعنی وقتی به LOAD_FACTOR رسید ؛ آستانه پر شدن آرایه را مشخص می‌کند - به طور پیش‌فرض، 0.75 است ). . هر یک از گره ها یک هش از کلید، کلید، یک مقدار و یک ارجاع به عنصر بعدی را ذخیره می کند: در این مورد، "ارجاع به عنصر بعدی" به این معنی است که ما با یک لیست تک پیوندی روبرو هستیم. جایی که هر عنصر حاوی پیوندی به عنصر بعدی است. به عبارت دیگر، HashMap داده های خود را در آرایه ای از لیست های تک پیوندی ذخیره می کند. اما اجازه دهید فوراً بگویم که وقتی یک سلول از آرایه جدول دارای یک لیست تک پیوندی است که از بیش از یک عنصر تشکیل شده است، خوب نیست. به این پدیده برخورد می گویند . اما اول از همه. بیایید ببینیم چگونه یک جفت جدید با استفاده از روش put ذخیره می شود . ابتدا، متد hashCode() کلید را دریافت می کند . این بدان معناست که برای اینکه HashMap به درستی کار کند، کلیدهایی که استفاده می کنید باید کلاس هایی باشند که این روش را لغو کنند. سپس این کد هش در متد hash() داخلی برای تعیین شاخصی از سلول های موجود در آرایه جدول استفاده می شود. شاخص به دست آمده به ما امکان می دهد به یک سلول خاص از آرایه جدول دسترسی داشته باشیم. در اینجا دو مورد داریم:

1. سلول خالی است - در این مورد، مقدار Node جدید در آن ذخیره می شود.
2. سلول خالی نیست - در این مورد، مقادیر کلیدها با هم مقایسه می شوند. اگر برابر باشند، مقدار Node جدید مقدار قبلی را بازنویسی می کند. اگر مساوی نباشد، سپس به بعدی دسترسی پیدا می‌کند، و کلید آن مقایسه می‌شود... و به همین ترتیب، تا زمانی که مقدار جدید مقداری قدیمی را بازنویسی کند یا به انتهای فهرست پیوندی منفرد برسیم و سپس مقدار جدید را در آنجا ذخیره کنیم. آخرین عنصر

هنگام جستجوی یک عنصر توسط کلید (با استفاده از روش get(<key>) )، hashCode() کلید محاسبه می‌شود و سپس شاخص آن در آرایه با استفاده از hash() محاسبه می‌شود . عدد به دست آمده، شاخص یک سلول در آرایه جدول است که سپس با تکرار روی گره ها و مقایسه کلید گره مورد نظر با کلید گره فعلی، آن را جستجو می کنیم. در حالت ایده‌آل، عملیات Map دارای پیچیدگی الگوریتمی O(1) است، زیرا ما به یک آرایه دسترسی داریم، و همانطور که به یاد دارید، بدون توجه به تعداد عناصر موجود در آن، O(1) است. اما ما با حالت ایده آل روبرو نیستیم. وقتی سلول خالی (2) نباشد و برخی گره‌ها را قبلاً ذخیره کند، پیچیدگی الگوریتمی O(N) (خطی) می‌شود، زیرا اکنون لازم است قبل از یافتن مکان مناسب، روی عناصر تکرار شود. من نمی توانم به این نکته اشاره نکنم که با شروع در جاوا 8، اگر یک گره به شکل یک لیست تک پیوندی بیش از 8 عنصر داشته باشد (برخورد)، آنگاه به یک درخت باینری تبدیل می شود. در این مورد، پیچیدگی الگوریتمی دیگر O(N) نیست، بلکه O(log(N)) است - و این موضوع کاملاً دیگری است، اینطور نیست؟ HashMap یک موضوع بزرگ است و مردم دوست دارند در مصاحبه های شغلی در مورد آن سوال بپرسند. بنابراین، من پیشنهاد می کنم که آن را مانند پشت دست خود بشناسید. من شخصاً هرگز مصاحبه ای نداشته ام که شامل سؤالات در HashMap نباشد . برای امروز کافی است. ادامه دارد...