Three for Three, Recursion Threads, and Wrong Answer

« Return to Article
  • woliveirajr 2011-07-21 11:51
    frist ! with aliquam
  • Mason Wheeler 2011-07-21 11:53
    Re: Wrong Answer, this sounds a lot like the original Inner-Platform Effect story. Same company?
  • CaptainCaveman 2011-07-21 11:57
    "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.
  • Anon 2011-07-21 11:59
    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.


    And I'm sure they were told that they were being fired because they aren't "team players".
  • Not a Java programmer 2011-07-21 12:00
    To clarify, that second one just reverses the string right? Does the Java string type not have a method to do that?
  • John Galt 2011-07-21 12:01
    Won't that Java snippet run forever in an infinite loop if you supply it with a string that's more than 1 character long? It looks like all it's doing is moving the first character to the end of the submitted string over and over again.
  • John Galt 2011-07-21 12:03
    John Galt:
    Won't that Java snippet run forever in an infinite loop if you supply it with a string that's more than 1 character long? It looks like all it's doing is moving the first character to the end of the submitted string over and over again.


    Ah - never mind, didn't see the parenthesis in the last line.
  • dohpaz42 2011-07-21 12:04
    Not a Java programmer:
    To clarify, that second one just reverses the string right? Does the Java string type not have a method to do that?


    Yes, it reverses the string. And, it doesn't matter if there is a built-in for that; this was a coding challenge to gauge the ability of the interviewee to see if they could tell from looking at the code what the code should be doing - well, I hope that's what it is, anyway. :)
  • Xenon Xavior 2011-07-21 12:05
    John Galt:
    Won't that Java snippet run forever in an infinite loop if you supply it with a string that's more than 1 character long? It looks like all it's doing is moving the first character to the end of the submitted string over and over again.


    That's what I thought at first, but look closer at the parenthesis. It will reverse the string.
  • hoodaticus 2011-07-21 12:05
    I once interviewed a "C++ programmer" who couldn't pass FizzBuzz. He didn't even know how to do logical negation (!).

    Less amusing, I had an assembly programmer who did pass it, but without using the mod operator or even attempting to roll his own. He had to use string conversion and tested for the decimal point.
  • Not a Java programmer 2011-07-21 12:06
    I looked it up and it doesn't anyway.
  • hoodaticus 2011-07-21 12:06
    John Galt:
    Won't that Java snippet run forever in an infinite loop if you supply it with a string that's more than 1 character long? It looks like all it's doing is moving the first character to the end of the submitted string over and over again.
    Is this the John Galt from Stack Overflow?
  • bob 2011-07-21 12:09
    "I looked it up and it doesn't anyway"

    Not suprising, when would that ever come in useful for anything useful?
  • WC 2011-07-21 12:12
    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.
  • bencoder 2011-07-21 12:12
    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?
  • dohpaz42 2011-07-21 12:14
    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).
  • resmoker10 2011-07-21 12:17
    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.
  • snoofle 2011-07-21 12:19
    We're stuck on 1.5, so:

    return s==null || s.length()<2 ? s : new StringBuilder(s).reverse().toString();

    Though I once got: what if you couldn't use StringBuilder?

    I didn't want to work for the guy so I said I'd hire a junior programmer to handle the piddle work so I could get on with solving the company's real problems.
  • dohpaz42 2011-07-21 12:19
    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!
  • Helix 2011-07-21 12:20
    hoodaticus:
    I once interviewed a "C++ programmer" who couldn't pass FizzBuzz. He didn't even know how to do logical negation (!).

    Less amusing, I had an assembly programmer who did pass it, but without using the mod operator or even attempting to roll his own. He had to use string conversion and tested for the decimal point.


    I am trying to think how you would do fizzbuzz with strings and chars in asm?
  • boog 2011-07-21 12:20
    Mason Wheeler:
    Re: Wrong Answer, this sounds a lot like the original Inner-Platform Effect story. Same company?
    Sadly, I doubt it. This anti-pattern is all too frequent in IT, as so many developers see it as a fun and challenging way to avoid the boring task of thinking about data structures.
  • snoofle 2011-07-21 12:22
    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>"
  • somechick 2011-07-21 12:23
    hoodaticus:
    I once interviewed a "C++ programmer" who couldn't pass FizzBuzz. He didn't even know how to do logical negation (!).


    I see what you did there ...

    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).
  • NickS 2011-07-21 12:27
    Oh, that idea's floating around? Here's what you should do: Shoot it down, take it outside, put it on the hood of whoever thought it up, light it on fire, and leave it as a warning to others who attempt to have similar "ideas".
  • piskvorr 2011-07-21 12:31
    Re Wrong Answer: I think I used to work there. Running away, screaming in terror, would indeed be the sane course of action - the founder used to program, way back in the 1990s, and most of such brillant inventions were his. (And yes, you were right, that inner platform turned into a Lovecraftian nightmare no-one dared disturb)
  • Anon 2011-07-21 12:32
    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.
  • Rootbeer 2011-07-21 12:36

    How come there isn't a caffeinated soft drink called FizzBuzz?

    Maybe the name is TOO clever. Self-identifying geeks are content to suck down a half-dozen Bawls per day.

  • Machtyn 2011-07-21 12:39
    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!


    Actually, I think he means String.reverse(String.reverse). He didn't mention anything about an encrypt in "Password reversal is a useful when storing passwords..."

    String.reverse(String.reverse("I then had a good laugh because they are now double encrypted")). (They'll never guess what I said now!)
  • Abso 2011-07-21 12:50
    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.
  • ooblek 2011-07-21 12:51
    I'm currently working on an "enterprise" application with such a meta-database.

    I just had to write a query that had a dozen table joins in it. The join criteria is a bunch of strings. It is slow as hell, but there is nothing I can do about it.

    At least a few of the joins are on the same table with different criteria. They store the relations in a single column of a table. A lot of the tables have columns with names like ATTRIB_001 up to ATTRIB_100+.

    Fortunately, I don't have to work at this low of a level in this application much.
  • Hanoi 4 ever 2011-07-21 12:52
    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.
  • Joel B 2011-07-21 12:53
    I think you forgot to run ROT13 on that. Twice.
  • hoodaticus 2011-07-21 12:55
    Helix:
    hoodaticus:
    I once interviewed a "C++ programmer" who couldn't pass FizzBuzz. He didn't even know how to do logical negation (!).

    Less amusing, I had an assembly programmer who did pass it, but without using the mod operator or even attempting to roll his own. He had to use string conversion and tested for the decimal point.


    I am trying to think how you would do fizzbuzz with strings and chars in asm?
    It wasn't a machine coder's position. He was using .NET.
  • Anon 2011-07-21 12:56
    "storing passwords in a database".
    And that's TRWTF.

    Reversing them won't help you. Specially when the hackers begin eikooc as a password.
  • Anon 2011-07-21 13:00
    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.


    Or calculating factorial. I always thought that was the canonical example.
  • Sutherlands 2011-07-21 13:00
    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.

    Psuedocode:

    foreach(letter in string)
    StringBuilder.AppendFront(letter)
  • Jeff 2011-07-21 13:01
    What about improvements to the recursive string reversal code?

    I'm thinking:

    1) First choice, use any built in library functions since they're already coded, tested, and optimized.

    2) Don't use recursion since that's a lot of overhead and you could get a possible stack overflow if the string was long. (Can you even get stack overflows in C#? I honestly haven't had one in many many years).

    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?
  • C-Octothorpe 2011-07-21 13:02
    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.
    That's what I would've done.
  • Abso 2011-07-21 13:02
    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.


    This wasn't meant as an example, though. It makes sense for them to use something that would be easier to do with a loop, because then they can look for people whose answer to the second question is "use a loop".
  • Hortical 2011-07-21 13:09
    Sutherlands:

    Psuedocode:

    foreach(letter in string)
    StringBuilder.AppendFront(letter)


    Consider the possibility that the StringBuilder uses a char[] internally.

    Consider the possibility that every time you insert a char at the beginning, all the other chars that have been added have to be moved over a space. Every time.
  • Dank 2011-07-21 13:12
    Anon:
    "storing passwords in a database".
    And that's TRWTF.

    Reversing them won't help you. Specially when the hackers begin eikooc as a password.


    Failing to comprehend sarcasm. That's TRWTF. Unfortunately this won't help you. Specially when the jokers begin to mock you too.
  • TheCPUWizard 2011-07-21 13:14
    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.
  • resmoker10 2011-07-21 13:15
    no the RWTF is this comment in which I comment on the fact that your comment was the RWTF
  • Jay 2011-07-21 13:15
    There are basically two reasons why someone might ask your opinion.

    1. On rare occasions, it may be because the asker has not made up his mind and believes that insights or suggestions that you have may help him to arrive at a better decision.

    2. Most of the time, the asker has already made up his mind and is looking for someone else to validate his decision.

    I regularly have conversations with my boss where he asks, "What do you think we should do about X?" Then I say what I think we should do. Then he explains to me why he's already decided to do something else.

    Still, it's better then the way we used to work. That was, he would make a decision about something. Then he would tell me to come up with a solution to whatever problem, without telling me what his idea was. I would spend days writing up a design document or coding a program or whatever. Then he would yell at me because I hadn't done it the way he wanted. I thought of it as "the I'm-thinking-of-a-number management style".
  • Dank 2011-07-21 13:20
    String reverseString(String input) {
    if (input == null || input.length < 2) return input;

    char[] inp = input.toCharArray();
    StringBuilder output = new StringBuilder();

    for (int i = inp.length - 1; i >=0 i--) {
    output.append(inp[i]);
    }
    return inp.toString();
    }
  • Hortical 2011-07-21 13:27
    Dank:
    String reverseString(String input) {
    if (input == null || input.length < 2) return input;

    char[] inp = input.toCharArray();
    StringBuilder output = new StringBuilder();

    for (int i = inp.length - 1; i >=0 i--) {
    output.append(inp[i]);
    }
    return inp.toString();
    }


    You should have read all the comments.
    Someone already did this better than you.
  • dohpaz42 2011-07-21 13:31
    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.


    Recursion is usually a precursor to larger algorithms, such as sorting. If you can't understand recursion, you have no hope of quick sort or tree traversal.
  • hoodaticus 2011-07-21 13:31
    resmoker10:
    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.
    +5
  • C-Octothorpe 2011-07-21 13:34
    hoodaticus:
    resmoker10:
    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.
    +5
    Here, here! They should add this to the OWASP secure development guide.
  • wizzard 2011-07-21 13:37
    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.

    One project I worked on had to do so many JOINs just to get a single record out of their database that they exceeded MySQL's JOIN limit (61). Twice. They had to write code to keep track of the # of joins while building the query, and break the query into separate pieces when necessary. It goes without saying that the queries also took about 100 times longer than necessary, and data integrity was a complete nightmare.
  • hoochiekiss 2011-07-21 13:41
    hoodaticus:
    cockSmoker10:
    More recently what with all the raping stories in the news I have increased my precautions by reverse-facing the spikes in my RapeEx two times before inserting it into my rectum so it is double protected.
    +5
    I concur as well.
  • Nebler 2011-07-21 13:41
    Jeff:
    What about improvements to the recursive string reversal code?

    I'm thinking:

    1) First choice, use any built in library functions since they're already coded, tested, and optimized.

    2) Don't use recursion since that's a lot of overhead and you could get a possible stack overflow if the string was long. (Can you even get stack overflows in C#? I honestly haven't had one in many many years).

    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?


    1) Is the only correct option. Always use unicode-aware methods, like string.reverse. All your surrogate pairs will die otherwise. The code in the interview gets this wrong as well.
  • hoodaticus 2011-07-21 13:51
    dohpaz42:
    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.


    Recursion is usually a precursor to larger algorithms, such as sorting. If you can't understand recursion, you have no hope of quick sort or tree traversal.
    recursion (n) - see: recursion
  • B1 Bomber in the Lavatory 2011-07-21 13:51
    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.

    This is really not so surprising when you consider that the boss obviously valued his own personal perceptions far higher than any other inputs.
  • Rumen's Boss 2011-07-21 14:09
    Machtyn:
    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!


    Actually, I think he means String.reverse(String.reverse). He didn't mention anything about an encrypt in "Password reversal is a useful when storing passwords..."

    String.reverse(String.reverse("I then had a good laugh because they are now double encrypted")). (They'll never guess what I said now!)


    I think me meant String.EncryptROT26(String.Reverse(String.Reverse(s)));
  • ih8u 2011-07-21 14:52
    Rumen's Boss:
    Machtyn:
    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!


    Actually, I think he means String.reverse(String.reverse). He didn't mention anything about an encrypt in "Password reversal is a useful when storing passwords..."

    String.reverse(String.reverse("I then had a good laugh because they are now double encrypted")). (They'll never guess what I said now!)


    I think me meant String.EncryptROT26(String.Reverse(String.Reverse(s)));


    I do 26 ROT1's for the win! More method calls me more secure!
  • Fat 2011-07-21 15:05
    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.
  • SG_01 2011-07-21 15:09

    String EncryptRot(String s, int amount)
    {
    for ( int i = 0; i < s.Length; ++i )
    {
    s[i] = 1 + ( ( s[i] - 1 + amount ) % 255 );
    }
    return s;
    }


    I do 255 custom ROT1's for the win! ;)
  • SG_01 2011-07-21 15:10
    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 ^^
  • C-Octothorpe 2011-07-21 15:16
    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, it is recursion.

    imagine this:

    string GetRecursionDef() 
    
    {
    return GetRecursionDef();
    }
  • boog 2011-07-21 15:19
    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));
  • anonymouser 2011-07-21 15:21
    Hortical:
    Sutherlands:

    Psuedocode:

    foreach(letter in string)
    StringBuilder.AppendFront(letter)


    Consider the possibility that the StringBuilder uses a char[] internally.

    Consider the possibility that every time you insert a char at the beginning, all the other chars that have been added have to be moved over a space. Every time.


    I would bet it's more like <char>List, or something similar.

  • Hortical 2011-07-21 15:29
    anonymouser:
    Hortical:
    Sutherlands:

    Psuedocode:

    foreach(letter in string)
    StringBuilder.AppendFront(letter)


    Consider the possibility that the StringBuilder uses a char[] internally.

    Consider the possibility that every time you insert a char at the beginning, all the other chars that have been added have to be moved over a space. Every time.


    I would bet it's more like <char>List, or something similar.



    Ok, now consider the possibility that I've seen the source code and it does use a char[].

    http://www.docjar.com/html/api/java/lang/AbstractStringBuilder.java.html
  • C-Octothorpe 2011-07-21 15:31
    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...
  • EvanED 2011-07-21 15:35
    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.

    String reversal has been deprecated as an encryption technique for some time now. It's highly recommended that you switch to ROT13 for enhanced security.

    [Yeah, lots of other people have already made that joke. Sue me.]

    Hanoi 4 ever:
    dohpaz42:
    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.

    I feel that it's better to start with a case where there is only one recursive call. While you can adapt both of your examples to this (e.g. a search in a BST or finding the kth order statistic), both require more explanation than you need.

    I'm not sure I would choose string reversal though; IMO factorial is about ideal for a first example. It's something that is actually fairly reasonable to do recursively anyway, lends itself to an easier description of how you achieve that result, has the same complexity as a loop solution (unlike that reverse function; and in fact it may generate the same code with an optimizing compiler in C or C++), etc.

    I'd probably do Fibbonicci as a first example of having more than one recursive call, with the disclaimer that it's actually a really bad way of implementing it (without memoizing). Only after that would I get into stuff like trees and quicksort.

    (This is especially true because I'm not sure you can talk much about trees before you talk about recursion.)

  • Fat 2011-07-21 15:38
    C-Octothorpe:
    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, it is recursion.

    imagine this:

    string GetRecursionDef() 
    
    {
    return GetRecursionDef();
    }


    Of course, technically it could be called recursion. It's just the worst possible example of it.
    This joke to me feels kind of like a guy, who says "lol, I'm cool, check out my mad driving skillz", and than drives with parking brake on, on reverse, into the wall. Technically, he was driving. But honestly, he wasn't.
  • Hortical 2011-07-21 15:41
    Fat:
    C-Octothorpe:
    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, it is recursion.

    imagine this:

    string GetRecursionDef() 
    
    {
    return GetRecursionDef();
    }


    Of course, technically it could be called recursion. It's just the worst possible example of it.
    This joke to me feels kind of like a guy, who says "lol, I'm cool, check out my mad driving skillz", and than drives with parking brake on, on reverse, into the wall. Technically, he was driving. But honestly, he wasn't.


  • Fat 2011-07-21 15:46
    EvanED:

    I'd probably do Fibbonicci as a first example of having more than one recursive call, with the disclaimer that it's actually a really bad way of implementing it (without memoizing).


    I've had a thought recently, that this might be a pretty good question: writing recursive function which calculates Fibonacci number without memoizing/loops/arrays, and works O(n).
  • Bryan the K 2011-07-21 15:49
    hoodaticus:
    John Galt:
    Won't that Java snippet run forever in an infinite loop if you supply it with a string that's more than 1 character long? It looks like all it's doing is moving the first character to the end of the submitted string over and over again.
    Is this the John Galt from Stack Overflow?


    Close, it's Howard Rorack.
  • C-Octothorpe 2011-07-21 15:54
    Fat:
    C-Octothorpe:
    Actually, it is recursion.

    imagine this:

    string GetRecursionDef() 
    
    {
    return GetRecursionDef();
    }


    Of course, technically it could be called recursion. It's just the worst possible example of it.
    This joke to me feels kind of like a guy, who says "lol, I'm cool, check out my mad driving skillz", and than drives with parking brake on, on reverse, into the wall. Technically, he was driving. But honestly, he wasn't.
    Well, at least you're consistent... Stupid, but consistent. That counts for something, right?
  • Fat 2011-07-21 15:56
    Hortical:
    Fat:
    C-Octothorpe:
    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, it is recursion.

    imagine this:

    string GetRecursionDef() 
    
    {
    return GetRecursionDef();
    }


    Of course, technically it could be called recursion. It's just the worst possible example of it.
    This joke to me feels kind of like a guy, who says "lol, I'm cool, check out my mad driving skillz", and than drives with parking brake on, on reverse, into the wall. Technically, he was driving. But honestly, he wasn't.




    Yeah, you can justify any level of stupidity these days simply by calling an opponent a troll.

    So, you do think that example has more sense than, say

    bool a=true;
    bool b;
    if (a==true)
    b=true;
    else if (a==false)
    b=false;
    else
    b=(!true)&&(!false);

    ?
  • Mahomedalid 2011-07-21 16:00
    Re: Wrong Answer

    Actually sounds like the guy that create NoSQL.
  • Fat 2011-07-21 16:04
    C-Octothorpe:
    Fat:
    C-Octothorpe:
    Actually, it is recursion.

    imagine this:

    string GetRecursionDef() 
    
    {
    return GetRecursionDef();
    }


    Of course, technically it could be called recursion. It's just the worst possible example of it.
    This joke to me feels kind of like a guy, who says "lol, I'm cool, check out my mad driving skillz", and than drives with parking brake on, on reverse, into the wall. Technically, he was driving. But honestly, he wasn't.
    Well, at least you're consistent... Stupid, but consistent. That counts for something, right?


    Why do you call me stupid? No one has told me that yet.
    Perhaps, I don't understand the real meaning of this joke, and it is not "look, I defined recursion as recursion, so now it's recursive, hahaha, I've heard what recursion is", but "look what a dumb-ass definition I wrote, no one in his right mind would take this as a remotely valid illustration of recursion". It's just that I've seen people thinking of a first meaning as true far too often.
  • Hortical 2011-07-21 16:11
    Fat:
    Why do you call me stupid? No one has told me that yet.


    Well, he did you benefit of no keeping you in the dark anymore.

    Fat:
    Perhaps, I don't understand the real meaning of this joke,


    Oh, is that what it is?

    Fat:
    and it is not "look, I defined recursion as recursion, so now it's recursive, hahaha, I've heard what recursion is", but "look what a dumb-ass definition I wrote, no one in his right mind would take this as a remotely valid illustration of recursion". It's just that I've seen people thinking of a first meaning as true far too often.


    More like "look, I defined recursion as recursion, so now it's recursive, hahaha, everyone (hopefully) else here understands what recursion is, so the irony and the cleverness with which it was demonstrated".
  • C-Octothorpe 2011-07-21 16:12
    Fat:
    Yeah, you can justify any level of stupidity these days simply by calling an opponent a troll.

    So, you do think that example has more sense than, say

    bool a=true;
    bool b;
    if (a==true)
    b=true;
    else if (a==false)
    b=false;
    else
    b=(!true)&&(!false);

    ?
    You're not an opponent, you're just wrong. And I don't think anybody called you a troll.

    Regarding your example: it's perfectly cromulent for displaying the use of an if statement... What, did you want an example with real business domain models, and perhaps a dash of DI, maybe even a recursion provider?

    You're wrong *and* you're loud... The worst combination.
  • PRMan 2011-07-21 16:20
    Sutherlands:
    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.

    Psuedocode:

    foreach(letter in string)
    StringBuilder.AppendFront(letter)


    What?!? Don't you realize how many memory copies you are going to do with that?

    Do a reverse for loop and build it up the normal way.

    (As if it matters on today's processors...)

    CAPTCHA - erat (Isn't he a Right Wing for the Nashville Predators?)
  • PRMan 2011-07-21 16:23
    Jeff:
    (Can you even get stack overflows in C#? I honestly haven't had one in many many years).


    Yes, I got one a couple weeks ago. I was parsing an XSD to make a TreeView out of it and I didn't notice that a certain named element was in there below itself, confusing my parser into an endless loop. It took a long time (about 2-3 minutes) before it happened (other people distracted me right as I was running it). It had to fill all 8GB on my machine first before I got a stack overflow.
  • Fat 2011-07-21 16:34
    Hortical:
    Fat:
    Why do you call me stupid? No one has told me that yet.


    Well, he did you benefit of no keeping you in the dark anymore.

    Fat:
    Perhaps, I don't understand the real meaning of this joke,


    Oh, is that what it is?

    Fat:
    and it is not "look, I defined recursion as recursion, so now it's recursive, hahaha, I've heard what recursion is", but "look what a dumb-ass definition I wrote, no one in his right mind would take this as a remotely valid illustration of recursion". It's just that I've seen people thinking of a first meaning as true far too often.


    More like "look, I defined recursion as recursion, so now it's recursive, hahaha, everyone (hopefully) else here understands what recursion is, so the irony and the cleverness with which it was demonstrated".


    OK, thanks, I get what you all mean now.
    I guess I'm too sensitive about these kind of jokes (e.g. stupider kinds of jokes about Shrodinger's cat), which make people believe they understand something by simply remembering a couple of remotely relevant witty remarks. I guess, that's an elitist in me talking.
  • fu2uf 2011-07-21 16:39
    I don't think this will work, because I can crack that by placing the doublelbuod encrypted password table between two opposed mirrors. This works for an infinite number of test cases or until it vanishes.
  • C-Octothorpe 2011-07-21 16:41
    Fat:
    I guess, that's an elitist in me talking.
    Yeah, that must be it, or the more likely explanation was that you started a dick measuring contest while missing a, um, prerequisite.
  • Hortical 2011-07-21 16:43
    Fat:
    OK, thanks, I get what you all mean now.
    I guess I'm too sensitive about these kind of jokes (e.g. stupider kinds of jokes about Shrodinger's cat), which make people believe they understand something by simply remembering a couple of remotely relevant witty remarks. I guess, that's an elitist in me talking.


    Cool. You do this all by yourself.
  • B1 Bomber in the Lavatory 2011-07-21 16:46
    Fat:
    Hortical:
    Fat:
    Why do you call me stupid? No one has told me that yet.


    Well, he did you benefit of no keeping you in the dark anymore.

    Fat:
    Perhaps, I don't understand the real meaning of this joke,


    Oh, is that what it is?

    Fat:
    and it is not "look, I defined recursion as recursion, so now it's recursive, hahaha, I've heard what recursion is", but "look what a dumb-ass definition I wrote, no one in his right mind would take this as a remotely valid illustration of recursion". It's just that I've seen people thinking of a first meaning as true far too often.


    More like "look, I defined recursion as recursion, so now it's recursive, hahaha, everyone (hopefully) else here understands what recursion is, so the irony and the cleverness with which it was demonstrated".


    OK, thanks, I get what you all mean now.
    I guess I'm too sensitive about these kind of jokes (e.g. stupider kinds of jokes about Shrodinger's cat), which make people believe they understand something by simply remembering a couple of remotely relevant witty remarks. I guess, that's an elitist in me talking.

    I think it all started when you erroneously declared that this is infinitely recursive. Why don't you take a look at the function again?

    Hint: java.lang.String.substring(int) returns the substring starting at the zero-based int index.
  • Sock Puppet #5 2011-07-21 16:48
    B1 Bomber in the Lavatory:
    Fat:
    Hortical:
    Fat:
    Why do you call me stupid? No one has told me that yet.


    Well, he did you benefit of no keeping you in the dark anymore.

    Fat:
    Perhaps, I don't understand the real meaning of this joke,


    Oh, is that what it is?

    Fat:
    and it is not "look, I defined recursion as recursion, so now it's recursive, hahaha, I've heard what recursion is", but "look what a dumb-ass definition I wrote, no one in his right mind would take this as a remotely valid illustration of recursion". It's just that I've seen people thinking of a first meaning as true far too often.


    More like "look, I defined recursion as recursion, so now it's recursive, hahaha, everyone (hopefully) else here understands what recursion is, so the irony and the cleverness with which it was demonstrated".


    OK, thanks, I get what you all mean now.
    I guess I'm too sensitive about these kind of jokes (e.g. stupider kinds of jokes about Shrodinger's cat), which make people believe they understand something by simply remembering a couple of remotely relevant witty remarks. I guess, that's an elitist in me talking.

    I think it all started when you erroneously declared that this is infinitely recursive. Why don't you take a look at the function again?

    Hint: java.lang.String.substring(int) returns the substring starting at the zero-based int index.

    To be fair, he did start by saying he had never studied algorithms.
  • hoodaticus 2011-07-21 16:49
    Sock Puppet #5:
    B1 Bomber in the Lavatory:
    Fat:
    Hortical:
    Fat:
    Why do you call me stupid? No one has told me that yet.


    Well, he did you benefit of no keeping you in the dark anymore.

    Fat:
    Perhaps, I don't understand the real meaning of this joke,


    Oh, is that what it is?

    Fat:
    and it is not "look, I defined recursion as recursion, so now it's recursive, hahaha, I've heard what recursion is", but "look what a dumb-ass definition I wrote, no one in his right mind would take this as a remotely valid illustration of recursion". It's just that I've seen people thinking of a first meaning as true far too often.


    More like "look, I defined recursion as recursion, so now it's recursive, hahaha, everyone (hopefully) else here understands what recursion is, so the irony and the cleverness with which it was demonstrated".


    OK, thanks, I get what you all mean now.
    I guess I'm too sensitive about these kind of jokes (e.g. stupider kinds of jokes about Shrodinger's cat), which make people believe they understand something by simply remembering a couple of remotely relevant witty remarks. I guess, that's an elitist in me talking.

    I think it all started when you erroneously declared that this is infinitely recursive. Why don't you take a look at the function again?

    Hint: java.lang.String.substring(int) returns the substring starting at the zero-based int index.

    To be fair, he did start by saying he had never studied algorithms.

    I wish people would stop quoting this comment thread, it's getting quite long.
  • Fat 2011-07-21 16:51
    No, what I meant was a joke about recursion (by hoodaticus). The code in article is finite, as far as my knowledge of Java allows me to judge.
  • you know who 2011-07-21 16:55
    hoodaticus:
    Sock Puppet #5:
    B1 Bomber in the Lavatory:
    Fat:
    Hortical:
    Fat:
    Why do you call me stupid? No one has told me that yet.


    Well, he did you benefit of no keeping you in the dark anymore.

    Fat:
    Perhaps, I don't understand the real meaning of this joke,


    Oh, is that what it is?

    Fat:
    and it is not "look, I defined recursion as recursion, so now it's recursive, hahaha, I've heard what recursion is", but "look what a dumb-ass definition I wrote, no one in his right mind would take this as a remotely valid illustration of recursion". It's just that I've seen people thinking of a first meaning as true far too often.


    More like "look, I defined recursion as recursion, so now it's recursive, hahaha, everyone (hopefully) else here understands what recursion is, so the irony and the cleverness with which it was demonstrated".


    OK, thanks, I get what you all mean now.
    I guess I'm too sensitive about these kind of jokes (e.g. stupider kinds of jokes about Shrodinger's cat), which make people believe they understand something by simply remembering a couple of remotely relevant witty remarks. I guess, that's an elitist in me talking.

    I think it all started when you erroneously declared that this is infinitely recursive. Why don't you take a look at the function again?

    Hint: java.lang.String.substring(int) returns the substring starting at the zero-based int index.

    To be fair, he did start by saying he had never studied algorithms.

    I wish people would stop stroking my commendable tool, it's getting quite long.
  • you know who 2011-07-21 16:58
    Fat:
    No, what I meant was a joke about recursion (by hoodaticus). The code in article is finite, as far as my knowledge of Java allows me to judge.

  • Obvious Troll is Obvious 2011-07-21 17:11
    I heard sucking Bawls can be very soothing.
  • Matt 2011-07-21 17:11
    I'm still in Uni (actually year off to work on some OSS), so go easy and what not.

    Aside from the fact that the string reversal in a recursion is really daft idea and using the built in library is a good one, I'd do it with a simple as for loop.
    I'm fuzzy on Java syntax and what it allows...

    /////////////////////////////////////
    String funcX (String s)
    {
    String res = "";

    if (s == null || s.length() < 2)
    return s;

    for (i = s.length()-1; i > -1; i--)
    {
    res += s.charAt(i);
    }
    return res;
    }
    /////////////////////////////////////
    There's no need for the else as it will just continue regardless or "exit" because of the return. I count down to avoid a string prepend and thus moving every char in the string "over". I assume for loops can count down, else replace with a while and be done with it.
    If this is really bad, please do say.
  • boog 2011-07-21 17:13
    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...
    In retrospect, I could have pointed out that if I advised him to look up recursion in the dictionary, the joke and ensuing comment thread would just repeat itself indefinitely.

    Of course, since that joke has no base case either, it too would be a poor example of recursion by his standards, so he'd have made the same comment about it, and the joke and ensuing comment thread would just repeat itself indefinitely.

    Either way, our supply of stack space would soon be spent.
  • Fat 2011-07-21 17:23
    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.
  • EvanED 2011-07-21 17:29
    Matt:
    I'm still in Uni (actually year off to work on some OSS), so go easy and what not.

    ...
    There's no need for the else as it will just continue regardless or "exit" because of the return. I count down

    This is all fine (though personal style dictates i >= 0 instead of i > -1 for decreasing loops, there's nothing wrong with the latter).

    to avoid a string prepend and thus moving every char in the string "over".

    Now here is where there's a bit of a problem. Java strings (I'd like to say "like most common languages", though I'm not positive that would hold*) are immutable, which means that it's copying the string each time anyway. So you're not "moving every char over", but you are copying the whole string, and in the process turning what should be O(n) into O(n^2). You should really use a StringBuffer or a char array to avoid this. Pretty much "be very wary of string concatenations in loops" is a widely-applicable rule.

    * Off the top of my head, we have Java, C# and .Net in general, and Python as immutable, and C++ as mutable. I don't count C as having strings for purposes of this discussion. :-)

    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.

    I have an idea which I will try soon.
  • DWalker59 2011-07-21 17:45
    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.
  • hoodaticus 2011-07-21 17:45
    Fat:
    Hortical:
    Fat:
    Why do you call me stupid? No one has told me that yet.


    Well, he did you benefit of no keeping you in the dark anymore.

    Fat:
    Perhaps, I don't understand the real meaning of this joke,


    Oh, is that what it is?

    Fat:
    and it is not "look, I defined recursion as recursion, so now it's recursive, hahaha, I've heard what recursion is", but "look what a dumb-ass definition I wrote, no one in his right mind would take this as a remotely valid illustration of recursion". It's just that I've seen people thinking of a first meaning as true far too often.


    More like "look, I defined recursion as recursion, so now it's recursive, hahaha, everyone (hopefully) else here understands what recursion is, so the irony and the cleverness with which it was demonstrated".


    OK, thanks, I get what you all mean now.
    I guess I'm too sensitive about these kind of jokes (e.g. stupider kinds of jokes about Shrodinger's cat), which make people believe they understand something by simply remembering a couple of remotely relevant witty remarks. I guess, that's an elitist in me talking.
    Then you are TRWTF for believing that recursion is an elite topic. How the fuck do you do Retry without recursion?
  • hoodaticus 2011-07-21 17:50
    boog:
    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...
    In retrospect, I could have pointed out that if I advised him to look up recursion in the dictionary, the joke and ensuing comment thread would just repeat itself indefinitely.

    Of course, since that joke has no base case either, it too would be a poor example of recursion by his standards, so he'd have made the same comment about it, and the joke and ensuing comment thread would just repeat itself indefinitely.

    Either way, our supply of stack space would soon be spent.
    ... and all the world's internet backbones would start fuming ozone from the unbounded bandwidth consumption, killing millions as satellites fall out of orbit... basically all the worst parts of Christian eschatology.
  • Tim 2011-07-21 18:00
    Until you said Fall (as opposed to Autumn), I thought I might have featured in that article...
  • EvanED 2011-07-21 18:02
    EvanED:
    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.

    I have an idea which I will try soon.

    After fighting with SML and O'Caml a bit, I gave up and used Python.
    >>> def fibb2(n):
    
    ... if n==0:
    ... return (0,1)
    ... if n==1:
    ... return (1,1)
    ... (a,b) = fibb2(n-1)
    ... return (b, a+b)
    ...
    >>> def fibb(n):
    ... return fibb2(n)[1]
    ...
    >>> [(n,fibb(n)) for n in xrange(0,9)]
    [(0, 1), (1, 1), (2, 2), (3, 3), (4, 5), (5, 8), (6, 13), (7, 21), (8, 34)]


    I want to make it tail recursive, but I don't see how to get that into this version.
  • Johnny 2011-07-21 18:13
    John Galt:
    Won't that Java snippet run forever in an infinite loop if you supply it with a string that's more than 1 character long? It looks like all it's doing is moving the first character to the end of the submitted string over and over again.

    This is the second time in the last few days that I've realised people don't understand what different parameters in SubString are....or are you a troll?
  • painful swelling of the salivary glands 2011-07-21 18:15
    dohpaz42:

    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).


    answers to question 1:
    (a) code reverses a string
    (b) function could be improved by writing it in a language that has a built-in string-reversal capability, like MUMPS
    (c)
    REVERSE
    
    ;Take in a string and reverse it using the built in function $REVERSE
    NEW S
    READ:30 "Enter a string: ",S
    WRITE !,$REVERSE(S)
    QUIT
  • Annihilatorg 2011-07-21 18:22
    C-Octothorpe:
    Fat:
    Yeah, you can justify any level of stupidity these days simply by calling an opponent a troll.

    So, you do think that example has more sense than, say

    bool a=true;
    bool b;
    if (a==true)
    b=true;
    else if (a==false)
    b=false;
    else
    b=(!true)&&(!false);

    ?
    You're not an opponent, you're just wrong. And I don't think anybody called you a troll.

    Regarding your example: it's perfectly cromulent for displaying the use of an if statement... What, did you want an example with real business domain models, and perhaps a dash of DI, maybe even a recursion provider?

    You're wrong *and* you're loud... The worst combination.

    And for feck's sake... this IS tdwtf...

    bool a=true;
    bool b;
    if (a==true)
    b=true;
    else if (a==false)
    b=false;
    else
    b=FILE NOT FOUND;
  • da Doctah 2011-07-21 18:27
    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 18:45
    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 18:52
    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.
  • Mr.'; Drop Database -- 2011-07-21 18:59
    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.
  • gnasher729 2011-07-21 19:10
    [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.
  • a 2011-07-21 19:19
    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
  • a 2011-07-21 19:31
    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...
  • miguel 2011-07-21 19:40
    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));
    }
  • Mr.'; Drop Database -- 2011-07-21 19:56
    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 20:08
    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.
  • Junior Grad 2011-07-21 20:42
    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
  • BOngo 2011-07-21 20:58
    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.
  • Malarkey 2011-07-21 21:02
    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.
  • Earp 2011-07-21 22:02
    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.
  • Earp 2011-07-21 22:07
    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 22:21
    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 22:25
    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 22:56
    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);
  • Mr.'; Drop Database -- 2011-07-21 23:04
    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 23:20
    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, reworded:
    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"?
  • Dave 2011-07-22 00:35
    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.
  • Dave 2011-07-22 00:37
    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.
  • Dave 2011-07-22 00:40
    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.
  • Dave 2011-07-22 00:41
    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.
  • Matt 2011-07-22 00:54
    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 00:55
    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 01:59
    Jay:
    I thought of it as "the I'm-thinking-of-a-number management style".


    Funny, I thought that was a matrimonial style ...
  • dörte 2011-07-22 03:54
    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 03:54
    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.
  • QJo 2011-07-22 04:03
    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 04:11
    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--);
    }
  • resmoker10 2011-07-22 04:52
    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".


  • Meep 2011-07-22 05:15
    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.
  • math_geek 2011-07-22 05:59
    it is possible, google for it
    and it's such an elegant solution
  • math_geek 2011-07-22 06:00
    [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
  • Sylver 2011-07-22 06:10
    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));
  • Baggy 2011-07-22 06:12
    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();
    }
    }
  • Sylver 2011-07-22 06:29
    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;
    }
  • resmoker10 2011-07-22 07:20
    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 07:26
    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);
    }
    }
  • Fat 2011-07-22 07:29
    [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.
  • metapedant 2011-07-22 07:58

    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;
    }
    }
  • Mike 2011-07-22 08:06
    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 08:13
    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.
  • mcv 2011-07-22 08:17
    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.
  • you know who 2011-07-22 08:41
    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.


  • LordOfThePigs 2011-07-22 09:05
    Real programmer would realize that this code is wrong.

    For two reasons:

    1. 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)

    2. 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.
  • gnasher729 2011-07-22 09:21
    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.
  • AlphaGremlin 2011-07-22 09:35
    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());
    }
  • QJo 2011-07-22 09:44
    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).
  • tragomaskhalos 2011-07-22 09:50
    hoodaticus:
    I once interviewed a "C++ programmer" who couldn't pass FizzBuzz. He didn't even know how to do logical negation (!).

    Less amusing, I had an assembly programmer who did pass it, but without using the mod operator or even attempting to roll his own. He had to use string conversion and tested for the decimal point.

    Oh yes the old string conversion bodge - once reviewed some ASP code that had to alternate the colours of rows in a list; the guy had accomplished this by converting the row number to a float, dividing by 2, stringising, then picking the colour based on the presence or absence of a decimal point. Happily he's a big management wheel now, so out of harm's way !
  • Fat 2011-07-22 09:52
    That's not a matter of belief.
    The *magnitude* of fibonacci numbers F(n) grows exponentially with n (it's almost ((sqrt(5)+1)/2)^2), therefore their *length* grows lineary with n. So, to add two numbers F(n) you need O(n) operations, and to multiply - about O(n*log(n)), as far as I know.
  • Yitscar 2011-07-22 10:11
    Thanks for bringing up the magnitude problem.
    I've been trying to explain that to the hash table guys on wikipedia (http://en.wikipedia.org/wiki/Talk:Hash_table#Look_up_is_not_O.281.29_at_all) : if your number of elements becomes large enough, you'll have to use a key of O(log(n)) bits, and its manipulation will take a time of O(log n), not O(1)
  • hoodaticus 2011-07-22 10:12
    gnasher729:
    boog:
    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.

    This.
  • Makky 2011-07-22 10:13
    Reverse a string by swapping leftside with rightside.

    String s = "ReverseMePlease";
    int left = 0;
    int right = s.length() - 1;
    char[] c = s.toCharArray();

    while(left < right)
    {
    char tmp = c[left];
    c[left] = c[right];
    c[right] = tmp;
    left++;
    right--;
    }

    return new String(c);
  • hoodaticus 2011-07-22 10:17
    Yitscar:
    Thanks for bringing up the magnitude problem.
    I've been trying to explain that to the hash table guys on wikipedia (http://en.wikipedia.org/wiki/Talk:Hash_table#Look_up_is_not_O.281.29_at_all) : if your number of elements becomes large enough, you'll have to use a key of O(log(n)) bits, and its manipulation will take a time of O(log n), not O(1)
    I think I agree with your opponents there.
  • hoodaticus 2011-07-22 10:18
    resmoker10:
    Sylver:

    Love it too, but how about:

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


    that just causes a stack overflow
    NICE!
  • veggen 2011-07-22 10:21
    I'm absolutely certain the last story had already appeared on this site before... I remember the "it's an idea floating around" comment.
  • hoodaticus 2011-07-22 10:22
    Dave:
    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.
    BEST BURN EVER! Tchshhhhhhhhh.
  • boog 2011-07-22 10:31
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.

    Sorry everybody.
  • you know who 2011-07-22 10:42
    boog:
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.

    Sorry everybody.



    public int fib(int n){
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow((1+sqrt5), n);
    double termTwo = Math.pow((1-sqrt5), n);
    return (int)((termOne + termTwo)/(2 * sqrt5));
    }

    public void fibSeq()
    {
    for (int n = 0; n < 100; ++n)
    System.out.println(fib(n));
    }
  • hoodaticus 2011-07-22 10:42
    boog:
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.
    O(1) would be even more interesting.
  • you know who 2011-07-22 10:47
    you know who:
    boog:
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.

    Sorry everybody.



    public int fib(int n){
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow((1+sqrt5), n);
    double termTwo = Math.pow((1-sqrt5), n);
    return (int)((termOne - termTwo)/(2 * sqrt5));
    }

    public void fibSeq()
    {
    for (int n = 0; n < 100; ++n)
    System.out.println(fib(n));
    }


    whoops
  • Fat 2011-07-22 10:54
    you know who:
    you know who:
    boog:
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.

    Sorry everybody.



    public int fib(int n){
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow((1+sqrt5), n);
    double termTwo = Math.pow((1-sqrt5), n);
    return (int)((termOne - termTwo)/(2 * sqrt5));
    }

    public void fibSeq()
    {
    for (int n = 0; n < 100; ++n)
    System.out.println(fib(n));
    }


    whoops


    I think if you'd actually tried and execute this code, you'd understand it has at least one error.
  • Fat 2011-07-22 10:57
    And even if this code was right, this pinciple would give you O(n*log(n)) time for really large n (starting from 100 or so), at least if you wanted to calculate *exact* value of fibonacci number, not approximate.
  • boog 2011-07-22 10:57
    you know who:
    you know who:
    boog:
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.

    Sorry everybody.



    public int fib(int n){
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow((1+sqrt5), n);
    double termTwo = Math.pow((1-sqrt5), n);
    return (int)((termOne - termTwo)/(2 * sqrt5));
    }

    public void fibSeq()
    {
    for (int n = 0; n < 100; ++n)
    System.out.println(fib(n));
    }


    whoops
    "Whoops" indeed - you failed to understand the amended comment and went and generated a list of numbers.

    As fake frits would say, "your[sic] not too bright, are you?"
  • you know who 2011-07-22 11:00
    Fat:
    you know who:
    you know who:
    boog:
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.

    Sorry everybody.



    public int fib(int n){
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow((1+sqrt5), n);
    double termTwo = Math.pow((1-sqrt5), n);
    return (int)((termOne - termTwo)/(2 * sqrt5));
    }

    public void fibSeq()
    {
    for (int n = 0; n < 100; ++n)
    System.out.println(fib(n));
    }


    whoops


    I think if you'd actually tried and execute this code, you'd understand it has at least one error.


    0
    1
    1
    2
    3
    5
    8
    13
    21
    34
    55
    89
    144
    233
    377
    610
    987
    1597
    2584
    4181
    6765
    10946
    17711
    28657
    46368
    75025
    121393
    196418
    317811
    514229
    832040
    1346269
    2178309
    3524578
    5702887
    9227465
    14930352
    24157817
    39088169
    63245986
    102334155
    165580141
    267914296
    433494437
    701408733
    1134903170
    1836311903
    2147483647
    2147483647
    2147483647
    2147483647
    2147483647
    2147483647
    ...several more 2147483647's ...
  • boog 2011-07-22 11:01
    hoodaticus:
    boog:
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.
    O(1) would be even more interesting.
    Indeed. I once saw a C++ implementation of fibonacci numbers that used macros to unroll for-loops, so it could calculate fibonacci numbers at compile time. Sure, not O(1) when compiling, but O(1) at run-time.
  • you know who 2011-07-22 11:04
    boog:
    you know who:
    you know who:
    boog:
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.

    Sorry everybody.



    public int fib(int n){
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow((1+sqrt5), n);
    double termTwo = Math.pow((1-sqrt5), n);
    return (int)((termOne - termTwo)/(2 * sqrt5));
    }

    public void fibSeq()
    {
    for (int n = 0; n < 100; ++n)
    System.out.println(fib(n));
    }


    whoops
    "Whoops" indeed - you failed to understand the amended comment and went and generated a list of numbers.

    As fake frits would say, "your[sic] not too bright, are you?"


    What, would you say, is the complexity of the fib function?
  • boog 2011-07-22 11:09
    EvanED:
    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.
    Fair enough, but this challenge actually has a point: improved performance. In order to improve performance of any algorithm, a programmer will most likely need to use math.

    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.
    Also fair. I don't use a lot of functional languages (only one, and not very much). In that case, the problem is much more "functional-language" interesting, and not at all "imperative-language" interesting. Like my O(log(n)) problem, it's apparently being marketed to the wrong audience.

    EvanED:
    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.
    Also fair. I often forget that some people like to have fun. I should get out more. Consider that part of my comment taken back.
  • boog 2011-07-22 11:10
    you know who:
    What, would you say, is the complexity of the fib function?
    What, would you say, is the point of the fibSeq() function? Or the comment "whoops"?
  • you know who 2011-07-22 11:16
    boog:
    you know who:
    What, would you say, is the complexity of the fib function?
    What, would you say, is the point of the fibSeq() function? Or the comment "whoops"?
    And you have the audacity to imply I'm not too bright.
  • Sutherlands 2011-07-22 11:39
    Hortical:
    Sutherlands:

    Psuedocode:

    foreach(letter in string)
    StringBuilder.AppendFront(letter)


    Consider the possibility that the StringBuilder uses a char[] internally.

    Consider the possibility that every time you insert a char at the beginning, all the other chars that have been added have to be moved over a space. Every time.
    Consider the possibility that this is pseudocode.
  • Fat 2011-07-22 11:42
    That is strange, since




    import java.util.*;
    import java.lang.*;

    class Main
    {

    public static int fib(int n){
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow((1+sqrt5), n);
    double termTwo = Math.pow((1-sqrt5), n);
    return (int)((termOne - termTwo)/(2 * sqrt5));
    }



    public static void fibSeq()
    {
    for (int n = 0; n < 10; ++n)
    System.out.println(fib(n));
    }

    public static void main (String[] args) throws java.lang.Exception
    {
    fibSeq();
    }
    }


    gave me


    0
    1
    2
    8
    24
    80
    256
    832
    2688
    8704

    Doesn't look like fibonacci sequence at all.
  • Rootbeer 2011-07-22 11:58
    Converting a string from (7-bit) ASCII to (invariant) EBCDIC and back shouldn't result in any loss of information, as long as it doesn't contain any characters outside of the set 1234567890-=@%&*()_+qwertyuiopQWERTYUIOP|asdfghjkl;'ASDFGHJKL:"zxcvbnm,.ZXCVBNM<>? and regular space.
  • Sutherlands 2011-07-22 11:59
    resmoker10:
    Sylver:

    Love it too, but how about:

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


    that just causes a stack overflow

    Ok, how about:
    public bool learn(recursion)
    {
    if(understand(recursion))
    return true;
    return learn(recursion)
    }
  • Jay 2011-07-22 12:09
    dohpaz42:
    Recursion is usually a precursor to larger algorithms, such as sorting. If you can't understand recursion, you have no hope of quick sort or tree traversal.


    And if you can't understand recursion, you have no hope of understanding recursion.

    (Sorry, I couldn't help it.)
  • boog 2011-07-22 12:14
    you know who:
    boog:
    you know who:
    What, would you say, is the complexity of the fib function?
    What, would you say, is the point of the fibSeq() function? Or the comment "whoops"?
    And you have the audacity to imply I'm not too bright.
    That's unfair. In no way did I ever imply such a thing.

    However, I did say it quite explicitly.
  • Jay 2011-07-22 12:17
    Nebler:
    Jeff:
    What about improvements to the recursive string reversal code?

    I'm thinking:

    1) First choice, use any built in library functions since they're already coded, tested, and optimized.

    2) Don't use recursion since that's a lot of overhead and you could get a possible stack overflow if the string was long. (Can you even get stack overflows in C#? I honestly haven't had one in many many years).

    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?


    1) Is the only correct option. Always use unicode-aware methods, like string.reverse. All your surrogate pairs will die otherwise. The code in the interview gets this wrong as well.


    What language are we supposing here? A Java string is a collection of chars, i.e. code points, not of bytes. So you don't need to worry about breaking the Unicode sequences when doing char manipulation.
  • SCB 2011-07-22 12:18
    you know who:
    boog:
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.

    Sorry everybody.



    public int fib(int n){
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow((1+sqrt5), n);
    double termTwo = Math.pow((1-sqrt5), n);
    return (int)((termOne + termTwo)/(2 * sqrt5));
    }

    public void fibSeq()
    {
    for (int n = 0; n < 100; ++n)
    System.out.println(fib(n));
    }

    But that calculates them in O(1).
    You need to add:
    sleep(log(n));
  • Jay 2011-07-22 12:19
    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 ^^


    That's what happens when you fail to spend at least 2 hours studying algorithms.
  • boog 2011-07-22 12:23
    SCB:

    But that calculates them in O(1).
    You need to add:
    sleep(log(n));
    Really? If n changed to 1000 or 10000, fibSeq would run in the same amount of time?

    Interesting...
  • EvanED 2011-07-22 12:24
    Jay:
    What language are we supposing here? A Java string is a collection of chars, i.e. code points, not of bytes. So you don't need to worry about breaking the Unicode sequences when doing char manipulation.

    Look up combining characters. There are single "logical characters" (that's probably not a real term) that are represented by multiple code points. Or see the second question here. (It uses "grapheme" for something that approximates my "logical character." I'm not sure if it's exactly the same as what I have in mind.)

    I don't know whether surrogate pairs enter the picture here or not.
  • Jay 2011-07-22 12:43
    On a mildly serious note: To all those saying that the "right answer" is to use a built-in reverse function:

    If I was applying for a job and the interviewer asked me to write a function to reverse a string, or if I was taking a class and this was a project assignment, I'd think an assumption in the question is that I can't just call a function that someone else wrote. I suppose I might ask if that's a legal solution. But presumably the point of the question is to test the appplicant's ability to write code to solve the problem, not his ability to look things up in the reference docs.

    If you were given a school assignment to "write an e-mail program", do you think you could just hand in a copy of MS Outlook and get an A? (Well, probably a C, but that's another story.) That's not "writing an e-mail program", that's "making a copy of an e-mail program that someone else wrote".

    I suppose it's possible that the goal of the question is to find out if you're familiar with the library, or if you know to use library functions rather than re-writing everything yourself from scrath. But if I was interviewing someone, "Does the applicant remember that a relatively-infrequently-used function is in the library?" does not seem like a useful thing to know.

  • you know who 2011-07-22 13:27
    boog:
    you know who:
    boog:
    you know who:
    What, would you say, is the complexity of the fib function?
    What, would you say, is the point of the fibSeq() function? Or the comment "whoops"?
    And you have the audacity to imply I'm not too bright.
    That's unfair. In no way did I ever imply such a thing.

    However, I did say it quite explicitly.


    You asked, implying it was the case, you didn't state it.
  • you know who 2011-07-22 13:32
    boog:
    you know who:
    What, would you say, is the complexity of the fib function?
    What, would you say, is the point of the fibSeq() function? Or the comment "whoops"?


    I know what you said. I gave you an (incorrect translation) of an algorithm that will do it faster than O(n). It's not O(log n), but it's faster than O(n). I thought it would be interesting.

    The fibSeq() was part of the code used to frame the function.

    The "whoops" was cause I mistyped a minus sign the first time. It still doesn't work. This does, as I actually tested it this time:

    public static long fib(int n)
    {
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow(1+sqrt5, n);
    double termTwo = Math.pow(1-sqrt5, n);

    return (long)((termOne - termTwo)/(sqrt5 * 2));
    }

    public static void main(String[] args) throws IOException
    {
    long[] fibNums = new long[50];

    for (int x = 0; x < 50; ++x)
    System.out.println(fibNums[x] = fib(x));

    for (int x = 2; x < 50; ++x)
    if (fibNums[x] != fibNums[x - 1] + fibNums[x - 2])
    throw new Error();

    System.out.println("success");
    System.exit(0);
    }


    0
    1
    1
    2
    3
    5
    8
    13
    21
    34
    55
    89
    144
    233
    377
    610
    987
    1597
    2584
    4181
    6765
    10946
    17711
    28657
    46368
    75025
    121393
    196418
    317811
    514229
    832040
    1346269
    2178309
    3524578
    5702887
    9227465
    14930352
    24157817
    39088169
    63245986
    102334155
    165580141
    267914296
    433494437
    701408733
    1134903170
    1836311903
    2971215073
    4807526976
    7778742049
    success
  • hoodaticus 2011-07-22 13:32
    boog:
    Fair enough, but this challenge actually has a point: improved performance. In order to improve performance of any algorithm, a programmer will most likely need to use math.
    + 1/0 for truth. If you ever need calculus, and you try to approximate it with procedure, your system's performance will suck xunesis's donkey balls.
  • you know who 2011-07-22 13:34
    boog:
    SCB:

    But that calculates them in O(1).
    You need to add:
    sleep(log(n));
    Really? If n changed to 1000 or 10000, fibSeq would run in the same amount of time?

    Interesting...


    Don't be an ass. We already have plenty of those.
  • C-Octothorpe 2011-07-22 13:38
    you know who:
    Don't be an ass. We already have plenty of those.

    Clearly... ^^
  • Hortical 2011-07-22 13:39
    Sutherlands:
    Hortical:
    Sutherlands:

    Psuedocode:

    foreach(letter in string)
    StringBuilder.AppendFront(letter)


    Consider the possibility that the StringBuilder uses a char[] internally.

    Consider the possibility that every time you insert a char at the beginning, all the other chars that have been added have to be moved over a space. Every time.
    Consider the possibility that this is pseudocode.


    pseudocode typically doesn't involve references to specific class libraries does it?

    You'll notices that I understood by "AppendFront(letter)", you meant "insert(0, letter)". I understand your pseudocode and that is it pseudo. But when we apply your approach it doesn't work out nearly as well as other approaches that have been posted, for the reason I gave.

    You were wrong, get over it.
  • Sutherlands 2011-07-22 13:50
    Hortical:
    Sutherlands:
    Hortical:
    Sutherlands:

    Psuedocode:

    foreach(letter in string)
    StringBuilder.AppendFront(letter)


    Consider the possibility that the StringBuilder uses a char[] internally.

    Consider the possibility that every time you insert a char at the beginning, all the other chars that have been added have to be moved over a space. Every time.
    Consider the possibility that this is pseudocode.


    pseudocode typically doesn't involve references to specific class libraries does it?

    You'll notices that I understood by "AppendFront(letter)", you meant "insert(0, letter)". I understand your pseudocode and that is it pseudo. But when we apply your approach it doesn't work out nearly as well as other approaches that have been posted, for the reason I gave.

    You were wrong, get over it.
    Really? Please tell me what language I was using.

    The best approach is to simply use a library function that exists to do the task at hand, and that is what I would do.
  • Loren Pechtel 2011-07-22 14:09
    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.


    That's a REALLY backwards approach!

  • Hortical 2011-07-22 14:09
    Sutherlands:
    Really? Please tell me what language I was using.

    The best approach is to simply use a library function that exists to do the task at hand, and that is what I would do.


    I saw "StringBuilder" and assumed java class libraries, but that's obviously not the case after a second glance. Then again, C#'s interface has the same method - underlying implementation, I don't know.

    I agree about using library functions, but that's not what you did, then again, it's not what you're supposed to do on this test and the approach you took in doing what you were supposed to do wasn't ideal either, despite the fact that it's just pseudocode.
  • Fat 2011-07-22 14:11
    I still don't believe you've executed your code.
    All I get is
    0
    1
    2
    8
    24
    80
    256
    832
    2688
    8704
    28160
    91136
    294912
    954368
    3088384
    9994240
    32342016
    104660992
    338690048
    1096024064
    3546808320
    11477712896
    37142659072
    120196169728
    388962975744
    1258710630400
    4073273163776
    13181388849152
    42655870353408
    138037296103424
    446698073620480
    1445545331654657
    4677882957791237
    15137947242201104
    48987426315567160
    158526641599938752
    513002988462146176
    1660112543324047360
    5372237040496678912
    9223372036854775807
    9223372036854775807
    9223372036854775807 (repeatedly)

    and then an exception.

    Besides, I clearly see the error that leads to this error. But I don't understand, why would you lie you tested it?
  • you know who 2011-07-22 14:12
    C-Octothorpe:
    you know who:
    Don't be an ass. We already have plenty of those.

    Clearly... ^^


    Speak of the devil. Of course, you're a different kind of ass. boog is the kind that misunderstands things and then tries to make someone else look ridiculous so no one notices. You're the kind that takes jabs at others for being nerds despite the fact that you spend a good portion of your day here.
  • boog 2011-07-22 14:13
    you know who:
    boog:
    you know who:
    boog:
    you know who:
    What, would you say, is the complexity of the fib function?
    What, would you say, is the point of the fibSeq() function? Or the comment "whoops"?
    And you have the audacity to imply I'm not too bright.
    That's unfair. In no way did I ever imply such a thing.

    However, I did say it quite explicitly.


    You asked, implying it was the case, you didn't state it.
    Actually, I stated it, and asked for confirmation. :)
  • you know who 2011-07-22 14:13
    Fat:
    I still don't believe you've executed your code.
    All I get is
    0
    1
    2
    8
    24
    80
    256
    832
    2688
    8704
    28160
    91136
    294912
    954368
    3088384
    9994240
    32342016
    104660992
    338690048
    1096024064
    3546808320
    11477712896
    37142659072
    120196169728
    388962975744
    1258710630400
    4073273163776
    13181388849152
    42655870353408
    138037296103424
    446698073620480
    1445545331654657
    4677882957791237
    15137947242201104
    48987426315567160
    158526641599938752
    513002988462146176
    1660112543324047360
    5372237040496678912
    9223372036854775807
    9223372036854775807
    9223372036854775807 (repeatedly)

    and then an exception.

    Besides, I clearly see the error that leads to this error. But I don't understand, why would you lie you tested it?


    So you're under the impression that I got out a calculator and figured the output by hand?
  • you know who 2011-07-22 14:15
    boog:
    you know who:
    boog:
    you know who:
    boog:
    you know who:
    What, would you say, is the complexity of the fib function?
    What, would you say, is the point of the fibSeq() function? Or the comment "whoops"?
    And you have the audacity to imply I'm not too bright.
    That's unfair. In no way did I ever imply such a thing.

    However, I did say it quite explicitly.


    You asked, implying it was the case, you didn't state it.
    Actually, I stated it, and asked for confirmation. :)


    Cool! We already forgot about how you (apparently) don't understand the complexity of algorithms. Nice work, boog!
  • Fat 2011-07-22 14:19
    I believe that either you post here not the code you execute, or you get the right output from some place else (maybe calculator, maybe almighty google).
    But again, your motives for this are unclear.
  • Sutherlands 2011-07-22 14:20
    Hortical:
    Sutherlands:
    Really? Please tell me what language I was using.

    The best approach is to simply use a library function that exists to do the task at hand, and that is what I would do.


    I saw "StringBuilder" and assumed java class libraries, but that's obviously not the case after a second glance. Then again, C#'s interface has the same method - underlying implementation, I don't know.

    I agree about using library functions, but that's not what you did, then again, it's not what you're supposed to do on this test and the approach you took in doing what you were supposed to do wasn't ideal either, despite the fact that it's just pseudocode.

    C# uses a string and memcpy under the hood for Insert. Despite that, I wasn't answering the question in the OP, I was answering someone's question who didn't understand how you would do it without recursion.

    Re: answering the question in the article with a statement to use the library function: That's the first thing I would do, depending on how the question was worded. "How would you do this?" vs "Write this function". In the second case, I'd probably ask if we can insert a call to the function, which is something I've had to do at my job to "improve" a function that didn't exist in previous versions of the framework. Answering in this way shows that you actually know the framework and have used it. It's amazing when you interview people how many simply don't know how to use what they're working with.
  • C-Octothorpe 2011-07-22 14:20
    you know who:
    C-Octothorpe:
    you know who:
    Don't be an ass. We already have plenty of those.

    Clearly... ^^


    Speak of the devil. Of course, you're a different kind of ass. boog is the kind that misunderstands things and then tries to make someone else look ridiculous so no one notices. You're the kind that takes jabs at others for being nerds despite the fact that you spend a good portion of your day here.
    No, I was taking a jab at you because, like most everyone else here, you're an ass. It just seems silly to call someone an ass when you're clearly one yourself (pot, kettle, black, etc.).

    boog is an ass, but at least he's funny, you just throw a tantrum...
  • you know who 2011-07-22 14:21
    Fat:
    I believe that either you post here not the code you execute, or you get the right output from some place else (maybe calculator, maybe almighty google).
    But again, your motives for this are unclear.

  • kilroo 2011-07-22 14:22
    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.

    One project I worked on had to do so many JOINs just to get a single record out of their database that they exceeded MySQL's JOIN limit (61). Twice. They had to write code to keep track of the # of joins while building the query, and break the query into separate pieces when necessary. It goes without saying that the queries also took about 100 times longer than necessary, and data integrity was a complete nightmare.

    ...This wasn't by any chance a situation where there were a whole lot of different views for converting different combinations of attributes into columns, and there was code for redefining the views programmatically if something changed, and each view actually existed three times...once joined with test data and twice for two different kinds of production data?
  • Fat 2011-07-22 14:24
    http://ideone.com/tLLki

    The game is called "find the difference". Perhaps, you will help me? Or, maybe, someone else? Anyone?
  • you know who 2011-07-22 14:32
    Fat:
    http://ideone.com/tLLki

    The game is called "find the difference". Perhaps, you will help me? Or, maybe, someone else? Anyone?


    Here. I'm done.

    http://www.dreamincode.net/code/snippet6172.htm
  • boog 2011-07-22 14:36
    you know who:
    boog is the kind that misunderstands things and then tries to make someone else look ridiculous so no one notices.
    You have to admit I have a pretty unique way of misunderstanding things, in that my earlier comment completely misunderstood your consequent reply to it.

    Hint: Time travel is necessary.
  • Fat 2011-07-22 14:39
    What does this have to do with your code? This is valid and working code, as far as I see. Yours is not.
    If you don't see the difference between this code and yours, then I hope you're trolling. I'd lose faith in humanity if I found out that someone can be as retarded as you appear to be.
  • you know who 2011-07-22 14:40
    C-Octothorpe:
    No, I was taking a jab at you because, like most everyone else here, you're an ass. It just seems silly to call someone an ass when you're clearly one yourself (pot, kettle, black, etc.).

    boog is an ass, but at least he's funny, you just throw a tantrum...


    True, we are asses. Apparently we're also both hypocritical about throwing tantrums.
  • you know who 2011-07-22 14:41
    Fat:
    What does this have to do with your code? This is valid and working code, as far as I see. Yours is not.
    If you don't see the difference between this code and yours, then I hope you're trolling. I'd lose faith in humanity if I found out that someone can be as retarded as you appear to be.


    IHBT apparently. That's were I got the idea. I tried to edit it for some reason. Then were was alot of talking to you that I regret.
  • C-Octothorpe 2011-07-22 14:43
    you know who:
    C-Octothorpe:
    No, I was taking a jab at you because, like most everyone else here, you're an ass. It just seems silly to call someone an ass when you're clearly one yourself (pot, kettle, black, etc.).

    boog is an ass, but at least he's funny, you just throw a tantrum...


    True, we are asses. Apparently we're also both hypocritical about throwing tantrums.
    Again, you're wrong... I'm far too immature to throw a tantrum.
  • boog 2011-07-22 14:49
    you know who:
    boog:
    you know who:
    boog:
    you know who:
    boog:
    you know who:
    What, would you say, is the complexity of the fib function?
    What, would you say, is the point of the fibSeq() function? Or the comment "whoops"?
    And you have the audacity to imply I'm not too bright.
    That's unfair. In no way did I ever imply such a thing.

    However, I did say it quite explicitly.


    You asked, implying it was the case, you didn't state it.
    Actually, I stated it, and asked for confirmation. :)


    Cool! We already forgot about how you (apparently) don't understand the complexity of algorithms. Nice work, boog!
    Indeed, I've said nothing to demonstrate an understanding of computational complexity. How you'd therefore assume I have no such understanding seems to indicate a poor understanding of logic on your part.
  • boog 2011-07-22 14:51
    Fat:
    What does this have to do with your code? This is valid and working code, as far as I see. Yours is not.
    If you don't see the difference between this code and yours, then I hope you're trolling. I'd lose faith in humanity if I found out that someone can be as retarded as you appear to be.
    You must be new to this site. Look through the archives; there are 7 years worth of examples of people as retarded as he appears to be.
  • boog 2011-07-22 14:59
    C-Octothorpe:
    boog is an ass, but at least he's funny...
    I'd like to think that I only ever act like an ass to people who deserve it.

    Yes, I'm quite sure I'd like to think that.
  • Fat 2011-07-22 15:00
    I always thought there wes a big deal of exaggeration in these stories.
    I guess, being in academia for a long time really changed my opinion about people.
  • you know who 2011-07-22 15:17
    boog:
    Fat:
    What does this have to do with your code? This is valid and working code, as far as I see. Yours is not.
    If you don't see the difference between this code and yours, then I hope you're trolling. I'd lose faith in humanity if I found out that someone can be as retarded as you appear to be.
    You must be new to this site. Look through the archives; there are 7 years worth of examples of people as retarded as he appears to be.

    Now that's painful. I'd never heard of a constant-time way to compute a Fibonacci number before and when I saw you say something about finding one in logarithmic time, I thought, "I'll do you one better - look at this". Just posting the link might have worked better. I'll remember that for next time.
  • C-Octothorpe 2011-07-22 15:30
    boog:
    I'd like to think that I only ever act like an ass to people who deserve it.
    My bad; I didn't read before I posted.

    Allow me to rephrase: boog *can* be an ass... :)
  • boog 2011-07-22 15:38
    C-Octothorpe:
    My bad; I didn't read before I posted.

    Allow me to rephrase: boog *can* be an ass... :)
    No, you were right the first time. I just didn't properly emphasize in my reply:
    boog:
    I'd like to think that I only ever act like an ass to people who deserve it.

    Yes, I'm quite sure I'd like to think that.
    FTFM
  • xoonyzyz 2011-07-22 16:11
    hoodaticus:
    boog:
    Fair enough, but this challenge actually has a point: improved performance. In order to improve performance of any algorithm, a programmer will most likely need to use math.
    + 1/0 for truth. If you ever need calculus, and you try to approximate it with procedure, your system's performance will suck xunesis's donkey balls.
    Ahem. He's a MULE. Not a donkey.

    The donkey is a miscarriaged freeze-dried FEMALE fetus with eye sockets emptied and enlarged. Thank you very much.
  • xoonyzyz 2011-07-22 16:13
    C-Octothorpe:
    boog:
    I'd like to think that I only ever cum on an ass of people who deserve it.
    My bad; I didn't look before I squirted.

    Allow me to reiterate: boog *can* use my ass... :)
  • the zune system 2011-07-22 16:36
    C-Octothorpe:
    you know who:
    C-Octothorpe:
    you know who:
    Don't be an ass. We already have plenty of those.

    We could always use more ass!


    Right on, bro... ^^

    You suck me[/color=white]!
    You suck [color=white]me[/color=white]!
    You suck [color=white]me[/color=white]!

    Stop making fun of my boyfriend!


    How can you guys stand to take[color=white] it in the ass
    yourselves so seriously?
  • The Web is the Root of All Info 2011-07-22 21:18
    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.


    There's two parts to the answer:
    1. Since this is Java, the solution should use the 'StringBuilder' class as 'String's are immutable when created.
    So _each_ time the given solution recurses, at least _another_ copy of the supplied String is created.
    This makes the supplied solution O(n^2) in memory.

    2. Using StringBuilder allows the adjustment of individual characters in-place, so you could create a for loop that travels along 1/2 of the string, swapping the character at the current position with the character at [total string length minus the current position]
  • Mr Java 2011-07-23 05:18
    Hortical:
    anonymouser:
    Hortical:
    Sutherlands:

    Psuedocode:

    foreach(letter in string)
    StringBuilder.AppendFront(letter)


    Consider the possibility that the StringBuilder uses a char[] internally.

    Consider the possibility that every time you insert a char at the beginning, all the other chars that have been added have to be moved over a space. Every time.


    I would bet it's more like <char>List, or something similar.



    Ok, now consider the possibility that I've seen the source code and it does use a char[].

    http://www.docjar.com/html/api/java/lang/AbstractStringBuilder.java.html



    Of course, one could always be boring and just use StringBuilder.reverse().
  • hikari 2011-07-23 09:08
    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.


    Yeah, but you can at least just write an extension method in C#
  • Don L 2011-07-23 16:14
    I once assisted our Manager of the Support Division in evaluating candidates' technical skills. While the manager was present at the interviews, I'd ask all sorts of questions.
    Quite often, the manager ignored my recommendations, even though I could pinpoint all the candidate's errors.
    Equally often, he sacked the hired candidate after 3 months for not being good enough.
    Sigh.
    Once, they hired a guy without the necessary skills just because he'd been a sharpshooter in the Army. The HR manager was an ex army guy, too.
  • someone 2011-07-23 20:34
    I remember being a part of a German start-up because it was the only company with an English environment which was still hiring. The English was with such a strong German accent, that I could barely understand. What's worse, all tasks were specified in Mantis using grammatically illogical and incomplete sentences. The boss hated explaining anything that was clear to him, and the rest of the stuff was my job to find out. You cannot imagine how bad their codebase was. I refused to work with their code and offered working on new modules and new CMS only. That way I got immediately 20% lower salary for refusing to work with their code. Never minds, it was still 100% more than the average salary in my country. One of the pearls they were so proud about was exactly the same stupid thing as described in this article; database tables stored as ordinary data inside a MyISAM DB. Their code was so bad that with every request for new functionality, the company would rewrite the whole CMS module. The code was simply write-only. No matter how many times they rewrote it, it never came to their mind this is now how you develop software. I've seen so many bad start-ups, and only one which was a good one.
  • someone 2011-07-23 20:36
    s/this is now how you develop software/this is *NOT* how you develop software
  • Matt Westwood 2011-07-24 04:51
    Don L:
    I once assisted our Manager of the Support Division in evaluating candidates' technical skills. While the manager was present at the interviews, I'd ask all sorts of questions.
    Quite often, the manager ignored my recommendations, even though I could pinpoint all the candidate's errors.
    Equally often, he sacked the hired candidate after 3 months for not being good enough.
    Sigh.
    Once, they hired a guy without the necessary skills just because he'd been a sharpshooter in the Army. The HR manager was an ex army guy, too.


    I once failed to bag a sweet internal promotion because I'm not a soccer fan. After everything went tits-up in that department I discussed this with the guy whose responsibility it had been to make that decision. He had to agree with me that it had been the worst mistake of his career.

    Sometimes management skills are things you have to learn through trial and error. Wisdom comes with age. And it takes a particularly cool head to deliberately *not* select a person to whom you've (unwisely, perhaps even drunkenly) promised a position when encountering him in a social situation.

    Apparently most positions are filled via the "network" rather than the formal interview process. Whether this is on the whole a good or a bad thing is debatable, but it may be more worthwhile cultivating social contacts than relying on job adverts and agencies.
  • Anonymous 2011-07-24 07:34
    The Web is the Root of All Info:

    ...

    1. Since this is Java, the solution should use the 'StringBuilder' class as 'String's are immutable when created.
    So _each_ time the given solution recurses, at least _another_ copy of the supplied String is created.
    This makes the supplied solution O(n^2) in memory.

    ...


    I know I'm days late on this thread, but this thread is full of posts talking about the memory usage here incorrectly...

    substring in Java shares the char[] buffer from the parent string, so there's no copying involved. In fact, that's one of the reasons that the strings are immutable.

    Yes, this solution uses a bunch of memory, but it uses it coming up out of the recursion, not going down it. The + operator is the issue, not the substring call.


    // Unicode problems aside, this is O(n) memory
    // and no copying happens.
    String reverse(String s, StringBuilder b) {
    if (s == null || s.length() == 0) return s;
    boolean top = false;
    if (b == null) {
    b = new StringBuilder(s.length());
    top = true;
    }
    reverse(s.substring(1), b);
    b.append(s.charAt(0));
    return top ? builder.toString() : null;
    }
  • Jesper 2011-07-25 03:53
    The real WTF: Calling that Java method a function on a senior Java developer test.
  • The Poop... of DOOM 2011-07-25 05:34
    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.

    Back in the two-weeks student job I did software testing for hospital software, I had a similar thing. I followed the test scenario and created a bug report for every bug found. Same with inconsistencies in the GUI (which was specified to check for in the intro text of the test scenario). One day, the main developer came in to tell me to stop filing so many bugs, cause he had to close them all. Not fix them all, just close them all. Must be some pretty dangerous hospitals, running on such a buggy OR scheduling software...
  • QJo 2011-07-25 06:37
    The Poop... of DOOM:
    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.

    Back in the two-weeks student job I did software testing for hospital software, I had a similar thing. I followed the test scenario and created a bug report for every bug found. Same with inconsistencies in the GUI (which was specified to check for in the intro text of the test scenario). One day, the main developer came in to tell me to stop filing so many bugs, cause he had to close them all. Not fix them all, just close them all. Must be some pretty dangerous hospitals, running on such a buggy OR scheduling software...


    <irony>
    We had a QA person like that. I propped her up in front of my lovely application that I knew was completely bug-free (I wrote it, it must have been) and she came back to me with page after page of all sorts of things wrong: stackdumps, incorrect messages, pages being misdirected, 404s so help me. It turned out she had been pressing buttons and entering stuff I hadn't specifically told her to, just *randomly* pretending to be an awkward customer!
    </irony>
  • c 2011-07-25 07:08
    Hm, so how come after Tim had been rejected that guy got to have 2 more free lunches? It was clear the other two would be hired no matter what.
  • blarg 2011-07-25 13:36
    Jay:
    There are basically two reasons why someone might ask your opinion.

    1. On rare occasions, it may be because the asker has not made up his mind and believes that insights or suggestions that you have may help him to arrive at a better decision.

    2. Most of the time, the asker has already made up his mind and is looking for someone else to validate his decision.

    I regularly have conversations with my boss where he asks, "What do you think we should do about X?" Then I say what I think we should do. Then he explains to me why he's already decided to do something else.

    Still, it's better then the way we used to work. That was, he would make a decision about something. Then he would tell me to come up with a solution to whatever problem, without telling me what his idea was. I would spend days writing up a design document or coding a program or whatever. Then he would yell at me because I hadn't done it the way he wanted. I thought of it as "the I'm-thinking-of-a-number management style".


    and it sounds like were using the "I'm-not-going-to-ask-which-number,-maybe-it-is-47" approach
  • drummerp 2011-07-25 15:37
    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).


    See, I usually had recursion explained through the use of factorials. That's a pretty simple example of recursion.
  • Mikkel 2011-07-27 08:55
    John Galt:
    John Galt:
    Won't that Java snippet run forever in an infinite loop if you supply it with a string that's more than 1 character long? It looks like all it's doing is moving the first character to the end of the submitted string over and over again.


    Ah - never mind, didn't see the parenthesis in the last line.


    Thanks for pointing that out, I missed it as well and came to the comments for an explanation because I only saw it as an endless loop :-)
  • Satanicpuppy 2011-07-27 17:16
    dohpaz42:
    Not a Java programmer:
    To clarify, that second one just reverses the string right? Does the Java string type not have a method to do that?


    Yes, it reverses the string. And, it doesn't matter if there is a built-in for that; this was a coding challenge to gauge the ability of the interviewee to see if they could tell from looking at the code what the code should be doing - well, I hope that's what it is, anyway. :)


    I always find it amusing that people test on recursion, when recursion has very little place in the real world. I worked a lot in SCHEME when I was younger, and SCHEME is very friendly to recursion. And recursion is so fricking *pretty*. It's very elegant.

    But usually you have to document it so thoroughly that it's not worth not doing it iteratively. It also hogs memory dramatically compared to iteration, and even seasoned coders have to stop and scratch their heads for a minute.

    The last time I seriously used recursion was in school. I wrote a program on an exam. The paper provided was almost two pages, and my recursion worked in 3 *lines*. I was so proud of myself when I turned it in. I got full credit, but the prof took the opportunity provided to write a massive diatribe about it in the remaining space. Told me that if he'd seen it in the real world, he'd have fired me, and that if he saw it on another exam, I'd only get half credit.

    It's a lesson I took to heart, and to this day, I can count the number of legitimate uses of recursion I've seen in other peoples code on one hand. On the other hand, I can't count the number of times I've seen it used for obfuscation.

    That being the case, I'd recommend you make harder, less recursive tests.
  • Anonymous Coder 2011-07-31 07:47
    you know who:
    you know who:
    boog:
    gnasher729:
    boog:
    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.
    Sorry, calculating a number in the fibonacci sequence in O(log(n)) would be interesting.

    Sorry everybody.



    public int fib(int n){
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow((1+sqrt5), n);
    double termTwo = Math.pow((1-sqrt5), n);
    return (int)((termOne - termTwo)/(2 * sqrt5));
    }

    public void fibSeq()
    {
    for (int n = 0; n < 100; ++n)
    System.out.println(fib(n));
    }


    whoops


    Sorry, the divide by 2 at the end also needs to be power of n:

    public static long fib(int n)
    {
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow(1+sqrt5, n);
    double termTwo = Math.pow(1-sqrt5, n);

    return (long)((termOne - termTwo)/(sqrt5 * Math.pow(2,n)));
    }

    Alternatively, it can be merged into termOne and termTwo:

    public static long fib(int n)
    {
    double sqrt5 = Math.sqrt(5);
    double termOne = Math.pow( (1+sqrt5)/2 , n);
    double termTwo = Math.pow( (1-sqrt5)/2 , n);

    return (long)( (termOne - termTwo) / sqrt5 );
    }

    I don't understand why others choose to endlessly bicker rather than pointing out this simple fact.
  • roman_mir@hotmail.com 2011-08-01 08:39
    Retail software package I am building uses plenty of recursion to optimize tree like data structures in memory, before they are cached and reused.
  • christianshoes 2011-08-02 22:09
    Woman High Heels are one of the most adored form of footwear ever, whether you love them of hate them, because of their such extreme variety and diversity by shpae, colour and look, they are always popular by so many women and girls.
  • Bryan 2011-08-11 10:38
    They may HAVE implemented the solution from "Wrong Answer." I was at a Code Camp recently where a speaker gave a presentation about doing EXACTLY this. He'd apparently built a library to do it.
  • Zenlogix 2011-08-16 20:26
    To the interview question: Would have said that it's cool, a recursive function. basically, it takes a string as parameter and return it unchanged if null or less then 2 characters or shuffles thing around and well could create an infinite loop. Im a PHB
  • PedanticCurmudgeon 2011-09-29 16:52
    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.

    fib n = if n < 2 then 1 else fibaux 1 1 2 n
    where fibaux x y i n =
    if i = n then y else fibaux y (x + y) (i + 1) n
    NOTE: untested as I don't have Haskell on my work machine.
  • The Lord of Cheese 2011-10-04 23:45
    they had fired the QA group for repeatedly rejecting Charles' and Terry's high quality work. Talk about firing the messenger!

    Hey! I had that happen! I was the entire QA group for UPMC ISG.

    Norman Kulinski (sp? I don't remember) is a moron project manager.
  • François DELBOUVE 2011-10-28 12:33
    The CMS eZpublish uses this kind of antipattern :
    http://doc.ez.no/schemadoc-450/tables/ezcontentclass_attribute.html

    Easier to upgrade (structure never change) ? but a nightmare for DBA and programmers...
  • Lymia 2012-09-07 13:20
    boog:
    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...
    In retrospect, I could have pointed out that if I advised him to look up recursion in the dictionary, the joke and ensuing comment thread would just repeat itself indefinitely.

    Of course, since that joke has no base case either, it too would be a poor example of recursion by his standards, so he'd have made the same comment about it, and the joke and ensuing comment thread would just repeat itself indefinitely.

    Either way, our supply of stack space would soon be spent.

    recursion n. If you don't get it already, see recursion.