On 6/22/13 3:18 AM, Jacob Carlborg wrote:
> I watch a couple of videos from a course from Standford, I think it was
> algorithms and data structures or similar. The teacher introduce the Map
> data structure by showing an interface for it and how it works. She
> tells the student that you cannot have any other type for the keys than
> strings.

I'm very surprised to hear that, Stanford is a good university. You'd certainly need good evidence to make us believe that :o).

Andrei

On 6/22/13 5:54 AM, Jacob Carlborg wrote:
> On 2013-06-21 21:11, Walter Bright wrote:
>
>> I've been around long enough to have seen an endless parade of magic new
>> techniques du jour, most of which purport to remove the necessity of
>> thought about your programming problem.
>
> One needs to be opened minded and be able to try new things.
>
>> But there is one technique that stands head and shoulders above the
>> others in improving code quality, sometimes dramatically so. That's unit
>> testing coupled with a coverage analyzer.
>
> I can imagine that these techniques have been new at some point in time
> as well. It's possible that a new technique comes a long that help you
> as much as these techniques do.

Was new in 1962: http://www.dtic.mil/dtic/tr/fulltext/u2/282767.pdf.

Andrei

On 6/22/13 7:10 AM, Adam D. Ruppe wrote:
> On Saturday, 22 June 2013 at 13:55:26 UTC, Jérôme M. Berger wrote:
>> I haven't tried running it, but this looks to me like it won't find
>> "ababc" in "abababc"...
>
>
> You're right. I should have went backwards all the way, not just in the
> one case.
>
> This passes all the tests:

It's still buggy. Overly complicated, too - at 21 lines, it's about twice as large as the canonical implementation.

Andrei

On 6/22/2013 4:01 AM, Andrej Mitrovic wrote:
> On 6/22/13, Walter Bright <newshound2@digitalmars.com> wrote:
>> Can I play, too? Mine from the Digital Mars C library. Haven't looked at it
>>
>> #if 0 /* Smaller but slower under many circumstances. */
>> char *strstr(const char *s1,const char *s2)
>> {   size_t len2;
>>       size_t len1;
>>       char c2 = *s2;
>>
>>       len1 = strlen(s1);
>>       len2 = strlen(s2);
>>       if (!len2)
>> 	return (char *) s1;
>>       while (len2 <= len1)
>>       {
>> 	if (c2 == *s1)
>> 	    if (memcmp(s2,s1,len2) == 0)
>> 		return (char *) s1;
>> 	s1++;
>> 	len1--;
>>       }
>>       return NULL;
>> }
>
> Some things i've noticed about this implementation:

It's wrapped in #if 0 ... #endif ? :-)

> - c2 is assigned by pointer dereference, but then strlen is called on
> s2 and you may get an early exit, meaning c2 was not needed at this
> point. I'd move c2 below the strlen call.

Yup.

> - The memcp doesn't have to compare len2 amount of chars if you've
> already compared the first character, it can call memcmp(s2+1, s1+1,
> len2-1). Although I'm not sure whether it's faster to do it this way
> (maybe it is, if those variables are actually registers..).

Yup.

> And notes about both implementations:
>
> - You're casting a const char * to a char * in the return, you should
> instead provide an overload of strstr taking char* and returning
> char*.

The function bodies would be identical - why have two of them?

> - You seem to have missed the most basic and most important check. You
> didn't attempt to compare the memory address of both pointers against
> each other before doing any other work. If they both point to the same
> memory, the strings are guaranteed to be equal.

Most important? I've never even run across this case.

On Friday, 21 June 2013 at 21:33:43 UTC, Andrei Alexandrescu wrote:
> Also it's fair to ask about implementing a stdlib function itself if the interview concerns some systems-level work; e.g. brute-force strstr() is fair game and I think any engineer should be able to lift it off the ground quickly (to my dismay, only a fraction can). Paradoxically use of stdlib functions may actually hurt; I've seen people who e.g. call strlen() in a loop in order to implement strstr()!

