On Friday, 21 June 2013 at 22:23:01 UTC, Adam D. Ruppe wrote:
> being built in to D

Or maybe it is because everybody else does it in the documentation and such, since #include <assert.h> in C isn't *that* big of a deal. idk, all I do know for sure is that I do it now and didn't before.

On 6/21/13 2:50 PM, Adam D. Ruppe wrote:
> On Friday, 21 June 2013 at 21:33:43 UTC, Andrei Alexandrescu wrote:
>> 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).
>
> But, should the return value be const or not? :P
>
>
> I think I'd write in D just cuz of inout().

That would be a nice touch and bring bonus points, but in most of the cases I tell the candidate to gloss over that detail.

Andrei

On 6/21/13 3:22 PM, Adam D. Ruppe wrote:
> Just for laughs I just slapped together a strstr

Post it and I'll destroy it.

Andrei

On 6/21/2013 3:35 PM, Andrei Alexandrescu wrote:
> On 6/21/13 3:22 PM, Adam D. Ruppe wrote:
>> Just for laughs I just slapped together a strstr
>
> Post it and I'll destroy it.

Can I play, too? Mine from the Digital Mars C library. Haven't looked at it since 2001.
==================================================

/*_ strstr.c */
/* Copyright (C) 1985-2001 by Digital Mars		*/
/* All Rights Reserved					*/
/* www.digitalmars.com					*/
/* Written by Walter Bright				*/

#include	<stdio.h>
#include	<ctype.h>
#include	<stddef.h>
#include	<string.h>
#include	<stdlib.h>

#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;
}
#else
#include <limits.h>    /* defines UCHAR_MAX */
/****************************************************************************
See "Algorithms" Second Edition by Robert Sedgewick.  Boyer-Moore string
search routine.
****************************************************************************/
char *strstr(const char *text, const char * pattern)
{
  const size_t M = strlen(pattern);
  const unsigned long N = strlen(text);
  const char *p_p = pattern;
  const char *t_p;
  size_t skip[UCHAR_MAX + 1];
  size_t i, j;

  if(M == 0)
    return (char *)text;

  if(M > N)   /* If pattern is longer than the text string. */
    return 0;

#if __INTSIZE == 4
  _memintset((int *)skip, M, UCHAR_MAX + 1);
#else
  { size_t *s_p = skip + UCHAR_MAX;
    do
    {
      *s_p = M;
    }while(s_p-- > skip);
  }
#endif

  p_p = pattern;
  do
  {
    skip[*(const unsigned char *)p_p] = M - 1 - (p_p - pattern);
  } while(*++p_p);

  p_p = pattern + M - 1;
  t_p = text + M - 1;

  while(1)
  {
    char c;

    c = *t_p;
    if(c == *p_p)
    {
      if(p_p - pattern == 0)
	return (char *)t_p;

      t_p--; p_p--;
    }
    else
    {
      size_t step = M - (p_p - pattern);

      if (step < skip[(unsigned char)c])
	step = skip[(unsigned char)c];

      /* If we have run out of text to search in. */
      /* Need cast for case of large strings with 16 bit size_t... */
      if((unsigned long)(t_p - text) + step >= N)
	return 0;

      t_p += step;

      p_p = pattern + M - 1;
    }
  }
}
#endif	/* #if 0 */

On Fri, Jun 21, 2013 at 06:12:57PM -0400, Nick Sabalausky wrote:
> On Fri, 21 Jun 2013 09:47:46 -0700
> "H. S. Teoh" <hsteoh@quickfur.ath.cx> wrote:
> > 
> > universities that actually *teach* real programming are more interested in finding solutions to uncomputable problems than teaching students how to solve computable ones
> > 
> 
> That doesn't match my experience (also in the US here).

Actually, I'm up in the Great White North, so my perception of "North America" may be a bit biased on the first word. :-P


> Granted, all my info is from ten years ago, but what I saw was mainly a bunch of what The "Joel on Software" guy called "Java Schools" <http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html>.

LOL... that article made me laugh. Thanks for the great read!


> The following includes what I've seen at BGSU and OSU (party schools, not that I personally attended OSU, but I did have a friend that went through OSU's "RESOLVE/C++" stuff) and also JCU (a private univ that, at least around Cleveland, is highly-regarded by everyone except me).
> 
> What I've seen at these places, and apparently many others from what I understand, is that while they *do* recognize the importance of creating programmers, the problems are:
> 
> - The theory is minimal to make sure they get all those high-paying
>   students through the revolving door.

