გიოლეკვა

მინდა შემოგთავაზოთ ჩემი მეგობრის დავით რაჭველიშვილის პოსტი, რომელიც ჯერ თავის თავს გაგაცნობთ ხოლო შემდეგ მოგიყვებათ თავის ძალიან საინტერესო ისტორიას.

სანამ ძირითად თემაზე გადავიდოდი მინდა ყველას გაგეცნოთ, რომ გქნოდეთ წარმოდგენა ჩემს შესახებ. მე ვარ დავით რაჭველიშვილი(რაჭველა), 2008 წელს დავამთავრე თბილისის სახელმწიფო უნივერსიტეტი და ეხლა ვმუშაობ რამოდენიმე ადგილას ჯავა პროგრამისტად, ასევე ჩემს მეგობრებთან ერთად ვარ GeOlymp-ის დამფუძნებელი. უნივერსიტეტის დაწყებისას მე მხოლოდ C/C++ საბაზისო ცოდნა მქონდა და პირველივე დღეებიდან დავიწყე ინფორმატიკის ოლიმპიადებში მონაწილეობის მიღება. გზა საკმაოდ რთული იყო ვინაიდან არ გამაჩნდა არანაირი ცოდნა, მაგრამ საკუთართავზე ბევრი მუშაობის შედეგად მოვედი დღევანდელ დღემდე. მას შემდეგ 6 წელზე მეტი გავიდა და კიდევ დიდი სიამოვნებით ვწერ პროგრამირების შეჯიბრებებს და ვსწავლობ ახალახალ ალგორითმებს. ეხლა გადავიდეთ მთავარზე...

ვინც ლეკვას ბლოგს კითხულობთ კარგად გემახსოვრებათ მისი და facebook-ის ურთიერთობის ისტორია, რამაც ჩემზე დიდი შთაბეჭდილება მოახდინა და მაგალითი მომცა რომ მეც მეცადა ბედი. უამრავ ადგილად გავაგზავნე ჩემი CV და ყველამ უარი მითხრა, მაგრამ ამ დროს გამოჩნდა Facebook რომლიც TopCoder-ის ჩემპიონატის ერთერთ მთავარ სპონსორად მოგვევლინა. მეც ვიფიქრე გამოვიყენებ ამ შანს და ტოპკოდერის საიტზე დავაჭირე “Apply” ღილაკს.

დიდი ხნის ლოდინი არ დამჭირდა, 2 დღეში ჩემს ინბოქსში გამოჩნდა წერილი კინჰ დემარისგან, რომელიც მეკითხებოდა თუ ვიყავი დაინტერესებული მათან მუშაობაზე. მეც მაშინვე მივწერე პასუხი და დავნიშნეთ პირველი გასაუბრება.

გასაუბრება I

პირველი გასაუბრება, როგორც ყოველთვის ზოგადი ხასიათის იყო. ამიხსნა ვინ იყო, რა უნდოდა, რა ხდებოდა FB-ში. შემომთავაზა სტაჟირებისათვის ჩაგიტარებთ გასაუბრებებსო, როგორც სტუდენტსო. მე ცალსახად გადაწყვეტილი მქონდა რომ სრულ განაკვეთზე მინდოდა მუშაოაბა და თუ ამიყვანდნენ უნივერსიტეტს მივატოვებდი. ეს ყველაფერი ავუხსენი და გადაწყდა რომ ორივე პოზიციაზე განმიხილავდნენ. ამის შემდეგ ჩემდა გასაკვირვად კითხვები დამისვა ჯავაზე, საკმაოდ მარტივი კითხვები, შემამოწმა რამე ვიცოდი თუ არა. ესე დასრულდა პირველი გასაუბრება...

გასაუბრება II

ეს გასაუბრება თავიდანვე ცუდად დაიწყო, ვერაფრით ვერ დამირეკა ტელეფონზე და გადავწყვიტეთ, რომ სკაიპით დამიკავშირდებოდა. მაგრამ ახალი დაწყებული გვქონდა საუბრარი, რომ ზარი გაწყდა, რამაც ძალიან დამძაბა. თუმცა ამის შემდეგ უკვე კავშირის პრობლემა აღარ გვქონია. ეს ინტერვიუც როგორც ველოდი დაიწყო ზოგადი საუბრებით, ამიხსნა ვინ იყო, რას აკეთებდა. აღმოჩნდა რომ სტენდფორდის ალუმნი იყო, 9 თვეა რაც FB security ჯგუფის წევრია და ეს მისი პირველი სამსახური იყო. პირველი კითხვა რაც დამისვა იყო, თუ რატომ ვიღებდი მონაწილეობებს ამდენ შეჯიბრებებში. ლეკვასგან დარიგებული რომ რაც შეიძლება ბევრი მელაპარაკა. მოვუყევი მთელი ჩემი ისტორია პირველი კურსის შემდეგ. შემდეგ იყო კითხვები Java-ზე და C++ -ზე, შევადარეთ ერთმანეთს, მკითხა თუ რატომ გადავედი C++ დან Java-ზე. ამას მოყვა კითხვები Python-ზე, რამაც მაგარად დამაბნია. CV-ში მეწერა რომ პითონი ვიცოდი დამწყების დონეზე, მაგრამ მაინც დამისვა კითხვები. შევადარეთ მკაცრად ტიპიზირებული და არა ტიპიზირებული ენები, რა პლიუსები და მინუსები აქვთ, სად რისი გამოყენება ჯობია. ამ კითხვებზე პასუხები ადგილზე მოვიფიქრე, იმიტომ რომ მანამდე თითქმის არ მქონია შეხება არა ტიპიზირებულ ენებთან, რაც ძალიან მოეწონა მას.

