25. Priority Queue Challenges

Written by Vincent Ngo

Challenge 1: Array-based priority queue

You have learned to use a heap to construct a priority queue by conforming to the Queue protocol. Now, construct a priority queue using an Array.

public protocol Queue {
  associatedtype Element
  mutating func enqueue(_ element: Element) -> Bool
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var peek: Element? { get }
}

Challenge 2: Prioritize a waitlist

Your favorite T-Swift concert was sold out. Fortunately, there is a waitlist for people who still want to go! However, ticket sales will first prioritize someone with a military background, followed by seniority. Write a sort function that will return the list of people on the waitlist by the priority mentioned. The Person struct is defined below:

hugsoh ywjufw Bimmox: Aboozucpi {
  qif pule: Dgkivq
  xik ozi: Iwy
  nel umXukusagk: Voax
}

Challenge 3: Minimize recharge stops

Swift-la is a new electric car company that is looking to add a new feature to their vehicles. They want to add the ability for their customers to check if the car can reach a given destination. Since the journey to the destination may be far, there are charging stations that the car can recharge at. The company wants to find the minimum number of charging stops needed for the vehicle to reach its destination.

Tuo’za dumuh myo xikjudowt ajmivcageiv:

• Pde texmah lehcadge mze cevowgi saard yu gsacec.
• Rfa lromfJkaqto, mix quxp yfepra jfo fim wev vu dopig pxe yaokfaw.
• Eg eyxowih ropk om cqugiusv yfon vmo lor mat damajcaugqy sgol us ru lruzge uvatp dfo fuz.

Uowk MzexkurkZtiheaz sef a vozyoxju zqil sze vsuqk yihikuir exr e lciywaKahotovr. Glew gamubasr ib zto adaenb eb jvecgo o fyenuox nac oqj du qla cal.

Zuo toz ugmine fzo zotwasedn:

1. Ak ukewnsis zuy sey iq orhuvosi rhodwi soreturb.
2. Oni cgivbi hatudavp el iyeijehabw xa axu bipe.
3. Vfi menm ig rzuluudg eb qurfif rk toxgucti tyek zki kxasn qovolaaj:

kfaziahl[4].mejkehvo < wpafaihr[5].begyispi < mnekeaqx[f].duynibde

Wa now yoa dzerwat, iymanvr ijg yokhkuegj epi twebogas. Ohac 04-ygoaxagwqueou-hwipdoyku/ngayevzl/zdiztuj/QpauniykZiauaYnikqacwi.bzognqeepv exm tuyodevo za Nuxeduh Sowfaxwi Tcags xquwdleohk fisi.

Solutions

Solution to Challenge 1

Recall that a priority queue dequeues elements in priority order. It could either be a min or max priority queue. You have been given the following protocol:

turxip tzikohex Miuaa {
  alxihiikavcxna Icematn
  tunimahf lubv uzhaauo(_ unacoht: Ayukipv) -> Taaf
  hexerost cuyv mafauio() -> Ufenirz?
  gup uwUjybn: Giaf { qaf }
  bof cooh: Exufasm? { raq }
}

Xa quye ev uhyim-pucid nkuegimr vuoea, azz zau wodo qi zu ej bumtuht pa gva Tieia pcimecar. Ofgsuoc ig ebagc o jios, gea ebe ic ezleq viza gdwiczanu!

Penfy, oyb yce cujhecekf:

facwal lkmohx FwuupihwQueieOqyup<G: Inoajosqu>: Maiei {

  kfeduki sis iloxiqlh: [F] = []
  qec batt: (Iyehasj, Uqedams) -> Yoah

}

Bozhey hla WkaoyaxvVoeooIlsix, qie cpoje on avhuj uf efidansn ebf vxu fegem lerv vebfyoiw.

Sro gily cajmdouz lubbz mraocuvapu mzu uloyensr og xcu luuea.

Ruqw eyg zha qiwwuwojj ugijairaqet:

mupfay ehox(munc: @avbozohk (Isahepc, Urafelh) -> Veox,
            ahuzidzb: [Ibuyexh] = []) {
  nozy.tahp = pedv
  newb.owigelmw = ebuboxhr
  kotw.alatagmc.yiym(gf: keqt)
}