Huh. I had the opposite experience. We were pounded with so much theory from day one, and then summarily executed on our Computability Theory finals (the infamous exam that was so hard, you were allowed to bring *anything* -- any textbook, reference book, your desktop PC if you were so inclined -- and none of it would help), that I came out with a rather strong distaste for anything that mentions the word "computability", lasting for quite a while before it wore off.


> - Tests and exams do *not* teach people. An yet, that's where the
>   emphasis is, instead of on instruction.
> 
> - The really *big* issue: You just simply CANNOT expect people to go
>   from beginner to competent programmer when they spend *at most*
>   one-third of their credits, and about 3 hours a week, over a mere 4
>   years on actual programming material instead of irrelevant liberal
>   arts garbage that *belongs* in high school, not a college so-called
>   "major".

That, I have to agree. I wanted to double-major in CS and Chemistry, but gave up on the first day in 2nd year when I looked at my course / lab / programming project schedule, and said, "that's not gonna work". Without adequate time actually spent programming, it's impossible to get good at it.


> - The nasty little details like pointer/memory problems, linker errors,
>   etc that real people have to deal with are neatly glossed over and
>   sidestepped.

OK, that's one of my pet peeves. Back in the day, I was taught pointers (though not linker errors -- I learnt that on my own) and recursion. Nowadays, people hear the word "pointer" and go "ewwww", and when you say "recursion" their eyes glaze over. What on earth did they do to the CS programs?!


> - There was one CS101 teacher (I had to tutor her unfortunate students)
>   who constantly bragged about being from a real-world software
>   company...but she was a Java-addict (circa v1.2-v1.4) who kept trying
>   to teach OO *before* basic flow-of-execution. Consequently, none of
>   her unfortunate students had the slightest clue what was going on.

Ugh. Talk about putting the cart before the horse...


> - Many of the professors are terrible programmers themselves. For
>   example, I had one who openly admitted the only language he knew was
>   C, and yet at one point it became painfully obvious that he had
>   almost no comprehension of null-terminated strings.

That's the beef I have with over-emphasis on CS theory. There's nothing wrong with theory in and of itself -- in fact it's foundational and very much indispensible -- but when you become so detached from reality that you think in terms of pure idealizations -- when you can *only* think in terms of pure idealizations -- that you can't even write a single line of real code without some external help, then something has clearly gone very, very wrong.


> - Many of the teachers don't even teach, they just collect the
>   thousands of dollars in tuition and give you a book recommendation
>   (really more of a "demand" than a recommendation).

That's because the incentives are all wrong. Professors aren't paid to teach; they're paid to produce research. Publish or perish, so goes the saying in those circles. To them, teaching is an additional burden imposed upon them that they'd rather get over with ASAP and get back to their research, whatever it takes. Turn away the students showing up at your office hours. Bore them to death in class so they wouldn't know *what* to ask even if they wanted to. Read from a photocopy of the textbook word-for-word to pass lecture time with zero effort (I've actually been in a class where this was done). Anything, to get it over with and get back to the work that pays.

Some of my best teachers in university were part-time lecturers, one of whom won several teaching awards and accolades for 3 years straight. I don't know if there's even one faculty member that ever got *one* teaching award. (On the contrary, a certain faculty member was so arrogant of his tenurehood that he'd show up on evaluation day and tell students to their face that they can write whatever they want and it wouldn't affect him in the least, 'cos his tenure meant he can never be fired. And of course, he consistently gets rock-bottom reviews from students, and incoming students are consistently warned by said students to avoid his courses at all costs.)


>   Now, I'm a strong believer in being self-taught and learning from
>   books, but all I need for that is a library card, not a $100k debt
>   and four years of elitist attitudes from people who clearly don't
>   know what they're doing anyway.

Heh. Nearly all of my programming skills are self-taught (well, and learned from experience now that I have some number of years in the industry), but I'm no reader either. I was doing online learning long before the 'Net became cool, and every now and then I still browse around learning new algorithms and stuff, while everybody else is clicking their lives away on FB and twitter (no offense, Andrei, but I do think FB is an evil waste of time, at least when it comes to the way most people use it).


T

-- 
If it tastes good, it's probably bad for you.

On Friday, 21 June 2013 at 22:35:55 UTC, Andrei Alexandrescu wrote:
> Post it and I'll destroy it.


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

    if(needle is null)
        return haystack;

    const(char)* where = needle;
    inout(char)* gotit;

    while(*haystack) {
        if(*haystack == *where) {
            if(gotit is null)
                gotit = haystack; // store where the match started
            where++;
            haystack++;
            if(*where == 0)
                return gotit;
        } else {
            // if we were in the middle of a match, we'll want to
            // check the current character again so only advance if
            // we're at the beginning
            if(gotit is null)
                haystack++;
            else {
                // partial match, but not complete so no good
                // start over, including the current *haystack
                where = needle;
                gotit = null;
            }
        }
    }

    return null;
}