და აი ამის შემდეგ მივედით კოდის წერამდე, პირველი დავალება იყო BFS (Bread First Search), რომელიც მანამდე ძალიან ბევრჯერ დამიწერია შეჯიბრებების დროს და ადვილად გავართვი თავი. შემდეგ მთხოვა დამეწერა რიცხვიდან ფესვის ამოღების ფუნქცია მოცემული P სიზუსტით, ისე რომ სტანდარტული sqrt() არ გამომეყენებინა. ესეც ადვილად დავუწერე ორობითი ძებნის მეთოდით, სამწუხაროდ ამ კოდში ბაგი მქონდა, არასწორედ ვახდენდი ცვლადების ინიციალიზაციას, რომელიც მალევე ვიპოვე. და ბოლო დავალება იყო დამეწერა ფუნქცია რომელიც LinkedList-ს შეაბრუნებდა.

კოდის წერის დროს საკმაოდ ბევრს ველაპარაკებოდი და რაღაცეებზე ვხუმრობდით კიდეც, რამოდენიმეჯერ კარგადაც ვიცინეთ. ბოლოს ჩემი კითხვების დრო დადგა, ამაზეც ვიყავი გაფრთხილებული ლეკვასგან რომ ბევრი კითხვები უნდა დამესვა. ვკითხე თუ რას ნიშნავს იყო FB ინჟინერი, რა დეველოპმენტ თულზებს იყენებენ, რა ენებზე შეიძლება წერა, თუ ყოფილა რაიმე დიდი შემოტევა FB-ზე რომელიც ჩელენჯი იყო მისი გუნდისათვის. ამაზე ამომწურავი პასუხები გამცა და დავემშვიდობეთ კარგად.

ინტერვიუს შემდეგ საკმაოდ დადებითად ვიყავი განწყობილი და მოვძებნე ინტერვიუერი FB-ში. ძებნისას მის ერთ საკმაოდ საინტერესო ვიდეო წავაწყდი: ვიდეო იწყება და თვითონ ლაპრაკობს, რომ მისი ძმის მეგობრებს არ ჯერათ რომ FB-ში მუშაობს და ვერაფრით ვერ ამტკიცებს ამას, და ამიტომ ჩაიწერა ეს ვიდეო, ამ დროს კამერას აბრუნებს და ჩანს მარკ ცუკენბერგი, რომელიც ამბობს, ბიჭებო დაუჯერეთ ამ კაცს ის მართლა ჩემთან მუშაობსო . მარტო ეს ვიდეოც კი განსაზღვრავს თუ როგორი სიტუაცია FB-ში.

გასაუბრება III

წინა გასაუბრების შემდეგ მალევე დამიკავშირდა რეკრუიტერი და შემდეგი ინტერვიუც დავნიშნეთ. ვერც ამ ინტერვიუერმა დამირეკა ტელფონზე და ამასთანაც სკაიპით ვისაუბრეთ. ეხლაც ყველაფერი სტანდარტულად დაიწყო, მომიყვა თავის შესახებ და შემდეგ კითხვები დამისვა ჩემი პროექტების შესახებ: მანამდე რა გამიკეთებია, რომელი პროექტი იყო ყველაზე საინტერესო და რატომ, რას შევცვლიდი შენ პროექტებში ეხლა რომ შეგეძლოსო – ამზე პირდაპირ ვუპასუხე რომ აბსოლუტურად ყველაფერს თქო

შემდეგ კოდირებაზე გადავედით. ორი პროგრამა დამაწერიანა, ორივე რეკურსია იყო და საკმაოდ ადვილად გავრთვი თავი. მეორე იყო N ლაზიერის ამოცანა, ფუნქციას უნდა დაებრუნება ან კი ან არა, იმის მიხედვით შეიძლებოდა თუ არა ლაზიერების დასმა დაფაზე ისე რომ ერთმანეთს არ დამუქრებოდნენ. ამაზე მე დავუწერე, რომ თუ N განსხვავებულია ორისგან და სამისგან, მაშინ პასუხი ყოველთვის “კი” არის მაგრამ მაინც დამაწერინა რეკურსია.

შემდეგ ჩემი კითხვების დრო მოვიდა, ვკითხე თუ როგორი იყო ერთი დღე FB-ში, რა ბონუსები აქვთ თანამშრომლებს, ასევე ვკითხე Cassandra, მითხრა რომ inbox-ის ინდექსირებისათვის იყენებენ და მათი სისტემა დაახლოებით 100 node-ისგან შედგება. შემდეგ ვილაპარაკეთ Thrift-ზე და ამასაც ტკბილად დავემშვიდობე.

გასაუბრება IV

