Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The software development final exam: Algorithms and Data Structures

daemonology.net

Post reply on HN
Print view View original

191–200 of 208 posts

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

#191

Post by shrughes »

nollidge wrote: post #104
shrughes wrote: post #81

Earlier quoted context omitted.

They're the sort of thing I use on a daily^H^H^H^H^Hfrequent basis. The questions are not asking trivia questions or looking for knowledge, they're asking questions whose answers can be figured out.

How do you "figure out" what a B-tree is? That's a trivia question.

Right, you need to know certain things. But the point of the question is not that you know what a B-tree is a have memorized a fact about the btree. The point is the followup question, which requires you to understand the consequences of using different kinds of trees. That's not the sort of thing you memorize, it's the sort of thing you internalize. If you can't answer the second question, you probably wouldn't know enough about trees to be able to casually think about certain problems you might come across in "systems programming".

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

#192

Post by shrughes »

sukuriant wrote: post #173
nollidge wrote: post #104

Earlier quoted context omitted.

How do you "figure out" what a B-tree is? That's a trivia question.

My school didn't teach B-trees, though they did teach 2-4 trees. I've never really been in a situation where I've needed to use a B-tree; and, I was an accomplished competition programmer in college. That said, I looked up on the internet what they were and it was pretty easy to follow.

It would be very cool if there was a programming contest problem that required efficient disk access.

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

#193

Post by DannyBee »

hermannj314 wrote: post #168
radagaisus wrote: post #159

Earlier quoted context omitted.

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…

I'll give this a shot. The code I would write would take longer the more friends you have. Basically, it would grow linearly with the size of all the sets and the number of intersections found. Something like O(n * M) in the worst case. But I don't get why later you say that n is the size of the smallest set. So I don't see how you can beat that. I guess you could sort the lists, but that take O(n log n) over M lists…

With extra memory, and if you don't care about ordering, multiple set intersection can be made O(N) where N = size of each set added together, assuming no duplicates in any single set (which should be true, but it depends on how loosely you are using the word set) You only have to walk each element exactly once, and all other operations are (amortized) O(1)

For each element in all sets: Insert element into hash table. If it does not exist, use key = element, value = 1. If it exists, increment counter. This is O(1)

When done over all sets, it's O(N)

Walk hash table, the only elements that are in the intersection are those with value = number of sets. This is O(N)

O(N) + O(N) = O(N). This only works if there are no duplicates within a single set. It transforms set intersection into a counting problem over the universe of elements.

You can optimize it as well. You never need to deal with elements that don't exist in the hash table after the first set is processed, as they can never be in the intersection. This does not change the asymptotic complexity, except it means the hashtable will never resize after the first set. So it's advantageous to choose the smallest set to process first if you can do so easily. If you use dynamic perfect hashing or something similar, you can also guarantee all operations after the first set will be O(1), rather than amortized O(1).

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

#194

Post by hermannj314 »

DannyBee wrote: post #193
hermannj314 wrote: post #168

Earlier quoted context omitted.

I'll give this a shot. The code I would write would take longer the more friends you have. Basically, it would grow linearly with the size of all the sets and the number of intersections found. Something like O(n * M) in the worst case. But I don't get why later you say that n is the size of the smallest set. So I don't see how you can beat that. I guess you could sort the lists, but that take O(n log n) over M lists…

With extra memory, and if you don't care about ordering, multiple set intersection can be made O(N) where N = size of each set added together, assuming no duplicates in any single set (which should be true, but it depends on how loosely you are using the word set) You only have to walk each element exactly once, and all other operations are (amortized) O(1) For each element in all sets: Insert element into hash table…

That's a very interesting solution, I would have never thought to try that.

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

#195

Post by Locke1689 »

rhizome wrote: post #160
js2 wrote: 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?

Any n-dimensional grid (sometimes called a "Manhattan space") is a bipartite graph. You may find it useful that no odd-length cycles can exist in such a graph.

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

