Getting a job in software development: A Reddit discussion round-up

December 10, 2011 4:53 PM

Getting a job in software development: A Reddit discussion round-up A great round up of CS articles about getting a job in CS, then also links to info about CS concepts.

Any thoughts or additions?

posted by snow_mac (62 comments total)

Also shared on HN: http://news.ycombinator.com/item?id=3337804
posted by snow_mac at 4:54 PM on December 10, 2011

Wow, that's a lot of stuff. Unfortunately CS != software development. If I was interviewing a software developer I'd ask:

* Do you like to figure out what that f*** other developers were thinking when they wrote these crappy libraries that you have to interface with?

* Do you like to divine what upper management wants out of the product, and do you love turning on a dime when they change their mind, while playing passive-aggressive mind games?

* Will you refrain from spraying a carafe of hot coffee all over the office when you get sick of the above?

* How do you like getting paid in gum?

Congrats, you're a developer.
posted by RobotVoodooPower at 5:08 PM on December 10, 2011 [12 favorites]

Yep true "Computer Science" is as theoretical as any math or theoretical physics department, closer to math. Well it is basically a niche of math, except when it sidles over towards psychology when they try to think about user interfaces and the interaction with the real world.

I don't know any good software developer that would do something as uncreative as spraying coffee, they'd do something like recoding everyone's car door opener to open a different persons car, or trigger neighboring vehicles alarm while popping the trunks.

The software industry has always been absurdly buzzword compliant. A few months after java was first release I saw add asking for two years experience.

But if you can code and get stuff to work, you can probably get work.
posted by sammyo at 5:27 PM on December 10, 2011

If you want to learn to write software study art and writing. Then take programming classes and study some math. If you write well and can make thing beautiful you will go far
posted by humanfont at 5:33 PM on December 10, 2011 [2 favorites]

Nobody ever paid me in gum.


(thankfully)
posted by Pruitt-Igoe at 5:43 PM on December 10, 2011

If I was interviewing a software developer I'd ask:

Things like "write a function that takes an ASCII string as input, removes all occurrences of any character that is not a letter, changes all letters to lowercase, removes all occurrences of any letter that occurs an odd number of times, alphabetizes the remaining letters, and returns the result" are surprisingly effective.

Many people who make good livings as software developers simply have no idea how to do something like that, surprisingly enough. And many of those who can do something like that can essentially do whatever software development task you throw at them.
posted by Flunkie at 5:59 PM on December 10, 2011 [1 favorite]

Flunkie, I assume you mean "without using library functions"?

Bet you can't do it with a UTF-8 string...
posted by Leon at 6:24 PM on December 10, 2011

Right, let them use whatever language they want, but make it clear that while knowing library functions is great and all, you're interested in seeing them roll their own.
posted by Flunkie at 6:29 PM on December 10, 2011

Flunkie: How?! How do those people have jobs? Wouldn't they be found out in the first week of employment?
posted by JDHarper at 6:30 PM on December 10, 2011

And, of course, I mean high-level library functions, String.alphabetize for a hypothetical example. Obviously things like memcpy would be fine.
posted by Flunkie at 6:31 PM on December 10, 2011

Flunkie: How?! How do those people have jobs? Wouldn't they be found out in the first week of employment?

At large companies with large programming divisions, people can fall through the cracks and remain employed while essentially producing nothing of value. In fact, there are even people who remain employed while producing negative net value, in my opinion.
posted by Flunkie at 6:32 PM on December 10, 2011 [1 favorite]

Additions? Be male.
posted by the young rope-rider at 6:38 PM on December 10, 2011 [1 favorite]

In fact, there are even people who remain employed while producing negative net value, in my opinion.