როგორც აღომჩნდა წინა ინტერვიურს მოვეწონე და მეოთხე ინტერვიუც მალე დავნიშნეთ. ინტერვიუ გვიან დავიწყეთ, პრობლემები ქონდა ტელეფონზე დარეკვასთან. აქაც სტანდარტულად დავიწყეთ ზოგადი საუბრებით, და გავაგრძლეთ კოდირებით. პირველი პროგრამა რაც დამაწერინა იყო რომელიღაც ჩემთვის მანამდე უცნობი დაფაზე თამაშის სვლის სიმულაცია უნდა გამეკეთებინა. ამის შემდეგ დამაწერინა Composite იტერატორი next(), hasNext() და remove() მეთოდით, ანუ ისეთი იტერატორი რომელიც Collection-ების Collection-ებზე მოახდენდა იტერირებას უკვე არსებული სტანდარტული იტერატორის გამოყენებით. ამის წერისას როდესაც ბოლოში გავედი მივხვდი, რომ რაღაც არ მქონდა გათვალისწინებული და ის რაც დავწერე არ იმუშავებდა, ამიტომ საჭირო გახდა კოდში დიდი ცვლილებების შეტანა. შევთავაზე ორი გზა გასწორების, მაგრამ დიდი ხანია უკვე ვლაპრაკობთო და არ დამამთავრებინა. ამაზე მაგარად გავბრაზდი და უკვე იმედი მქონდა დაკარგული რომ შემდეგ ინტერვიუზე დამპატიჟებდნენ.

ამის მერე მე დავუსვი კითხვები, ველაპარაკე Open Graph-ის შესახებ, ვკითხე თუ აპირებდნენ like-ის გარდა ახალი კავშირის შემოტანას, რაზეც მიპასუხა, რომ ფიქრობენ მაგრამ არ უნდათ რომ გაართულონ პროტოკოლი ამიტომ ჯერ გადაწყვეტილება არ მიუღიათ. ასევე ვკითხე თუ აპირებდნენ ინდექსირება/ძებნას ახალ ნოუდებში, ამაზეც იგივე ტიპის პასუხი მივიღე, რომ სურთ მაგრამ ჯერ ფიქრობენ როგორ გააკეთებენ. ამით დასრულდა ბოლო სატელეფონო ინტერვიუ.

და დაიწყო ნერვების თამაში, ერთი კვირის მანძლიზე ველოდებოდი მათგან პასუხს, დამპატიჟებენ თუ არა დასწრებულ გასაუბრებაზე. ბოლო წარუმატებელი ინტერვიუს შემდეგ საკმაოდ პესიმისტურად ვიყავი განწყობილი და მხოლოდ პატარა იმედი მქონდა. ნერვიული დღეების შემდეგ, ხუთშაბათ დილის 7 საათზე დამხვდა წერილი, რომელიც მამცნობდა, რომ მოვეწონე ყველას და მზად არიან ჩამიყვანონ კალიფორნიაში, პალო ალტოში მე-5-ე გასაუბრებისათვის. ჩემს რეაქციაზე აღარაფერ მოვყვები, ყველა მიხვდებოდით რა დამემართებოდა. აქ შევწყვეტ მოყოლას და დანრჩენს კალიფორნიიდან დაბრუნების შემდეგ მოგიყვებით.

მინდა წარმატება ვუსურვო რაჭველას და დარწმუნებული ვარ რომ ყველაფერი კარგად დამთავრდება . ასე რომ დარჩით ჩვენთან გაგრძელება იქნება

ინფორმატიკის ოლიმპიადებისთვის ჩემი ცხოვრების და დროის საკმაოდ დიდი დრო მქონდა დათმობილი.

• 7-ე კლასიდან ვმონაწილეობდი სასკოლო ოლიმპიადებში.
• 2006 წელს ავიღე ბრინჯაოს მედალი მოსწავლეთა საერთაშორისო ოლიმპიადაზე მექსიკაში
• ხოლო წელს აპრილში თსუ-ს გუნდმა, რომლის ერთერთი წევრიც მე ვიყავი აიღო ასევე ბრინჯაოს მედალი მსოფლიოს საერთაშორისო გუნდურ ოლიმპიადაზე სტუდენტთა შორის (შედეგები).
• ასევე TopCoder-ის საკმაოდ აქტიური წევრი ვიყავი.

ეს იყო მოკლე შესავალი ჩემი საოლიმპიადო გამოცდილებიდან, რომელმაც თავისი შედეგი გამოიღო . სწორედ TopCoder-ზე სადღაც ნახევარი წლის წინ Facebook-მა გამოაქვეყნა განცხადება, რომ თუ ვინმე დაინტერესებული იყო მათთან მუშაობით, შეეძლოთ გაეგზავნათ თავიანთი CV რასაც განიხილავდნენ და მოწონების შემთხვევაში დაუკავშირდებოდნენ. მეც რათქმაუნდა გავაგზავნე ჩემი CV. მაშინვე არავინ არ დამკავშირვებია და რათქმაუნდა გადამავიწყდა კიდეც ეს ამბავი. თუმცა ორი კვირის წინ, 11 ნოემბერის საღამოს, როცა უკვე დაძინებას ვაპირებდი მივიღე წერილი ვინმე სარასგან, რომელიც არის Facebook-ის ერთ-ერთი რეკრუიტერი. წერილში ეწერა რომ სამწუხაროდ გვიან ნახეს ჩემი გაგზავნილი CV, რომელიც მოეწონათ და სურდათ ჩემთან გასაუბრება . წერილის წაკითხვის შემდეგ ისეთ ემოციებში ჩავვარდი კარგა ხნის განმავლობაში საღად აზროვნების უნარი დავკარგე , თუმცა ერთ-ერთ მეგობართან ემოციების გაზიარების და დამშვიდების შემდეგ (რასაც დაახლოებით ნახევარი საათი დაჭირდა ), მივწერე ჩემი მობილურის ნომერი და ვუთხარი რომ ხვალ საღამოს შემეძლო მათი ზარისთვის მეპასუხა. საღამოს იმიტომ რომ თბილისსა და Palo Alto-ს შორის (სადაც FB-ს სათაო ოფისია) 12 საათია განსხვავება. სამწუხაროდ ვერ მოვახერხე face to face გასაუბრებაზე მოხვედრა , თუმცა კიდევ ერთი საინტერესო ამბავი გადამხდა თავს, რომლის მოყოლაც არასდროს დამეზარება .