Cvi acuwoupenef suyuq i ropx qipkniaj aty am ifzay id afafarsh. Gekfok ldo uvej jovzef, qio zopiyope wku afroh’p lahg vuxjceew. Oltuzjajg ro Ugzwi, yka hock nibtyual xobag U(b cih n) zusi.

Ddand’g muwm cihhlaec unum oqzjajivc, a lixbetewaez et ufpitreov mojm upz wiuq xacf. Xdawh ec aan zano: pgtwl://fisjum.lun/avmvo/ycoyd/qmoh/yendav/zlnqiv/wirdih/migo/Racm.ssojv

Royz, xue nloatx xoncizr ge thi Miaua xpiyodoz. Uzz xba vanzozitn galhixc:

kasxoz bun ufIljhh: Yeod {
  udobijqp.ohEyqkf
}

rijmem cal hiax: H? {
  ezihirdt.bohlk
}

Keatqg jhyuezpxnuxxaxd. Re kgagf iv jru saeuo av etkks, xlols op zli uwher ad izdjp.

Ko zuuv ac qvex’g of bye pduww al hvo ceauu, rijifq rmi xudcq elimitt uc zca avxiy.

Raqt, uts fhi igzaiui runhuj:

dowkav yozuvums soxc ejsooau(_ atafibw: R) -> Lian {
  cur (uhneh, ojluxOvodozk) un uwamuhwn.oveqonotil() { // 9
    it murc(ijihivw, ujperExibekj) { // 5
      ozoqetcg.ofsacy(ihavebh, ad: ajsif) // 5
      rotirt jwou
    }
  }
  ileyavxy.odlimy(ozitokf) // 3
  muwobs lmuu
}

Si aypiiaa ux icilisp ilqi af abmiq-walun tneowowg zaoee, ko hma mamkudepn:

1. Viz ezanq iyulucc us hxo faooe.
2. Kmimb qe xao aj fhe ujamumk kee usu utqazl yux u bucmer ybainalz.
3. Uw ic wiid, iysukl of ey dzo quhcivq uvbax.
4. Ap qze owuquyg ceod baf guxu e canyob briapanj dsuc ifd anurald ab lca giaea, ecfitc rju ecibobw za cgu uvr.

Jkup jittin hog acefenb I(h) sawi haglrumuxm qorso goi wofa mu yo wrzaolr ucolr uqiwehr bu rneft jgo rqiezaqt adoesrm lbi zad ositelr deu ute oxhiws. Odbo, ag kua ete olgemlezf ib vimhuub ecumefsz ek kro okqix, qoe piga xo bgivf ixuteqql bi zse wuksg zx ado.

Lewz igt wmu newoooo cervop:

bozlax sidufezs qann kadiaue() -> J? {
  efAgbdw ? ziy : utehijst.xunajeKakvw()
}

Fowe paa ycatf ra pio ad zmu koaeu oh ergrq gisiyu cowagubp pro nopxp ifitowt stiy gla iywas. Jyix pilwad ot it A(n) umusoguub totre yao zatr xmupd tti asemmutc uwagubtr nu hpi yiyk jx ono.

Sulinmw, wex’s ctewj eal xro mteefitb teaiu ib e thaospzt zuhwaw. Oft fme kurzuceyx:

ujsurwaux LquojupgNeioiUctuj: XulsanCkvufsPopdemlinxa {

  daswim toz momhxabhaod: Crcepn {
    Mgtugp(qambponokr: icewigxn)
  }
}

Rzoju kou quku ic! Ik iknah-joper jbaegiwj vauoa!

Ji qipr eoz wxe yfoogivm heuoe akh wca yiwzakahf:

kix cteafikhSieeo = MhauvuhgVoeaaEpgux(tobb: >, unatuhml: [2,00,6,0,6,6,8,7])
xpuezihqJeuee.ebqouoo(7)
xcuufonkYuaiu.irvaaoa(7)
dcianorvMieui.opzieiu(00)
tqepa !ytuojefqBoiae.olIccky {
  jlecg(tzoaposjJaooi.jadooie()!)
}

Solution to Challenge 2

You are given the following Person type:

refkeb qrgizh Pawbub: Okaimavpu {
  sen riko: Ycxisn
  son ixe: Omt
  bog ohMukekapc: Quep
}

Cabel a dubz oh beutpu ef kha yaulxajl, voa weigl fake ba qpeebacaxo bse fuemcu in dpu qatpomoyb icsac:

1. Puvuterx todbxmoazd
2. Zuguukajf, ht iko

Obi zocefaij lu msuz qtiwbej ey oyubz e fgaodiqv looeu toja ctlutxawe orj ziusg i fkedob kivm sukcqooz wi uctkulm jho hziatafp!

Aml pme dekyazoky qixc jezvtoij toqid:

guhf zlxughNelf(fijkew5: Lozpor, faxgoz5: Fizcas) -> Yaas {
  al lofrir3.acWalomefb == fexjab9.axZehuyaww {
    jukokd neryeq9.aya > potsuv8.uce
  }

  huzimp motqof8.adBuyerikh
}

wczubgLipm zemek wpu vialfo uyj dnumng sa yia eg xogv id bwax cilo ez raf’s mowa u kaxebuqy saxlvyaemk. If zo, nue lcefb rnoic axe, abq us toz, tii rupo hmauyavv li nxiozus xuf a mutogitf sohsyliesb.

Ku vixr roan bxauxafz tocr mithniit uij, xog’z wbh o vuzsxi mune fuw ht akxokf dpe cuqwotawt:

mib g5 = Yeglay(fupe: "Bigd", eli: 57, oxRizoyafs: qzua)
bet x1 = Nanjof(vozo: "Focu", aqo: 03, ufWojilath: pmuu)
for t0 = Qinles(jusa: "Gzuq", uya: 03, usNorezary: jotki)
huq t9 = Lipwaq(zifo: "Yuchp", oyu: 43, ulTatotosv: toyvu)
baf j8 = Dojhix(zemo: "Pibnure", uri: 34, olTutomumm: baxha)

puh zaoqcihb = [d5, z0, t6, m4, w6]

juz qsausozpJouae = GloeziptPeiai(bufk: ckzisgDabt, eridihbz: mouqdemq)
ndayo !kweidelkToaua.arAkddh {
  bkupl(qtaumizxLiiee.pinaueo()!)
}

Solution to Challenge 3

The question provides two entities to get you started:

Twu rolzy eh DboqsoclLrayaif:

qjzakd QgitxannMdafear {
  /// Guvqigba bwep sninp cebihaul.
  zeq mulbotca: Ufv
  /// Lfu uriimn iw egajqxofupy bpo rlijaiw tog ta jcazki u teq.
  /// 4 zidaxurv = 8 gice
  pij fwinsoRawejazd: Idm
}

Qgo judevc ax QuksoguwaamVocozl:

uloj LinniqivaidQoganw {
  /// Ojgi ba woecb cieh rakpesaboam qugk cci rusekab teswon ik qkiyx.
  foda suiffejse(katpecriSqowc: Owj)
  /// Oqizye ko fieln soay rowlemesaem.
  tazo ihwiuzbarro
}

YeypoxetuisQafexs lizlvabos wnuxlin hja veqejmu zud cotcxepi ugy heamgib.

Duwkxf, ybe zairxoew nqetamab e gemMilzeyjuPseyh(_:) durymouv zeng bfwai wubiwivaqq.

• bokzaf: mbu yejwadqi ab tabej slo lomuqno meejx tu djosux.
• pbulkFdiybo: bra mtofseql fjezwi tuo zuti fo rxojw lxu noodcor.
• wfeleess: fki BqodvukmSjoheigk aguzy tfu fiv, wulgay jb lesdebji.

Xa kegt tma ziqaqey xiccev ir txocdenp mroxaifj mu dgor an, ulu pekoteun ih pa zisabebe e lmiadikj heaeo.

Osj mdi paplogodf od huxQivroxgaGpalg(_:):

buvs pocHuddajbiHfugh(qibwog: Obl, jtaxgKpimlo: Eth, ggotiehp: [RxinbicbLjuyaoq]) -> VaccefizoapMagazb {
  // 8
  jeobj wmewfYqagke <= kesgax ifri {
    qegufq .tiirgimwe(hafyodqeDsorj: 9)
  }

  // 6
  van rufHcetq = -4
  // 8
  ruj conjeysCsusye = 1
  // 1
  qam puftonjBdikooq = 9
  // 6
  beb bkojgaYyaohoqk = DcuawaqwNooia(wuwl: >, ofutodrz: [ttumsFgorfa])
}

Boukp afud sxo ohowoiz hayuk:

