Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

Rick Hallihan

Rick Hallihan RickH

Niner since 2004

I'm basically a professional computer geek. I maintain a broad skillset so that I can pick up whatever gets thrown my way...
  • PhotoSynth: What. How. Why.

    Ok, geeky question..  How much processing horspower does this thing take?  If I feed it 1000 5MP photos of a tourist trap, how long (roughly) does it take to churn through and create a 3d model like you showed in the demo?  What if instead of individual photos, I feed it a video of a walkthrough of a house?  Could it use each frame and build a high resolution 3d model of the inside of the house? 
  • Gary Daniels and Evan Goldring - Mock whiteboard problem

    Beyond the specifics of the problem definition (what is a palindrome, case sensitivity, whitespace, punctiation, etc.) I think that it's also important to ask what properties the ideal solution should have.  Many posters have utilized pre-built string reversals and string compares.  This allows them to code a quick solution, but it may not be the most optimal in terms of performance, i.e. cpu time and memory utilization.

    My thought process followed something like this:

    1. work on the assumption that the best solution is the most efficient at execution time.  This makes the problem more interesting...

    2. Reverse and compare are too expensive in terms of CPU and Memory.

    3. I think you should be able to do that at around O(n), where n is the length of the string.

    4.  I played around with different ideas about traversing the string once, and creating a hash of 1) the entire string, and 2) the first half of the string.  The importance of the order of the characters makes this impractical though, and the different cases of odd and even length strings add complexity.  Abandoned this....

    5.  Next idea was to start with pointers at both ends and work my way towards the middle, comparing as I go.  I added a while/compare to skip spaces.  Code follows:

    bool IsPalindrome(TCHAR* tcstring)
    {
     if(tcstring==NULL|| *tcstring==NULL) return false;
     TCHAR* first=tcstring;
     TCHAR* last=(tcstring+_tcsclen(tcstring)-1);
     TCHAR space=*_T(" ");

     while(1)
     {
      if(*first!=*last)
       return false;
      while(*(++first)==space);
      while(*(--last)==space);
     if(last<=first)
      return true;
     
     } 
    }

    Now I wasn't quite happy with having to use the built-in _tcsclen, but this does provide a relatively efficient result, and I managed to work in the ignoring of spaces, and I checked for null strings and null pointers.

    6.  In an effort to make the solution a little more "pure", I decided to manually traverse the list, looking for the null, and then work my way half-way backwards checking as I go backwards. Code follows:

    bool IsPalindrome(TCHAR* tcstring)
    {
     if(tcstring==NULL|| *tcstring==NULL) return false;
     TCHAR* ptr=tcstring;
     TCHAR* halfptr;
     while(*(++ptr)!=NULL);
     halfptr=tcstring+(ptr-tcstring)/2;
     while(*(tcstring++) == *(--ptr) && ptr>halfptr);
     if(*(--tcstring) == *ptr) return true; 
     return false;
    }

    I like this solution for its efficiency, even though it won't handle spaces, case, or punctuation.  I could handle any of those by expanding the while loops.

    7.  Lastly, I thought I'd see if I could gain anything by trying the typicalyl gimmicky recursion method.  Code follows:

    bool IsPalindromeHelper(TCHAR* first, TCHAR* last)
    {
     if(first>=last) return true;
     if(*first!=*last) return false;
     return(IsPalindromeHelper(first+1,last-1));
    }


    bool IsPalindrome(TCHAR* thestr)
    {
     TCHAR* last=thestr;
     while(*(++last)!=NULL);
     return(IsPalindromeHelper(thestr,--last));
    }

    While the recursion adds a bit of a "cool" factor to the solution, it doesn't handle spaces or case, and you have the added overhead of the recursive call, so I don't think it's quite worth it.

    8.  I'd probably go back to my second solution, and work in any requirements for spaces / case insensitivity. (and add comments of course!)

    9.  For preliminary testing, I'd include null pointers, invalid pointers, null strings, non-terminated strings, even-length palindromes, odd-length palindromes, even and odd length non-palindromes, near palindromes with differences at the beginning/end, near palindromes with differences at the middle two chars for even length, and differences at +/-1 from middle for odd length.  Palindromes and non-palindromes of length 1,2, 3, and very large palindrome and non-palindrome inputs of lengths 2^10, 2^16-1,2^16,2^16+1, 2^32-1,2^32, 2^32+1, etc.  Also test palindromes that excercise any of the special requirements, i.e. spaces, punctuation, etc...  Include these special chars at beginning/end/middle...