გასაუბრება I - 12 ნოემბერი: მართლაც მეორე დღის საღამოს 10 საათზე დარეკა სარამ . თავიდან მომიყვა თავის შესახებ თუ ვინ არი და რას წარმოადგენს (ადრე YouTube-ში მუშაობდა), შემდეგ კი ჩემი ინტერესების შესახებ მკითხა და საერთოდ ვიყავი თუ არა დაინტერესებული Facebook-ში მუშაობით . საუბრის ბოლოს, რომელიც სულ რაღაც 15 წუთი გაგრძელდა, შემითანხმდა მომდევნო გასაუბრებაზე რომელიც უკვე თექტნიკური იქნებოდა.

გასაუბრება II - 14 ნოემბერი: საღამოს 11 საათზე დარეკა Facebook-ის ერთ-ერთმა დეველოპერმა, სახელად ტიმი . აქ უკვე დამისვეს შეკითხვები ალგორითმების შესახებ და დამაწერინა 3 ძალიან მარტივი ამოცანა:

• მოცემული გვაქვს ორი სტრიქონი, უნდა ვიპოვოთ მოიძებნება თუ არა ერთი მეორეში.
• მოცემული გვაქვს სტრიქონების მასივი და ერთად უნდა დავაჯგუფოთ სტრიქონები, რომლებიც ერთმანეთის ანაგრამები არიან. თუ ერთი სტრიქონი მიიღება მეორის სიმბოლოების გადანაცვლებით, მაშინ ისინი არიან ერთმანეთის ანაგრამები.
• ცნობილი დახურდავების ამოცანა: მოცემული გვაქვს თანხა და უნდა ვიპოვოთ რამდენნაირად შეიძლება მისი დახურდავება წინასწარ განსაზღვრული ხურდების გამოყენებით.

ამ ამოცანებს საკმაოდ ადვილად გავართვი თავი. საუბრის ბოლოს მითხრა რომ მე შემეძლო მისთვის კითხვების დასმა . იმის გამო რომ ჯერ კიდევ 4-ე კურსზე ვარ, ვკითხე აქვთ თუ არა რაიმე შეზღუდვა თანამშრომლის მინიმალურ ასაკზე და აქცევენ თუ არა ყურადღებას უნივერსიტეტის დიპლომს, რაზეც პასუხად მივიღე რომ FB-ს თანამშრომლების ნახევარს დიპლომი საერთოდ არ აქვს . საუბარი დაახლოებით 25 წუთი გაგრძელდა.

ამ გასაუბრების დამთავრების თანავე სარამ მომწერა წერილი, რომ ტიმს მოეწონა ჩემთან საუბარი და უნდოდათ კიდევ 2 სატელეფონო გასაუბრების დანიშვნა. თარიღებზე რათქმაუნდა მაშინვე შევთანხმდით .

გასაუბრება III - 16 ნოემბერი: ისევ საღამოს 11-ზე რეკავს ვინმე პენსლერი, რომელმაც ისევ სტანდარტულად თავის თავზე მომიყვა, ხოლო შემდეგ დამაწერინა 2 ამოცანა:

• მოცემული გვაქვს Linked List, უნდა დამეწერა მეთოდი რომელსაც გადაეცემა სიის სათავე, ხოლო უნდა დააბრუნოს მოცემული სიის შებრუნებული სიის სათავე . ანუ თუ მოცემული გვაქვს სია 1 -> 2 -> 3 უნდა დაგვებრუნებინა 3 -> 2 -> 1.

  ორი გზა არსებობს ამ ამოცანის ამოხსნის: ერთი რეკურსიული, ხოლო მეორე პირდაპირ ერთი ციკლის გამოყენებით. დაწერით პირველი დავუწერე, ხოლო თქმით ზეპირად მეორეც ვუთხარი.

• მითხრა C/C++ ზე დამეწერა ორი დიდი რიცხვის (Java-ში BigInteger) გადამრავლების რეალიზაცია. რაც მალევე დავუწერე, რის შემდეგაც დამისვა კითხვები თუ როგორ შეიძლებოდა ჩემი დაწერილი კოდის გაუმჯობესება/ასწრაფება. ვუთხარი რომ მისი ერთ-ერთი გაუმჯობესების გზა არის გამოთვლების ჩატარება ათობითი სისტემის მაგივრად რაიმე უფრო დიდ სისტემაში მაგალითად ათასობითში, სამწუხაროდ არ მომაფიქრდა სისტემის ფუძედ ამეღო ორის ხარისხი, რომლის შემთხვევაში მათემატიკური ოპერაციები კიდევ უფრო სწრაფად სრულდება.