I think it's fair game whatever kind of work you are doing. The tests aren't so much about the algorithm, but showing that the candidate thinks about edge cases, interfaces, possible failure cases etc.  These are things you need to think about even if your job is just to essentially glue libraries together. Simple tasks like strstr just provide a nice small task that test these things.

On 6/22/13, Walter Bright <newshound2@digitalmars.com> wrote:
> It's wrapped in #if 0 ... #endif ? :-)

Hehe. I should totally use that as an argument in a future interview. I'll wrap all my coding-answers in '#if 0', and if they're wrong I'll just say "oh, but this code doesn't *actually* exist!". :p

> The function bodies would be identical - why have two of them?

Yeah nevermind, it's C, I was thinking about C++. Then again D would blow them both out the water since it has inout.

> Most important? I've never even run across this case.

Ok, maybe not that important. It's likely a rare case.

Btw, does anyone know if the typical memcmp implementation tries to compare the pointers' addresses first to see if they match?

On Saturday, 22 June 2013 at 16:38:31 UTC, Andrei Alexandrescu wrote:
> It's still buggy.

What's the test case? I also forgot the empty string, blargh. Let's scrap it.

> Overly complicated, too - at 21 lines, it's about twice as large as the canonical implementation.

Huh, even the shortest impl I can think of is about the same length:

inout(char)* mystrstr(inout(char)* haystack, const(char*) needle) {
        assert(haystack !is null);

        if(needle is null)
                return haystack;

        while(*haystack) {
                auto h = haystack;
                const(char)* n = needle;
                while(*n == *h && *n && *h) {
                        h++;
                        n++;
                }
                if(*n == 0)
                        return haystack;
                haystack++;
        }

        return null;
}


I like this a lot better because it is more straightforward. My first draft was trying to avoid looking at the same character twice, but obviously that didn't work so fixing that ended up doing the same thing as this anyway. I guess better to KISS than be embarrassingly wrong, eh?


You could do it in about ten lines like this:

inout(char)* mystrstr(inout(char)* haystack, const(char*) needle) {
        while(*haystack) {
                auto h = haystack;
                const(char)* n = needle;
                while(*n == *h && *n && *h)
                        h++, n++; // LOL COMMA OPERATOR
                if(*n == 0)
                        return haystack;
                haystack++;
        }
        return null;
}


But I really like the null check. Yes, I know the hardware does it, but it is a pain in the butt to fire up a debugger when a null hits you in the middle of something. The nice assertion failure message is so much faster to handle.

On 6/22/2013 12:12 PM, Andrej Mitrovic wrote:
>> Most important? I've never even run across this case.
>
> Ok, maybe not that important. It's likely a rare case.
>
> Btw, does anyone know if the typical memcmp implementation tries to
> compare the pointers' addresses first to see if they match?

I don't know about typical, but I've never seen one that did.

On 2013-06-22 18:27, Andrei Alexandrescu wrote:

> I'm very surprised to hear that, Stanford is a good university. You'd
> certainly need good evidence to make us believe that :o).

I was surprised when I watch the video. But here it is:

https://itunes.apple.com/se/podcast/6.-programming-abstractions/id384232917?i=85092416&mt=2

Around 14:50 in the video.

She actually didn't say it was impossible.

-- 
/Jacob Carlborg

On 2013-06-22 17:24, QAston wrote:

> I'm not saying that you can't get all of this on your own, yet it's
> easier that way. I was a self taught programmer, but I feel that my
> knowledge is more complete now (and some of the knowledge is very
> important for a systems programmer). It's obviously the same other way
> around - you can pass all the exams and get nothing from that. It's up
> to you what you're going to do with free time. Important note: public
> unis are free in my country, I probably wouldn't study otherwise.

I would say if you want to learn about programming, read these newsgroup. I have learned more when reading these newsgroup then I ever could at the university. So I just want to say, thank you all.

-- 
/Jacob Carlborg