5 ms·
Hacker CS: Computer Science Challenges
- spaghetti 15y agoBored at work so I thought I'd try this one: "First non-repeated character in a string": char firstNonRepeatedChar(string s){ HashTable H; foreach(char c in s) H[c]++; foreach(char c in s) if(H[c] == 1) return c; }
- deleted 15y ago[deleted]
- kenjackson 15y agoIf you're still bored, what if the alphabet is small (say 26 characters), but string is typically huge (billions of characters) -- and on average the first repeated character is in the middle of the string. How does that change your algorithm?
- spaghetti 15y agoI assume you mean first non-repeated character. Anyways heres a possible performance improvement for a very long string: Assume the string is stored as a linked-list (so removing characters from the middle of the string is cheap). Then remove duplicates from the string during the initial traversal (keep track of unique characters that were removed as duplicates in a hashtable). After this single traversal the character in the head node of the remaining linked-list will be the first non-repeated character in the original string. Note the string must be stored in the linked-list initially... if we're responsible for moving the string from a theoretical array w/ billions of elements then we have to traverse the string twice just like the original algorithm and nothing is gained. Please clarify the "usually in the middle" part of your question. In this case do we always have to return the first non-repeated character? Or can we just be close?
- kenjackson 15y agoYes, first non-repeated, my bad. The usually in the middle is meant to say that typically the first character returned is position ~s.length/2. The linked list idea is good. I wasn't thinking of that at all.
- spaghetti 15y agoOne mistake I made: after the first traversal over the linked-list the character in the head node of the remaining list is not necessarily the first non-repeated character. Consider the string "aba" for example. However the second traversal will be over a shorter list... So this approach might get you somewhere :-)
- idunno246 15y agoIt couldn't average in the middle, right? You're guaranteed one in the first 27(alphabet+1) characters, so just do it on that substring
- kenjackson 15y agoWhat if most of the strings look like: "abcabcabcabc....abcabcxabcabcabcabc...abcabc"
- idunno246 15y agobleh, missread the non part
- cpeterso 15y agoHere's my Python implementation. It scans the string only once. It allocates at most 2*len(alphabet) characters while scanning the string. It also bails early if every character in the alphabet has been repeated. import string def first_nonrepeating_char(s, alphabet=string.printable): notrepeated = [] # remember order of appearance! repeated = [] # set of repeated chars, order unimportant for c in s: if c in notrepeated: # c has now been repeated! notrepeated.remove(c) repeated.append(c) if len(repeated) == len(alphabet): return None # every letter repeated! elif c not in repeated: # we have not seen c before notrepeated.append(c) return notrepeated[0] if len(notrepeated) > 0 else None assert first_nonrepeating_char('trait') == 'r' assert first_nonrepeating_char('aardvark') == 'd' assert first_nonrepeating_char('aabbac') == 'c' assert first_nonrepeating_char('aabacc') == 'b' assert first_nonrepeating_char('aaba ccdbe') == ' ' assert first_nonrepeating_char('aabad ccbe') == 'd'
- kenjackson 15y agoLooks good. Although is [] associative in Python (haven't coded in Python in about 12 years)? The append method makes me think it isn't. If it's not then it goes from: O(n) where n is the length of the string to O(mn) where m is the length of the alphabet -- although m is small, so maybe not that bad of a deal, you could almost treat it is a constant factor, since it will be dwarfed by n. I do like the early exit.
- cpeterso 15y agoGood point. Python's [] is a list (array). I considered using a Python dictionary, but that seemed wasteful for a small alphabet. Python does have a built-in set() class, which would have been more appropriate.
- mtogo 15y agoLooks interesting, but i'm really starting to get annoyed at the overuse of the word hacker.
- laconian 15y agoMeh, this looks like a short list of Glassdoor interview questions. Here's the real deal: http://projecteuler.net/ http://projecteuler.net/
- jcapote 15y agoEh, project euler is good, but its more Math than computer science.
- CountHackulus 15y agoThe difference between this and Project Euler is that Project Euler is far more math focused. Once you get past the first couple dozen problems you're just looking for a math trick to make the brute forcing easier. These challenges actually seem to test your knowledge of programming, not mathematical identities.
- iqster 15y agoI like the look of the site! Good job. QQ .. In the very first video on Linked Lists, is the Node type defined correctly? Shouldn't next be a pointer to Node?
- masterj 15y agoMy take on in-place reversing words in a string. Would appreciate any suggestions for improvement :) #include <string.h> void reverseRange(char *i, char *j) { char temp; for (--j; i <= j; ++i, --j) { temp = *i; *i = *j; *j = temp; } } void reverseString(char *str) { char *ptr; // reverse the whole string reverseRange(str, strchr(str,'\0')); // reverse each individual word for (ptr = str; *ptr; str = ptr + 1) { for (ptr = str; *ptr != ' ' && *ptr; ++ptr) {} reverseRange(str, ptr); } }