#196

Post by sukuriant »

shrughes wrote: post #192
sukuriant wrote: post #173

Earlier quoted context omitted.

My school didn't teach B-trees, though they did teach 2-4 trees. I've never really been in a situation where I've needed to use a B-tree; and, I was an accomplished competition programmer in college. That said, I looked up on the internet what they were and it was pretty easy to follow.

It would be very cool if there was a programming contest problem that required efficient disk access.

There are some problems that require efficient reading, which is from the disk; and some that require efficient writing --- though that's more of just "buffer your outputs and don't use complex print methods, like System.out.printf"

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

#197

Post by xentronium »

DannyBee wrote: post #193
hermannj314 wrote: post #168

Earlier quoted context omitted.

I'll give this a shot. The code I would write would take longer the more friends you have. Basically, it would grow linearly with the size of all the sets and the number of intersections found. Something like O(n * M) in the worst case. But I don't get why later you say that n is the size of the smallest set. So I don't see how you can beat that. I guess you could sort the lists, but that take O(n log n) over M lists…

With extra memory, and if you don't care about ordering, multiple set intersection can be made O(N) where N = size of each set added together, assuming no duplicates in any single set (which should be true, but it depends on how loosely you are using the word set) You only have to walk each element exactly once, and all other operations are (amortized) O(1) For each element in all sets: Insert element into hash table…

That ("how would you implement ruby array intersection operator & and what computational complexity does your implementation have") was actually one of my interview warmup questions. In ruby core it's done exactly like you described, using a hash table, but I didn't know that until after the interview. I proposed a slightly worse solution, with sorting both inputs and then walking them simultaneously, which was O(n*log(n)). Still got the job, though :)

As a side note, I think that tasks like "implement a data structure with following operations and calculate computational complexity for each operation" are much better for exam than trivia questions like "Name the heap operations used by heapsort and the asymptotic running time of each.", with all due respect to @cperciva.

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

#198

Post by xentronium »

jemfinch wrote: post #167
columbo wrote: post #149

Earlier quoted context omitted.

> Call me a snob if you will, but I don't want to work with mediocre programmers > I want people with passion for our field, and those people can't avoid gaining the kind of knowledge that Colin's test asks about. Claiming to own the definition of passion is not snobbish but conceited. Perhaps I consider programmers mediocre if they lack design experience and cannot show me how to setup custom guides in illustrator.…

Your post is largely a straw man and contains snark that certainly does not raise the level of this conversation. I'm talking about passion for programming . I'm not "claiming to own the definition of passion," I'm saying that passion for programming manifests in knowing the answers to questions like Colin's. It simply does.

> contains snark that certainly does not raise the level of this conversation

Calling people that don't agree with you mediocre or apologists of mediocrity is just rude.

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

#199

Post by jobu »

cperciva wrote: post #170
jobu wrote: post #169

Earlier quoted context omitted.

I really wish the OP had linked to the explanation for the exams: http://www.daemonology.net/blog/2012-10-08-software-developm... The author believes this test is very basic, and to follow your auto mechanic metaphor it would be like asking anyone from a Midas Muffler employee to Kiichiro Toyoda the difference between disc and drum brakes. (Not that I agree with the author - to me, "basic knowledge" would be "What is…

I really wish the OP had linked to the explanation for the exams I did...

Oh, funny. I just noticed your name and realized you're the author. Sorry about that.

Your explanation is linked in the top of the test, but based on many of the comments here I don't think many people read it. It helped me put the test into perspective.

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

#200

Post by rhizome »

Locke1689 wrote: post #195
rhizome wrote: post #160

Earlier quoted context omitted.

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?

Any n-dimensional grid (sometimes called a "Manhattan space") is a bipartite graph. You may find it useful that no odd-length cycles can exist in such a graph.

What is a practical scenario for odd-length cycles in a grid?
Post reply on HN