The Daily WTF: Curious Perversions in Information Technology

da Doctah · 2011-07-21 Reply Admin

somechick:
I still say my favorite interview question I was ever asked was "What is this '|' symbol?" 'A Pipe' "What is it used for?" 'It's a pipe.' My brain went blank for a couple seconds there and then I explained what pipes do on the unix command line (in more detail than was necessary, from what my boss said afterwards, as they weren't looking for the term FIFO, oddly enough).

You could have gone on to explain the origin of the term: "Pipe derives from the expression of approval used by the character Artie (aka 'the strongest man in the world') in the cult sitcom 'The Adventures of Pete and Pete'".

boog · 2011-07-21 Reply Admin

Fat:
By the way, no one has yet answered my question about recursive fibonacci numbers calculation. I've got one solution, but it looks kind of sloppy (at least when the implementation is in C++; I guess, on Haskell or Matlab it'd look much better). I want to see if you come up with something more elegant. And besides, I think this problem is pretty neat.

Actually, no, your problem is not very neat at all. Asking for fibonacci numbers in O(n) using recursion is boring, because it's trivial to achieve O(n) with a simple loop, so the recursion is an unnecessary requirement.

Calculating fibonacci numbers in O(log(n)) is what I'd call interesting.

EvanED · 2011-07-21 Reply Admin

boog:
Actually, no, your problem is not very neat at all. Asking for fibonacci numbers in O(n) using recursion is boring, because it's trivial to achieve O(n) with a simple loop, so the recursion is an unnecessary requirement.
Calculating fibonacci numbers in O(log(n)) is what I'd call interesting.

I have three objections to that statement.

First, your proposed problem is interesting in a very different way -- much more of a "mathy" interesting, and not really a "programming" interesting. That's not bad by any means, but it is different and at least for me appeals to a very different part of my mind.

Second, you say "a simple loop", but what if you're writing Fibonacci in a functional language? Then that "simple loop" suddenly becomes much more difficult, and the recursive expression is very natural.

Third, so what if it's somewhat of an artificial requirement? That doesn't make it uninteresting. Most people add lots artificial requirements on a regular basis. I rock climb. That doesn't become uninteresting because the "go up the rock instead of walking up that trail" is unnecessary.

I thought it was reasonably neat.

2011-07-21 Reply Admin

With "Wrong Answer", I have heard of a few occasions that metadatabases have worked (Reddit, for example, gets by with some periodic performance problems). I believe that it can work when it's done to get things done, but fails when it's done as a work-avoidance technique.

2011-07-21 Reply Admin

[quote user="boog"][quote user="Fat"]Calculating fibonacci numbers in O(log(n)) is what I'd call interesting.[/quote]

That would indeed by interesting, but since the result has a size of O(n), it is not possible.

2011-07-21 Reply Admin

dohpaz42:
resmoker10:
Actually that's something that bugs me about C# that it doesn't have a string reverse function. For some reason Microsoft didn't see fit to add a string.Reverse() method and I have had to roll my own.
Password reversal is a useful when storing passwords in a database to obscure them from potential attackers. More recently what with all the hacking stories in the news I have increased my precautions by reversing the strings two times before inserting them into the password table so they are double encrypted.

I hope that you don't mean that you do String.encrypt(String.reverse(String.reverse)), and I'm just reading your post wrong!

YHBT.

He doesn't even encrypt them , dummy

2011-07-21 Reply Admin

Abso:
Anon:
Other than this being a reverse function, since I am not a java developer what *would* be the proper way to reverse a string since the interview question explicitly asks how you would improve on the function.
I'm not a java developer either, but I suspect the answer is to use a loop instead of recursion.

Or (even using recursion), swap rather than move:

String reverse(String s)
{
  int sLength = s.length();

  return sLength<=2?s:(s.charAt(sLength-1) + reverse(s.substring(1,sLength-2) + s.charAt(0));

}

or something....

I'm amused by the response: Use meaningful names and comment code...

2011-07-21 Reply Admin

a:
Abso:
Anon:
Other than this being a reverse function, since I am not a java developer what *would* be the proper way to reverse a string since the interview question explicitly asks how you would improve on the function.
I'm not a java developer either, but I suspect the answer is to use a loop instead of recursion.
Or (even using recursion), swap rather than move:
String reverse(String s)
{
  int sLength = s.length();

  return sLength<=2?s:(s.charAt(sLength-1) + reverse(s.substring(1,sLength-2) + s.charAt(0));

}
or something....

I'm amused by the response: Use meaningful names and comment code...

Or:

String reverse(String s)
{
  int sLength = s.length();
  if(sLength<=1) return s);
  return reverse(s.subString(sLength/2, sLength-1)) + reverse(s.subString(0, sLength/2-1));
}

2011-07-21 Reply Admin

EvanED:
First, your proposed problem is interesting in a very different way -- much more of a "mathy" interesting, and not really a "programming" interesting. That's not bad by any means, but it is different and at least for me appeals to a very different part of my mind.
Second, you say "a simple loop", but what if you're writing Fibonacci in a functional language? Then that "simple loop" suddenly becomes much more difficult, and the recursive expression is very natural.

Third, so what if it's somewhat of an artificial requirement? That doesn't make it uninteresting. Most people add lots artificial requirements on a regular basis. I rock climb. That doesn't become uninteresting because the "go up the rock instead of walking up that trail" is unnecessary.

I agree with your first and third points but not so much your second one. If you have a "simple loop" then it's easy to rewrite it with recursion:

def fib(n): # with a loop (using 'while' instead of 'for' so the conversion is clearer)
m, a, b = 0, 1, 0
while m != n:
m, a, b = m + 1, b, a + b
return b
def fib2(n): # with recursion
def loop(m, a, b):
if m == n: return b
else: return loop(m + 1, b, a + b)
return loop(0, 1, 0)
(define (fib n) ; same approach in the functional language Scheme
(define (loop m a b)
(if (= m n) b
(loop (+ m 1) b (+ a b))))
(loop 0 1 0))

Furthermore, functional languages always end up providing some way to run imperative code (even Haskell has its ST monad or, in the extreme case, unsafePerformIO).

smxlong · 2011-07-21 Reply Admin

Hanoi 4 ever:
Reversing a string is a poor example of recursion, as it's so obviously easier to do with a loop. Use something like quicksort or a tree-traversal.

You want to choose an easier example? I think you overlooked the part where the question is supposed to be difficult, not easy.

2011-07-21 Reply Admin

SG_01:
Fat:
I don't really like this joke. It'n not a legitiamte use of recursion, it's just an infinite loop. Of course, it doesn't defeat its real purpose, make beginner programmers feel superior to anyone who didn't spend 2 hours studying algorithms.

It's actually NOT an infinite loop. Back to school ^^

HAHAHA PMSL

2011-07-21 Reply Admin

DWalker59:
As mentioned, factorial is often used as an example of something that can easily be understood recursively. But implementing factorial in a loop is often easier (And sometimes shorter). Depending, of course, on whether you allow non-integers (the gamma function) as arguments.
Directory traversal, on the other hand, seems to be easier to implement recursively. Depending on exactly what you're doing, there might be more "state" to keep track of, which recursion can do more neatly.

I think the point being made was that there is a certain intuition in implementing Factorial recursively...the gamma function is an extension of the Factorial idea, but I wouldn't really have thought it has context here - especially as everyone is talking about exercises for beginner programmers.

Likewise (or perhaps conversely), although I can see there is a certain intuition that makes recursion suitable for Directory (or any tree) traversal, but I don't really understand what you mean by the comments about more state=.

Thanks for playing, Dave.

2011-07-21 Reply Admin

I think you forgot to run ROT13 on that. Twice.

You really need to combine the techniques. Something such as:

reverse(s).rot13().ascii2ebcdic().rot13().reverse().ebcdic2ascii()

would be the beginnings of an industrial-strength obfuscator.

2011-07-21 Reply Admin

Not really a smart way to reverse a string however. Even without built in support for reversing strings, this could be done much more readably just iterating through the string in reverse.

Recursion has its place, but is a PITA to debug or easily understand from just a quick look.

I find recursion much easier to understand, when its being demonstrated in some area where it is actually useful, like file spidering etc.

2011-07-21 Reply Admin

You'd have no hope of WRITING your own quick sort or tree traversal.

However, you'd probably still be able to implement it into your own code. I'd guess the majority of programmers (from what i've seen in business, gives me a bit of an ego boost when I see how crap some other peoples code is) have lots of things they use but dont understand.

I miss the 80's and 90's sometimes, when you had to not only understand stuff, but to learn new stuff, you had to either find a book with the info in (or someone who knew about it), or just spend hours and hours hacking stuff from scratch. I have to admit I can get more done nowadays however by leveraging other peoples code and not reinventing the wheel..

Coyne · 2011-07-21 Reply Admin

Sounds very familiar!

My boss sent me to interview someone; I think it was because he was too chicken to tell her to her face that he had no intention of hiring her.

EvanED · 2011-07-21 Reply Admin

Mr.'; Drop Database --:
EvanED:
Second, you say "a simple loop", but what if you're writing Fibonacci in a functional language? Then that "simple loop" suddenly becomes much more difficult, and the recursive expression is very natural.
I agree with your first and third points but not so much your second one. If you have a "simple loop" then it's easy to rewrite it with recursion:

And if you have recursion, it's easy to mechanically transform it into iterative code that doesn't use recursion. I'm not sure what your point is.

People who like to write in functional languages don't do it that way. (Or at least I suspect. At least I don't really think that way; that's definitely not how I came up with my answer.) They don't come up with an iterative solution and turn it into the recursive one because that's what the language supports any more than people who do all their programming in imperative languages make functions by coming up with the recursive one and then transforming it to an explicit stack. In both cases you may, once in a few blue moons, actually do that, but it's not the norm.

Furthermore, functional languages always end up providing some way to run imperative code (even Haskell has its ST monad or, in the extreme case, unsafePerformIO).

Yeah, but how does code that uses one of those compare to a recursive solution in those languages? I didn't say it was impossible, just that it's harder than the recursive version. And I stand by that statement. :-)

Maurits · 2011-07-21 Reply Admin

boog:
Fat:
Calculating fibonacci numbers in O(log(n)) is what I'd call interesting.

That would indeed by interesting, but since the result has a size of O(n), it is not possible.

Perhaps we should define what n is?

Here's an O(1) solution.

http://www.dreamincode.net/code/snippet6172.htm

It can be optimized further by realizing that termTwo is always less than .5 so you can just do (int)(termOne + 0.5);

2011-07-21 Reply Admin

EvanED:
Mr.'; Drop Database --:
EvanED:
Second, you say "a simple loop", but what if you're writing Fibonacci in a functional language? Then that "simple loop" suddenly becomes much more difficult, and the recursive expression is very natural.
I agree with your first and third points but not so much your second one. If you have a "simple loop" then it's easy to rewrite it with recursion:
And if you have recursion, it's easy to mechanically transform it into iterative code that doesn't use recursion. I'm not sure what your point is.

That functional programmers see recursive functions as a way to implement loops, so they're not really easier than loops, per se.

EvanED · 2011-07-21 Reply Admin

Mr.'; Drop Database --:
EvanED:
Mr.'; Drop Database --:
EvanED:
Second, you say "a simple loop", but what if you're writing Fibonacci in a functional language? Then that "simple loop" suddenly becomes much more difficult, and the recursive expression is very natural.
I agree with your first and third points but not so much your second one. If you have a "simple loop" then it's easy to rewrite it with recursion:
And if you have recursion, it's easy to mechanically transform it into iterative code that doesn't use recursion. I'm not sure what your point is.
That functional programmers see recursive functions as a way to implement loops, so they're not really easier than loops, per se.

Oh, if I understand what you're saying now, I think we may be talking across each other a bit while actually agreeing. :-)

What I meant by "then that 'simple loop' suddenly becomes much more difficult, and the recursive expression is very natural" can probably be more precisely stated as follows:

me:
In a functional language, writing that 'simple loop' in an imperative fashion (using Scheme's do, Haskell's ST monad, etc.) can suddenly become a lot harder than the natural recursive presentation.

Is that clearer? Does it sound like that was the point of "disagreement"?

2011-07-22 Reply Admin

bencoder:
bob:
"I looked it up and it doesn't anyway"
Not suprising, when would that ever come in useful for anything useful?

Have you seen Java?

Yup, the horns, the facial tentacles, the claws, all of it. And not a noodly appendage in sight.

2011-07-22 Reply Admin

dohpaz42:
resmoker10:
Actually that's something that bugs me about C# that it doesn't have a string reverse function. For some reason Microsoft didn't see fit to add a string.Reverse() method and I have had to roll my own.
Password reversal is a useful when storing passwords in a database to obscure them from potential attackers. More recently what with all the hacking stories in the news I have increased my precautions by reversing the strings two times before inserting them into the password table so they are double encrypted.

I hope that you don't mean that you do String.encrypt(String.reverse(String.reverse)), and I'm just reading your post wrong!

You are reading it wrong, he's doing String.reverse(String.reverse). Doing it your way would be insecure.

2011-07-22 Reply Admin

Hanoi 4 ever:
dohpaz42:
WC:
No, it's the John Galt from Atlas Shrugged.
I read that code snippet and thought, "Is that really a recursive function to reverse a string?" ... Yup, apparently it is. Wow.

Reversing a string is a simple analogy for describing recursive functions. It's an easy concept to understand, and just as simple to implement, and it demonstrates recursion in an easy to understand way. Usually this sort of exercise is done in a beginner programming class (at least, it was for me back when I took beginning programming in college).

Reversing a string is a poor example of recursion, as it's so obviously easier to do with a loop. Use something like quicksort or a tree-traversal.

That would be horribly inefficient. I bet I could train a finite-context automaton to do that far more quickly than your tree-walk could do it.

2011-07-22 Reply Admin

Jeff:
3) As a coding exercise, off the top of my head I'd probably use a one character buffer and swap characters from the outside to the inside. Ala:
strToRev="CodeTest";

