Live data from Hacker News

The software development final exam: Algorithms and Data Structures

daemonology.net

151–160 of 208 posts

Re: The software development final exam: Algorithms and Data Structures

#151
post #7

While I can answer some of these questions (and could answer them all a few years ago while attending university) this kind of knowledge is simply not something that I use on a daily basis. I also doubt that many others developers use it unless they have very specialized jobs. These kind of questions should not be the only basis of the software development final exam. In software development problem solving, communic…

Yes, this is CompSci, not software engineering

It depends on the country.

My degree in Portugal was a 5 year degree with lectures from computer science and software engineering.

Re: The software development final exam: Algorithms and Data Structures

#152

I'm seeing a lot of apologists for mediocrity here. They seem to be drawn out by articles like this one as well as articles about interviewing. Despite the sentiment here, Colin is right: this is knowledge that developers ought to have. Not because they need it to do their day job, but because they can't avoid learning these topics if they truly love the field. Sure, you can earn a pretty decent paycheck hacking web…

I agree with you.

However, there is a difference between having been taught something, knowing about it, and having the information available in instant recall. For example, the B-tree question. three possible thought processes for this question (forgive me for my all-male cast):

Alan thinks, "Hmm. Well, they're both trees, but I don't really remember that difference. Maybe a BST is optimized for binary search, hence the name? This is a waste of time, I'll google it. Oh, of course, now I remember."

Bob thinks, "What!? What are trees!? Like outside? Oh no. Oh no oh no oh no. I remember what binary search is but how does it apply to a tree? Oh geez :("

Carl thinks, "A B-tree is a generalization of a BST, nodes in a B-tree can have more children than a BST"

Alan is probably a typical software developer with experience who might or might not have a degree but has been exposed to concepts. Bob is a college sophomore or someone who was never exposed to algorithms and doesn't have the background to even grapple with the question. If he googles for the answers, he'll be able to write them down but won't be able to relate them to other concepts or incorporate them into his mental model.

Carl just wrote a B-tree. Maybe Carl is a college senior, maybe a senior computer scientist at IBM.

in my opinion, you want people like both Alan and Carl. There are probably a lot more Alans than Carls. Hiring either is probably fine. There are probably a lot of Alans reading the OP, they probably won't be too upset about not knowing these off the top of their head because they know that they can refresh their memory on demand. Or maybe this is just my apology for my own mediocrity, because I had very few Carl level responses to the OP!

the problem I recognize is differentiating Alan from Bob. It's harder. If you only take the Carl responses to these questions, you'll draw only from a pool of smart people. If you start to allow Alan-level responses to be acceptable, you could also get a Bob. That would be bad.

Re: The software development final exam: Algorithms and Data Structures

#153
post #150

Earlier quoted context omitted.

I'm employed in Portugal without a (completed) CS degree, and I had more than one company to choose from. From what I could tell, the interviews were much more important than any lines on my CV.

I'm actually Portuguese, the only people I know that managed to do that, were guys and girls from my degree doing something on the side during the .com days for some startups, back in the 90's. Never saw that in the big companies, but it's been several years that I don't work there.

Well, the only "big" company I interviewed for was Sybase, but they were interested (although, I think they mentioned that my salary would be affected by that).

I chose a smaller software company, though. I much rather earn less but have a less enterprise-y work environment.

Re: The software development final exam: Algorithms and Data Structures

#154
post #134

Earlier quoted context omitted.

16 in the first 1.5 hours.

Given that you're only getting dozens of replies, why are you asking for institution? The only useful pattern I can think of would be something like correlating against university ranking, but that doesn't sound too useful.

I was thinking I'd start with a "places most of us have heard of" (Oxford, Cambridge, Harvard, MIT, Stanford, etc.) vs. "everywhere else" comparison. I'm at somewhere over 100 replies at this point, so I imagine I'll have enough data for that sort of comparison to be meaningful.

Re: The software development final exam: Algorithms and Data Structures

#156
post #129

Why do people who like to ask O(N) questions have this obsession with sorting algorithms?

Because in the 1960s, sorting records was what computers spent most of their time doing.

At this point, it's mostly a "because that's how we've always introduced algorithms and complexity" thing.

Re: The software development final exam: Algorithms and Data Structures

#158
These questions test the students' familiarity of the basic CS topics taught during the previous year. It's a test on the subject matters of the CS courses. If you don't use some of these stuff over the years, you will forget about them. I forgot the properties of the bipartite graph and have to look them up.

This reminds me of those trigonometry proofs we learnt in high school. I remember I could go through those complicate trig proofs with ease back then. Now beside some basic sine/consine stuff due to work, I completely forgot about the rest of them since there wasn't a chance to use any of them.

Basic course level knowledge are good to learn. Just the test needs to be relevant and in context.

Re: The software development final exam: Algorithms and Data Structures

#159

Earlier quoted context omitted.

from all the questions this is the one you MUST know if you want me (or anyone) to trust you with a piece of code. It takes one hour (in wikipedia!) to learn everything you'll need for a day-to-day work complexity assessment with the Big O notation. They asked us this questions on our high school final exams, I'm sure you'll manage.

> O(2^n) equal to O(3^n) Yep. So I looked into it and it seems they are not equal. Every f(n) in the set O(2^n) belongs to O(3^n). While this means that O(2^n) is a subset of O(3^n), we can see from the trival case f(n)=3^n that O(3^n) is not a subset O(2^n) since 3^n > 2^n for all n as n approaches infinity, or there is no k such that is exists an n0, such that all n > n0 implies 3^n Great. I still don't see how I a…

That's a great textbook summary, now for applications:

You got an array of your friends, an array of people who upvoted this post and an array of people who replied to this post. Filter all your friends who upvoted and replied to this post.

Now, before you write the code, how fast/slow will it run? for 1,000 friends? 1,000,000? will the runtime grow extremely fast? why?

Here's a Redis command that intersects two keys - http://redis.io/commands/sinter - the complexity is "O(N*M) worst case where N is the cardinality of the smallest set and M is the number of sets." - do you understand why? do you understand when it will be fast and when will it be slow?

Re: The software development final exam: Algorithms and Data Structures

#160
post #121

I have a CS degree from a respectable CS department. I got straight A's in my major and never crammed for a CS test. I am sure I could have answered these questions in 1997. Today, I can answer the first two questions. I think I can get partial credit on the third. I believe I knew the fourth once. I don't even remember what bipartite means [see edit below]. And that's with having implemented a topological sort withi…

Frankly, asking the question either way is what I would call prejudicial. What is a scenario in which bipartite graphs occur, and why not ask how that would be dealt with?
Post reply on HN