TusharDwivedi Just remember that there will be two conditions to check. (Look out for abc and abcde in below test cases):
The prefix string comes before the longer string.
- 7
- aab
- defgab
- abc
- abcde
- cedaaa
- bbbbbbbbbb
- jabjjjad
Prefix string will come after the longer string.
- 7
- aab
- defgab
- abcde
- abc
- cedaaa
- bbbbbbbbbb
- jabjjjad
Make sure that you get correct output for both the cases, and you may trust that other things will fall in place.
karthikpriyatham Before seeing your comment Got atleast 50% cases wrong . But after seeing your comment, I got all cases accepted .. Thanks dude . And one more thing that is missing is that ..
3
b
aa
aa
output
BAD SET
aa
If any one can overcome these cases , you can directly get AC ..
iwill in the second case you mentioned above do we have to output abc or abcde?
karthikpriyatham BAD SET
abc
is the output you will obtain :)
lijubjohn would have been more fun if the output for this case should have been :
BAD SET abcde
shubhshrma Yes i was really thinking this as the expected output after reading sample cases given in question because they suggest this only.
sidajwalia it would have been real pain, to maintain order of insertion also.
roufamatic That was the hint I needed! With no test cases I was flying blind. Thanks!
douaaatouailaa thank you =D
john_canessa This was probably the best hint to figure out what needed to be checked to solve the challenge. I went with the following.
For after: 2 abcd abc
For before: 2 abc abcd
Good advice :o)
uvinodh90 Thanks for the valuable comment. This helped me to cover the exceptional case.
chickoo_1 If i ever missed to read your comment i could never do this problem lol thanks:)
adk96r Thanks bro ! Half of the test cases were failing. Once I saw this, I realised where the bug was.
devbabu @bokamvinaykumar Please upload the test cases.
avidprog [deleted]
pdog1111 you can do a neat one-line tree in python using defaultdict which is pretty cool:
from sys import stdin from collections import defaultdict def Trie(): return defaultdict(Trie) def add(trie, word): if word == '': if len(trie) > 0: # current word is a prefix of a previous word return False trie[word] = '' return True if '' in trie: # a prefix of the current word is a previous word return False return add(trie[word[0]], word[1:]) stdin.readline() trie = Trie() for line in stdin: line = line.strip() if not add(trie, line): print "BAD SET" print line sys.exit() print "GOOD SET"
richardpenman love that Trie definition!
bendyl very nice solution! I stumbled upon the same infinite defaultdict pattern but used
reduceto build the tree. (Arguably assertion shouldn't be used for main control flow but maybe ok for this short exercise.)from collections import defaultdict def infdict(): return defaultdict(infdict) def build_trie(node, ch): child_node = node[ch] assert None not in child_node # no existing words are prefixes of this word return child_node n = int(raw_input()) trie = infdict() try: for _ in range(n): s = raw_input() end_node = reduce(build_trie, s, trie) assert not end_node # not a prefix of an existing word end_node[None] # None = end-of-word sentinel print "GOOD SET" except AssertionError: print "BAD SET" print s
devbabu awesome guys, do post new questions on suffix trees, segment trees, Binary Indexed Tree, kd-trees.
Thanks
btamada Can you please add more Trie problems in various difficulties? I think this is becoming a more commonly asked question in technical interviews.
squire40 These instructions are not clear. They say "Output GOOD SET if the set is valid. Else, output BAD SET followed by the first string for which the condition fails."
Is the first string for which the condition fails the string that is a prefix of another string, the string that is prefixed by another string, or the first string that appears ordinally in the input list?
vladimirt221 Agree.
as_mallem I believe that the test cases here are not all correct : let me give you an example I got this test case
100 hgiiccfchbeadgebc biiga edchgb ccfdbeajaeid ijgbeecjbj bcfbbacfbfcfbhcbfjafibfhffac ebechbfhfcijcjbcehbgbdgbh ijbfifdbfifaidje acgffegiihcddcdfjhhgadfjb ggbdfdhaffhghbdh dcjaichjejgheiaie d jeedfch ahabicdffbedcbdeceed fehgdfhdiffhegafaaaiijceijdgbb beieebbjdgdhfjhj ehg fdhiibhcbecddgijdb jgcgafgjjbg c fiedahb bhfhjgcdbjdcjjhaebejaecdheh gbfbbhdaecdjaebadcggbhbchfjg jdjejjg dbeedfdjaghbhgdhcedcj decjacchhaciafafdgha a hcfibighgfggefghjh ccgcgjgaghj bfhjgehecgjchcgj bjbhcjcbbhf daheaggjgfdcjehidfaedjfccdafg efejicdecgfieef ciidfbibegfca jfhcdhbagchjdadcfahdii i abjfjgaghbc bddeejeeedjdcfcjcieceieaei cijdgbddbceheaeececeeiebafgi haejgebjfcfgjfifhihdbddbacefd bhhjbhchdiffb jbbdhcbgdefifhafhf ajhdeahcjjfie idjajdjaebfhhaacecb bhiehhcggjai bjjfjhiice aif gbbfjedbhhhjfegeeieig fefdhdaiadefifjhedaieaefc hgaejbhdebaacbgbgfbbcad heghcb eggadagajjgjgaihjdigihfhfbijbh jadeehcciedcbjhdeca ghgbhhjjgghgie ibhihfaeeihdffjgddcj hiedaegjcdai bjcdcafgfjdejgiafdhfed fgdgjaihdjaeefejbbijdbfabeie aeefgiehgjbfgidcedjhfdaaeigj bhbiaeihhdafgaciecb igicjdajjdegbceibgebedghihihh baeeeehcbffd ajfbfhhecgaghgfdadbfbb ahgaccehbgajcdfjihicihhc bbjhih a cdfcdejacaicgibghgddd afeffehfcfiefhcagg ajhebffeh e hhahehjfgcj ageaccdcbbcfidjfc gfcjahbbhcbggadcaebae gi edheggceegiedghhdfgabgcd hejdjjbfacggdccgahiai ffgeiadgjfgecdbaebagij dgaiahge hdbaifh gbhccajcdebcig ejdcbbeiiebjcagfhjfdahbif g ededbjaaigdhb ahhhcibdjhidbgefggdjebfcf bdigjaehfchebiedajcjdh fjehjgbdbaiifi fbgigbdcbcgffdicfcidfdafghajc ccajeeijhhb gaaagfacgiddfahejhbgdfcfbfeedh gdajaigfbjcdegeidgaccjfi fghechfchjbaebcghfcfbdicgaic cfhigaciaehacdjhfcgajgbhhgj edhjdbdjccbfihiaddij cbbhagjbcadegicgifgghai hgdcdhieji fbifgbhdhagch cbgcdjea dggjafcajhbbbaja bejihed eeahhcggaaidifdigcfjbficcfhjj
the output is supposed to be (as suggested by the test case):
BAD SET d
How come?????
is there any word which is a prefix of "d"?
if you think so, give me which one???
Killer2020 dbeedfdjaghbhgdhcedcj decjacchhaciafafdgha
its both vice-versa d is prefix of these words,this also count
cewillis Make sure to treat two identical strings as a BAD SET.
claguna Did you manage to get all the test cases right?
cewillis Yup
claguna I don't know why my code fails in half of the test cases. I'd appreciate your help finding the bug:
https://github.com/claguna/hacker_rank/blob/master/src/trie.cpp
tusharmarda Why have you made isLeaf=false in line 34? I understand that it would be irrelevant in this question, but in a suffix tree, aren't you erasing the information that some word that you inserted earlier was ending at that point?
cmoncure This.
witekbobrowski The last test case is unsolvable with Swift!
gauravgupta5895 how to optimize the code for this as my code is not running for last 5 cases . help me !!!
Sort 80 Discussions, By:
Please Login in order to post a comment