for(int i=0; i< strToRev.length() / 2; i++) { int farCharPosition = strToRev.length()-i-1; char buf = strToRev[farCharPosition]; strToRev[farCharPosition] = strToRev[i]; strToRev[i] = buf; }

Thoughts?

Real programmers would use an XOR-swap.

2011-07-22 Reply Admin

Thanks EvanED.

I don't like using >= I like keeping the symbol as one. Don't ask why, as I don't even know.

For some reason I remember strings simply being arrays, but if they re immutable in Java, then it certainly doesn't hold. Definitely more of a C++ guy despite two years of java that felt like a piss take at times. It's good to know these things though I hopefully never need to apply them.

EvanED · 2011-07-22 Reply Admin

Dave:
Jeff:
3) As a coding exercise, off the top of my head I'd probably use a one character buffer and swap characters from the outside to the inside. Ala:
strToRev="CodeTest";

for(int i=0; i< strToRev.length() / 2; i++) { int farCharPosition = strToRev.length()-i-1; char buf = strToRev[farCharPosition]; strToRev[farCharPosition] = strToRev[i]; strToRev[i] = buf; }

Thoughts?

Real programmers would use an XOR-swap.

Real Programmers know that xor swaps are extremely likely to be slower than temporary-variable swaps.

oheso · 2011-07-22 Reply Admin

