Hacker CS: Computer Science Challenges

http://hackercs.com/streams/Computer-Science-Challenges/

by hackly • 15 years ago

59 21 15 years ago

spaghetti3• 15 years ago

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

kenjackson4• 15 years ago

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?

idunno2462• 15 years ago

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

spaghetti3• 15 years ago

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?

cpeterso3• 15 years ago

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'

mtogo• 15 years ago

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

laconian• 15 years ago

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

jcapote• 15 years ago

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

CountHackulus• 15 years ago

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.

iqster• 15 years ago

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?

hackly• 15 years ago

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

bm1362• 15 years ago

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.

masterj2• 15 years ago

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

cpeterso3• 15 years ago

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

masterj2• 15 years ago

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

Hacker CS: Computer Science Challenges

Related Stories