სამწუხაროდ საკმაოდ ვინერვიულე ამ გასაუბრების დროს, რასაც ხელი შეუწყო შუა საუბარში სატელეფონო ზარის გაწყვეტამ . მე თვითონ არ ვიყავი ჩემი თავით კმაყოფილი და საუბრის ბოლოს წარმოდგენა არ მქონდა მოეწონა თუ არა პენსლერს ჩემთან საუბარი, რაღაც მომენტში ვიფიქრე კიდეც რომ მეოთხე/ბოლო გასაუბრება არ შედგებოდა , რაც საბედნიეროდ ასე არ აღმოჩნდა .

გასაუბრება IV - 19 ნოემბერი წინა დღით მომწერა სარამ და მითხრა კარგად მოვმზადებულიყავი, რადგან ამ გასაუბრების შემდეგ გადაწყდებოდა მომიწევდა თუ არა კალიფორნიაში ჩასვლა onsite გასაუბრებაზე . რათქმაუნდა ისევ საღამოს 11-ზე რეკავს მომდევნო FB-ს დეველოპერი, რომელსაც თუ სწორად მახსოვს მარკი ერქვა. მანაც ორი ამოცანა დამაწერინა:

• პირველი დამისვა ორობითი არასრული ხის შემოვლის ამოცანა: Tree Traversal.
• ხოლო მეორე ამოცანა იყო სორტირებულ მასივში ორობითი ძებნის გამოყენებით რიცხვის მოძებნა: Binary Search. რაც მალევე დავუწერე, შემდეგ კი ცოტა გაართულა ამოცანა და მითხრა ამეხსნა ალგორითმი რომელიც მოძებნიდა რიცხვს წაძრულ/მობრუნებულ სორტირებულ მასივში (მაგ. 4 5 1 2 3). ამ ამოცანის ამოსახსნელად ჯერ ორობითი ძებნით უნდა ვიპოვოთ რამდენით მოხდა მასივის მობრუნება (ზემოთ მოყვანილი მაგალითისთვის მობრუნების სიდიდეა 2), რის შემდეგაც შეგვიძლია მასივი გავყოთ ორ ნაწილად (პირველი 4 5, ხოლო მეორე 1 2 3) და შემდეგ თითოეულ ნაწილში მოვძებნოთ ასევე ორობითი ძებნით მოვძებნოთ მოცემული რიცხვი. ამ ალგორითმის მუშაობის დრო არის O(log N), ისევე როგორც პირდაპირ ორობითი ძებნის.

ამ გასაუბრების დროსაც ორჯერ გაწყდა ზარი . საუბრის ბოლოს მარკს ვკითხე თუ რას საქმიანობდა FB-მდე და მითხრა რომ 6 წელი მუშაობდა Microsoft-ში Windows Mobile-ზე .

ყველაზე მეტად ეს გასაუბრება მომეწონა.

საერთო ჯამში საათნახევარიანი სატელოფონო საუბრები დამთავრად იმით რომ ხუთშაბათს, 2 დღის წინ მივიღე წერილი ისევ სარასგან, რომელმაც მითხრა რომ ესაუბრა ჩემს გამსაუბრებლებს და ერთ-ერთს არ მოეწონა ჩემი დაწერილი კოდი , ამის გამო მომიბოდიშა და მითხრა რომ ამ ჯერზე შევწყვიტოთ ურთიერთობაო. თუმცა ამით საბოლოოდ არ გაწყვეტილა ჩემი და FB-ს ურთიერთობა , 9 თვეში ისევ დამიკავშირდებიან და გაგრძელდება გასაუბრებები .

ჩემდა გასაკვირად არცერთ გასაუბრებაზე არ დაუსვამთ არა ალგორითმული შეკითხვა, ვფიქრობდი დამისვამდნენ კითხვებს MySQL, Threading-ის ირგვლივ მაგრამ არც დაინტერესებულან რომელიმე მათგანი გამიგია თუ არა საერთოდ (მართლაც რომ გამიგია, მაგრამ არცერთი არ ვიცი კარგად ).

იმის მიუხედავად რომ ბევრს ვერაფერს მივაღწიე ამ გასაუბრების შედეგად, მაინც ძალიან კმაყოფილი ვარ. ძალიან დიდი გამოცდილება მივიღე. დავინახე თუ რაში მოვიკოჭლებ, პირველ რიგში ინგლისურში , კი მესმოდა ყველაფერი რასაც მელაპარაკებოდნენ და ჩემს ნათქვამსაც ვაგებინებდი, მაგრამ ეს არაა საკმარისი. ასევე უნდა გავიღრმავო ცოდნა პრაქტიკული პროექტების ხარჯზე.

ასე რომ 9 თვეში ელოდეთ მომდევნო პოსტს ამ თემასთან დაკავშირებით, რომელიც იმედია Happy End-ით დასრულდება .

პ.ს. იმ ხალხის გასაგონად, რომელიც თვლის რომ მათემატიკა და ზოგადად ალგორითმები არაფერში ჭირდება, მინდა გითხრათ რომ ძალიან ცდებით .

From Facebook Job Interview

From Facebook Job Interview