Jay:
I thought of it as "the I'm-thinking-of-a-number management style".

Funny, I thought that was a matrimonial style ...

2011-07-22 Reply Admin

I guess the easiest solution is the best and fastest one - at least on my machine.

For i = Len(s) To 1 Step -1

meh = meh & Mid(s, i, 1) 'mid == substring

Next i

funcX2 = meh

(yes vb :P )

da Doctah · 2011-07-22 Reply Admin

EvanED:
Dave:
Jeff:
3) As a coding exercise, off the top of my head I'd probably use a one character buffer and swap characters from the outside to the inside. Ala:
strToRev="CodeTest";

for(int i=0; i< strToRev.length() / 2; i++) { int farCharPosition = strToRev.length()-i-1; char buf = strToRev[farCharPosition]; strToRev[farCharPosition] = strToRev[i]; strToRev[i] = buf; }

Thoughts?

Real programmers would use an XOR-swap.
Real Programmers know that xor swaps are extremely likely to be slower than temporary-variable swaps.

Not in assembly code, but you do have to distinguish between strings with even or odd numbers of characters, or you run the risk of turning the character at the very center into all zeroes.

2011-07-22 Reply Admin

Coyne:
Sounds very familiar!
My boss sent me to interview someone; I think it was because he was too chicken to tell her to her face that he had no intention of hiring her.

