İş Görüşmesi Algoritması?

Question

GÜNCELLEME: Birisi n'deki son yorumuma cevap verebilir mi? zamirler m.'nin cevabı?

Lütfen Dikkat: Bunu daha önce sordum, ancak tam bir karmaşa oldu, bu yüzden daha ayrıntılı ve orijinal haliyle yazıyorum.

Soru:

Aşağıdaki işlevleri desteklemek istediğim N katılımcı arasında (Her biri 1'den N'ye indekslenmiş) bir oylama sistemi yönetiyorum:

1. Init (N) - Veri yapısını başlatın. -O (1)
2. Oy verin (j, i) - J kişisinin oy verdiği (tam olarak 1) i kişisine oy verin - burada birinin kendi oy kullanmasına izin verilmiyor. -O (1)
3. Seçmenler (i) - i'ye oy veren kişi sayısını döndür. -O (1)
4. Menşei (j) - j kişisinin diğerlerine verdiği oy sayısını döndür. -O (1)
5. Beğenilen (k) - En iyi katılımcıları aldıkları oy sayısına göre (azalan sırayla) yazdırın. -Tamam)
6. Kaçınıldı () - Oy almayan tüm katılımcıları yazdırın. -O (r) burada r basılı katılımcı sayısıdır

Bu, söz konusu alan karmaşıklığı olmalıdır O (N) .

Yalnızca dizilerin ve (çift) bağlantılı listelerin kullanımına izin verildi.

---

Ben ne yaptım? 1-4'ü çok kolay bir şekilde boyutu N olan ve her hücrenin değerleri içeren bir dizi tanımlayarak çözdüm; gotve sent. 'a verilen ioylar jarttığında değer aldı jve bir değer gönderdi i.

Yine de 5 ve 6'yı gerekli karmaşıklıkta nasıl çözeceğime dair hiçbir fikrim yok.

Not: Gerçek bir kod yerine algoritma / fikir arıyorum.

Answer 1

Her operasyon için oy alan adayın puanını tam olarak bir artırdığına dikkat edin.

Bu, yeni bir strateji açar - bir adayı kendi puanına eşlemek yerine, bu puana sahip adaylar listesine bir puan eşleyin.

Bu, aday listeleri listesi olarak oldukça basit bir şekilde uygulanabilir: (sözdizimi gibi şablonda:) list<list<Candidate>>.

Ek olarak, her aday numarayı gerçek Candidateöğenin işaretçisine eşleyen bir dizi tutun .

0 olan adayların listesi, O (1) 'de bir diziyi başlatmanıza benzer şekilde , başlangıçta tüm adaylara dolaylı olarak ayarlanacaktır .

• Bir oy verildiğinde:

1. Adayı referanstan bulabilirsiniz: O (1)
2. Mevcut listesinden kaldırır ve sonraki listeye eklersiniz: O (1)
3. Desteklemek Avoided()için O(r): "0" listesindeki elemanların sayısı yarıdan azsa, bunun yerine normal bir liste olarak değiştirin.
4. Bir puanı temsil eden önceki öğenin artık adayları yoksa, bırakın ve önceki puanı doğrudan bir sonrakine bağlayın (yani, puan 3'e sahip aday yoksa bağlanın 2<->4) Bu , O(n)çok fazla boş liste düğümünden dolayı alan sağlar .

• TopK'ye ulaşmak artık çok kolay ve O(k)puan listesini baştan sona yineleyerek tamamlandı ( kadayların çıktısını aldıktan sonra durarak )
• Kaçınılan, O(n) = O(r)adayların yarısından fazlasından kaçınıldıysa veya O(r)başka türlü yerleştirmede optimizasyon (3) sayesinde artık.

Answer 2

İşte Avoided () uygulamasının alternatif bir yolu. Oylanan her bir kişiyle, koşu başlangıcı ve çalışma sonu olmak üzere iki sayıyı ilişkilendirin. Başlangıçta tüm elemanlar ayarlanır None(O (1) dizi başlatma numarasıyla yapılabilir).

Kişi milk kez oylandığında , güncelleme startOfRunve endOfRundiziler:

if startOfRun[m-1] != None and startOfRun[m+1] == None
   endOfRun[startOfRun[m-1]] = m
else if startOfRun[m-1] == None and startOfRun[m+1] != None
   startOfRun[endOfRun[m+1]]
else if startOfRun[m-1] != None and startOfRun[m+1] != None
   endOfRun[startOfRun[m-1]] = endOfRun[m+1]
   startOfRun[endOfRun[m+1]] = startOfRun[m-1]
else
   startOfRun[m] = m
   endOfRun[m] = m

(kısalık için kenar koşulları ihmal edildi).

Artık oy verilmiş birçok kişi var ve her koşunun başından sonuna kadar kolayca gidebilirsiniz. Koşuların içindeki sayıların hepsi yanlış ama onları umursamıyoruz. O (r) turları vardır, böylece O (r) 'de oylananların tümünü atlayabilirsiniz.

---

Favored () 'i uygulamanın alternatif bir yolu. İki diziye sahip olun, (1) puana göre sıralanmış genişleyen bir kişi dizisi ve (2) bir puandan en az puanı olan ilk dizideki son kişinin dizinine bir harita (böyle bir kişi yoksa, o zaman None) . Başlangıçta ilk dizi boştur ve ikincisi Nones içerir . Misal:

(array 1)
(index)       1 2 3 4 5 6 7 8 9
person        3 6 5 1 4 2 8 9 7
score         7 7 7 5 5 3 2 2 2

(array 2)
score         1 2 3 4 5 6 7 8 9
index in 1st  9 9 6 5 5 3 3 - -

Bir kişi ilk kez oylandığında, 1 puanla dizinin sonuna eklenir ve array2[1]güncellenir. Kişi tekrar oylandığında, dizideki aynı puana sahip ilk kişi ile değiştirilir, puan artırılır ve ikinci dizi güncellenir (yalnızca bir öğeyi güncellememiz gerekir, yenisine karşılık gelen Puan).