Yöneticisinden fazla kazananlar
Görev tanımı
Problem
Bir employee(id, name, salary, manager_id) tablosu bir şirketteki herkesi tutuyor; manager_id kişinin bağlı olduğu kişinin id'si, en tepede de NULL. Doğrudan yöneticisinden daha fazla kazanan (eşitler hariç) her çalışanı name, salary ve manager_salary sütunları (column) olarak, ada göre sıralı döndüren bir sorgu yaz.
Örnekler
Input: employee = [(1, "Ana", 120, None), (2, "Ben", 90, 1), (3, "Cleo", 130, 1), (4, "Dev", 95, 3), (5, "Finn", 100, 4)]
Output: [("Cleo", 130, 120), ("Finn", 100, 95)]
Neden: Cleo, Ana'dan; Finn de Cleo'ya bağlı olan Dev'den fazla kazanıyor
Input: employee = [(1, "Ana", 100, None), (2, "Ben", 100, 1)]
Output: []
Neden: edge case: eşit maaş fazla değildir
İpuçları
0 / 3
Her satırın yan yana iki maaşa ihtiyacı var: çalışanınki ve yöneticininki. İkisi de aynı tabloda yaşıyor.
Bir tablo iki alias altında kendisiyle join yapılabilir; biri çalışanı, biri yöneticiyi oynar.
JOIN employee m ON m.id = e.manager_id yap, sonra WHERE e.salary > m.salary olanları tut. Inner join, karşılaştıracağı yöneticisi olmayan en tepedeki kişiyi atar.
Kısıtlar
- manager_id is NULL at the top
Çözüm
Yöneticinin maaşı aynı tablonun başka bir satırında durur; bu yüzden tablo kendisiyle join yapılır: e alias'ı çalışan, m alias'ı yönetici olur ve m.id = e.manager_id herkesi patronuyla hizalar. Bundan sonra karşılaştırma sıradan bir WHERE'dir. Inner join bilinçlidir: en tepedeki kişinin manager_id'si NULL'dır, hiçbir şeyle eşleşmez ve kaybolur; bu doğrudur, çünkü kimse sahip olmadığı bir yöneticiden fazla kazanamaz. İlişkili bir alt sorgu (correlated subquery), e.salary > (SELECT salary FROM employee WHERE id = e.manager_id), aynı cevabı verir. Birincil anahtar (primary key) olarak id ile her yönetici araması O(log n)'dir; yani bütün sorgu O(n log n).
import sqlite3
QUERY = """
SELECT e.name, e.salary, m.salary AS manager_salary
FROM employee e
JOIN employee m ON m.id = e.manager_id
WHERE e.salary > m.salary
ORDER BY e.name
"""
def run(employees):
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE employee (id INTEGER PRIMARY KEY, name TEXT, salary INTEGER, manager_id INTEGER)")
db.executemany("INSERT INTO employee VALUES (?, ?, ?, ?)", employees)
return db.execute(QUERY).fetchall()
print(run([(1, "Ana", 120, None), (2, "Ben", 90, 1), (3, "Cleo", 130, 1), (4, "Dev", 95, 3), (5, "Finn", 100, 4)])) # -> [('Cleo', 130, 120), ('Finn', 100, 95)]
print(run([(1, "Ana", 100, None), (2, "Ben", 100, 1)])) # -> []Kodda değil de fikirde mi takıldın? INNER ve OUTER JOIN'ler bunu anlatıyor.