Might have been because (a) he was too busy doing other things and/or (b) might have wanted to offer you the experience of doing an interview in a context where if you perform badly the consequences are minimal.

OTOH perhaps not - I'm unfamiliar with your exact situation so I'm guessing.

Anonymouse · 2011-07-22 Reply Admin

Jeff:
strToRev="CodeTest";
for(int i=0; i< strToRev.length() / 2; i++) { int farCharPosition = strToRev.length()-i-1; char buf = strToRev[farCharPosition]; strToRev[farCharPosition] = strToRev[i]; strToRev[i] = buf; }

Thoughts?

Unfortunately, that is not proper Java code (Java does not support direct indexing of characters in strings, at least not up to and including 1.6, dunno about 1.7).

Here's the version I came up with for fun, which is (IMHO) a bit cleaner (less messing around with the indexes):

public String reverse(String s) {
  if (s == null || s.length() <= 1) return s;
  char[] c = s.toCharArray();
  int lower = 0;
  int upper = c.length - 1;
  while (lower < upper) {
    char tmp = c[upper];
    c[upper] = c[lower];
    c[lower] = tmp;
    lower++;
    upper--;
  }
  return new String(c);
}

And if you go so far as to define a helper method like

public void swap(char[] array, int i, int j) {
  char tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
}

then the while loop boils down to a pretty neat

  while (lower < upper) {
    swap(c, lower++, upper--);
  }

2011-07-22 Reply Admin

Malarkey:
I think you forgot to run ROT13 on that. Twice.
You really need to combine the techniques. Something such as:
reverse(s).rot13().ascii2ebcdic().rot13().reverse().ebcdic2ascii()
would be the beginnings of an industrial-strength obfuscator.

Actually apart from a slight problem this would actually obfuscate the text quite a bit because it doesn't return the input.

The slight problem is that ascii2ebcdic would convert many alphabetic characters into non alphabetic ones leaving rot13 behavior as undefined (as far as I know, how do you rot13 the character "1"?)

If you solve that by instead using some non-ascii encoding that just maps letters differently, eg:

a <-> f b <-> z c <-> b d <-> s etc

Then this: asciiToAlt(s).rot13().altToAscii(s).rot13()

Doesn't return the same string as input. For example pass in "a", it's converted to "f", then rot13ed to "s", converted to "d" and then rot13ed to an output of "q".

2011-07-22 Reply Admin

TheCPUWizard:
EAV (Entity, Attribute Value) data structures have real uses in many application, unfortunately they seem to be abused much more often than used properly.
There are a complete set of transparent optimizations that can be done in this environment, that are much harder to implement with table/column fixed formats.

Bullshit.

2011-07-22 Reply Admin

it is possible, google for it and it's such an elegant solution

