სარჩევი[დამალვა][ჩვენება]
- 1. როგორ განვსაზღვროთ მასივი?
- 2. დინამიური მასივები: რა არის ისინი? რა განასხვავებს მათ ძირითადი მასივებისგან?
- 3. როგორ განსხვავდება მასივი და ლექსიკონი ერთმანეთისგან?
- 4. ჩამოთვალეთ მასივების ზოგიერთი დადებითი და უარყოფითი მხარე.
- 5. რას გულისხმობს „Sparse Array“?
- 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 ტექნიკურ ბიზნესთან.
კოდირების ინტერვიუების უმეტესობაში, ის მეორე ადგილზეა სტრინგზე. მასივი არის დაკავშირებული მონაცემთა ელემენტების დაჯგუფება, რომლებიც ინახება ერთმანეთთან ახლოს მეხსიერებაში.
რადგან ისინი დაკავშირებულია პროგრამირების ყველა ენასთან, როგორიცაა C, C++, Java, Python, Perl და Ruby, ისინი ყველგან არიან. განაგრძეთ კითხვა კოდირების პრაქტიკული გამოწვევებისთვის და ინტერვიუს კითხვები და პასუხები მასივების საფუძველზე.
პითონი გამოყენებული იქნება ამ პოსტში კოდირების საკითხების მოსაგვარებლად, რადგან ის მარტივი გამოსაყენებელია, გასაგები და ჩვენგანი უმეტესობისთვის ნაცნობი უნდა იყოს.
მოდით დავიწყოთ.
1. როგორ განვსაზღვროთ მასივი?
- დაკავშირებული მონაცემთა ტიპების ჯგუფი არის მასივი.
- მასივები ყოველთვის ფიქსირდება.
- იგივე ტიპის ცვლადი ინახება რამდენიმე ადგილას მასივის ობიექტების მიერ.
- პრიმიტიული ტიპები და ობიექტების მითითებები ორივე თავსებადია მასთან.
2. დინამიური მასივები: რა არის ისინი? რა განასხვავებს მათ ძირითადი მასივებისგან?
ავტომატური მასშტაბირება, რომელსაც დინამიური მასივები (ასევე მოიხსენიებენ როგორც მზარდი მასივები, ზომის შეცვლადი მასივები, ცვალებადი მასივები ან ArrayLists ჯავაში) უზრუნველყოფს მნიშვნელოვანი უპირატესობა.
თქვენ ყოველთვის უნდა იცოდეთ რამდენ ელემენტს შეინახავს თქვენი მასივი წინასწარ, რადგან მასივებს აქვს ფიქსირებული ზომა. მეორეს მხრივ, დინამიური მასივი იზრდება მასში დამატებითი წევრების დამატებისას, ასე რომ თქვენ არ გჭირდებათ წინასწარ იცოდეთ მისი ზუსტი ზომა.
3. როგორ განსხვავდება მასივი და ლექსიკონი ერთმანეთისგან?
ეს არის ინტერვიუს კითხვების საფუძვლებზე დაფუძნებული მასივი, რომლებიც რეგულარულად სვამენ. ქვემოთ მოცემულია ძირითადი განსხვავებები მასივებსა და ლექსიკონებს შორის:
- მასივი არის მსგავსი ნივთების შეკვეთილი სია. ლექსიკონს, თავის მხრივ, აქვს გასაღები-მნიშვნელობის წყვილი.
- მასივის ზომები შეიძლება დინამიურად შეიცვალოს. ასეთი დინამიური იდეები ლექსიკონებში არ არსებობს.
- მასივის გამოყენებამდე უნდა იყოს მითითებული მისი ზომა. ლექსიკონის ზომები არ საჭიროებს მორგებას.
- გამოიყენეთ Redim განცხადება, თუ გსურთ გააფართოვოთ მასივის ზომა. ლექსიკონებში ელემენტი შეიძლება დაემატოს დეკლარაციის გარეშე.
4. ჩამოთვალეთ მასივების ზოგიერთი დადებითი და უარყოფითი მხარე.
უპირატესობები:
- მასივებს შეუძლიათ რამდენიმე ელემენტის ერთდროულად დალაგება.
- სხვა მონაცემთა სტრუქტურები, როგორიცაა სტეკები, რიგები, დაკავშირებული სიები, ხეები, გრაფიკები და ა.შ., შეიძლება განხორციელდეს მასივში.
- ინდექსი შეიძლება გამოყენებულ იქნას მასივის ელემენტის მისაღწევად.
ნაკლოვანებები:
- მასივის ზომა წინასწარ უნდა იყოს გამოცხადებული. მასივის გამოცხადების მომენტში, ჩვენ შეიძლება არ ვიცოდეთ საჭირო ზომა.
- მასივის სტრუქტურა სტატიკურია. ეს ნიშნავს, რომ მასივის ზომა ყოველთვის ფიქსირდება და მეხსიერების განაწილება არ შეიძლება გაიზარდოს ან შემცირდეს.
5. რას გულისხმობს „Sparse Array“?
იშვიათი მასივი არის მონაცემთა მასივი, რომელსაც აქვს ბევრი ჩანაწერი ნულოვანი მნიშვნელობებით. ამის საპირისპიროდ, მკვრივი მასივი შეიცავს მისი ელემენტების უმრავლესობას არანულოვანი მნიშვნელობებით. მწირი მასივის ინდექსები, რომლებიც რიცხვებს ობიექტებად გარდაქმნის, შეიძლება შეიცავდეს ხარვეზებს. HashMap-თან შედარებით, ისინი მეხსიერების უფრო ეფექტურია.
6. როდის აირჩევთ დაკავშირებულ სიას მასივზე?
მასივების ნაცვლად დაკავშირებული სიების გამოყენებისას გაითვალისწინეთ:
- თქვენ არ გჭირდებათ რაიმე ელემენტი შემთხვევითი წვდომისთვის.
- სადაც დროებითი პროგნოზირება აუცილებელია, საჭიროა მუდმივი დროის ჩასმა და ამოღება სიიდან.
- პრიორიტეტული რიგის შესაქმნელად, შეიძლება დაგჭირდეთ ელემენტების განთავსება სიის ცენტრში.
- წარმოდგენაც არ გაქვთ, რამდენი იქნება სია. თუ მასივის ზომა იზრდება, თქვენ უნდა ხელახლა გამოაცხადოთ და დააკოპიროთ მეხსიერება, ისევე როგორც მარტივი მასივების შემთხვევაში.
7. რით განსხვავდება ინდექსირებული მასივი ასოციაციური მასივისაგან?
ასოციაციურ და ინდექსირებულ მასივებს შორის ძირითადი განსხვავებები მოცემულია შემდეგ ცხრილში.
- გასაღები-მნიშვნელობის წყვილი ტექსტის ან რიცხვითი ფორმატის გამოიყენება ასოციაციური მასივის დასალაგებლად. ინდექსირებული მასივის კლავიშები ყველა ციფრულია და თითოეული გასაღები დაკავშირებულია განსხვავებულ მნიშვნელობასთან.
- ასოციაციურ მასივში გასაღები შეიძლება იყოს სტრიქონი. ინდექსირებული მასივი 0-დან დაწყებული მთელი კლავიშებით.
- ორსვეტიანი ცხრილი ასახავს ასოციაციური მასივის ქცევას. ერთსვეტიანი ცხრილის მსგავსია ინდექსირებული მასივები.
- რუკები ასოციაციური მასივის ტიპია. ინდექსის მასივი არ არის რუკა.
8. რა უპირატესობა აქვს Heap-ს დახარისხებულ მასივებთან შედარებით?
დალაგებულ მასივებზე გროვის გამოყენების დროის ეფექტურობა მთავარი უპირატესობაა. მიუხედავად იმისა, რომ გროვის ოპერაციები უფრო სწრაფია, მასივის დახარისხება დიდ დროს მოითხოვს. გროვას შეუძლია აღმოაჩინოს უმცირესი ელემენტი ბევრად უფრო სწრაფად, ვიდრე მასივის დახარისხება.
რიცხვების მოცემული კოლექცია შეიძლება განლაგდეს ორიდან ერთ-ერთი გზით დახარისხებული მასივების გამოყენებით. მეორეს მხრივ, რიცხვების მოცემული კოლექციისთვის შეიძლება იყოს ერთზე მეტი პოტენციური გროვა.
9. შეგვიძლია განვსაზღვროთ მასივის ზომა უარყოფითი?
არა, ჩვენ არ შეგვიძლია განვსაზღვროთ უარყოფითი მთელი რიცხვი, როგორც მასივის ზომა. არ იქნება შედგენის დროის შეცდომა, თუ ჩვენ ვაცხადებთ. მუშაობის დროს, ჩვენ შევხვდებით NegativeArraySizeException.
10. როგორ განვსაზღვროთ დაკარგული მთელი რიცხვი 1-დან 100 ელემენტიან მასივში?
სერიების ჯამი შეიძლება გამოითვალოს შემდეგი ფუნქციის გამოყენებით: n (n + 1) / 2
ეს ფუნქცია იმუშავებს მხოლოდ იმ შემთხვევაში, თუ მასივს არ აქვს დუბლიკატები ან აკლია ერთზე მეტი რიცხვი. აქვს თუ არა მასივს დუბლიკატი ელემენტები, შეგიძლიათ დაალაგოთ მასივი, რომ ნახოთ არის თუ არა ეკვივალენტური ელემენტები.
11. როგორ მოვძებნოთ ელემენტის ინდექსი მასივში?
ელემენტის ინდექსის აღმოჩენა შესაძლებელია წრფივი ან ორობითი ძიების საშუალებით. სანამ არ აღმოაჩენს საჭირო ელემენტის შესაბამისობას, წრფივი საძიებო ფუნქცია მოძრაობს მასივის თითოეულ ელემენტზე. ის აბრუნებს ინდექსს, როგორც კი შესატყვის ელემენტს აღმოაჩენს. შესაბამისად, წრფივი ძიების დროითი სირთულე არის O. (n). როგორც დალაგებულ, ისე დაუხარისხებელ მასივს შეუძლია გამოიყენოს წრფივი ძებნა.
ორობითი ძიების გამოყენებით, რომელიც განუწყვეტლივ ყოფს მასივს შუაზე, სანამ ინტერვალის მედიანა არ ემთხვევა საჭირო ელემენტს და უზრუნველყოფს ინდექსს, შეგიძლიათ მიიღოთ ელემენტის ინდექსი, თუ მასივი დალაგებულია. შესაბამისად, ბინარული ძიების დროითი სირთულე არის O. (log n).
12. როგორ შეიძლება მასივიდან კონკრეტული ელემენტის მოშორება?
იმის გამო, რომ თქვენ არ შეგიძლიათ უბრალოდ წაშალოთ ელემენტები ორიგინალური მასივიდან, რადგან ისინი ფიქსირებული კომპლექტებია განსაზღვრული ზომით, ინტერვიუერი ეძებს, რომ შემოგთავაზოთ განსხვავებული მიდგომა და გაუმკლავდეთ პრობლემას, რომელსაც აჩენს შეკითხვა. მოქმედების საუკეთესო გზაა ახალი მასივის შექმნა ელემენტის წაშლის მიზნით. თქვენ შეგიძლიათ დააკოპიროთ ელემენტები პირველი მასივიდან ამ მასივში და შეიტანოთ მხოლოდ ის ელემენტი, რომლის წაშლაც გსურთ.
კიდევ ერთი სტრატეგია მოიცავს მასივში სამიზნე ელემენტის პოვნას და შემდეგ ყველა ელემენტის თანმიმდევრობის შეცვლას, რომლებიც სამიზნე ელემენტის მარჯვნივ არის.
13. როგორ შეიძლება დადასტურდეს ორი მასივის ტოლობა?
თქვენ ჯერ უნდა გადაამოწმოთ ორი მოწოდებული მასივის სიგრძე. ორივე მასივის შესატყვისი ერთეულები შედარებულია, როდესაც მათი სიგრძე ტოლია. ორი მასივი განიხილება როგორც თანაბარი. თუ კომპონენტების თითოეული წყვილი ყველა შესაბამისობაში ტოლია. ეს მიდგომა არ არის რეკომენდებული ორი მასივის ტოლობის შესამოწმებლად, თუ მასივები დიდი ზომისაა, რადგან ამას დიდი დრო დასჭირდება. თქვენ ასევე შეგიძლიათ გამოიყენოთ Equals() მეთოდი, რომელიც შედის Arrays კლასში, თუმცა, თუ ინტერვიუერი მოგთხოვთ შეადაროთ ორი მასივი ჩაშენებული მეთოდების გამოყენების გარეშე, ეს გზა სასარგებლო იქნება.
14. როდესაც განვიხილავთ მასივებს, რას გულისხმობთ ფრაზებში „განზომილება“ და „ქვემოწერა“?
მასივის „განზომილება“ არის ინდექსების, ანუ ქვესკრიპტების რაოდენობა, რომლებიც საჭიროა თითოეული ინდივიდუალური წევრის იდენტიფიცირებისთვის. ხელმოწერები და ზომები შეიძლება გაურკვეველი იყოს. განზომილება არის ნებადართული გასაღებების დიაპაზონის აღწერა, ხოლო ხელმოწერა არის რიცხვი. მასივის თითოეული განზომილებისთვის საჭიროა მხოლოდ ერთი ხელმოწერა.
მაგალითად, მასივს 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 ინდექსების შევსება 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}
გამომავალი იქნება {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[] და 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. რა არის წვიმის წყლის დაჭერის პრობლემა?
ყველაზე მეტი წყლის პოვნა, რომელიც შეიძლება იყოს ხაფანგში მოცემულ ზოლებში თითო ერთეულის სიგანით, ცნობილია, როგორც "ნალექის დაჭერის" საკითხი.
მიზანია დაადგინოთ ყველაზე მაღალი ზოლი, რომელიც შეიძლება განთავსდეს თითოეული ზოლის მარცხნივ და მარჯვნივ. მარცხნივ და მარჯვნივ წამყვანი ზოლების მინიმუმი, მიმდინარე ზოლის სიმაღლეზე ნაკლები, არის წყლის რაოდენობა, რომელიც ინახება თითოეული ზოლის თავზე.
დასკვნა
მონაცემთა სტრუქტურის სხვა თემებთან შედარებით, მასივები უფრო მარტივია. ასის მასივის ინტერვიუს კითხვების დასადგენად, თქვენ უნდა გქონდეთ მასივების ფუნდამენტური გაგება.
თქვენ უნდა ვრცლად გადახედოთ მასივების საფუძვლებს, მათ შორის მასივის ოპერაციებს (მაივის გამოცხადებიდან/შექმნიდან მასივის ელემენტებზე წვდომამდე/მოდიფიკაციამდე), ასევე პროგრამირების ცნებები, როგორიცაა მარყუჟები, რეკურსია და ძირითადი ოპერატორები, რათა წარმატებით უპასუხოთ მასივის ინტერვიუს კითხვებს. სრულად აღიარეთ საკითხი.
თქვენ უნდა მოიძიოთ განმარტება, თუ გაქვთ რაიმე შეკითხვა. იფიქრეთ საკითხის უფრო მართვად ნაწილებად დაყოფაზე. პროგრამირების დაწყებამდე დარწმუნდით, რომ გაითვალისწინეთ ალგორითმი; ჩაწერეთ იგი ან წარმოიდგინეთ იგი სქემაში. შემდეგ დაიწყე კოდის წერა.
დატოვე პასუხი