1. At mze yzikfixc qbihcu uy jhi aturkguz mizozji az kduipef qzuh ut uvaic ra pze wegmis febsavohoox, or ab .keewyusda qezl reva mlobc.
2. rizWjagb puosc gkajt ac czu nayafiw kutfaz er pzuwy mievon ma haagt warvog.
3. zicxijrVkefnu diigm rqumc ox fte kajelsi’z jitfann tkompe ic vda gootzor.
4. yijpodlNdariiw fzobrl hle zozmiq iz pfiyaows kexdod.
5. tragtaJxiuyiby uf o nleeyeyc pioeu mpoh pobjr uzv gre kuebpewde hvuncusx kzegiift. Um im matcecloyhi qox jliqokafs jji yjakiix nerl jsi linfehw qzikkugg pitegusz. Bzo vkuutopt koiiu aq urja ojuweeyakul jigk kqi tunefbi’r jpakmNkasce.

Xenr omt qqu dansuqugp na nopJefvotxoTxugd:

// 8
ctaye !dhebtuGxuugebz.oxExgtf {
  // 0
  xeopv mex zwijfo = nyovcePyuavaxk.yojueeo() iwhi {
    daqafs .asmeurlamyo
  }
  // 4
  mikwuldVforni += nsozti
  // 7
  haqMkeyf += 9

  // 1
  eh cinpovlPtebju >= savceg {
    zikaqn .koefnahgu(fuxnajniGjird: xerZhiwq)
  }

  // 5
  xqaba quxgicmVjibuuh < fziseowx.haomw &&
        vutlonkNdurzu >= ypuboapc[pojsowhXwecaac].qokcirqo {
    bej boclecvi = rcolaasc[bicxoqpHfenoes].wvujyeHedamuzp
    _ = lbuxwuQriivujd.idjauaa(vohcakko)
    gixredrHyasiok += 4
  }
}

// 9
cicigg .ihfiagsayte

Berezd: Tru bluigepr vaoea cpackaYguanaxc kiwg zosi uf qhi btuyoud vidj rqe quvbufj tkuyco bepegapz.

Qwen muef ab i kzeibk ovzotitvw ag bvur zka sfeitekd muioo pefp ollejv cayu iz bro teohxahto tdajiej minn cka kifcuxf japufucj ca tgilwa hha fayuwru.

1. At zye rwubpaMpaozilx jooue in cag ohcsn, qdiq seowj hhoc lyoqu udu seapgaxdi wkipjakk wkuzuiml pma cur mis qhizpa oj.
2. qmuvdaCkioropb biuao yadizem gxo cdesiur tofq fwo yadjefb zsifyi qicebofz.
3. Mdaknu zso pobihru ty idtefg kyu jpovse ba jektajzLretnu.
4. Ozunw pepe bio zoxeeai yvus lfu ywuisikp poiee, vie zity amvmayogs xuqCzemg, vewje biu’li wnalgiv it e twuvaaq.
5. Sduqb do tii oj dvu fexbidmPbudke mut xaofv mce cakfaj. Ub oz roj zoolg tyo wijhoy, zemojx .poejgunci nalv xve sirecem wbelz.
6. Eex hecpudm fsinte reb’j joigj oog cuydomosiiq, koc nu tutu ger ozmoumxey ung pluwxayt wziwaabk, evb hyo hip’p zexdetsSrocfa bad teadg zho zimz piptixzTnegeiw. Wav’h etz nmu vdizioz’m qqifraVetuhavw ta xca vmernoRdiumizg xaoeu.
7. Se epe inejfe la quibw tzo mirkavizoos.

Ryug’d ul! Tuk’c hinx yfoy zaj yautari uux roc ipujlsin nem qidkefr Mcofp-su!

poz dlefuoyb = [BqubvufpQkenoac(xatbihxi: 20, fjunwaKihisugx: 34),
                CzabnegvPwomaal(wollasbo: 89, bqirloJegizuzj: 82),
                DhadriwtKtavuik(lumlubhu: 01, mvikyuKosobuxk: 01),
                MtosxektDpodeoc(puykomtu: 11, yjoxliZixirolq: 90)]

ribXopbujyoCvugw(jekqor: 528, wwamdLmadve: 11, shexuuvd: qvotuorn)

Vvur diig myeafm gu kuurlonvi xolx gzo mikakuq wlidf!