Until recently there was a guy I worked with like that. It got to the point that I'd eyeball anything he checked in when I saw it in the hg history just so I could fix it straight away rather than it blowing up after we'd released it. (I wasn't his boss and reviewing his code wasn't part of my job, but I knew I'd be the guy doing the emergency fix).

The stunning thing is he wasn't sacked, he left after getting another job closer to where he lived.
posted by markr at 6:45 PM on December 10, 2011

Things like "write a function that takes an ASCII string as input, removes all occurrences of any character that is not a letter, changes all letters to lowercase, removes all occurrences of any letter that occurs an odd number of times, alphabetizes the remaining letters, and returns the result" are surprisingly effective.

spoilers

So, I started thinking about this, grumbling to myself at first how the restriction on use of libraries was typical of unrealistic software engineering interviews that don't reflect real life.

So, I started working through a solution. The frustrating part was that I knew blocks of letters in ASCII are consecutive, and in C/C++ you can use that guaranteed sequential ordering to transform upper to lowercase, etc. But I didn't know where 'A' and 'a' started, and I thought there might be symbols between the two sequences. "Ugh!", I thought, "another of those stupid artificial restrictions in interviews. Why can't I just look it up."

Then the solution of calculating it during run time by doing something like:

int uc_to_lc_diff = 'a' - 'A';

hit me. And I got that rush you get solving a problem/puzzle, even a small part, and realized why I love software engineering and programming again. These problems may seem artificial and unrealistic, but you're really testing candidates problem solving abilities and insight, and maybe even looking for that moment of "Eureka" and seeing if they get the joy too.
posted by formless at 7:32 PM on December 10, 2011 [5 favorites]

And formless's comment brings up another point about this testing method:

It's actually 'A' - 'a', not 'a' - 'A', but you as an interviewer should not care about things like that.

You're not interested in seeing whether they know trivia that can be looked up, and you're not interested in making sure that their solution contains no small mistakes that would be obviously detected as soon as they compiled or did a little unit testing on their code.

You're interested in trying to determine whether the candidate is capable of thinking algorithmically and (as formless says) solving puzzles.
posted by Flunkie at 7:43 PM on December 10, 2011 [3 favorites]

Developers don't like other developers code

If developers are scarce then it might be prudent in the interview to ask to see some examples of the code you will be asked to deal with - maybe 2nd or third interview. But in a buyers market I doubt it. I would actually have heaps more respect for a candidate if they did ask to see some of the code they would be working with, but that would scare them away.

Hidden in the bowels of the shit that was handed to me when I started is a 75000 (I shit you not) line method with and additional 30000 (or thereabouts) commented out section that is unfortunately the core of the major business app here.

There is a custom build fax server, a custom built XML templating class that seems to replicate XSLT - yet does not use XSLT and is as buggy as shit.

My predecessor is was a CS - and didn't seem to understand much, liked to build shit though. I should have asked but didn't. Worked with heaps of CS grads, can't say I've come across many that show a distinct advantage.
posted by the noob at 7:45 PM on December 10, 2011

And it's a good thing you're not interested in things like that, because upon actually looking it up I now see that it's 'a' - 'A', not 'A' - 'a'.

:)
posted by Flunkie at 7:45 PM on December 10, 2011

Computer Science is an academic discipline. Its canonical text was published in 1968.

Software engineering is a profession. Its canonical texts were written in the 70's and 90's.

Software development is craft. Its canonical text are whatever answers on stackoverflow gets your code to compile.
posted by gwint at 8:11 PM on December 10, 2011 [23 favorites]

What I really want is some kind of a guide that tells me what kind of software company to work for. At this point I'm pretty sure I'd have a shot at any of the large software companies (other than a few famously competitive places like Google). But I have absolutely no freaking clue what it's like to work at those companies, whether I'd be fixing bugs all day or writing interesting code, whether there are prospects for advancment or it's a 2-year deal, whether housing costs in an area completely eat up a salary difference. Software companies are just so secretive, and engineers never gossip.
posted by miyabo at 8:12 PM on December 10, 2011 [1 favorite]

I think my favorite interview moment happened the time we were looking for a new SQL developer. We asked the guy, "Suppose you have a table Foo that keeps track of which employees work at which branches. It has two fields: BranchId and EmployeeId. What SQL statement would you write to move all of the employees at branch 1234 to branch 5678?" He thought for a moment, uncapped his dry erase marker, and started writing "ALTER TABLE..."
posted by Blue Jello Elf at 8:28 PM on December 10, 2011 [2 favorites]

At one point I worked for a software company that had the following policy: If you had a bachelor's degree you could do technical support. If you had a master's degree you were allowed to maintain existing code. If you had a Ph.D. you could write new code. That experience taught me a lot, and not just about software development.
posted by LastOfHisKind at 8:49 PM on December 10, 2011

int uc_to_lc_diff = 'a' - 'A';? I wish I could take the first step to understanding such a thing.

It sounds like such a roll in the hay spewing out logical strings for a living. Understanding programming and CS and such is like having a lovely giant schlong. Most people aren't born with the equipment, and pumps just make it all spongy and obvious.
posted by gorgor_balabala at 9:33 PM on December 10, 2011

Oddly, gorgor, what humanfont said is probably more true than the idea of spewing out "logical strings" for a living.

humanfont: If you want to learn to write software study art and writing. Then take programming classes and study some math. If you write well and can make thing beautiful you will go far

Sure, if you write a lot of perl you start tossing out lines that look like gibberish, but most programming is about thinking clearly and fluidly, about saying to yourself "How can I generalize this" and "Is this an ugly way to do this?" I find my best code is aesthetically pleasing as much as it is functional. My worst code has a lot of if X then Y statements to handle edge cases or checks. Most programming languages tend to be pretty natural language after a fashion, and tends to be about saying A = B; a lot, but just in its own abbreviated syntax.

There's a story in one of the Richard Feynman autobiographies about how he would look at engineering problems like an orange, and every little addition, modification, workarounds, one-offs were like a physical addition to that orange. Good programming is like that; if you think of your finished code as a Rube Goldberg orange, you may have taken a misstep.

I really like Flunkie's interview question and clarifiers because I hate when people expect people to write perfect, compilable code on a white board; it's more important to me to see code that is thoughtful and algorithmically sound, and code that assumes garbage is coming in from ever dependent function or service. The former makes it scale and modify well, and the latter makes it run without a lot of failures and support time.
posted by hincandenza at 9:53 PM on December 10, 2011 [3 favorites]

But that's not to say I don't also have a lovely giant schlong. Because I do. Ol' Schlongy McHorsecock they used to call me, back in my college days...
posted by hincandenza at 9:53 PM on December 10, 2011

Yeah, hincandenza I think I get the less schlongy side of it. But trust me, the giggles would never stop if I walked my bugfucker into your lockerroom.
posted by gorgor_balabala at 9:59 PM on December 10, 2011

Miyabo:

> What I really want is some kind of a guide that tells me what kind of software company to work for.

I would suggest you should decide what kind of software development job interests you the most. I've had very interesting software development positions in a large bank (while other people at the same bank were doing some of the most godawful software development on the planet) and I've seen some pretty awful jobs at big companies such as Google, HP, and Apple (where all three have some great, great positions.)


> At this point I'm pretty sure I'd have a shot at any of the large software companies (other than a few famously competitive places like Google).

Yes, any competent software developer should have a shot at a position in any large software company. One question you haven't answered is "what kind of job do you want?"

Large companies are typically collections of smaller groups doing their jobs inside a larger infrastructure. These smaller groups have many different dynamics, so it's impossible to generalize for every group in a large company. There is no "Google." There is no "Apple". There is no "Facebook". There are groups inside each of these companies which are great.

> But I have absolutely no freaking clue what it's like to work at those companies, whether I'd be fixing bugs all day

yes, depending upon the group and the job assignment

>or writing interesting code

yes, depending upon the group and the job assignment

> whether there are prospects for advancement

yes, depending upon the group and the job assignment

>or it's a 2-year deal

yes, depending upon the group and the job assignment

The point of the above nonsense is that every job, and the circumstances which make the job good or bad, depend upon the group which is hiring you, why that group exists, and what the management of that group feels is important in employee relations. I know of jobs in large companies which are a grind; ugly, 24x7 pressure, rough managers. And in the same companies I know people who have been thrilled with their jobs for a very long time, finding the management great, the job interesting, and the colleagues outstanding. it all depends on group dynamics. That's part of the reason for the interview, you know; you use the interview to impress them, and to find out if they are a good fit for you.


>whether housing costs in an area completely eat up a salary difference.

That depends upon the area, and where you live in the area. For instance, in the Silicon Valley, I know engineers who choose to pay very high prices to live in San Francisco and get the cultural advantages thereof, and others who pay less to live in a more affordable more rural area but have an even longer commute. Most engineers live somewhat nearby their place of employment. In a large company, that place may be many miles from the corporate headquarters. (or in a different state or country.)

If you live in Austin Texas, costs are _significantly_ cheaper than New York City or Silicon Valley, or San Francisco.

Good luck.
posted by blob at 10:00 PM on December 10, 2011

int uc_to_lc_diff = 'a' - 'A';? I wish I could take the first step to understanding such a thing.

It would probably be easier for non-CS people to understand

int x = 'a' - 'A';

That just specifies an integer variable x as the distance between 'a' and 'A' on a chart of alphabets. On any sane chart it should be the same as the distance between 'b' and 'B', 'c' and 'C', and so on. Hence its usefulness in solving the problem Flunkie proposed.

formless named the variable uc_to_lc_diff to make the code more readable for CS people. The name makes no difference to the logic whatsoever. It's more or less a writing convention like lolspeak.
posted by fatehunter at 1:46 AM on December 11, 2011 [1 favorite]

But I have absolutely no freaking clue what it's like to work at those companies, whether I'd be fixing bugs all day

yes, depending upon the group and the job assignment

This a dozen more times. The team and group you'll work with, including the manager, make the job. Especially in a big corporation, there are huge cultural differences among the different groups / departments. Think of a large tech corporation and all the products they have, each of which may have several different groups. And it's not just the team, but things like the age of the product, whether they have resources and backing from management, etc.

int uc_to_lc_diff = 'a' - 'A';? I wish I could take the first step to understanding such a thing.

I realize this is diverging somewhat, but I'll try to give a summary to help with understanding, and hopefully along the way provide some more enlightenment about software engineering and interviews in the field.

First, Flunkie specified that the input string for his problem was ASCII, an old encoding scheme for converting characters like 'A' or 'a' into numbers. And underneath the hood, numbers are what most computers really deal with. So in ASCII, the letter 'A' is equal to 65 (I had to look it up myself). It doesn't matter whether the machine is an Apple II or a PC running Office, A = 65. That's one of the ways heterogeneous hardware and software can communicate over the Internet, they all agree on this common coding scheme (it's not always ASCII, there are other standards that support more character sets like Unicode, maybe using UTF-8 like Leon mentioned.)

So like I mentioned up thread, the letters in ASCII are consecutive. A = 65, B = 65, C = 67, etc. And similarly, a = 97, b = 98, etc. How do I know this? I just do, from working with ASCII over the years. Not everyone will, but it's one of those subtle indicators in a multi-layered interview question like Flunkies that signals the experience of the developer.

Bubbling up for a second, our original goal was to convert all characters to upper-case. How does knowing characters are consecutive help us? Well, that involves another domain-specific knowledge item, that you can perform arithmetic with characters in C-like languages. In the normal world, that seems insane. What does "B - A" even mean? But C is an old programming language that is close to the metal, so performing arithmetic on characters was natural for guys who dealt with things like ASCII codes every day. A = 65 and B = 66, so why the hell can't we subtract A from B? Most developers working nowadays may not think on that level, for good or bad*

On preview, fatehunter provides a good summary of the rest of the statement.

And remember, this is just one small part of Flunkie's problem. Just converting letters to uppercase. There are still the problems of alphabetizing, etc.

Most people aren't born with the equipment, and pumps just make it all spongy and obvious.

Like so many fields, whether it's gender studies or nuclear engineering, so much of the interview process and work itself is first understanding and communicating in a common language. In software engineering, that common language includes arcane acronyms and abbreviations like ASCII and C++. Having a giant schlong helps in some problems, but you need the experience and shared cultural understanding to solve others.

*This isn't entirely true, things like comparators in Java and operator overloading in OO actually expand on the idea of ordering of basic types and arithmetic to any data type, so in some ways modern developers may be more enlightened.
posted by formless at 2:41 AM on December 11, 2011

And it's a good thing you're not interested in things like that, because upon actually looking it up I now see that it's 'a' - 'A', not 'A' - 'a'.

Yeah, not that it matters, but I can't let this stand. Either one is fine; it doesn't matter if you get a negative number.

There are still the problems of alphabetizing, etc.

Anyone who didn't quickly end up with an integer array of letter counts rather than a string for that little problem probably isn't a C programmer.
posted by sfenders at 4:53 AM on December 11, 2011 [2 favorites]

Computer Science : Fluid Dynamics :: Programming : Team Plumbing
posted by blue_beetle at 5:38 AM on December 11, 2011 [1 favorite]

I'm over 50 and don't have a degree. But if I can get a reference and a proper interview, I generally get the programming/developing job, and I have only ever been let go once, in a mass layoff. I've been in the field since 1998.

But if I have to come in the 'front' door (applying via HR or an agency), I rarely get an interview. So my strategy now is to stay put and seek advancement within the company. I'm with a great company right now, so things are good.

I also find that too many employers are too specific in their requirements: you must be PHP + Zend, or ext.js and not YUI. In my career I've successfully learned 3 languages on-the-job (Java, C#, Object-oriented PHP) and associated frameworks, so I try to sell myself as a proven problem-solver, regardless of the toolset. Some employers buy it; many don't.

I still love to program and to solve problems, and I still think it's neat that I can get paid (reasonably well) to do this.
posted by Artful Codger at 6:59 AM on December 11, 2011

I work at a company with a thoughtful, semi-famous interview process (shameless plug: Fog Creek, NYC, we're hiring, we're nice people with big hearts and soft skin) and I've also interviewed at many of the places that have what people consider tough vetting processes, and I have to admit that I think this reddit post is kind of overkill.

A giant percentage of the people we turn down could have improved themselves by doing two things:

• Coding for fun. It's not fair that, to be at the top of your profession as a programmer, you have to do it in your spare time as well. But, really, without coding outside school or work you won't ever match the skill level of someone who does. There's just no way. As a field, software engineering is exploding right now. New languages, new technologies, new arguments, new smells. If you don't push yourself every now and then to do something that makes you feel like a five-year old trying to learn BASIC by typing code from the back of a magazine, you are dropping the ball. And it's easy to spot. It's easy to spot in way the person writes about being a coder and the way the person talks shop. People who don't code for fun are the people who take five minutes to write a function that takes a point and a rectangle and returns true iff the point is inside the rectangle. They're not dumb. They're just not confident because their only experience with a program that had rectangles and points was in class, which was an assignment they completed while hung over four hours before it was due. People who don't code for fun are the people whose favorite language is their favorite language only because that's how that class was taught. People who don't code for fun broadcast distress signals that can be picked up from miles away, and we run away as fast as we can.
• Paid more attention in intro data structures and algorithm class. Not data structures and algorithm class. Intro. There's a negligible chance you'll fail an interview because you couldn't work your way through a three-page proof about the design and properties of a data structure and algorithm that you're forced to generate on the spot. I'm sure there are great companies who want killer ninja theory people, but for each one of those there are a million other positions out there at companies that are equally great that won't ever quiz you on anything beyond an intro level. Lists, maps, sorts, strings, graphs. Basic time and space analysis. State machines, maybe. Some other stuff. The flip side is you need to know this stuff like there was a poster of it above your bed when you were five and the only way you fell asleep was staring at it. That means both depth and speed. You should be the rain man of this tiny, tiny, tiny slice of computer science. That means blowing off all your other homework because you have to finish the extra credit in your intro theory class. It's not fair. There probably aren't many professions that expect you to reach back and have a perfect memory of one 200-level class you took as a sophomore. It's not. But CS curricula aren't the real world. Most software engineering will only require you to know five out of the thirty chapters in your CS textbook; the rest of the time your employer will have no problem with Googling for the library that implements that data structure. Red-black trees? Please spend your time studying something else before you dive in. You should know binary trees. You should know balancing. You shouldn't kill yourself remembering the three-page pseudocode covering all five cases for when you deleting an element from a red-black tree. Here's an aside: we used to ask a question about AVL trees not as a way to see if the candidate was super theory hero man (we gave them a high-level algorithm and held their hand through the process) but as a way to see how well the candidate communicated, under stress, to the interviewer when given incomplete information (oh boy was there a lot of incomplete information). Back to the story at hand: I deeply deeply deeply believe if you code for fun and crack up on your intro DS&A you'll have a great head start. If I combined you with the first half of an operating systems class and the first half of a networks class, you'd be goddamn unstoppable.

posted by shadytrees at 8:48 AM on December 11, 2011 [7 favorites]

Anyone who didn't quickly end up with an integer array of letter counts rather than a string for that little problem probably isn't a C programmer.

Oh duh. Easy to do (something like) this in other languages too:

import Data.Char -- toLower
import Data.List -- sort
import Data.Map

incm Nothing = Just 1
incm (Just x) = Just $ x + 1
fillmap = foldr (\letter m -> if isLetter letter then alter incm (toLower letter) m else m) empty
output m = concatMap (\k -> let count = m ! k in if count `mod` 2 == 0 then replicate count k else "") $ sort $ keys m
flunkie = output . fillmap
posted by kenko at 2:17 PM on December 11, 2011 [1 favorite]

shadytrees: "Paid more attention in intro data structures and algorithm class. Not data structures and algorithm class. Intro."

I found out the hard way that I could winnow out more than half of the "professional, veteran" developers by asking if they knew the difference - any difference! - between a linked list and an array, with the question adapted to language if necessary. It was simply incomprehensible to me that people had been working as programmers for years without basic knowledge like this. I guess tools and IDEs make it so easy to make something that look like it works that they never had to learn.

Recruiting agencies can't help with this, because recruiters would of course not know to ask that question, or judge the answer if they did.
posted by vanar sena at 2:19 PM on December 11, 2011

Saw this on my friend's facebook feed today, and... yes, pretty much. :)
posted by hincandenza at 4:08 PM on December 11, 2011

vanar sena: one of my weeder questions is "write me a function that reverses a singly linked list given the head pointer [reference]". It's amazingly effective, albeit painful. When I do find someone good I feel bad for wasting time and insulting them. Sigh.
posted by R343L at 5:27 PM on December 11, 2011

To expand on my earlier comments. I'm a software author with 20 years experience. My view is that a major problem in the industry is a view that what we are doing is engineering; when in fact the activity is much closer to collaborative writing and design. Humans have done collaborative writing and art projects for a very long time; yet because offers programming is relegated to "engineering" the profession seems to ignore the lessons learned from the creative arts. Big writing projects have editors who check continuity and make sure that the junior copy writers adhere to the house style. In software development the unreable gibberish is allowed to pass too often just because it compiles. Programming leads should be more like creative directors at an ad agency. What would Don Draper do with the pile of shit that just got submitted?

Ultimately your purpose as a software programmer is to write and teach. You will produce code and define the interface to the code in a clear understandable syntax consistent with the hous style. You will write intelligent comments which are easily understood by others. You will spend time teaching your teammates how to use your code. You will write unit tests and code samples. You will write notes when you change your code. You will reply to emails and big reports and requirements clarification documents.

Write beautiful, usable interfaces that solve complex problems. Make them well understood by everyone in your team. See that they are used everywhere.
posted by humanfont at 5:33 PM on December 11, 2011 [2 favorites]

There is a very simple trick for uppercase/lowercase

The ASCII codes are 20h or 32 apart. All you need to do to switch from one to the other is set the appropriate bits. Lower case start at 61h and upper case start at 41h.

Flunkie's question is almost easier to do in assembly. Loop through the array of chars, set the bit to switch the case, subtract 61 and you get 0-26. Use this as an index in your array or in ASM an offset for your memory location you are storing your frequency table values. Increment the count at that location. Other bits are a no brainer. For non alpha chars just check to make sure the ASCII code is not above X. To check for an odd number of occurrences shift right and check the carry flag to see if there was a 1 in the least significant bit.

Also to reverse a linked list you can simply traverse the list and push the values onto a stack then pop them off.

You can also write a recursive method to traverse to the end, then do whatever you want with the values as the recursion unwinds. That is using a stack as well though :)
posted by Ad hominem at 6:47 PM on December 11, 2011

Oh BTW, UTF8 preserved the original codes from ASCII for Latin characters so my solution works for UTF8 as well.
posted by Ad hominem at 6:52 PM on December 11, 2011

kenko: no need for post-construction lookups. Also, enumerated imports and untyped top level definitions make baby lambdas cry. :-)

import Data.Char (toLower, isLetter)
import Data.List (sort)
import Data.Map (Map, empty, fromList, toList, alter)

incm Nothing = Just 1
incm (Just x) = Just $ x + 1

fillmap :: [Char] -> Map Char Int
fillmap = foldr (\letter m -> if isLetter letter then alter incm (toLower letter) m else m) empty

output :: Map Char Int -> [Char]
output = concatMap (\(k,c) -> if even c then replicate c k else "") . sort . toList
where even = (== 0) . flip mod 2

flunkie :: [Char] -> [Char]
flunkie = output . fillmap
posted by cytherea at 5:24 AM on December 12, 2011 [1 favorite]

I just ran into this today by coincidence.

Personally, I think this exercise would be a lot more revealing if it dropped the restriction that the input string was in ASCII; the interviewer could then see whether the candidate just blindly went ahead and assumed ASCII / UTF-8.
posted by whir at 8:16 AM on December 12, 2011

Also to reverse a linked list you can simply traverse the list and push the values onto a stack then pop them off.

This solution works but isn't efficient in terms of memory usage or execution time. You have to duplicate the entire contents of the list in the stack and you have O(2n) runtime, as you have to traverse the list and then empty the stack.

It's possible to do this operation by iterating once through the list, swapping pointers around as you go. This gives O(n) runtime and all you have to allocate is some temp variables to serve as pointers to the previous node, the current node, and the next node.
posted by Sauce Trough at 10:31 AM on December 12, 2011

Ahh but he never asked for the most effient way.

The "this is a programming interview" way to do an in place reversal of a singly linked list is to traverse the list and swap the pointers to point backwards.
posted by Ad hominem at 10:44 AM on December 12, 2011

Doh, you already said that.
posted by Ad hominem at 10:45 AM on December 12, 2011

Right, let them use whatever language they want, but make it clear that while knowing library functions is great and all, you're interested in seeing them roll their own.

On the other hand, if I gave your question to a candidate and they didn't immediately hit the obvious solution using library functions and regexes, that'd be a strong disinclination to hire there.

There are lots of people out there who will reimplement things to cover for their lack of knowledge of their programming environment, and that's an antipattern.

Consider the example of Area Number Three on Steve Yegge's Five Essential Phone Screen Questions
posted by Sauce Trough at 10:45 AM on December 12, 2011

Ahh but he never asked for the most effient way.

In all the interviews I've done lately, efficiency is an implied requirement.
posted by Sauce Trough at 10:50 AM on December 12, 2011

This discussion demonstrates my point. We have lots of people trying to figure out the most efficient and compact way to write the function. Yet almost nothing on the interface, exceptions / error conditions or defining a semantically meaningful name.

Do we really want a flunkie class, method or function name? Should we extend an existing utility library? How will this code interact with the overall system? Do we call this as a static method or do we anticipate a larger class?
posted by humanfont at 10:56 AM on December 12, 2011

Well the real point of the interview is that you know the trick. How many candidates are going to know what a linked list is, know what pointers are and know how to manipulate them, not know how to do an in place reversal and hit on it right there in the interview.

Likewise how many people are going to figure out that upper and lower case ASCII codes are 20h apart.

I am on the fence about all this. If, in the real world, someone was hand crafting a in place reversal instead of using list.reverse() that would be a problem unless there was a compelling reason to do so.

This discussion demonstrates my point. We have lots of people trying to figure out the most efficient and compact way to write the function. Yet almost nothing on the interface, exceptions / error conditions or defining a semantically meaningful name.

We are discussing an interview situation. In that context, unless specified, you are entirely justified in delivering the cleverest solution.
posted by Ad hominem at 11:01 AM on December 12, 2011

This discussion demonstrates my point. We have lots of people trying to figure out the most efficient and compact way to write the function. Yet almost nothing on the interface, exceptions / error conditions or defining a semantically meaningful name.

You're mistaking our discussion for a complete response to an interview question.

Whenever I have to answer an interview question I run this sequence:

1. What's the story?
2. What should happen for various edge / exception cases -- null input, empty input, infinite input, etc?
3. What are the test cases?
4. What's the implementation?

I write the test cases before I write the implementation, which should demonstrate that the interface is well-chosen. If the interviewer prompts me to move directly to the implementation, I do so, but that's a clue that the interviewer and I don't see eye-to-eye on some things.
posted by Sauce Trough at 11:09 AM on December 12, 2011 [1 favorite]

How many candidates are going to know what a linked list is, know what pointers are and know how to manipulate them, not know how to do an in place reversal and hit on it right there in the interview.

I swear this exact thing happened to me in an interview once. I hit on the stack thing first off, but then the guy wanted to know if I saw anything suboptimal about that. After I figured out its deficiencies I managed to hit on the optimal solution in about ten minutes after that.
posted by Sauce Trough at 11:15 AM on December 12, 2011

That is interesting, I'm not sure I would figure it out, especially during an interview.

I always wanted to just bullshit with people I was interviewing, I ended up with great guys who couldn't program. I started bringing in one of my contractors, management got him by calling up a outsourcing firm and asking for their most expensive guy, he had been kicking around doing HFT development. God knows what the guy was charging but he had a house in Miami as well as New York and flew back and forth every weekend.

We started interviewing people and he was asking questions like what gets pushed onto the stack during stdcall vs fastcall, what happens to various registers, SP and IP. I know a bit about x86 assembly but there is no way I would have been prepared for those questions.

We were looking for a guy to do HTML and asp.net. These poor people didn't even know what the questions meant let alone the answers. His position was that if they were claiming to have a degree in CS they should know x86 calling conventions.

I think if I had to go through a really rigorous interview process I would never get a job.
posted by Ad hominem at 11:40 AM on December 12, 2011

Cytherea: thanks, I'm pretty much a n00b in Haskell, and it didn't occur to me to convert the map to a list (though I was more interested in doing that to make output more easily points-free-able than for efficiency reasons, ha).

I did go back because I thought an actual array would be nicer than a map, even though destructive updates in Haskell feel like cheating to me:

import Data.Array.Unboxed (assocs)
import Data.Char (isLetter,toLower)
import Data.Array.ST (readArray,writeArray,newArray,runSTUArray)

output = concatMap (\(l,c) -> if c `mod` 2 == 0 then replicate c l else []) . assocs
updateArray a k op = readArray a k >>= writeArray a k . op
flunkie s = output $ runSTUArray $ do
a <- newArray ('a','z') 0
mapM_ (\l -> if isLetter l then updateArray a (toLower l) (+1) else return ()) s
return a
posted by kenko at 12:04 PM on December 12, 2011

kenko: Pretty good stuff for a "noob", you deserve a great big pat on the back!

Actually, I preferred your first version much more: simplicity and clarity are much more important than efficiency: there's going to be maybe 1% of your application that will actually ever need any serious optimization, and the profiler is awfully good at pointing that out (and most of the time, this will involve a few key strictness annotations (mostly on data structures) to avoid building up enormous thunks which are only evaluated at the very end, and perhaps some manual inner loop fusion.) Note that Warp achieves its enormous speed (blowing away Node.js and every other web-server on the planet) with purely functional data structures: iteratrees and enumerators)

Moreover, while it intuitively seems tempting to go for destructive updates for speed, your results in practice will be quite different: by going with purely functional data structures, you are giving the compiler the opportunity to do its magic juggling and optimization (which you would deny it by explicit sequencing and/or performing destructive updates). GHC has a seriously fast, industrial strength garbage collector. Further, you're only replacing small parts of the Map at any one time (not the whole thing--an issue that troubles haskell arrays).

In fact, I'd prefer to unfuse the loop in fillmap, rewriting

fillmap :: [Char] -> Map Char Int
fillmap = foldr (\letter m -> if isLetter letter then alter incm (toLower letter) m else m) empty

as the simpler

fillmap = foldr (\l m -> alter incm (toLower l) m) empty . filter isLetter

But (you might protest)! But now we have to traverse the list twice! Actually, no: 1) since haskell is lazy, it only evaluates as much of filter isLetter as is consumed by the fold, and 2) haskell is smart enough to know that map f . map g === map (f . g) and will automatically fuse your composed loops for you, and I'd venture it should be able to recognize that foldr f z . filter p === foldr (\x a -> if p x then f x a else a) z. If not, you could tell it so with the RULES pragma.

But composition is what we really care most about. So always go for a compositional solution, and worry about making the 1% fast later.

When haskell isn't smart enough to fuse your loops for you, rather than opt for destructive updates, you'll want to take advantage of some of the new libraries which aggressively fuse loops, such as Data.Vector (1-d arrays, boxed and unboxed, and quite apt in this case), Data.ByteString (even more apt in this case?), and Data.Repa (regular, multi-dimension, shape-polymorphic, parallel, unboxed arrays, and the answer to many of haskell's array woes).

Note that all of these are ready-to-wear offshoots of the holy grail: Nested Data Parallelism, which is in GHC's case, dph or Data-Parallel Haskell. Which will be ready for prime time with the next release of GHC, 7.4. But you can already play with a pretty stable, pretty fast implementation for SMP in 7.2.

Haskell, more than just about any other language, has a never-ending learning curve--it's the language drug that will keep you addicted for life. And I'm so glad to see someone on metafilter using my favorite language! It smells like victory in the next half century is at hand! Enjoy!
posted by cytherea at 6:34 PM on December 12, 2011 [3 favorites]

Actually, let's go further and rewrite

output :: Map Char Int -> [Char]
output = concatMap (\(k,c) -> if even c then replicate c k else "") . sort . toList
  where even = (== 0) . flip mod 2

as

output :: Map Char Int -> [Char]
output = concatMap (uncurry $ flip replicate) . filter (even . snd) . toList
  where even = (== 0) . flip mod 2

Since 1) we've already sorted our data (by virtue of building the Map) (and quicksorting a second time is Very Bad), and 2) we're now purely compositional.
posted by cytherea at 7:04 PM on December 12, 2011 [1 favorite]

Oh, just realized. We can further rewrite fillmap as:

fillmap :: [Char] -> Map Char Int
fillmap = foldr (alter incm) empty . map toLower . filter isLetter

In fact, why stop there?

flunkie :: String -> String
flunkie = concat
            . map (uncurry $ flip replicate)
            . filter (even . snd)
            . toList
            . foldr (alter incm) empty
            . map toLower
            . filter isLetter
    where even = (== 0) . flip mod 2
              incm = Just . maybe (+1) 1

That's pretty. And purely compositional (with no free variables)--ideal Haskell code. Should be immediately clear to even a non-programmer what is going on. By changing our imports, we should be able to take advantage of the aggressive list-fusion libraries without changing our code (Let's leave it up to the compiler to fuse our loops for us). And if we need to alter the behavior due to a change in spec, it should only involve inserting and/or removing a step in the composition. And it has a nice mapping to the English expression of the algorithm. And it's lazy (using foldr instead of foldl)--we could give it an infinite sequence, and just take a finite initial sequence Ok. Done now, with the haskell golf game. Eeep!
posted by cytherea at 8:59 PM on December 12, 2011 [2 favorites]

eep. for those following, typo: incm should be: incm = Just . maybe 1 (+1)
eep.
posted by cytherea at 10:08 PM on December 12, 2011

You're hired!
posted by whir at 5:25 PM on December 13, 2011

Since 1) we've already sorted our data (by virtue of building the Map)

Really, will toList produce a list with keys in sorted order? I didn't know that.

I had hit on the "uncurry . flip replicate" thing, but wanted to avoid the separate filter call—good to know that kind of thing isn't really necessary.

The final version is super sweet! I keep forgetting about functions like maybe and either.
posted by kenko at 7:48 PM on December 13, 2011

The funny thing about reading all these responses is that the intent of comment about my "filter" question and how often candidates fail wasn't to elicit solutions. It's such a basic question that anyone in the field who is at all competent can do it (and most likely in five minutes or less). It's not intended as a good question for design or naming. Obviously in practice we use standard libraries that provide many good collection types.

But you have to know how they work. This question weeds out people who don't even know how a very fundamental data structure works. It's a proxy for other things and tells me if it's worth actually moving onto something remotely challenging. Challenging means a problem that requires clean design. Or requires knowing how to select good data structures for efficiency. Or requires improving incrementally to get to a good solution. Or challenging at a higher level because I intentionally asked the question a little vague to see how you handle ambiguity and how you ask questions.

TL;DR: Being able to code up "reverse a singly linked list" tells me very little about whether you'll do well on the rest of the interview. Not being able to is, however, very informative.

(But, yes, to talk about solutions: if you can't code up the in-place solution (I'll even prompt you to improve on your stack solution!), it will be hard for you to do well on the rest of the interview. Iterating thru a list and copying some pointers around is not that hard.)
posted by R343L at 11:30 PM on December 14, 2011

kenko: Well, there are different kinds of Maps. Too often, with silly languages, they conflate hash lookups with other kinds of maps. (The difference is that things that can be put into a hashed map have a function which returns a hash value, nominally an int, but all a Tree cares about is less than and equals). The ways of mapping are endless. But, in Haskell, Data.Map happens to be implemented via a particular balanced binary Tree. Still, in general, you can be pretty safe in assuming that turning a map/dictionary into a list is going to give you pairs ordered by the keys. In the same vein, it's easier to turn a list into a set than to strip out duplicate list elements. Fun fact: in haskell head . sort xs == same O as minimum xs in a non-lazy language.

so, yes: Data.Map.toList on a Map String x is going to be in alphabetical order.

Heh. Well, I think maybe was the first function I wrote in Java at my current Java/Python oriented company. Outside of id and either and fold and map, it's just about the best function ever. What function would you take to a deserted island? I don't think lambda counts. But I thank you for reminding me about alter--it's a much more elegant way to make Maps than the usual insertWith things I write by default.
posted by cytherea at 10:49 PM on December 16, 2011

Actually, what's funny is that fold (reduce), the most basic component of category theory--transferring a structure from one domain to another--is considered evil, bad, too abstract by the python people, yet is the most basic building block of Haskell. Weird, huh?
posted by cytherea at 10:56 PM on December 16, 2011

Thanks for posting that stuff, I'm gradually trying to learn me a Haskell although it's a low-priority background task.

As another hint for all the would-be writers of software out there, here's a C version after running it on its own source code: aaaaccccccccccccmmnnnnnnnnpppppppprrrrrrrrrrrrrrrruuww

And cytherea's latest: aaaaaacccccceeeeeeeeeeeeeeeeeeggkklllllllllllloooooopppppprrrrrrrrrrrrssssssttttttttttttttvvww

So you can see, even with an extremely verbose "memset(letters, 0x00, sizeof(letters));" in there, C is a more concise language, and has more 'c's in it.
posted by sfenders at 4:03 AM on December 17, 2011