Hacker CS: Computer Science Challenges | Hacker News Reader

Hacker CS: Computer Science Challenges

hackercs.com

59 pointshackly21 comments

My 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);
        }
    }

Looks good. reverseRange()'s end condition can just be `i < j` because you don't need to swap the middle character with itself. :)

Doh! Somehow I got that mixed up in my head because that was my original intention. Thanks!

Looks interesting, but i'm really starting to get annoyed at the overuse of the word hacker.

Bored 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;
}

If 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?

It 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

What if most of the strings look like:

"abcabcabcabc....abcabcxabcabcabcabc...abcabc"

bleh, missread the non part

I 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?

Yes, 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.

One 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 :-)

Here'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'

Looks 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.

Good 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.

Meh, this looks like a short list of Glassdoor interview questions. Here's the real deal: http://projecteuler.net/

Eh, project euler is good, but its more Math than computer science.

The 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.

I 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?

Of course it should! Fixed the typo. Thanks for pointing it out, and thanks for you kind words :)

The site, unfortunately, does not look good-IMO that would be the last way I would describe it. The videos are amazing though, good job.

Reply on news.ycombinator.com