unittest {
    void test(string haystack, string needle, size_t line = __LINE__) {
        import core.stdc.string;
        import std.conv;

        // .ptr is fine because the test uses all string literals, which are 0 terminated automatically
        assert(strstr(haystack.ptr, needle.ptr) is mystrstr(haystack.ptr, needle.ptr), to!string(line));
    }

    test("foobar", "f");
    test("foobar", "ob");
    test("foobar", "o");
    test("foobar", "a");
    test("foobar", "ar");
    test("foobar", "ea");

    test("bedtime bedazzled!", "beda");
}




I've heard of Boyer-Moore but don't actually know it, so I'd have to look it up! The brute force loop is simple enough though without needing a great deal of thought, though my first run through did actually fail the unittest, since I neglected the commented section in the else{} part. So if I was doing it on a whiteboard, (or didn't immediately use "foo" as a test variable, with the repeated o) I might not have actually caught that!

On Fri, Jun 21, 2013 at 04:02:20PM -0700, Walter Bright wrote: [...]
> /****************************************************************************
> See "Algorithms" Second Edition by Robert Sedgewick.  Boyer-Moore string
> search routine.
> ****************************************************************************/
> char *strstr(const char *text, const char * pattern)
> {
[...]
> }

Very nice!

Does it help at all to cast to uint[] and search that instead of just char[]? Or do the complications caused by non-alignment outweigh the benefits?

And where's the unittest block? ;-)  (OK OK, I know this wasn't written
in D. But I had to ask. :-P)

Also, this is a prime example of code you'll *never* arrive at just by blind application of TDD. (And there's my feeble attempt to bring this back on topic. :-P)


T

-- 
This sentence is false.

On Thursday, 20 June 2013 at 12:16:54 UTC, deadalnix wrote:
> On Thursday, 20 June 2013 at 10:13:53 UTC, Jacob Carlborg wrote:
>> On 2013-06-20 00:47, Nick Sabalausky wrote:
>>
>>> - Writing a unittest first forces the API to be designed before the
>>>  implementation is written. But implementation is necessary to flush
>>>  out unexpected design requirements (If you think you can always
>>>  come up with an appropriate design and interface before
>>>  implementing, then you're just plain wrong). Sometimes the
>>>  appropriate design and API is obvious. Sometimes it isn't. When it
>>>  isn't, then TDD skirts dangerously close to some of the problems of
>>>  "Waterfall Model". Sure, TDD advocates refactoring-as-needed, but I
>>>  can do that with or without TDD.
>>
>> Just because you have written a test doesn't mean you cannot change it. Perhaps you come up with a better API design, then change the tests.
>
> When I start something, it isn't always clear what mental model of the problem fit best the problem. I usually wait until I know I have a consistent mental model of the problem to write test. Otherwise, tests tend to get into your way to change the API( because you need to change tests as well. I start writing test when I know what kind of API make sense (it isn't always finished, but I know what it will look like overall).
>
> Which lead to TITMOD, test in the middle of dev.

You should write a book on that, it'd be a total paradigm shift for the non-yet-believers of TITMOD.

On Friday, 21 June 2013 at 21:33:43 UTC, Andrei Alexandrescu wrote:
> If there's any need to reach for documentation, the interviewer has failed. When interviewing we (at Facebook) ask problems that are likely to appear in a normal day's work, but for which the typical libraries don't help. (E.g. many libraries don't can't help with implementing unstable remove (see std.algorithm).)
>

Amongst other thing, I did a merge sort and a quicksort in my FB interviews. It is fair to assume they can be found as libraries. But overall the process is really accurate to assert what a dev can do. Most question were technically challenging, but weren't tricks or overly complicated and useless.

For the anecdote, my quicksort was buggy, but my interviewer convinced me it wasn't - when later check (after the interview) demonstrated is indeed was.

> 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()!
>

When i was doing interview, I used to ask people to program a function that sort an array of integer. No constraint of performance or anything, the good old 5 lines bubble sort would have been accepted. Most can't.

On 2013-06-21 23:33, Andrei Alexandrescu wrote:

> If there's any need to reach for documentation, the interviewer has
> failed. When interviewing we (at Facebook) ask problems that are likely
> to appear in a normal day's work, but for which the typical libraries
> don't help. (E.g. many libraries don't can't help with implementing
> unstable remove (see std.algorithm).)
>
> 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()!

Yes, if they tell you that from the beginning. Instead they said: "solve it anyway you like", then they started to add restrictions.

-- 
/Jacob Carlborg