فهرست مندرجات[پنهان شدن][نمایش]
- 1. چگونه یک آرایه را تعریف می کنید؟
- 2. آرایه های پویا: آنها چیست؟ چه چیزی آنها را از آرایه های پایه متمایز می کند؟
- 3. چگونه یک آرایه و یک فرهنگ لغت با یکدیگر متفاوت هستند؟
- 4. برخی از مزایا و معایب آرایه ها را فهرست کنید.
- 5. «آرایه پراکنده» به چه چیزی اشاره دارد؟
- 6. چه زمانی یک لیست پیوندی را از یک آرایه انتخاب می کنید؟
- 7. چه چیزی یک آرایه نمایه شده را از یک آرایه انجمنی متمایز می کند؟
- 8. Heap چه مزایایی نسبت به آرایه های مرتب شده دارد؟
- 9. آیا می توانیم اندازه آرایه را منفی تعریف کنیم؟
- 10. چگونه می توان عدد صحیح گم شده را در یک آرایه 1 تا 100 عنصری پیدا کرد؟
- 11. چگونه می توان شاخص یک عنصر را در یک آرایه پیدا کرد؟
- 12. چگونه می توانید از شر یک عنصر خاص از یک آرایه خلاص شوید؟
- 13. چگونه می توان برابری دو آرایه را تأیید کرد؟
- 14. وقتی در مورد آرایه ها بحث می کنیم، منظور شما از عبارات "بعد" و "مشترک" چیست؟
- کدنویسی سوالات مصاحبه
- 15. جفتی را در آرایه ای جستجو کنید که دارای مجموع مشخص شده باشد
- 16. مرتب سازی آرایه باینری با زمان خطی
- 17. بزرگترین محصول دو اینتی را در یک آرایه پیدا کنید.
- 18. چگونه تمام صفرهای آرایه را به انتها منتقل کنیم
- 19. چگونه یک آرایه را با دو ورودی که در یک عملیات سوئیچ می شوند مرتب کنیم.
- 20. نحوه ترکیب دو آرایه مرتب شده در جای خود.
- 21. چگونه می توان مجموعه ای از اقلام را در موقعیت های بالا و پایین متناوب مرتب کرد؟
- 22. چگونه می توان هر عنصر یک آرایه را بدون استفاده از عملگر تقسیم با حاصلضرب هر عنصر در آرایه جایگزین کرد؟
- 23. عجیب ترین عنصر یک آرایه را در زمان لگاریتمی پیدا کنید
- 24. چگونه می توان عنصر بزرگتر بعدی را برای هر عنصر در یک آرایه دایره ای بدست آورد؟
- 25. تعداد وارونگی یک آرایه را پیدا کنید؟
- 26. مشکل حبس آب باران چیست؟
- نتیجه
مصاحبه های کدگذاری شامل یک سری سوالات DSA است. اگر برای مصاحبه فنی آتی خود با FAANG یا یکی دیگر از مشاغل فناوری Tier-1 آماده می شوید، باید در آرایه ها مهارت داشته باشید.
در اکثر مصاحبههای کدنویسی، در رتبه دوم پس از Strings قرار میگیرد. آرایه گروهی از عناصر داده مرتبط است که در مجاورت یکدیگر در حافظه نگهداری می شوند.
از آنجایی که آنها به تمام زبان های برنامه نویسی مانند C، C++، Java، Python، Perl و Ruby متصل هستند، همه جا هستند. برای برخی از چالش های کدنویسی تمرینی و سوالات و پاسخ های مصاحبه بر اساس آرایه ها به خواندن ادامه دهید.
پایتون در این پست برای مقابله با مشکلات کدنویسی استفاده خواهد شد زیرا استفاده از آن ساده است، درک میکند و باید برای اکثر ما آشنا باشد.
شروع کنیم.
1. چگونه یک آرایه را تعریف می کنید؟
- گروهی از انواع داده های مرتبط یک آرایه هستند.
- آرایه ها همیشه ثابت هستند.
- یک نوع متغیر در چندین مکان توسط اشیاء آرایه ذخیره می شود.
- انواع اولیه و مراجع شی هر دو با آن سازگار هستند.
2. آرایه های پویا: آنها چیست؟ چه چیزی آنها را از آرایه های پایه متمایز می کند؟
مقیاسبندی خودکار آرایههای پویا (همچنین به آرایههای قابل رشد، آرایههای قابل تغییر اندازه، آرایههای قابل تغییر یا ArrayLists در جاوا نیز گفته میشود) یک مزیت قابل توجه است.
شما همیشه باید بدانید که آرایه شما چند عنصر را از قبل ذخیره می کند زیرا آرایه ها دارای اندازه ثابت هستند. از طرف دیگر، یک آرایه پویا با اضافه کردن اعضای اضافی به آن رشد میکند، بنابراین نیازی به دانستن اندازه دقیق آن از قبل ندارید.
3. چگونه یک آرایه و یک فرهنگ لغت با یکدیگر متفاوت هستند؟
این مجموعه ای از سوالات مصاحبه مبتنی بر اصول است که به طور مرتب پرسیده می شود. تفاوت های کلیدی بین آرایه ها و دیکشنری ها به شرح زیر است:
- آرایه لیست مرتب شده ای از موارد مشابه است. از سوی دیگر، دیکشنری دارای جفت های کلید-مقدار است.
- اندازه آرایه می تواند به صورت پویا تغییر کند. چنین ایده های پویایی در فرهنگ لغت وجود ندارد.
- قبل از استفاده از آرایه، اندازه آن باید مشخص شود. اندازه فرهنگ لغت نیازی به سفارشی سازی ندارد.
- اگر می خواهید اندازه آرایه را افزایش دهید از عبارت Redim استفاده کنید. در فرهنگ لغت، یک عنصر را می توان بدون اعلان اضافه کرد.
4. برخی از مزایا و معایب آرایه ها را فهرست کنید.
مزایای:
- آرایه ها می توانند تعدادی عنصر را به طور همزمان مرتب کنند.
- دیگر ساختارهای دادهمانند پشتهها، صفها، لیستهای پیوندی، درختها، نمودارها و غیره را میتوان در یک آرایه پیادهسازی کرد.
- برای رسیدن به عنصری از آرایه می توان از شاخص استفاده کرد.
معایب:
- اندازه آرایه باید از قبل اعلام شود. در لحظه اعلام آرایه، ممکن است ما از اندازه مورد نیاز خود آگاه نباشیم.
- ساختار آرایه ثابت است. به این معنی است که اندازه آرایه همیشه ثابت است و تخصیص حافظه قابل افزایش یا کاهش نیست.
5. «آرایه پراکنده» به چه چیزی اشاره دارد؟
آرایه پراکنده آرایه داده ای است که ورودی های زیادی با مقادیر صفر دارد. در مقابل، یک آرایه متراکم شامل اکثر موارد خود با مقادیر غیر صفر است. شاخص های یک آرایه پراکنده، که اعداد را به اشیا تبدیل می کند، ممکن است شامل شکاف باشد. در مقایسه با HashMap، حافظه کارآمدتری دارند.
6. چه زمانی یک لیست پیوندی را از یک آرایه انتخاب می کنید؟
هنگام استفاده از لیست های پیوندی به جای آرایه ها، در نظر بگیرید:
- برای دسترسی تصادفی به هیچ عنصری نیاز ندارید.
- در جایی که قابلیت پیشبینی زمانی ضروری است، به درج و حذف با زمان ثابت از فهرست نیاز دارید.
- به منظور ایجاد یک صف اولویت، ممکن است لازم باشد موارد را در مرکز لیست قرار دهید.
- شما نمی دانید که لیست چقدر طولانی خواهد بود. اگر اندازه آرایه افزایش یابد، باید حافظه را دوباره اعلام و کپی کنید، درست مانند آرایه های ساده.
7. چه چیزی یک آرایه نمایه شده را از یک آرایه انجمنی متمایز می کند؟
تمایز اولیه بین آرایه های انجمنی و نمایه شده در جدول زیر فهرست شده است.
- یک جفت کلید-مقدار در قالب متن یا عددی برای مرتبسازی یک آرایه انجمنی استفاده میشود. کلیدهای آرایه نمایه شده همگی عددی هستند و هر کلید به یک مقدار مجزا متصل است.
- در یک آرایه انجمنی، کلید ممکن است یک رشته باشد. آرایه نمایه شده با کلیدهای عدد صحیح که از 0 شروع می شود.
- یک جدول دو ستونی رفتار یک آرایه انجمنی را تقلید می کند. آرایه های نمایه شده مشابه جدول تک ستونی هستند.
- نقشه ها یک نوع آرایه انجمنی هستند. آرایه شاخص یک نقشه نیست.
8. Heap چه مزایایی نسبت به آرایه های مرتب شده دارد؟
بهره وری زمانی استفاده از Heap بر روی آرایه های مرتب شده مزیت اصلی است. در حالی که عملیات پشته سریعتر است، مرتب سازی یک آرایه به زمان زیادی نیاز دارد. یک پشته می تواند کوچکترین عنصر را بسیار سریعتر از مرتب سازی یک آرایه کشف کند.
مجموعه ای از اعداد را می توان به یکی از دو روش با استفاده از آرایه های مرتب شده مرتب کرد. از سوی دیگر، برای یک مجموعه معین از اعداد، ممکن است بیش از یک پشته بالقوه وجود داشته باشد.
9. آیا می توانیم اندازه آرایه را منفی تعریف کنیم؟
خیر، نمی توانیم یک عدد صحیح منفی را به اندازه یک آرایه تعریف کنیم. اگر اعلام کنیم، خطای زمان کامپایل وجود نخواهد داشت. در زمان اجرا، با یک NegativeArraySizeException مواجه خواهیم شد.
10. چگونه می توان عدد صحیح گم شده را در یک آرایه 1 تا 100 عنصری پیدا کرد؟
مجموع سری ها را می توان با اعمال تابع زیر محاسبه کرد: n (n + 1) / 2
تنها در صورتی که آرایه هیچ تکراری نداشته باشد یا بیش از یک عدد صحیح گم شده باشد، این تابع عمل می کند. این که آیا یک آرایه دارای عناصر تکراری است، می توانید آرایه را مرتب کنید تا ببینید آیا عناصری معادل وجود دارد یا خیر.
11. چگونه می توان شاخص یک عنصر را در یک آرایه پیدا کرد؟
شاخص یک عنصر را می توان از طریق جستجوی خطی یا باینری کشف کرد. تا زمانی که مطابقت عنصر مورد نیاز را پیدا کند، یک تابع جستجوی خطی بر روی هر عنصر در یک آرایه حلقه می زند. زمانی که عنصر منطبق را پیدا کرد، شاخص را برمی گرداند. در نتیجه، پیچیدگی زمانی جستجوی خطی O. (n) است. هر دو آرایه مرتب شده و مرتب نشده می توانند از جستجوی خطی استفاده کنند.
با استفاده از جستجوی دودویی، که به طور مداوم آرایه را به نصف تقسیم می کند تا زمانی که میانه بازه با عنصر مورد نیاز مطابقت داشته باشد و شاخص را فراهم کند، اگر آرایه مرتب شده باشد، می توانید شاخص عنصر را دریافت کنید. در نتیجه، پیچیدگی زمانی جستجوی باینری O. (log n) است.
12. چگونه می توانید از شر یک عنصر خاص از یک آرایه خلاص شوید؟
از آنجایی که شما نمی توانید به سادگی عناصر را از آرایه اصلی حذف کنید زیرا آنها مجموعه های ثابتی با اندازه تعریف شده هستند، مصاحبه کننده به دنبال این است که شما رویکرد متفاوتی را پیشنهاد دهید و با مشکلی که سوال ایجاد می کند مقابله کنید. بهترین اقدام این است که یک آرایه جدید بسازید تا یک عنصر را حذف کنید. میتوانید عناصر را از اولین آرایه در این آرایه کپی کنید و فقط عنصری را که میخواهید حذف کنید را شامل کنید.
استراتژی دیگر شامل یافتن عنصر هدف در آرایه و سپس معکوس کردن ترتیب همه مواردی است که در سمت راست عنصر هدف قرار دارند.
13. چگونه می توان برابری دو آرایه را تأیید کرد؟
ابتدا باید طول دو آرایه ارائه شده را بررسی کنید. موارد منطبق هر دو آرایه زمانی با هم مقایسه می شوند که طول آنها برابر باشد. دو آرایه برابر در نظر گرفته خواهند شد. اگر هر جفت جزء در هر تناظر با هم برابر باشد. اگر اندازه آرایهها بزرگ هستند، این روش برای بررسی برابری دو آرایه توصیه نمیشود، زیرا زمان زیادی میبرد. همچنین میتوانید از متد ()quals موجود در کلاس Arrays استفاده کنید، اما اگر مصاحبهکننده از شما بخواهد که دو آرایه را بدون استفاده از متدهای داخلی مقایسه کنید، این روش مفید خواهد بود.
14. وقتی در مورد آرایه ها بحث می کنیم، منظور شما از عبارات "بعد" و "مشترک" چیست؟
«بُعد» یک آرایه تعداد شاخصها یا زیرنویسهایی است که برای شناسایی هر عضو لازم است. اشتراک ها و ابعاد ممکن است نامشخص باشد. یک بعد توصیفی از محدوده کلیدهای مجاز است، در حالی که یک زیرنویس یک عدد است. برای هر بعد آرایه فقط یک زیرنویس مورد نیاز است.
به عنوان مثال، آرایه آرایه[10][5] دارای دو بعد است. سایز 10 روی یکی و 5 روی دیگری. برای پرداختن به اجزای آن، به دو زیرنویس نیاز دارید. هر دو بین 0 و 4 هستند. یکی بین 0 و 9، شامل.
کدنویسی سوالات مصاحبه
15. جفتی را در آرایه ای جستجو کنید که دارای مجموع مشخص شده باشد
به عنوان مثال،
ورودی:
- اعداد = [8، 7، 2، 5، 3، 1]
- هدف = 10
خروجی:
- جفت پیدا شد (8، 2)
- Or
- جفت پیدا شد (7، 3)
ورودی:
- اعداد = [5، 2، 6، 8، 1، 9]
- هدف = 12
خروجی:
- جفت یافت نشد
16. مرتب سازی آرایه باینری با زمان خطی
یک آرایه باینری را در زمان خطی و در یک ناحیه ثابت مرتب کنید. خروجی باید ابتدا همه صفرها و سپس همه یکها را نمایش دهد.
به عنوان مثال،
- ورودی: {1، 0، 1، 0، 1، 0، 0، 1 }
- خروجی: {0، 0، 0، 0، 1، 1، 1، 1 }
یک روش ساده این است که تعداد کل 0 آرایه را محاسبه کنیم، مثلا k، و سپس اولین k شاخص در آرایه را با 0 و شاخص های باقی مانده را با 1 پر کنیم. آرایه k، آخرین k شاخص های آرایه را با 1 پر کنید و بقیه شاخص ها را با 1 پر کنید.
رویکرد داده شده دارای پیچیدگی زمانی O(n) است و از ذخیره سازی اضافی استفاده نمی کند، جایی که n اندازه ورودی است.
17. بزرگترین محصول دو اینتی را در یک آرایه پیدا کنید.
بزرگترین حاصل ضرب دو عدد در یک آرایه اعداد صحیح را پیدا کنید.
آرایه 10 3 5 6 2 را به عنوان مثال در نظر بگیرید. جفت (-10، -3) یا (5، 6) بالاترین محصول است.
فکر کردن در مورد ترکیب هر عنصر و کشف محصول آنها یک رویکرد احمقانه است. اگر حاصل ضرب جفت فعلی بزرگتر از حداکثر محصول بدست آمده تا کنون است، حداکثر محصول را به روز کنید. آخرین قسمت اجزای محصول نهایی را چاپ کنید.
راه حل فوق، که در آن n مقدار ورودی است، پیچیدگی زمانی O(n2) دارد و فضای بیشتری را اشغال نمی کند.
18. چگونه تمام صفرهای آرایه را به انتها منتقل کنیم
تمام صفرهای یک آرایه عدد صحیح را به انتها منتقل کنید. در پاسخ باید از استفاده از فضای ثابت اجتناب شود و نظم نسبی اجزای آرایه حفظ شود.
ورودی: {1,2,3,0,8,0,4,7،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}
خروجی {1,2,3,8,4,7,0,0،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX} خواهد بود
اگر عنصر فعلی صفر نیست، عنصر را در موقعیت موجود زیر در آرایه قرار دهید. پس از پردازش آیتم های آرایه، همه شاخص های باقی مانده را با 0 پر کنید.
راه حل قبلی دارای پیچیدگی زمانی O(n) است که n اندازه ورودی است.
19. چگونه یک آرایه را با دو ورودی که در یک عملیات سوئیچ می شوند مرتب کنیم.
یک آرایه را در زمان خطی با توجه به دو مورد مبادله شده و یک آرایه با تمام عناصر آن به ترتیب صعودی مرتب کنید. وانمود کنید که آرایه حاوی موارد تکراری نیست.
ورودی: = [1,9,3,4,7,2،9,3,7,2,1,4،2,4,1,7,3,9،XNUMX،XNUMX،XNUMX] یا [XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX] یا [XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX]
خروجی: = [1,2,3,4,7,9،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX]
با شروع با عنصر دوم در آرایه، هدف مقایسه هر عنصر با سلف خود است. موقعیت اختلاف با گرفتن دو نشانگر x و y ذخیره می شود.
x را به شاخص عنصر قبلی و y را به شاخص عنصر فعلی در صورتی که اولی بزرگتر از دومی است به روز کنید. اگر معلوم شد که عنصر قبلی بزرگتر از عنصر فعلی است، y را به شاخص عنصر فعلی به روز کنید.
در نهایت، هنگامی که پردازش هر جفت از عناصر مجاور را به پایان رساندیم، عناصر را در شاخصهای x و y تغییر دهید.
با توجه به اینکه روش فوق تنها یک اسکن از آرایه ورودی به اندازه n انجام می دهد، پیچیدگی زمانی آن O(n) است. هیچ اتاق اضافی برای راه حل لازم نیست.
20. نحوه ترکیب دو آرایه مرتب شده در جای خود.
آیتم های آرایه های X[] و Y[] - دو آرایه مرتب شده با اندازه m و n هر کدام - با حفظ ترتیب مرتب شده، یعنی با پر کردن X[] با اولین m کوچکترین عناصر و پر کردن Y[] با عناصر باقی مانده
اگر عنصری در آرایه X[] در موقعیت مناسب قرار دارد (یعنی عنصری که در بین عناصر باقی مانده کوچکترین است)، آن را نادیده بگیرید. در غیر این صورت، آن را با کوچکترین عنصر جایگزین کنید، که اتفاقاً اولین عضو Y[] نیز هست. برای حفظ ترتیب مرتب شده پس از تعویض، عنصر (اکنون در Y[0]) را به مکان مناسب خود در Y[] منتقل کنید.
اندازه آرایه اول m و اندازه آرایه دوم n است و پیچیدگی زمانی O(mn) است.
21. چگونه می توان مجموعه ای از اقلام را در موقعیت های بالا و پایین متناوب مرتب کرد؟
یک آرایه عدد صحیح را به گونه ای تنظیم کنید که هر عضو بعدی بزرگتر از عناصر قبلی و بعدی باشد. فرض کنید آرایه شامل هیچ عنصر تکراری نیست.
مرتب کردن آرایه یا استفاده از فضای اضافی برای یک رویکرد مؤثر ضروری نیست. پلان برای شروع، دومین عضو آرایه است و برای هر تکرار حلقه دو تا بالا می رود.
اگر آخرین عنصر بیشتر از عنصر اول باشد، اجزا را عوض کنید. اگر عنصر زیر بزرگتر از عنصر فعلی است، به روشی مشابه، هر دو مورد را تغییر دهید. آرایه مورد نظر را که با محدودیت های مشخص شده مطابقت دارد در پایان حلقه بدست می آوریم.
22. چگونه می توان هر عنصر یک آرایه را بدون استفاده از عملگر تقسیم با حاصلضرب هر عنصر در آرایه جایگزین کرد؟
بدون استفاده از عملگر تقسیم، هر عنصر در یک آرایه عدد صحیح را با حاصلضرب همه عناصر دیگر جایگزین کنید.
در زمان خطی و فضای ثابت، میتوانیم از بازگشت برای پرداختن به این موضوع استفاده کنیم. محاسبه بازگشتی محصولات هر عنصر در زیرآرایه سمت راست و ارسال حاصلضرب زیرآرایه سمت چپ به عنوان پارامترهای تابع مفهوم است.
پیچیدگی زمانی O(n) است.
23. عجیب ترین عنصر یک آرایه را در زمان لگاریتمی پیدا کنید
با توجه به یک آرایه اعداد صحیح که در آن همه اعضا به جز یک عضو دارای تعداد اتفاقات زوج هستند، مشکل این است که تعیین کنیم این یک عنصر چند بار ظاهر می شود. اگر عناصر مشابه به صورت جفت در آرایه وجود داشته باشند و هرگز نمی توانند بیش از دو نمونه از یک عنصر معین در یک ردیف وجود داشته باشند، عنصر اتفاق افتاده را در زمان لگاریتمی و فضای ثابت بیابید.
عملیات XOR ما را قادر می سازد این مشکل را در زمان خطی حل کنیم. هدف XOR کردن هر عنصر در آرایه است. فقط عناصر اتفاق افتاده پس از اینکه عناصر زوج یکدیگر را خنثی کردند، باقی می مانند.
این مشکل حتی در زمان O(log(n)) قابل حل است.
24. چگونه می توان عنصر بزرگتر بعدی را برای هر عنصر در یک آرایه دایره ای بدست آورد؟
عنصر بزرگتر بعدی برای هر عنصر در یک آرایه عدد صحیح دایره ای باید قرار گیرد. اولین عدد صحیح بزرگتر بعد از عنصر x در آرایه، عنصر بزرگتر بعدی آن عنصر است.
از راست به چپ، ممکن است روی موارد آرایه کار کنیم. هدف این است که برای هر عنصر x حلقه بزنیم تا زمانی که پشته خالی شود یا یک عنصر بالاتر در بالای آن داشته باشیم. عنصر بزرگتر بعدی x را تنظیم کنید تا در زمانی که ظاهر شد در بالای پشته ظاهر شود.
25. تعداد وارونگی یک آرایه را پیدا کنید؟
تعداد کل وارونگی های یک آرایه را بیابید. جفت I j) به وارونگی آرایه A اشاره می شود اگر I j) و (A[i] > A[j]). ما باید هر جفت از اینها را در آرایه بشماریم.
شمارش تمام اعضای آرایه که کمتر از آن در سمت راست هستند و افزودن نتیجه به خروجی یک رویکرد ساده است.
این راه حل دارای پیچیدگی O(n2) است که n اندازه ورودی است.
26. مشکل حبس آب باران چیست؟
یافتن بیشترین آبی که می تواند در یک مجموعه معین از میله ها با عرض یک واحد هر کدام به دام بیفتد، به عنوان مسئله "باران به دام انداختن" شناخته می شود.
هدف تعیین بالاترین نواری است که ممکن است در سمت چپ و راست هر نوار قرار گیرد. حداقل میله های پیشرو به سمت چپ و راست، کمتر از ارتفاع میله فعلی، مقدار آبی است که در بالای هر میله ذخیره می شود.
نتیجه
در مقایسه با سایر موضوعات ساختار داده، آرایه ها ساده تر هستند. برای پاسخگویی به سوالات مصاحبه آرایه ای، باید درک اساسی از آرایه ها داشته باشید.
شما باید مبانی آرایه ها، از جمله عملیات آرایه (از اعلام/ایجاد یک آرایه تا دسترسی/تغییر آیتم های آرایه)، و همچنین مفاهیم برنامه نویسی مانند حلقه ها، بازگشت، و عملگرهای اساسی را به منظور پاسخگویی موفقیت آمیز به سوالات مصاحبه آرایه بررسی کنید. موضوع را کاملاً تشخیص دهید.
اگر سوالی دارید باید به دنبال توضیح باشید. به این فکر کنید که موضوع را به بخش های قابل کنترل تر تقسیم کنید. قبل از شروع برنامه نویسی مطمئن شوید که الگوریتم را در ذهن دارید. آن را یادداشت کنید یا در یک فلوچارت تجسم کنید. سپس شروع به نوشتن کد کنید.
پاسخ دهید