2011-07-22 Reply Admin

[quote user="gnasher729"][quote user="boog"][quote user="Fat"]Calculating fibonacci numbers in O(log(n)) is what I'd call interesting.[/quote]

That would indeed by interesting, but since the result has a size of O(n), it is not possible. [/quote]

(forgot the quote) it is possible, google for it and it's such an elegant solution

2011-07-22 Reply Admin

snoofle:
dohpaz42:
resmoker10:
Actually that's something that bugs me about C# that it doesn't have a string reverse function. For some reason Microsoft didn't see fit to add a string.Reverse() method and I have had to roll my own.
Password reversal is a useful when storing passwords in a database to obscure them from potential attackers. More recently what with all the hacking stories in the news I have increased my precautions by reversing the strings two times before inserting them into the password table so they are double encrypted.
I hope that you don't mean that you do String.encrypt(String.reverse(String.reverse)), and I'm just reading your post wrong!
That's exactly what he meant - you missed the implied "</wink>"

No that's not it. What he meant was

String.reverse(String.reverse(SuperSecretPassword));

2011-07-22 Reply Admin

In Java why not use the reverse method built into StringBuilder, rather than manually coding the reverse?

String funcX (String s) {
  if (s == null || s.length() == 1 || s.length() == 0) {
    return s;
  } else {
    return new StringBuilder( s ).reverse().toString();
  }
}

2011-07-22 Reply Admin

C-Octothorpe:
boog:
Fat:
I don't really like this joke. It'n not a legitiamte use of recursion, it's just an infinite loop. Of course, it doesn't defeat its real purpose, make beginner programmers feel superior to anyone who didn't spend 2 hours studying algorithms.
Actually, a proper example of an infinite loop would be
do
{ Fat.study(recursion); }
while (!Fat.understands(recursion));
That is fucking EPIC! That's going down in my quote book, and perhaps a T-Shirt...

Love it too, but how about:

public bool learn(recursion) { if (!understand(recursion)) { learn(recursion); } return true; }

2011-07-22 Reply Admin

Sylver:
Love it too, but how about:
public bool learn(recursion) { if (!understand(recursion)) { learn(recursion); } return true; }

that just causes a stack overflow

SlyEcho · 2011-07-22 Reply Admin

This is my take on the string reverse problem, notice the surrogate pair handling:

private static void swap(char[] c, int i, int j) {
	char t = c[i];
	c[i] = c[j];
	c[j] = t;
}
public static String reverse(String s) {
	if (s == null || s.length() == 1 || s.length() == 0) {
		return s;
	} else {
		char[] c = s.toCharArray();
		for (int i = 0, j = c.length-1; i <= j; i++, j--) {
			swap(c, i, j);
			if (Character.isHighSurrogate(c[i])) swap(c, i, i - 1);
			if (Character.isLowSurrogate(c[j])) swap(c, j, j + 1);
		}
		return new String(c);
	}
}

2011-07-22 Reply Admin

[quote user="math_geek"][quote user="gnasher729"][quote user="boog"][quote user="Fat"]Calculating fibonacci numbers in O(log(n)) is what I'd call interesting.[/quote]

That would indeed by interesting, but since the result has a size of O(n), it is not possible. [/quote]

(forgot the quote) it is possible, google for it and it's such an elegant solution [/quote]