დღეს TopCoder-ის სერვერზე ჩატარდა რიგით 441-ე SRM (Single Round Match), რომლის ამოცანების ავტორიც გახლდით მე . საკმაოდ შრომატევადი იყო თვითონ ამოცანების მომზადების პროცესი, თუმცა ამავდროულად საინტერესოც. განსაკუთრებით საინტერესო იყო ტესტერებთან ურთიერთობა, რომლებიც ამოწმებდნენ ჩემს ამოხსნებს და პირობასთან დაკავშირებით მითითებებს მაძლევდნენ. მოკლედ რამოდენიმე გათეული ღამის შემდეგ, როგორც იქნა ყველა ამოცანა გამზადდა და ველოდები SRM-ის დაწყებას. რამაც ყველაზე მეტად გამაოცა იყო ის, რომ ამ SRM-ზე მონაწილეობის მისაღებად დარეგისტრირდა 2000 მომხმარებელი აქედან 600-მდე იყო სრულიად ახალი ამ სისტემაში და უმეტესობა ჩინელები, როცა ადრე მაქსიმალური ლიმიტი 1750 იყო. მე ამას იმით ავხსნიდი რომ ჩინეთში ალბათ რაიმე პატარა ყრილობაზე TopCoder უბრალოდ ახსენეს და იმ ყრილობაზე მყოფთა 10%-ს მაინც რომ გაეგონა ეგ უკვე კი არის 600 კაცი . ასეთი დატვირთვის გამო SRM-ის დაწყებამდე სადღაც 10 წუთით ადრე სერვერი გადაეტვირთათ, რის გამოც შეჯიბრი ოდნავ მოგვიანებით დაიწყო. ამის მიუხედავად SRM-მა და შესაბამისად ჩემმა "დებიუტმაც" ვფიქრობ წარმატებით ჩაიარა.

ახლა მოკლედ დავწერ ამოცანებს და მათ ამოხსნისათვის ჩემს მიერ გამოყენებულ იდეებს:

Division 2 / Level 1: DifferentStrings

ამოხსნა: არანაირი ზედმეტი დამტკიცება და ახსნა არ ჭირდება, ვფიქრობ კოდიდანაც გასაგები უნდა იყოს:

 1 public class DifferentStrings {
 2
 3     public int minimize(String A, String B) {
 4         int res = 1000;
 5
 6         for (int i = 0; i <= B.length() - A.length(); i++) {
 7             int cnt = 0;
 8
 9             for (int j = 0; j < A.length(); j++)
10                 if (A.charAt(j) != B.charAt(i + j)) cnt++;
11
12             res = Math.min(res, cnt);
13         }
14
15         return res;
16     }
17 }

Division 2 / Level 2: PaperAndPaintEasy

ამოხსნა: აქ დასადგენია (x1, y1) (x2, y2) მართკუთხედს ფურცლის მარცხენა და მარჯვენა (x = xfold წრფის მარცხენა და მარჯვენა მხარეს არსებული ფურცლის ნაწილები) მხარეებთან რა საერთო ფართობი აქვს, რასაც მთლიანი ფურცლის ფართობს გამოვაკლებთ და მივიღებთ შეუღებავი ფურცლის ფართობს.

 1 public class PaperAndPaintEasy {
 2     private long area(long x1, long y1, long x2, long y2, long xfold) {
 3         if(x1 >= xfold) return 0;
 4         x2 = Math.min(x2, xfold);
 5         return (x2-x1)*(y2-y1);
 6     }
 7
 8     public long computeArea(int width, int height, int xfold, int cnt, int x1, int y1, int x2, int y2) {
 9         long res = width;
10         res *= height;
11
12         cnt++;
13         res -= cnt*area(x1, y1, x2, y2, xfold);
14         res -= cnt*area(x1, y1, x2, y2, width-xfold);
15
16         return res;
17     }
18 }

Division 1 / Level 1: PerfectPermutation

აქ უნდა დავითვალოთ რამდენი "ციკლური" ჯგუფი არსებობს, თუ ასეთი ჯგუფების რაოდენობა ერთია მაშინ ამოცანაზე პასუხი არის 0, ხოლო წინააღმდეგ შემთხვევაში თვითონ ჯგუფების რაოდენობა. I[0], I[1], ..., I[k-1] მიმდევრობა არის ციკლური ჯგუფი თუ P[I[i]] = I[(i+1)%k], 0 <= i <= k-1.

 1 public class PerfectPermutation {
 2     public int reorder(int[] P) {
 3         int n = P.length, res = 0;
 4         boolean[] vis = new boolean[n];
 5
 6         for(int i = 0; i < n; i++)
 7             if(! vis[i]) {
 8                 res++;
 9                 for(int j = P[i]; j != i; j = P[j]) vis[j] = true;
10             }
11
12         if(res == 1) res = 0;
13         return res;
14     }
15 }

Division 2 / Level 3: PerfectPermutationHard

