Statistics

Problem Statement for "Messaging"

Problem Statement

In many systems, there is a need for some sort of messaging service between various components of the system. The most common type of messaging service is probably first in/first out queue, meaning that the messages get sent out in the order that they are received. However, different messages often have different priorities, and in our service, whenever we send out a message, we want to send out the message with the highest priority. In this problem, you are to simulate this queue. You will be given a String[], messages, representing a number of messages that are sent to the queue. Each element of messages will be in the format "<message> <priority> <time>", where <message> is a string of lowercase letters ('a'-'z'), <priority> is an integer representing the priority of the message, and <time> is the time that the message was received, in seconds since the system was started. The messaging service is able to send out one message every second, if there is one in the queue. The queue may also send out a message the same second it comes in.
Your task is to model this messaging service. In addition to messages, you will be given an int, time, representing the number of seconds since the system was started. Your task is to determine which message the service sends at that second and return a String representing the message sent out. If no message is sent out at time, then you should return the empty String, "".

Definition

Class:
Messaging
Method:
getNext
Parameters:
String[], int
Returns:
String
Method signature:
String getNext(String[] messages, int time)
(be sure your method is public)

Notes

  • Note that, to make things simpler, each priority is distinct.

Constraints

  • messages will contain between 0 and 50 elements, inclusive.
  • Each element of messages will contain between 5 and 50 characters, inclusive.
  • Each element of messages will be formatted as "<message> <priority> <time>".
  • <message> will be a sequence of 1 or more lowercase letters ('a'-'z').
  • <priority> will be an integer with no leading zeros, between 1 and 100, inclusive.
  • Each <priority> will be distinct.
  • <time> will be an integer with no extra leading zeros between 0 and 1000, inclusive.
  • time will be between 0 and 2000, inclusive.
  • Elements of messages will be sorted in non-decreasing order, by time.

