The Joys Of Programming

boogle wrote:

Used recursion at work.
Feels good man.

The coding test I used to give to interview candidates was most elegantly solvable via recursion. Anyone who actually went that route was a must hire.

bandit0013 wrote:
boogle wrote:

Used recursion at work.
Feels good man.

The coding test I used to give to interview candidates was most elegantly solvable via recursion. Anyone who actually went that route was a must hire.

What was the test, if you don't mind me asking.

I've asked basic recursion questions like Fibonacci and am amazed at how bad people are at solving them.

SixteenBlue wrote:

I guess, in theory, that's what internships during undergrad are for. Learn theory in class and real world in your internship. But since they're optional that can leave a lot of grads without that experience.

Like me, for example.

I dropped out of CS and went to MIS because I (correctly) assumed that learning the language of business with a career goal as a business developer would be more valuable than CS theory. CS at my school mixed in a hefty does of EE, which while interesting isn't even slightly valuable to day to day duties in corporate IT.

SixteenBlue wrote:
bandit0013 wrote:
boogle wrote:

Used recursion at work.
Feels good man.

The coding test I used to give to interview candidates was most elegantly solvable via recursion. Anyone who actually went that route was a must hire.

What was the test, if you don't mind me asking.

I've asked basic recursion questions like Fibonacci and am amazed at how bad people are at solving them.

I had 4 data structures:

Customer
Payment
InvoicePayment
Invoice

They were tasked with creating a procedure that was able to create a new payment record for a customer and then continue paying in the oldest unpaid invoice until they ran out of money or ran out of invoices. Whatever they chose to implement for "apply payments" was definitely ready for recursion.

SixteenBlue wrote:
bandit0013 wrote:
boogle wrote:

Used recursion at work.
Feels good man.

The coding test I used to give to interview candidates was most elegantly solvable via recursion. Anyone who actually went that route was a must hire.

What was the test, if you don't mind me asking.

I've asked basic recursion questions like Fibonacci and am amazed at how bad people are at solving them.

We actually hired a guy recently who I thought bombed my Fibonacci question (I got to sit in on an interview after 2 weeks on the job). We thought he didn't really understand recursion, even though the code worked and produced the correct output. Turned out to be a blend of recursion/iteration, and was very fast. I modified it a bit to use System.Numerics.BigInteger, and like my favorite Python implementation, it neither causes a stack overflow, nor takes forever to calculate anything over fib(40).

public BigInteger GetFib(int n) { if (n < 0) return -1; if (0 == n) return 0; return Fib(0, 1, 1, n); } private BigInteger Fib(BigInteger first, BigInteger second, int currentIndex, int targetIndex) { if (currentIndex == targetIndex) return second; BigInteger third = first + second; return Fib(second, third, currentIndex + 1, targetIndex); }
complexmath wrote:

Yup. And to be fair, things like the impact of multi-level storage on algorithms is taught at the theoretical level. Just not to undergrads.

>_> It was taught to undergrads at Carnegie Mellon when I was a student here. (Don't see why it shouldn't be taught to all CS undergrads everywhere. ;>)

That solution is effectively iterative. It uses tail recursion so the stack should never grow in most languages.

That's a loop via tail-call recursion. A language implementation that handles things right can do really good things with that sort of loop, because there are no mutations of variables (which allows certain code analysis techniques to work better).

Edit: Damn. complexmathhausered

Tail recursion is something I just learned about in the Scala/Functional class on coursera. Learning new things is awesome.

Regarding the Fib problem in general: I'm open to any reasonable solution, typical recursion is just the simple/obvious answer. Generally if someone is going to make it more complicated or less intuitive I'd like for them to start with saying what the obvious solution is and why they're deviating.

complexmath wrote:

That solution is effectively iterative. It uses tail recursion so the stack should never grow in most languages.

I don't know that the set of languages that support tail call elimination is even close to "most languages", or even "most of the most common languages".

Although, up until a few moments ago, I thought that C#, which presumably the sample code is, didn't support it either. Apparently, MS added tail call elimination to the CLR, presumably when they added F#.

Also, I think it might help to be explicit, since at least I don't totally grok tail calls, here is what I think the equivalent loop would be

private BigInteger Fib(BigInteger first, BigInteger second, int currentIndex, int targetIndex) { while(currentIndex < targetIndex) { BigInteger third = first + second; first = second; second = third; currentIndex += 1; } return second; }

My own personal version for C# was:

public static BigInteger Iterative(Int32 n) { if (n <= 0) return 0; if (1 == n) return 1; BigInteger a = 1; BigInteger b = 1; for (int i = 0; i < n - 2; i++) { BigInteger temp = a + b; a = b; b = temp; } return b; }

or in Python:

def fib(n): a, b = 1, 1 for x in range(n-2): a, b = b, a+b return b;

I've also got recursive and iterative versions that cache results in case you're calling it in a loop (or just calling it period in the recursive case).

Hypatian wrote:
complexmath wrote:

Yup. And to be fair, things like the impact of multi-level storage on algorithms is taught at the theoretical level. Just not to undergrads.

>_> It was taught to undergrads at Carnegie Mellon when I was a student here. (Don't see why it shouldn't be taught to all CS undergrads everywhere. ;>)

If we're talking the same thing, it was taught at my Liberal Arts college too.

here's a short list of every language which can do tail call recursion:
functional languages (mostly cause I think that's where it was invented).

And yet no one's Fibonacci solution has included memoization? Not sure about you guys, but I'm fine with trading a miniscule amount of memory consumption for O(1) lookups... EDIT: I scanned Bonus' code and missed his blurb at the end. Gold star to you, sir.

I haven't had any opportunity to apply recursion to anything nifty in quite a while, but I did get to mock my boss (PhD in CS, focus on Java internals) about two months into my job when I discovered recursive code he had given a green light in code review without realizing it would overflow the stack.

I've been thinking a lot lately about the benefits to be gained by having the software profession go to a guild system. With companies up in arms about the constant talent shortage but being unwilling to hire, train, and retain junior people as well as universities not really doing a good job of providing job ready skills... maybe a guild system is the answer...

Start one and send me an invite

RolandofGilead wrote:
Hypatian wrote:
complexmath wrote:

Yup. And to be fair, things like the impact of multi-level storage on algorithms is taught at the theoretical level. Just not to undergrads.

>_> It was taught to undergrads at Carnegie Mellon when I was a student here. (Don't see why it shouldn't be taught to all CS undergrads everywhere. ;>)

If we're talking the same thing, it was taught at my Liberal Arts college too.

here's a short list of every language which can do tail call recursion:
functional languages (mostly cause I think that's where it was invented).

Don't forget about Perl!

bandit0013 wrote:

I've been thinking a lot lately about the benefits to be gained by having the software profession go to a guild system. With companies up in arms about the constant talent shortage but being unwilling to hire, train, and retain junior people as well as universities not really doing a good job of providing job ready skills... maybe a guild system is the answer...

This applies to System Administrators (at least on the Unix side) even more heavily.

I'm not sure employers will be behind it at first; a guild sounds too much like a union, and no one likes a union.

I'm also not sure the majority of the target audience will be behind it. For some reason, we seem (as a whole) to be strangely proud of our lack of a union. I have been guilty of this myself at times. I think there is also a stigma against the idea of a guild, because it means we are in a 'tradeskill'. 'Tradeskills' are for people who do manual labor because they weren't smart enough to go to college (or so the stigma goes). Both of those hurdles need solutions I think, especially the latter, before the idea could really take off.

absurddoctor wrote:
bandit0013 wrote:

I've been thinking a lot lately about the benefits to be gained by having the software profession go to a guild system. With companies up in arms about the constant talent shortage but being unwilling to hire, train, and retain junior people as well as universities not really doing a good job of providing job ready skills... maybe a guild system is the answer...

This applies to System Administrators (at least on the Unix side) even more heavily.

I'm not sure employers will be behind it at first; a guild sounds too much like a union, and no one likes a union.

I'm also not sure the majority of the target audience will be behind it. For some reason, we seem (as a whole) to be strangely proud of our lack of a union. I have been guilty of this myself at times. I think there is also a stigma against the idea of a guild, because it means we are in a 'tradeskill'. 'Tradeskills' are for people who do manual labor because they weren't smart enough to go to college (or so the stigma goes). Both of those hurdles need solutions I think, especially the latter, before the idea could really take off.

Guild != Union. Most developers would not be interested in a union style system because we desire a meritocracy.

I see a few problems in the industry that a guild style organization could really address:

Employer Side
There is a relatively constant "talent shortage". To employers, this means they can't locate workers that they can just plug and play into skilled positions. University/CS classes aren't designed to do this. So regardless of the perception of a "tradeskill", that is really what employers want. They have skilled labor that needs to be done, and given that for most positions a CS degree isn't required, only encouraged and they are more concerned with what you can do, like it or not we fall into a tradeskill category in reality.

Employers also have a hell of a time identifying qualified talent. Being that what we do is a mixture of creative thinking and logical/scientific construct it is exceptionally difficult for a non technical person to vet the quality of potential craftspeople. Even reasonably technical people have difficulty separating the good from the bad. The certification system in our field is easily gamed since it pretty much uses multiple choice test questions which get published and brain dumped, besides that just because you know the command syntax to do something doesn't have anything to do with your ability to recognize when it is appropriate to use. The guild style system of being vetted by your peers would serve the dual purpose of pushing great talent up the ranks quickly while also preventing mediocre (or worse) talent from receiving tenure base title increases that can be used to deceive employers as to their value.

It's getting better, slowly, but many employers also have a fundamental misunderstanding of how to apply good software processes and maximize productivity of knowledge workers. Having an organization that could collect data and case studies to assist employers with applying good practices would be an excellent value-add. Additionally the guild could provide subsidized training for all its members. Imagine a company having an organization available to them where they could send employees to actually take a half day / full day class on something at little to no cost to them.

So on the employer side better access to better vetted candidates and an organization that will provide the training and mentoring to assist getting talent experience in on-demand skills. A guild would have much more agility in teaching new software practices and techniques than a college would.

Employee Side
Now you have a group of real, actual peers that you can go to for mentoring and growth. We can take the time and effort that it takes to actually really certify someone in a skill set so that employers can hire with more confidence and at a lower rate. Fun fact is that most recruiting firms charge more than 20% of the first year's salary for a full time placement. A guild could place people at a much lower rate, with a higher confidence, and use that rate for operations such as the mentoring and classes I mentioned. If the guild got big enough, it could even start taking part in lobbying activities. Does anyone really think it's reasonable that companies can make you work 80 hours a week for 40 hours of pay? One thing that unions generally get right is that you have to be compensated for excessive overtime (especially in our field where fatigue drastically lowers quality and increases risk, it's nonsensical)

IT workers are often terrible, awful negotiators for the most part and there is a ton of variance in wage. I don't propose that we go to a union based tenure salary band, but I do propose that the guild openly publish data on positions and experience and what the total comp actually is (since the guild could be placing people, we would have that data on total comp, new members could verify existing comp by bringing in some paystubs). There are many salary surveys that float around but most of them are viewed with distrust since they are voluntary surveys and people (rightly) feel that the reports are inflated. By collecting and verifying real data we could provide our members (and employers) with a better negotiating position. You know how you see that women make 85 cents on the dollar compared to men in the same job? Transparency of pay would do a lot to eliminate that. I would also hope that having a guild with reliable trainers would help reduce some of the misogyny that is present in the field as well, giving women a place to develop their skills without having to deal with some of the crap we all know they do.

A guild could also reach arrangements with employers and universities to provide shadowing and apprenticeship for junior members. It doesn't even have to cost the employer anything since potentially you could pay apprentices out of the guild funds. All the employer would have to do is grant permission for a guild member on their staff to allow the apprentice to shadow / pair program with them. They get an extra set of eyes on the problem and yet another path to identify up and coming talent. The apprentice gets real world job experience from a real world developer... everyone wins.

I got to use it to implement some hierarchical clustering.
I really do like my job.

Tail call elimination is really a QOI issue for the compiler rather than something intrinsic to the language. It's just kind of required for functional languages since they generally don't have a loop construct.

But I agree that theory is very important. For example, I know a talented programmer with no formal background in the field and he's told me stories of how he's invented a cool solution to some problem only to discover later that it was an established algorithm.

If he independently came up with an algorithm that's in broad use, he's probably quite good.

Malor wrote:
But I agree that theory is very important. For example, I know a talented programmer with no formal background in the field and he's told me stories of how he's invented a cool solution to some problem only to discover later that it was an established algorithm.

If he independently came up with an algorithm that's in broad use, he's probably quite good.

Honestly I'll take the person that doesn't re-invent the wheel every time.

Using other people's wheels is easy; building new wheels is hard. Knowledge is easy to acquire. Talent is not.

Malor wrote:

Using other people's wheels is easy; building new wheels is hard. Knowledge is easy to acquire. Talent is not.

I consider the ability to know what tools already exist and when to use them to be an extremely important talent. I think lacking that talent is a much bigger deficit than lacking the talent to build those tools in the first place. My goal, for hiring purposes, isn't to revolutionize computer science, it's to build quality software quickly.

SixteenBlue wrote:
Malor wrote:

Using other people's wheels is easy; building new wheels is hard. Knowledge is easy to acquire. Talent is not.

I consider the ability to know what tools already exist and when to use them to be an extremely important talent. I think lacking that talent is a much bigger deficit than lacking the talent to build those tools in the first place. My goal, for hiring purposes, isn't to revolutionize computer science, it's to build quality software quickly.

While I see where your coming from and agree that knowing what tools already exist and when to use them is an important talent, I don't agree that it is more important than talent alone. If a programmer writes crappy software and use existing tools to do it, you still have crappy software. If a programmer writes good software but re-invented the wheel, you still have good software.

EDIT: And the good programmer that doesn't know CS theory can always be encouraged to learn CS theory. Sometimes crappy programmers are just not good at programming.

kazar wrote:
SixteenBlue wrote:
Malor wrote:

Using other people's wheels is easy; building new wheels is hard. Knowledge is easy to acquire. Talent is not.

I consider the ability to know what tools already exist and when to use them to be an extremely important talent. I think lacking that talent is a much bigger deficit than lacking the talent to build those tools in the first place. My goal, for hiring purposes, isn't to revolutionize computer science, it's to build quality software quickly.

While I see where your coming from and agree that knowing what tools already exist and when to use them is an important talent, I don't agree that it is more important than talent alone. If a programmer writes crappy software and use existing tools to do it, you still have crappy software. If a programmer writes good software but re-invented the wheel, you still have good software.

EDIT: And the good programmer that doesn't know CS theory can always be encouraged to learn CS theory. Sometimes crappy programmers are just not good at programming.

Sure, there are definitely multiple traits I'd look for in a potential hire. I just meant if all other things are equal, I'm taking the person who leverages existing solutions over the person who rolls their own.

Of course there are times when rolling your own is the best answer, but the person who always does it is not really in a good position to explain why.

One of the biggest traits I've observed that tend to indicate someone will be successful as a programmer that isn't obvious:

Excellent short term memory. The ability to keep local variables, etc in your head without having to "jump" through code really cranks up efficiency.

SixteenBlue wrote:

Sure, there are definitely multiple traits I'd look for in a potential hire. I just meant if all other things are equal, I'm taking the person who leverages existing solutions over the person who rolls their own.

Of course there are times when rolling your own is the best answer, but the person who always does it is not really in a good position to explain why.

A person that rolls his own solution will have a better understanding of how things work. The industry is flooded with people that just know frameworks but have absolutely no clue how those frameworks work. I am a firm believer that people should know how to do things from first principles.

While in the end, leverageing existing solutions has huge advantages such as the code being well tested and the time saved in development. So I am not advocating that a person should roll their own, but I would rather have someone who would normally roll their own and teach them how to leverage existing solutions vs the other way around.

kazar wrote:
SixteenBlue wrote:

Sure, there are definitely multiple traits I'd look for in a potential hire. I just meant if all other things are equal, I'm taking the person who leverages existing solutions over the person who rolls their own.

Of course there are times when rolling your own is the best answer, but the person who always does it is not really in a good position to explain why.

A person that rolls his own solution will have a better understanding of how things work. The industry is flooded with people that just know frameworks but have absolutely no clue how those frameworks work. I am a firm believer that people should know how to do things from first principles.

While in the end, leverageing existing solutions has huge advantages such as the code being well tested and the time saved in development. So I am not advocating that a person should roll their own, but I would rather have someone who would normally roll their own and teach them how to leverage existing solutions vs the other way around.

I like that attitude, yet I constantly come across programmers who have absolutely no interest in understanding relational databases even though 90% of the time that's where the performance problems are because they didn't care and treated it like a flat file store.

I made a tip calculator. It's pretty basic but as I learn stuff, I'll be expanding it. It's not that big of a deal, but to me it is.