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?
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:
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:
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...