By the way, are there any log(N) solutions other than golden ratio formula (although as Maurits suggested, from some point of view it's O(1), since power computing can be done in constant time)? Preferably, using only integer arithmetics.

2011-07-22 Reply Admin

Here's my attempt at the O(n) Fibonacci challenge:

//overload for when you don't need the previous value private int Fib(int n) { int prev; return Fib(n, out prev); }

//overload for the actual recursion private int Fib(int n, out int prev) { if(n==0) { prev = 0; return 1; } else { int prev2; prev = Fib(n-1, out prev2); return prev + prev2; } }

2011-07-22 Reply Admin

My Java-Fu is rather weak... I prefer the C (or C++) method:

void reverse (const char *in, char *out) { out += strlen(in); *out = '\0'; char c; while ((c = *in++) != '\0') *--out = c; }

I reloop through the string until '\0' because, to be 100% compliant, it is impractical to do a reverse loop using size_t, as you cannot test easily against 0 (less than zero becomes 0xFFFFFFFF, and testing against 0xFFFFFFFF is slower than testing against zero)... and a forward loop against size is just as slow if not slower than doing a loop towards '\0'.

dkf · 2011-07-22 Reply Admin

wizzard:
I have encountered "meta-databases" at least four times in my career. I will never understand why everybody thinks they're such a wonderful, revolutionary idea. I know there are some legitimate applications for EAV but these are not them.

At least it stops the semantic web advocates from rioting in the streets like teenage delinquents.

2011-07-22 Reply Admin

CaptainCaveman:
"And the only reason that release went out was they had fired the QA group for repeatedly rejecting Charles' and Terry's high quality work."
Hooray, lets fire people for doing their jobs well. I have seen this shit myself in the not-so-distant past. People who don't work in IT wonder why I became so jaded.

Charles and Terry are nephews of the CEO, right? That's the only possible explanation I can think of.

Hiring obviously bad people without even consulting the people involved in the hiring process, and then firing the people who can't help but reveal how bad they are, is only excusable if appeasing the CEO's family is more important than the continued profitability of the company.

2011-07-22 Reply Admin

Fat:
By the way, no one has yet answered my question about recursive fibonacci numbers calculation. I've got one solution, but it looks kind of sloppy (at least when the implementation is in C++; I guess, on Haskell or Matlab it'd look much better). I want to see if you come up with something more elegant. And besides, I think this problem is pretty neat.

[image]

2011-07-22 Reply Admin

Real programmer would realize that this code is wrong.

For two reasons:

Unicode is a 4 bytes character set. For efficiency, java (and most other languages too) store them in UTF-16 (or a variant thereof), which uses 2 bytes when possible and the whole 4 bytes when necessary. Quite a few asian characters are outside of the 2 bytes unicode range and need to be coded by two subsequent chars. Inverting both characters of a surrogate pair makes an invalid string that is likely to blow up in your face later on (when displaying it, for example)
Unicode supports combining characters. So 'é' can either be expressed as a single 'é' character, or as 'e' followed by the ''' combining character. Inverting the order of these two characters would place the accent on the wrong letter, on generate an invalid string.

Lesson: Use the API methods. Even if you think you know the problem domain, it may be more complicated than expected.

2011-07-22 Reply Admin

I know your "elegant" solution. It uses O (log (n)) additions and multiplications. But the numbers to be added are up to O (n) in size, and adding numbers of size O (n) with fixed hardware takes O (n) in time. The addition is not a primitive operation anymore. The result must take at least O (n) since that is the size of the result; doing it faster than O (n log n) seems difficult.

2011-07-22 Reply Admin

How about some C#? No string reversal built-in, but there IS an Array one.

string ReverseString(string input)
{
	if (input == null || input.Length < 2)
		return input; 

	char[] inputArray = input.ToCharArray();
	Array.Reverse(inputArray);
	return new string(inputArray);

	// Or since String is an enumerable, you can use LINQ...
	return new string(input.Reverse().ToArray());
}

2011-07-22 Reply Admin

gnasher729:
I know your "elegant" solution. It uses O (log (n)) additions and multiplications. But the numbers to be added are up to O (n) in size, and adding numbers of size O (n) with fixed hardware takes O (n) in time. The addition is not a primitive operation anymore. The result _must_ take at least O (n) since that is the size of the result; doing it faster than O (n log n) seems difficult.

I don't believe you - the length of time it takes to add up two numbers is proportional to the number of digits it has, and therefore, as we determined, O (log n).

Three for Three, Recursion Threads, and Wrong Answer

Leave a comment on “Three for Three, Recursion Threads, and Wrong Answer”