ამოხსნა: უნდა ვიპოვოთ ცოკლური ჯგუფები და დავალაგოთ ლექსიკოგრაფიულად. შემდეგ კი მეორედან დაწყებული ყოველი ჯგუფის ჩამატება უნდა ვცადოთ პირველ ჯგუფში პირველივე იმ პოზიციაზე რომელიც პირველ ჯგუფს ლექსიკოგრაფიულად უფრო პატარას ხდის.

 1 public class PerfectPermutationHard {
 2     public int[] reorder(int[] P) {
 3         int n = P.length, m = 0;
 4         boolean[] vis = new boolean[n];
 5         int[] sz = new int[n];
 6         int[][] cycles = new int[n][n+1];
 7
 8         for(int i = 0; i < n; i++)
 9             if(! vis[i]) {
10                 cycles[m][0] = i;
11                 sz[m] = 1;
12
13                 for(int j = P[i]; j != i; j = P[j]) {
14                     vis[j] = true;
15                     cycles[m][sz[m]++] = j;
16                 }
17
18                 m++;
19             }
20
21         if(m == 1) return P;
22
23         cycles[0][sz[0]] = 100;
24         int x = 0;
25         for(int i = 1; i < m; i++) {
26             for(; x < sz[0]; x++)
27                 if(cycles[0][x+1] > cycles[1][0]) break;
28
29             for(int j = sz[0]; j > x; j--) cycles[0][j+sz[i]] = cycles[0][j];
30             for(int j = 0; j < sz[i]; j++) cycles[0][x+j+1] = cycles[i][j];
31
32             sz[0] += sz[i];
33             x += sz[i];
34         }
35
36         cycles[0][n] = 0;
37         for(int i = 0; i < n; i++)
38             P[cycles[0][i]] = cycles[0][i+1];
39
40         return P;
41     }
42 }

Division 1 / Level 2: StrangeCountry

მე პირადად ყველაზე მეტად ეს ამოცანა მომწონს, ცოტა დაფიქრება ჭირდება რის მერეც საკმაოდ მარტივად იწერება ამოხსნა. თუმცა ამის მიუხედავად საკმაოდ ბევრს ჩაუვარდა ეს ამოცანა, რამაც მთლიანობაში SRM კიდევ უფრო საინტერესო გახადა.