Examples

  1. {"hello 1 1","how 4 1","are 2 3","you 5 4"}

    1

    Returns: "how"

    At time = 1, both "hello" and "how" are added to the queue. Of these, "how" has the higher priority, so it is sent.

  2. {"hello 1 1","how 4 1","are 2 3","you 5 4"}

    2

    Returns: "hello"

    At time = 2, no new messages arrive, so the remaining message from time 1 is sent.

  3. {"hello 1 1","how 4 1","are 2 3","you 5 4"}

    3

    Returns: "are"

    At time = 3, the queue starts out empty, and then receives a single message, "are". Since there is only one message in the queue to send, it is sent on.

  4. {"hello 1 1","how 4 1","are 2 3","you 5 5"}

    4

    Returns: ""

    At time = 4, the queue is empty.

  5. {"priority 9 1", "be 3 1", "queues 5 2", "can 4 3", "implemented 1 3", "but 8 7", "in 11 7", "would 2 7", "nlogn 12 8", "yours 21 10", "that 10 10", "slower 18 10", "than 14 11", "can 75 11", "be 50 11", "much 42 13", "be 30 30"}

    14

    Returns: "slower"

    Here is what the queue would send at each time step. (Note the hint and don't try to implement a heap) Time | Message sent ('_' means no message was sent) -----+-------------- 0 | _ 1 | priority 2 | queues 3 | can 4 | be 5 | implemented 6 | _ 7 | in 8 | nlgn 9 | but 10 | yours 11 | can 12 | be 13 | much 14 | slower 15 | that 16 | than 17 | would 18 | _ ... | _ 30 | be

  6. {"fnogtlxqpd 2 57","lpsrmjhoie 100 139","tvpedwvddn 67 166","mqekonkkso 99 466","opizsvczvk 73 541","gvtvzyaxbu 95 574","obrwoywjaj 37 633","fuhvmwsuzg 19 756","yjabaruado 81 893"}

    574

    Returns: "gvtvzyaxbu"

  7. {"xqowvwnbzy 82 16","yvpptlxxrn 38 134","vblhqpanhh 8 207","cgwdfgirfg 4 386","qlmghxecbw 81 394","ttlqgdswvp 12 403","ihnycaxxtb 13 418","vaumzmlcln 7 483","khqkqswyvs 41 522","diyrjcgbeq 42 639","kqdrdspjxk 76 691","qzpwmfreqv 84 737","xezbmoylsa 44 805","prfwsybuye 47 826","ebapbzmkyo 9 853","caauheekyg 89 934","osbnzqvybt 6 936","tzbuvxikay 1 973"}

    522

    Returns: "khqkqswyvs"

  8. {"xjighthjkg 26 59","jvkyayxutt 57 298","tgyzmjgjhf 73 323","crsftspzzh 48 386","cwvvhsrbku 60 484","gtlyeetjiv 39 572","iwdlkzrmik 24 949","uwbcxnmobx 87 956"}

    323

    Returns: "tgyzmjgjhf"

  9. {"gzgwllkwsg 35 141","tgeslsjhca 17 169","kxdardnuuo 31 217","smhkabgavm 23 240","sghqkvhgjk 84 432","hnnzhqjdca 2 448","gyntnvtdou 66 697","youlbumqmt 56 703","xvhporlvlz 28 839","eieqdkpcfg 89 899","utympsosjx 19 972"}

    899

    Returns: "eieqdkpcfg"

  10. {"dbxllyzxzf 57 19","isxvgkofef 43 168","xqnkwlgrva 35 231","gwbezlvjjt 89 634","oaoftiqjhb 36 764","ezuwvezgki 49 777","wrplnwuaia 44 778","nflsdlalcg 63 820","cfsmtaprsg 80 940","ziybevyhuk 31 985"}

    168

    Returns: "isxvgkofef"

  11. {"mrpbyzybwi 21 10","rhlwojgjzr 25 11","znsmkqtvxu 51 24","dbotciarvq 44 25","jbispyqzut 12 29","jywnmqcbtx 39 45","mzzocishmr 94 47","gdxjwyaibg 95 78","halzlfpvub 77 86","vpnlwyoasy 38 87"}

    87

    Returns: "vpnlwyoasy"

  12. {"fmlfnogqyo 2 0","spglgtlpnn 71 10","rdzduusjsv 56 57","ceiqjjfwiz 87 58","vifhcaoqcf 89 64","zftxmuuiic 84 65","mcxgoksdtf 29 68","ftftkdxhgx 38 76","vyexedtibl 80 80","dlmoyicicu 10 95"}

    58

    Returns: "ceiqjjfwiz"

  13. {"yrdqhvmynd 56 1","pfzzylkzwm 55 3","wanyijqgdy 25 36","cxwghvmvlu 66 36","pngwnlemxi 83 38","nueztthomv 24 42","hhkchozfyt 81 60","zzcwmqodvo 5 66","hucgiumbtt 12 70","sykjvazfqp 70 79","wnjgrzcnli 82 85","joockkfejr 30 89"}

    60

    Returns: "hhkchozfyt"

  14. {"ycumzkjmye 96 2","cgdipjulxh 28 6","duwyzlofsn 42 7","tlukiebzuy 75 12","uwpipzqaef 35 16","jvjadaobhl 50 24","zvpxeaduza 85 26","jlxyiaipjd 82 31","ridqgxixwq 58 32","xojhwdqawo 20 34","ntcoyrtgeh 100 45","ybwpvtzfif 3 46","norouohhak 36 57","xeukfzsayg 48 71","fgqflmyvvj 4 75","mlcdjhxmdl 25 78","snwrlhofja 55 81","vatzboqgjo 69 89","rnbbsuofmh 97 90","watmjowyjq 49 100","vrnhitxcly 95 100"}

    2

    Returns: "ycumzkjmye"

  15. {"mzeasygdjk 8 0","edhhylbfas 21 3","dmkajwhomo 85 5","wdadlkmqew 65 6","dlpnyjldei 39 8","cfbdgofbsh 15 9","nhpsafkrui 22 12","jyziojopwv 80 13","lfklyshzwx 75 17","fodlxuhbvc 4 26","mofsbvbljk 55 35","zuywjrdlgd 90 42","cgcjhwpktl 53 43","fgbdoxklon 14 46","tnycuwhbwg 97 46","pspmvkmcop 49 51","rxfumwbsbp 71 52","clgjwxnzwe 23 55","grdngxfzib 96 67","eqlumtptey 93 78","ojleqjqpgo 7 85","kcifzsgysw 24 88","euvmptfsgh 60 90","gyrlgbggjj 27 91"}

    9

    Returns: "cfbdgofbsh"

  16. {"gjvoeimovz 64 29","sqnzyspgaa 69 44","hxosalsajf 4 68","wvldgcssjn 33 76","tvpljviike 6 86"}

    44

    Returns: "sqnzyspgaa"

  17. {"qstxgkvlcn 86 2","rgbkdrpaiw 16 19","noicqeqkwl 77 23","blsbzljxnw 58 31","kixqcsrtbq 64 52","hbejemqjsg 33 54","bcsddumazk 97 59","ixkyqjqmxy 82 59","sfrodqvdsn 80 74","kbfujteaaw 41 75","vmykdbyouf 12 91","vdxkgamjcy 52 99"}

    99

    Returns: "vdxkgamjcy"

  18. {"sfycbmxphh 21 1","seygxqqhwb 28 3","ixioubtpop 50 5","yzcztkbohz 99 9","ouwvllheci 19 51","lbqjsmxzdw 56 51","iyyatbngxu 38 57","owrftgkrpo 29 65","souhsrhiga 63 80","jjgzqzlpyv 82 84","idvkghrweq 61 85","iztrayrohi 39 85","tnezmqvuys 81 89","byzsqeixgu 62 100"}

    51

    Returns: "lbqjsmxzdw"

  19. {"qlgdwhvutj 73 22","mnypiigobb 29 30","hswvwxbzjs 81 38","qyvfommnkl 97 42","cwmfrmluta 18 51","cgtfvewogk 100 78"}

    30

    Returns: "mnypiigobb"

  20. {"txxguanhzn 53 12","vtevuhuvoz 42 17","suuhojuvcp 86 18","vxlwjhrevl 89 21","jictpztuyp 52 24","sqxdsnpdzv 7 25","mzzfdjyofz 61 26","qodzvmfigq 23 30","ujncuwiwim 82 30","fqandpquqw 80 35","weapmkvllj 98 43","fwcwfdmyba 68 43","zavvqmpklw 26 60","nedhcgldpf 49 64","zvahtorhie 64 81","aczrekomsd 38 88","ilrjhefcci 3 97"}

    12

    Returns: "txxguanhzn"

  21. {"iainupgsbp 98 4","ndbuprytlj 80 4","hdlfnnzgfo 45 7","tjilufrcno 37 8","thafslpqwp 23 31","deyrlhsrkv 90 51","sshgdamhbg 73 73","ydvncouiqj 36 77","mbqobstjlo 94 96"}

    73

    Returns: "sshgdamhbg"

  22. {"uxqnrheuhl 79 4","tplopazazp 32 8","kacbaekfev 73 10","qzuoqipzei 14 56","tzzkimlzxp 33 58","axryyawrlu 77 70","ldntpmkktk 5 73","vgbqexkwdg 84 87"}

    56

    Returns: "qzuoqipzei"

  23. {"widsdsgdxd 42 13","tvjsnnurne 80 15","imrkwhvxtv 100 36","orlfetgsna 21 46","yhndwistrs 97 64","wgwbuotwke 4 69","kghjadbodi 37 76","yjifwhdyqi 72 87","mnztwtzqsl 58 91"}

    46

    Returns: "orlfetgsna"

  24. {"oeiqtqiips 54 11","bzqpcjskxo 66 13","aigaydzhbx 34 17","mgwlnozlxq 18 19","vjmbajyxtc 47 20","rswlifpyel 75 24","aivyrficyb 12 26","bredzerbdp 14 30","xjligluhic 52 86"}

    30

    Returns: "bredzerbdp"

  25. {"toemxqhejf 65 3","dhjogvefng 95 3","prqfhwszda 39 5","auduwktqlq 75 28","zpqbyqwqej 34 30","wxwzawtgou 28 41","afmgzchesi 16 48","ithdaltyvx 98 56","ewinckcktm 85 63","dttekkqguo 69 68","bacmiejjgv 55 71","quduwbqqab 91 82","ccxmplvjgj 97 87","xruqywinnb 88 91","fuobjxfobf 23 92","fivshfloiu 90 100"}

    28

    Returns: "auduwktqlq"

  26. {"dibfllbkwj 55 22","fplveddqfj 63 32","vhvnpraqjk 88 41","ymdauogupg 10 43","krcrmpbcjm 100 54","iscxhzcewu 42 56","rpowzmzqrm 71 62","qiopykmkbs 85 76","vxhnoojfoq 8 80","jepfsqstlu 61 90","dmutihdsvo 77 95","cxbraevxpz 87 98"}

    80

    Returns: "vxhnoojfoq"

  27. {"jszhzqnclk 80 13","tgmqytfknw 37 22","ibkbvzxfkt 85 23","blrcikpslt 52 25","abofhiralm 22 27","gjsdocntat 84 32","okkziezluk 30 42","wnyskbuzhs 97 65","jggabapzkk 74 74","hgikkzanhd 50 84","booucramvs 93 86","dabgzzsutz 61 89"}

    23

    Returns: "ibkbvzxfkt"

  28. {"toqekmydzq 67 28","ldxiatdgwm 23 34","uccvyutcnx 3 63"}

    34

    Returns: "ldxiatdgwm"

  29. {"kipjquvqgi 50 4","bfnkcitlbj 25 8","rlwaumflaa 71 12","imcrfyrwxg 2 26","ykpykuhsfh 37 77","llbhankpmo 16 82","bvzbkdgtxs 36 91","xsehndqtsh 88 91","kgxlawyesb 74 93"}

    91

    Returns: "xsehndqtsh"

  30. {"rrrubaztri 82 2","ybpktpyvfp 12 3","pxfldtkvbd 1 5","svxxtfkckj 95 7","tsxkvrgbhx 5 28","vwvyhtwzra 74 30","upxbcufrjf 96 30","wsnywelskv 40 34","aelbllbkfe 87 40","xxvapjwqhd 67 45","ujfmdewzel 30 62","egfzzexgsb 62 70","cfefkpvddv 16 71","yxjtfbgqah 26 94","eoxltswirl 13 97"}

    62

    Returns: "ujfmdewzel"

  31. {"ptrcnctyfi 72 8","yzlrhxythg 28 17","ocwpjucgoa 34 19","yaqydemvhc 57 19","ckwhjfeldx 15 27","ogqovqniej 66 51","nvqsployxh 33 54","yfibihsiqq 94 55","fiqrsmausp 96 72","htzlolxeqx 11 78","mimnvvnded 27 80","jfggilkcxt 59 86","itvhoplvty 14 90","wzectsmufl 44 96","oppnmonnwr 86 100"}

    8

    Returns: "ptrcnctyfi"

  32. {"gyipcynhkg 6 26","etnwegstfo 63 57","xzyzsplznj 10 62","qpkixbzwkh 9 91"}

    57

    Returns: "etnwegstfo"

  33. {"mxxuhuwwrm 35 11","nssmsgmfwy 71 11","ibdxnaafid 52 32","duoluoljwv 70 36","bdarnperga 13 38","oyiqjmwtej 49 39","bjreovmtxv 54 54","somxmctvcy 34 64","lprudvdvgs 85 64","djajsudnto 69 66","vurqegnbeo 48 71","lsxccbondo 98 74","xdrofnooxg 94 88","fkwkfdfzpz 81 92","vixxmzzzin 8 93","kcagudxkqh 9 94","osdhpwskvl 44 95","vaqacdqyxh 58 97"}

    95

    Returns: "osdhpwskvl"

  34. {"jdxkldjohr 30 1","wjpqurfwsd 93 2","pnxmvbocco 64 8","rbnncfjxev 90 9","tshavveepf 79 12","ykrofwwvvx 46 16","xympncsmoy 8 41","jecjkgftfo 17 43","ztgfjxotdu 75 45","riobemfekc 65 49","ebrmhddkuk 51 50","ejalbmrinx 7 51","bqcdbnxwzf 80 71","tpggcgrivm 10 75","okrddurour 72 86","iyzlsqcrto 81 88","qjcsbbcduy 38 92","yymcciwivf 92 97"}

    88

    Returns: "iyzlsqcrto"

  35. {"dihtawnhjw 94 6","dswcizqgjq 99 8","nnifiutsho 53 12","momeshsdld 95 35","veulecscpd 38 69","fllgdtwios 2 75","wuemvusizd 6 83","kqnqumjrcf 60 88","qczcznlyzy 41 98"}

    12

    Returns: "nnifiutsho"

  36. {"rdghuncmht 18 12","qlevxqssjp 74 13","lfhmcxziri 53 56"}

    13

    Returns: "qlevxqssjp"

  37. {"hkwirxwcca 43 15","vnppaukeyr 83 42","udjyaoyizp 50 48","twncpdkbql 15 54","ifsgpwzafp 69 57","hvkodhdbci 35 60","sdxsjarnfj 63 78","uxcmjunxum 36 80","cntrxovcnz 2 83"}

    80

    Returns: "uxcmjunxum"

  38. {"jrciswlxow 57 33","klhabsjeir 90 58","smneqrawsd 25 75","weooxetiyf 71 88","htzbwuzijc 52 91"}

    91

    Returns: "htzbwuzijc"

  39. {"awozzvwybr 60 7","zwfineyrdx 58 9","ddfuqmuhhy 48 12","daxznrsqvy 68 38","skinsbisul 15 52","oizmfaajwy 67 54","pyxyrcldfd 56 55","ymijhtscyv 31 70","icakxqhiku 96 91","asyfltldnv 17 95","afqqchwekt 32 98"}

    91

    Returns: "icakxqhiku"

  40. {"tnqwomerdp 52 0","txyhpsimqg 96 0","dnhctioqvx 86 2","pcgtxzyqvq 37 11","ebwzktaoll 65 16","adyunewotv 12 26","zbmcxkjwxu 91 32","iwnkpbrgoa 9 48","hrrdognzkm 7 52","bgwfgunogx 84 72","mybjbqprxu 24 79","cewhlqdvmf 87 82","gbhbyzrgfq 41 98","qpkinxkfse 28 100"}

    16

    Returns: "ebwzktaoll"

  41. {"gwdurijjhe 80 4","hmvwnityzc 10 7","xfjzuqigie 19 10","nwwrptbldd 84 19","ttrvthkjkf 53 24","tigwqjoxic 75 24","aepqczqyox 28 28","uycctqfran 47 29","kqcnejlgdg 98 40","foladysmwg 14 50","jddmwoadtk 8 53","cvfmmxafva 63 54","vdcgxvmgjv 38 72","ouhtphbhzj 34 75","ucdlzrjsuz 86 77","hylmmrxudr 11 88","cwpytvufcj 3 94","ppwexsswye 22 96","sftjmhhqme 61 96"}

    53

    Returns: "jddmwoadtk"

  42. {"bxfsaruxxh 30 0","hkvdzgxqkc 28 14","gyhckiivra 40 15","nzrzekqvhz 51 18","tjnubrjmxz 89 45","awamghuaxr 7 54","orrafldzps 55 67","buugmgzszl 25 71","kxynzlshcu 96 74","xzwwwgzeqj 95 78","zsmfbncyeh 98 79","thqxrvjctg 39 83","frwdgacnyj 87 95","bekuasgbqj 82 96","nkjlkbymje 50 98","laznrvrvds 11 98"}

    98

    Returns: "nkjlkbymje"

  43. {"gxcsixbysb 30 3","mkcodowimc 44 5","onkgennkxd 36 15","xnbdlswokh 93 39","waipsaewau 10 42","zcggyqrmwl 50 52","wkugzdjawy 86 83"}

    3

    Returns: "gxcsixbysb"

  44. {"nuydqavojk 33 12","dqopemhzuj 26 23","jvfmtwerzp 19 29","msfyrvjshg 12 43","rjbrjklnkk 54 76","kxupldjevl 29 77"}

    76

    Returns: "rjbrjklnkk"

  45. {"tvogrwijwv 16 0","igpvexudcu 59 27","cbraigkvup 32 30","gygkzfxlvv 50 30","hdqzbwqtnq 14 38","lzfekqxdsd 53 48","gqbljezztc 89 84","chrungaxpj 75 85","audegcjzro 81 93"}

    0

    Returns: "tvogrwijwv"

  46. {"qxoqgtvcxq 76 0","ezjytejicy 41 25","xjvxujoxsl 93 27","exdonpdkhy 74 37","bzuqztxugn 90 39","ykutmstndd 27 81","azqguquqse 72 87"}

    0

    Returns: "qxoqgtvcxq"

  47. {"hello 1 1", "how 4 1", "are 2 3", "you 5 4" }

    3

    Returns: "are"

  48. {"hello 1 1", "how 4 1", "are 2 3", "you 5 4" }

    2

    Returns: "hello"

  49. {"hello 1 1", "how 4 1", "are 2 3", "you 5 4" }

    1

    Returns: "how"

  50. {"priority 9 1", "be 3 1", "queues 5 2", "can 4 3", "implemented 1 3", "but 8 7", "in 11 7", "would 2 7", "nlogn 12 8", "yours 21 10", "that 10 10", "slower 18 10", "than 14 11", "can 75 11", "be 50 11", "much 42 13", "be 30 30" }

    14

    Returns: "slower"

  51. {"hello 1 0" }

    0

    Returns: "hello"

  52. {"a 3 0", "b 2 0", "c 1 0" }

    0

    Returns: "a"

  53. {"hello 1 1" }

    1

    Returns: "hello"

  54. {"hello 1 20", "how 2 20" }

    20

    Returns: "how"

  55. {"lalit 1 0" }

    0

    Returns: "lalit"

  56. {"lalit 1 1000" }

    1000

    Returns: "lalit"

  57. {"hello 4 1", "bye 3 1", "crap 2 2", "shit 1 2" }

    2

    Returns: "bye"

  58. { }

    10

    Returns: ""

  59. {"j 2 0", "k 1 1" }

    0

    Returns: "j"

  60. {"kora 1 1000", "bum 2 1000" }

    1001

    Returns: "kora"

  61. { }

    2

    Returns: ""

  62. {"ayaz 4 0", "ganteng 3 0", "haha 2 0" }

    1

    Returns: "ganteng"

  63. {"hw 100 0" }

    0

    Returns: "hw"

  64. {"hh 100 0" }

    0

    Returns: "hh"

  65. {"hello 2 0", "xx 1 1" }

    0

    Returns: "hello"

  66. {"hello 1 1000", "yo 2 1000" }

    1001

    Returns: "hello"

  67. {"hello 2 1000", "hell 3 1000" }

    1001

    Returns: "hello"

  68. {"hello 1 1", "hii 5 2" }

    2

    Returns: "hii"

  69. {"abc 1 100", "sabc 2 100" }

    4

    Returns: ""

  70. {"a 1 0" }

    0

    Returns: "a"

  71. {"hello 1 1", "how 4 1", "are 2 3", "you 5 4" }

    500

    Returns: ""

  72. {"hello 1 1", "how 4 1", "are 2 3", "you 5 5" }

    100

    Returns: ""

  73. { }

    2000

    Returns: ""

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: