کی میز کے مندرجات[چھپائیں][دکھائیں]
- 1. آپ ایک صف کی وضاحت کیسے کرتے ہیں؟
- 2. متحرک صفیں: وہ کیا ہیں؟ انہیں بنیادی صفوں سے الگ کیا ہے؟
- 3. ایک صف اور لغت ایک دوسرے سے کیسے مختلف ہوتی ہیں؟
- 4. صفوں کے کچھ فوائد اور نقصانات کی فہرست بنائیں۔
- 5. "Sparse Array" سے کیا مراد ہے؟
- 6. آپ ایک صف پر منسلک فہرست کا انتخاب کب کریں گے؟
- 7. انڈیکسڈ ارے کو ایسوسی ایٹیو صف سے کیا فرق کرتا ہے؟
- 8. ہیپ کو ترتیب شدہ صفوں سے زیادہ کیا فوائد حاصل ہیں؟
- 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، وہ ہر جگہ موجود ہیں۔ کچھ مشق کوڈنگ چیلنجز اور انٹرویو کے سوالات اور جوابات کے لیے پڑھنا جاری رکھیں۔
Python کو اس پوسٹ میں کوڈنگ کے مسائل سے نمٹنے کے لیے استعمال کیا جائے گا کیونکہ یہ استعمال کرنا، سمجھنا آسان ہے اور ہم میں سے اکثر کے لیے اس سے واقف ہونا چاہیے۔
چلو شروع کریں.
1. آپ ایک صف کی وضاحت کیسے کرتے ہیں؟
- متعلقہ ڈیٹا کی اقسام کا ایک گروپ ایک صف ہے۔
- صفیں ہمیشہ طے ہوتی ہیں۔
- ایک ہی قسم کا متغیر کئی جگہوں پر ارے آبجیکٹ کے ذریعے محفوظ کیا جاتا ہے۔
- قدیم اقسام اور آبجیکٹ کے حوالے دونوں اس کے ساتھ مطابقت رکھتے ہیں۔
2. متحرک صفیں: وہ کیا ہیں؟ انہیں بنیادی صفوں سے الگ کیا ہے؟
خودکار اسکیلنگ جو متحرک صفیں (جسے قابل گرویدہ صفوں، ریزیز ایبل اریز، بدلنے والی صفوں، یا جاوا میں ArrayLists بھی کہا جاتا ہے) ایک اہم فائدہ ہے۔
آپ کو ہمیشہ یہ معلوم ہونا چاہیے کہ آپ کی صف میں کتنے عناصر پہلے سے محفوظ ہوں گے کیونکہ صفوں کا ایک مقررہ سائز ہوتا ہے۔ ایک متحرک صف، دوسری طرف، بڑھ جاتی ہے جب آپ اس میں اضافی ممبرز شامل کرتے ہیں، لہذا آپ کو اس کے صحیح سائز کو پہلے سے جاننے کی ضرورت نہیں ہے۔
3. ایک صف اور لغت ایک دوسرے سے کیسے مختلف ہوتی ہیں؟
یہ انٹرویو کے سوالات کی بنیادی باتوں پر مبنی صف ہے جو باقاعدگی سے پوچھے جاتے ہیں۔ صفوں اور لغات کے درمیان کلیدی امتیازات درج ذیل ہیں:
- ایک سرنی ملتے جلتے آئٹمز کی ترتیب شدہ فہرست ہے۔ دوسری طرف لغت میں کلیدی قدر کے جوڑے ہوتے ہیں۔
- صفوں کے سائز متحرک طور پر تبدیل ہو سکتے ہیں۔ ایسے متحرک خیالات لغات میں موجود نہیں ہیں۔
- کسی صف کو استعمال کرنے سے پہلے، اس کا سائز بتانا ضروری ہے۔ لغت کے سائز کو اپنی مرضی کے مطابق کرنے کی ضرورت نہیں ہے۔
- اگر آپ صف کے سائز کو بڑھانا چاہتے ہیں تو Redim بیان کا استعمال کریں۔ لغات میں، ایک عنصر ایک اعلان کے بغیر شامل کیا جا سکتا ہے.
4. صفوں کے کچھ فوائد اور نقصانات کی فہرست بنائیں۔
فوائد:
- صفیں ایک ساتھ کئی عناصر کو ترتیب دے سکتی ہیں۔
- دیگر ڈیٹا ڈھانچےجیسے اسٹیک، قطار، منسلک فہرستیں، درخت، گراف وغیرہ، ایک صف میں لاگو کیا جا سکتا ہے۔
- ایک اشاریہ ایک صف کے عنصر تک پہنچنے کے لیے استعمال کیا جا سکتا ہے۔
نقصانات:
- ایک صف کے سائز کا پہلے سے اعلان کرنا ضروری ہے۔ صفوں کے اعلان کے وقت، ہم شاید اس سائز سے واقف نہ ہوں جس کی ہمیں ضرورت ہے۔
- صف کی ساخت جامد ہے۔ اس کا مطلب یہ ہے کہ صف کا سائز ہمیشہ طے ہوتا ہے اور میموری مختص کو بڑھا یا کم نہیں کیا جاسکتا۔
5. "Sparse Array" سے کیا مراد ہے؟
ایک ویرل سرنی ایک ڈیٹا سرنی ہے جس میں صفر کی قدروں کے ساتھ بہت ساری اندراجات ہیں۔ اس کے برعکس، ایک گھنے صف میں اس کی زیادہ تر اشیاء غیر صفر اقدار کے ساتھ ہوتی ہیں۔ ایک ویرل سرنی کے اشاریہ جات، جو اعداد کو اشیاء میں تبدیل کرتے ہیں، میں خلا شامل ہو سکتا ہے۔ HashMap کے مقابلے میں، وہ زیادہ یادداشت کے قابل ہیں۔
6. آپ ایک صف پر منسلک فہرست کا انتخاب کب کریں گے؟
صفوں کے بجائے منسلک فہرستوں کا استعمال کرتے وقت، غور کریں:
- بے ترتیب رسائی کے لیے آپ کو کسی بھی عناصر کی ضرورت نہیں ہے۔
- جہاں وقتی پیشین گوئی ضروری ہے، آپ کو فہرست سے مستقل وقت کے اندراج اور ہٹانے کی ضرورت ہے۔
- ترجیحی قطار بنانے کے لیے، آپ کو فہرست کے بیچ میں اشیاء رکھنے کی ضرورت پڑ سکتی ہے۔
- آپ کو اندازہ نہیں ہے کہ فہرست کتنی لمبی ہوگی۔ اگر سرنی کا سائز بڑھ جاتا ہے، تو آپ کو سادہ صفوں کی طرح میموری کا دوبارہ اعلان اور ڈپلیکیٹ کرنا ہوگا۔
7. انڈیکسڈ ارے کو ایسوسی ایٹیو صف سے کیا فرق کرتا ہے؟
ایسوسی ایٹیو اور انڈیکسڈ صفوں کے درمیان بنیادی امتیازات درج ذیل جدول میں درج ہیں۔
- متن یا عددی فارمیٹ میں کلیدی قدر کا جوڑا کسی ایسوسی ایٹیو صف کو ترتیب دینے کے لیے استعمال کیا جاتا ہے۔ انڈیکس شدہ صف کی کلیدیں تمام عددی ہیں، اور ہر کلید ایک الگ قدر سے جڑی ہوئی ہے۔
- ایک ایسوسی ایٹیو صف میں، کلید ایک تار ہو سکتی ہے۔ 0 سے شروع ہونے والی عددی کلیدوں کے ساتھ انڈیکس کردہ صف۔
- ایک دو کالم ٹیبل ایک ایسوسی ایٹیو صف کے رویے کی نقل کرتا ہے۔ سنگل کالم ٹیبل کی طرح انڈیکس شدہ صفیں ہیں۔
- نقشے ایک ایسوسی ایٹیو صف کی قسم ہیں۔ انڈیکس سرنی نقشہ نہیں ہے۔
8. ہیپ کو ترتیب شدہ صفوں سے زیادہ کیا فوائد حاصل ہیں؟
Sorted Arrays پر ہیپ کو استعمال کرنے کی وقت کی کارکردگی اہم فائدہ ہے۔ جبکہ ہیپ آپریشنز تیز تر ہوتے ہیں، ایک صف کو ترتیب دینے میں کافی وقت درکار ہوتا ہے۔ ایک ہیپ سب سے چھوٹے عنصر کو اس سے کہیں زیادہ تیزی سے دریافت کر سکتا ہے جتنا کہ کسی صف کو ترتیب دیا جا سکتا ہے۔
نمبروں کے دیے گئے مجموعہ کو دو طریقوں میں سے ایک ترتیب میں ترتیب دیا جا سکتا ہے۔ دوسری طرف، اعداد کے دیے گئے مجموعہ کے لیے، ایک سے زیادہ ممکنہ ہیپ ہو سکتے ہیں۔
9. کیا ہم صف کے سائز کو منفی قرار دے سکتے ہیں؟
نہیں، ہم ایک صف کے سائز کے لیے منفی عدد کی وضاحت نہیں کر سکتے۔ اگر ہم اعلان کرتے ہیں تو مرتب وقت کی غلطی نہیں ہوگی۔ رن ٹائم پر، تاہم، ہمیں ایک NegativeArraySizeException کا سامنا کرنا پڑے گا۔
10. آپ 1 سے 100 عنصر کی صف میں گم شدہ عدد کو کیسے تلاش کرتے ہیں؟
مندرجہ ذیل فنکشن کو لاگو کرکے سیریز کا کل شمار کیا جا سکتا ہے: n (n + 1) / 2
صرف اس صورت میں جب صف میں کوئی ڈپلیکیٹ نہ ہو یا اس میں ایک سے زیادہ عدد موجود نہ ہوں یہ فنکشن کام کرے گا۔ چاہے کسی سرنی میں ڈپلیکیٹ عناصر ہوں، آپ یہ دیکھنے کے لیے سرنی کو ترتیب دے سکتے ہیں کہ آیا اس کے مساوی عناصر موجود ہیں۔
11. آپ ایک صف میں کسی عنصر کا انڈیکس کیسے تلاش کرتے ہیں؟
ایک عنصر کا انڈیکس لکیری یا بائنری تلاش کے ذریعے دریافت کیا جا سکتا ہے۔ جب تک یہ مطلوبہ عنصر کے میچ کو تلاش نہیں کرتا ہے، ایک لکیری تلاش کا فنکشن ایک صف میں ہر ایک عنصر کے اوپر لوٹ جاتا ہے۔ جب یہ مماثل عنصر کا پتہ لگاتا ہے تو یہ انڈیکس واپس کرتا ہے۔ نتیجتاً، لکیری تلاش کی عارضی پیچیدگی O. (n) ہے۔ ترتیب شدہ اور غیر ترتیب شدہ سرنی دونوں لکیری تلاش کا استعمال کر سکتے ہیں۔
ایک بائنری تلاش کا استعمال کرتے ہوئے، جو ارے کو مسلسل نصف میں تقسیم کرتا ہے جب تک کہ وقفہ کا میڈین مطلوبہ عنصر سے میل نہیں کھاتا اور انڈیکس فراہم کرتا ہے، اگر صف کو ترتیب دیا گیا ہے تو آپ عنصر کا اشاریہ حاصل کر سکتے ہیں۔ نتیجتاً، بائنری تلاش کی عارضی پیچیدگی O. (log n) ہے۔
12. آپ ایک صف سے کسی مخصوص عنصر کو کیسے نکال سکتے ہیں؟
چونکہ آپ اصل صف سے عناصر کو آسانی سے حذف نہیں کر سکتے کیونکہ وہ ایک متعین سائز کے ساتھ طے شدہ سیٹ ہیں، اس لیے انٹرویو لینے والا آپ کو ایک مختلف نقطہ نظر تجویز کرنے اور سوال اٹھانے والے مسئلے سے نمٹنے کی کوشش کر رہا ہے۔ ایک عنصر کو حذف کرنے کے لیے ایک نئی صف بنانا بہترین عمل ہے۔ آپ اس صف میں پہلی صف سے عناصر کو نقل کر سکتے ہیں اور صرف وہی عنصر شامل کر سکتے ہیں جسے آپ حذف کرنا چاہتے ہیں۔
ایک اور حکمت عملی میں صف میں ہدف کے عنصر کو تلاش کرنا اور پھر ہدف کے عنصر کے دائیں جانب تمام اشیاء کی ترتیب کو تبدیل کرنا شامل ہے۔
13. دو صفوں کی مساوات کی تصدیق کیسے کی جا سکتی ہے؟
آپ کو پہلے دو فراہم کردہ صفوں کی لمبائی کی تصدیق کرنی ہوگی۔ دونوں صفوں کی مماثل اشیاء کا موازنہ اس وقت کیا جاتا ہے جب ان کی لمبائی برابر ہو۔ دونوں صفوں کو برابر سمجھا جائے گا۔ اگر ہر خط و کتابت میں اجزاء کا ہر جوڑا برابر ہے۔ اس نقطہ نظر کو دو صفوں کی مساوات کی جانچ کرنے کا مشورہ نہیں دیا جاتا ہے اگر ارے سائز میں بڑے ہیں کیونکہ اس میں بہت وقت لگے گا۔ آپ Arrays کلاس میں شامل equals() طریقہ بھی استعمال کر سکتے ہیں، تاہم، اگر انٹرویو لینے والا آپ سے بلٹ ان طریقوں کو استعمال کیے بغیر دو صفوں کا موازنہ کرنے کو کہے، تو یہ طریقہ کارآمد ہوگا۔
14. جب ہم صفوں پر بات کرتے ہیں، تو "ڈائمنشن" اور "سب اسکرپٹ" کے فقروں سے آپ کا کیا مطلب ہے؟
ایک صف کی "طول و عرض" انڈیکس کی تعداد ہے، یا سبسکرپٹس، جو ہر فرد کی شناخت کے لیے درکار ہیں۔ سبسکرپٹس اور طول و عرض غیر واضح ہو سکتے ہیں۔ ایک طول و عرض اجازت شدہ کلیدوں کی رینج کی وضاحت ہے، جبکہ سبسکرپٹ ایک نمبر ہے۔ ہر صف کے طول و عرض کے لیے صرف ایک سبسکرپٹ درکار ہے۔
مثال کے طور پر، array arr[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 انڈیکس کو 0s اور بقیہ انڈیکس کو 1 سے بھریں۔ متبادل کے طور پر، ہم حساب لگا سکتے ہیں کہ 1s میں کل کتنے ہیں۔ سرنی k، صف میں آخری k انڈیکس کو 1 سے بھریں، اور باقی انڈیکس کو 0 سے بھر کر چھوڑ دیں۔
دیئے گئے نقطہ نظر میں 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}
اگر موجودہ عنصر صفر نہیں ہے تو عنصر کو صف میں درج ذیل دستیاب پوزیشن پر رکھیں۔ تمام بقیہ انڈیکسز کو 0 سے پُر کریں ایک بار جب صف کے تمام آئٹمز پر کارروائی ہو جائے۔
پچھلے حل میں O(n) وقت کی پیچیدگی ہے، جہاں n ان پٹ کا سائز ہے۔
19. دو اندراجات کے ساتھ ایک صف کو کس طرح ترتیب دیا جائے جو ایک آپریشن میں تبدیل ہو جائیں۔
دو تبدیل شدہ آئٹمز اور اس کے تمام عناصر کے ساتھ صعودی ترتیب میں ترتیب دی گئی ایک صف کو لکیری وقت میں ترتیب دیں۔ دکھاوا کریں کہ صف میں کوئی نقل نہیں ہے۔
ان پٹ:= [1,9,3,4,7,2] یا [9,3,7,2,1,4] یا [2,4,1,7,3,9]
آؤٹ پٹ: = [1,2,3,4,7,9]
صف میں دوسرے عنصر سے شروع کرتے ہوئے، مقصد ہر عنصر کا اس کے پیشرو سے موازنہ کرنا ہے۔ تنازعہ کی پوزیشن کو دو پوائنٹرز، x، اور y لے کر محفوظ کیا جاتا ہے۔
x کو پچھلے عنصر کے انڈیکس میں اور y کو موجودہ عنصر کے انڈیکس میں اپ ڈیٹ کریں اگر سابقہ مؤخر الذکر سے بڑا ہے۔ موجودہ عنصر کے انڈیکس میں y کو اپ ڈیٹ کریں اگر یہ پتہ چلتا ہے کہ پچھلا عنصر موجودہ عنصر سے بڑا ہے۔
آخر میں، عناصر کو انڈیکسز x اور y پر سوئچ کریں جب ہم عناصر کے ہر ملحقہ جوڑے پر کارروائی مکمل کر لیں۔
اس حقیقت کی وجہ سے کہ مذکورہ طریقہ n سائز کے ان پٹ سرنی کا صرف ایک ہی اسکین کرتا ہے، اس کی وقت کی پیچیدگی O(n) ہے۔ حل کے لیے اضافی کمرے کی ضرورت نہیں ہے۔
20. دو ترتیب شدہ صفوں کو جگہ پر کیسے جوڑیں۔
ترتیب شدہ ترتیب کو برقرار رکھتے ہوئے، یعنی 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. بارش کے پانی کو پھنسنے کا مسئلہ کیا ہے؟
سب سے زیادہ پانی تلاش کرنا جو سلاخوں کے دیئے گئے سیٹ میں ایک یونٹ کی چوڑائی کے ساتھ پھنس سکتا ہے اسے "ٹریپنگ بارش" کے مسئلے کے طور پر جانا جاتا ہے۔
مقصد سب سے زیادہ بار کا تعین کرنا ہے جو ہر بار کے بائیں اور دائیں طرف رکھا جا سکتا ہے۔ بائیں اور دائیں طرف کی معروف سلاخوں کی کم از کم، موجودہ بار کی اونچائی سے کم، پانی کی وہ مقدار ہے جو ہر بار کے اوپر جمع ہوتی ہے۔
نتیجہ
ڈیٹا ڈھانچے کے دیگر موضوعات کے مقابلے میں، صفیں آسان ہیں۔ سرنی انٹرویو کے سوالات کو اکٹھا کرنے کے لیے، آپ کو صفوں کی بنیادی سمجھ کی ضرورت ہے۔
آپ کو صفوں کی بنیادوں کا وسیع پیمانے پر جائزہ لینا چاہیے، بشمول ارے آپریشنز (ایک صف کا اعلان کرنے/تخلیق کرنے سے لے کر ارے آئٹمز تک رسائی/ترمیم کرنے تک)، نیز پروگرامنگ کے تصورات جیسے لوپس، ریکریشن، اور بنیادی آپریٹرز کو کامیابی سے سرنی انٹرویو کے سوالات کا جواب دینے کے لیے۔ مسئلے کو پوری طرح پہچانیں۔
اگر آپ کے کوئی سوالات ہیں تو آپ کو وضاحت طلب کرنی چاہیے۔ مسئلے کو مزید قابل انتظام حصوں میں تقسیم کرنے کے بارے میں سوچئے۔ پروگرامنگ شروع کرنے سے پہلے یقینی بنائیں کہ آپ کے ذہن میں الگورتھم ہے۔ اسے لکھیں یا اسے فلو چارٹ میں دیکھیں۔ پھر کوڈ لکھنا شروع کریں۔
جواب دیجئے