ამოხსნა: ადვილი დასამტკიცებელია რომ თუ გრაფში წიბოების რაოდენობა ნაკლებია გრაფში წვეროების რადენობას მინუს ერთზე, მაშინ პასუხი უარყოფითია. წინააღმდეგ შემთხვევაში კი პასუხი არის გრაფში ბმული კომპონენტების რაოდენობას მინუს ერთი. კომპონენტი არის ბმული თუ მასში შემავალ ნებისმიერ ორ წვეროს შორის არის გზა.

 1 public class StrangeCountry {
 2     private int n;
 3     private boolean[] vis;
 4     private boolean[][] g;
 5
 6     private int dfs(int u) {
 7         int res = 0;
 8         vis[u] = true;
 9
10         for(int i = 0; i < n; i++)
11             if(g[u][i]) {
12                 g[u][i] = g[i][u] = false;
13
14                 if(vis[i]) res++;
15                 else res += dfs(i);
16             }
17
18         return res;
19     }
20
21     public int transform(String[] G) {
22         int k = 0, m = 0, l = 0;
23
24         n = G.length;
25         g = new boolean[n][n];
26         vis = new boolean[n];
27
28         for(int i = 0; i < n; i++) {
29             int cnt = 0;
30
31             for(int j = 0; j < n; j++) {
32                 g[i][j] = (G[i].charAt(j) == &#39;Y&#39;);
33                 if(g[i][j]) cnt++;
34             }
35
36             if(cnt == 0) return -1;
37         }
38
39         for(int i = 0; i < n; i++)
40             if(! vis[i]) {
41                 int t = dfs(i);
42
43                 if(t > 0) {
44                     k += t;
45                     l++;
46                 }
47                 else m++;
48             }
49
50         if(k-l+1 < m) return -1;
51         return l+m-1;
52     }
53 }

Division 1 / Level 3: PaperAndPaint

ეს საკმაოდ გართულებული ვარიანტია DIV2 L2 ამოცანის.

ამოხსნა: თავიდან დავადგინოთ ყოველი ოპერაციის მერე რა მართკუთხედები იღებება ფურცელზე საწყის მდგომარეობაში. ასეთი მართკუთხედების რაოდენობა შეიძლება იყოს 100,000. ამის შემდეგ შეგვიძლია გამოვიყენოთ საკმაოდ სწრაფი ალგორითმი Sliding Window (სამწუხაროდ ვერ მივაგენი რაიმე საინტერესო სტატიას მის შესახებ).

ასევე მისი ამოხსნა შეიძლება მონაცემთა სტრუქტურების გამოყენებით Segment Tree, Interval Tree. თუმცა როგორც აღმოჩნდა არსებობს კიდე უფრო მარტივი ალგორითმი მოცემული შეზღუდვებისათვის, რომელიც ზუსტად არ ვიცი როგორ არის.

  1 import java.util.ArrayList;
  2 import java.util.Arrays;
  3 import java.util.Comparator;
  4 import java.util.Iterator;
  5 import java.util.List;
  6 import java.util.Set;
  7 import java.util.TreeSet;
  8
  9 class Edge implements Comparable<Edge> {
 10
 11     int x, y1, y2;
 12     int id;
 13     int left;
 14     int leftX;
 15
 16     public Edge(int x, int y1, int y2, int id, int left, int leftX) {
 17         this.x = x;
 18         this.y1 = y1;
 19         this.y2 = y2;
 20         this.id = id;
 21         this.left = left;
 22         this.leftX = leftX;
 23     }
 24
 25     public int compareTo(Edge e) {
 26         if(this.x < e.x) return -1;
 27         if(this.x > e.x) return 1;
 28         if(this.left < e.left) return -1;
 29         if(this.left > e.left) return 1;
 30         if(this.y1 < e.y1) return -1;
 31         if(this.y1 > e.y1) return 1;
 32         if(this.y2 < e.y2) return -1;
 33         if(this.y2 > e.y2) return 1;
 34         return 0;
 35     }
 36 }
 37
 38 class EdgeComparator implements Comparator<Edge> {
 39
 40     public int compare(Edge a, Edge b) {
 41         if (a.y1 < b.y1) return -1;
 42         if (a.y1 > b.y1) return 1;
 43         if (a.id < b.id) return -1;
 44         if (a.id > b.id) return 1;
 45         return 0;
 46     }
 47 }
 48
 49 public class PaperAndPaint {
 50
 51     private int w, h;
 52     private Edge[] e;
 53     private List<Integer> X1;
 54     private List<Integer> Y1;
 55     private List<Integer> X2;
 56     private List<Integer> Y2;
 57
 58     private long count() {
 59         long res = (long)((long) w * (long) h);
 60
 61         int n = X1.size();
 62         e = new Edge[2 * n];
 63
 64         int i, j;
 65
 66         for (i = 0; i < n; i++) {
 67             e[2 * i] = new Edge(X1.get(i), Y1.get(i), Y2.get(i), i, 0, -1);
 68             e[2 * i + 1] = new Edge(X2.get(i), Y1.get(i), Y2.get(i), i, 1, X1.get(i));
 69         }
 70         Arrays.sort(e);
 71
 72         long sum = 0, prevX = 0;
 73
 74         Set<Edge> s = new TreeSet<Edge>(new EdgeComparator());
 75
 76         Iterator<Edge> it;
 77         for (i = 0; i < 2 * n; i = j) {
 78             res -= ((long) (e[i].x - prevX)) * sum;
 79
 80             for (j = i; j < 2 * n && e[i].x == e[j].x && e[j].left == 0; j++) {
 81                 s.add(e[j]);
 82             }
 83             for (; j < 2 * n && e[i].x == e[j].x && e[j].left == 1; j++) {
 84                 s.remove(new Edge(e[j].leftX, e[j].y1, e[j].y2, e[j].id, 0, -1));
 85             }
 86             sum = 0;
 87
 88             long l = 0, r = 0;
 89             it = s.iterator();
 90
 91             while (it.hasNext()) {
 92                 Edge a = it.next();
 93
 94                 if (l <= a.y1 && a.y1 <= r) {
 95                     r = Math.max(r, a.y2);
 96                     continue;
 97                 }
 98
 99                 sum += r - l;
100
101                 l = a.y1;
102                 r = a.y2;
103             }
104             sum += r - l;
105
106             prevX = e[i].x;
107         }
108
109         return res;
110     }
111
112     public void addRectangles(int h, int cnt, int x1, int y1, int x2, int y2) {
113         for(int i = 0; i < cnt; i++) {
114             if(i%2 == 0) {
115                 X1.add(x1);
116                 Y1.add(i*h+y1);
117                 X2.add(x2);
118                 Y2.add(i*h+y2);
119             }
120             else {
121                 X1.add(x1);
122                 Y1.add((i+1)*h-y2);
123                 X2.add(x2);
124                 Y2.add((i+1)*h-y1);
125             }
126             int j = X1.size()-1;
127         }
128     }
129
130     public long computeArea(int width, int height, int[] xfold, int[] cnt, int[] x1, int[] y1, int[] x2, int[] y2) {
131         X1 = new ArrayList<Integer>();
132         Y1 = new ArrayList<Integer>();
133         X2 = new ArrayList<Integer>();
134         Y2 = new ArrayList<Integer>();
135
136         w = width;
137         h = height;
138
139         int n = xfold.length;
140         for(int i = 0; i < n; i++) cnt[i]++;
141
142         for (int i = 0; i < n; i++) {
143             int y = height/cnt[i];
144
145             if (2 * xfold[i] <= w) {
146                 if (xfold[i] > 0 && x1[i] <= xfold[i])
147                     addRectangles(y, cnt[i], Math.max(0, xfold[i] - x2[i]), y1[i], xfold[i] - x1[i], y2[i]);
148                 addRectangles(y, cnt[i], xfold[i] + x1[i], y1[i], xfold[i] + x2[i], y2[i]);
149             } else {
150                 addRectangles(y, cnt[i], xfold[i] - x2[i], y1[i], xfold[i] - x1[i], y2[i]);
151                 if (w != xfold[i] && x1[i] <= w - xfold[i])
152                     addRectangles(y, cnt[i], xfold[i] + x1[i], y1[i], Math.min(w, xfold[i] + x2[i]), y2[i]);
153             }
154         }
155
156         for(int i = 0; i < X1.size(); i++) {
157
158         }
159
160         return count();
161     }
162 }

როგორც ზემოთ ავღნიშნე მხოლოდ იდეები დავწერე და არა ამოხსნები სრულად თავისი დამტკიცებებით .

პ.ს. to be continued ... TopCoder SRM X aka giolekva SRM 2.

პ.პ.ს. აბა ვინ იპოვის რისი ტოლია X