Comment On Three for Three, Recursion Threads, and Wrong Answer

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

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.

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?

http://ideone.com/tLLki

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

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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.

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

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?

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]

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

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#

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

s/this is now how you develop software/this is *NOT* how you develop software

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.

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;

}

The real WTF: Calling that Java method a function on a senior Java developer test.

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

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>

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.

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

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.

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

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.

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.

Retail software package I am building uses plenty of recursion to optimize tree like data structures in memory, before they are cached and reused.

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.

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.

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

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.

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.

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

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.