- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
Yeah, I actually thought that answer was funny, the filtering we all do every day.
Admin
I take it you're American? I'm from Sweden. Our education is free, all through your life. You can study however much you want as long as you can support yourself. You only get student loans for six years though (or is it five now?, can't remember). As for the "value education enough not to make it free", you might be interested to know that (among other countries) Sweden, along with Norway, Denmark, Finland, Germany and Japan --all countries with free higher education-- in international academic comparative tests all beat America. I'm not some disgruntled European taking a shot at the US here, I'm just reacting against that old-but-still-prevalent myth that charging for education imrpves its quality, when it's all about the culture in which the education is provided.
Admin
No, it's really not, as the Swedish income tax rate is somewhere between 33% to 60% per person, right? Let's not kid ourselves; you pay either way, somehow.
Admin
I'm sorry, but if I got asked to describe the internet in a job interview, I wouldn't be interested in the job.
Admin
Which is why you should look at how hash tables work. Performance is dependent on the hash algorithm both in terms of efficiency and effectiveness, but the initial hashlookup is via an array index derived from the hash modulo table size. Collisions are then typically resolved with a linear search.
Lol, yeah, fair point. Bayesian filtering is the answer though. We typically receive about 200 to 300 spams a day caught by our stats based filter, and zero false positives. It's really incredibly effective. We catch others via rule based filters, and that catches almost all of the remaining dregs but with some false positivies. There are relatively so few though a human neural net can handle it without too much pain :)
Admin
You can thank lawyers, not the company management for the prevalance of background checks now. Kind of like diving boards -- there aren't any anymore, sadly.
Admin
So is everyone in Cuba well-educated? Would Cuba be Utopia if it weren't for the US holding them back?
Admin
Admin
Feh! You're assuming that all 24 ports must be connected. I can see how a mathematician might make such an assumption, but... (ah, yes, never miss a chance to mock a mathematician, an experimentalist, or anyone else who's not a theoretical physicist).
Anyway, if you're allowed to connect any number of ports except none at all, and the cables really are identical, and there's really exactly 24 ports (no uplink or serial port or anything odd like that), there are 25!-1 ways to do it. I don't much feel like enumerating them right now, but I can email an enumeration of them to you if you wish.
Admin
>> 5. For which kind of keys, is a hash-table faster than a binary-search tree?
>According to our teacher, and big-O theory, hash tables are always faster.
Consider for a moment the set of keys for which the hash collides on every key. Store this set of keys in the hash table, and in the binary-search tree. Which data structure is faster for the lookup?
The answer (I believe) to the original problem must be sets of keys for which the collision rate is lower than log(n)/n (note, my rate calculation may be wrong, I did it in my head, but I think that's the exact answer, but it at least is the approximate answer).
Admin
Yeah... my degree is in computer science and engineering and I have a math minor and I can honestly say I did not retain enough knowledge to answer those questions intelligently. Partly it's because I probably retained a maximum of 10% of what I learned in college, and also because in the couple of years I've been out of school, I haven't gone back to look at that stuff. I've been doing enterprise application development.
I can maybe BS my way through 2 of those questions.
On the other side of that coin, how useful is knowledge like this to most people in computers? These sound like exam questions for a graduate-level game programming course.
See you in the bar,
Ribbly
Admin
>>> 5. For which kind of keys, is a hash-table faster than a binary-search tree?
>>According to our teacher, and big-O theory, hash tables are always faster.
>Consider for a moment the set of keys for which the hash collides on every key. Store this set of keys in the hash table, and in the >binary-search tree. Which data structure is faster for the lookup?
Did I really have to specify that it required a good hash-function? Isn't that always implicit when discussing hash-tables? Since we're being jackasses here, I'll just assume that the binary search tree is extemely unbalanced and both the hash table and the binary search tree have linear performance. Happy now?
Admin
I'd say undergraduate courses, but with a focus on AI.
I too would not have gotten most of those questions, because I too am ~10 years after my schoolling. I do know that some of those I never would have got, even when I was in school. My focus was not on AI, so I did not get an introduction to A*.
I suspect that if I had made such a list when I was in school, I would have found questions that seem basic and obvious that he would not have got - because I studied a different track than he is. (Don't ask me now, I've forgotten a lot)
Admin
>>>> 5. For which kind of keys, is a hash-table faster than a binary-search tree?
>>>According to our teacher, and big-O theory, hash tables are always faster.
>>Consider for a moment the set of keys for which the hash collides on every key. Store this set of keys in the hash table, and in the >binary-search tree. Which data structure is faster for the lookup?
>Did I really have to specify that it required a good hash-function? Isn't that always implicit when discussing hash-tables? Since we're being jackasses here, I'll just assume that the binary search tree is extemely unbalanced and both the hash table and the binary search tree have linear performance. Happy now?
The original question essentially asked about what keys violate the expected performance guarantee. Those are the keys. And the result for those keys is that even if in fact the binary search tree is maximally unbalanced and the search is also linear, so is the hash table, and so it is not faster.
This is a practical flaw you can actually hit in the real world. You think you have a good hash, but later discover that you have some interesting subset of the keyspace with a high collision rate.
I guess potentially there's another answer involving small sets of keys where the linear cost of computing the hash is larger than log(n).
Admin
>On the other side of that coin, how useful is knowledge like this to most people in computers? These sound like exam questions for a graduate-level game programming course.
Indeed, except for the spam filter question, I'd have said this was clearly a list of questions for someone specialized in games/AI. I doubt if one in ten people who get a BS in CS get exposed to all of those issues in their curricula. Maybe Games & AI is right. In any case, I would not use any of these questions to interview someone for a job at my company, not a one of them would give me a useful idea of whether or not the person could do useful work for me.
Admin
I can't speak for the rest, but the fact that Germany is inn your list shows just how bad the comp tition is. Historically (I say historically because Germany has in recent years recognized that their policy does not work and is changing this for the better - but the process is not done) German education. They evaluate your progress through the years, if you are not doing well (better than average) in school by third grade they cut you off from regular education and start moving you a job focused education.
So if you are a great student, German schools are great. Probably better than any other country, because you don't have to sit around bored while the teacher tries to explain something to your less
I suspect the competition was among the best in each country. In that case it is more how the contest is structured, and luck, than which education system is better.
As for the US, Do recall that we are a big country. If North Dakota (For those who don't know, North Dakota has essentially no industry, just a agricultural area, and it is nearly a desert) was a separate country, their education system would rank as among the best in the world. However they are part of the US which also has states like Mississippi with some of the worst education in the world.
If the EU was all combined, their overall education would be worse than Sweden's.
Admin
Citing academic tests to argue the value of education is technically correct, although 'pragmatists' would argue that per capita GDP is more important to quality of life of the average citizen (not the issue you addressed, I know, but I'd argue more imporant overall in my mind):
http://www.cia.gov/cia/publications/factbook/rankorder/2004rank.html
<br>
Of course, education is only one factor in determing a nation's economic health and the US economy also benefits from a large influx of high-education immigrants.
Admin
I appreciate your skepticism, hank, but the US public educational system has some very serious flaws. A recent test run by ABC News compared students in a better-than-average NJ high school to Belgian students on a test (and NJ schools are among the top in the nation). Are there flaws? Sure, use of the metric system exclusively being one, and if the questions were from the standard international comparison test, some of the answers are technically inaccurate (particularly in civics). However, the results were startlingly different, more so than the biases inherent in the tests would suggest.
However, here's my main point: it's the free part of the educational system (i.e., public school grades 1-12) that's screwed up in America. The private university system does rather well, many other countries send their citizens to America for post-high school education, and some other countries' systems of higher education (Japan in particular) are regarded as low quality in their own country.
Admin
Well actually, many 3com switches have two ports *on the back* that allow you to connect to another hub, provided you have the special cable. So you could easily create a 48 port hub with two 24 port hubs, and since each of these hubs have two ports you can continue to add additiona hubs until your network is too laggy to function properly.
-miah
Admin
True, our tax pressure is quite outstanding. However, those taxes covers medical treatment, retirement, civic services, libraries, social securities, in all, a pervasive package of that word "wellfare" that I understand has a quite negative connotation over the pond. I read a study showing that even though Sweden has a high tax pressure, adjusted for private medical insurance etc etc, the real purchasing power of Swedes and Americans is very similar.
Admin
Of course! Clearly if he's *Cisco* certified then he couldn't possibly be expected to figure out how that alien *3Com* hub technology works!
Admin
Right on, brother.
In the interview, I'll ask some tough questions, but they would be more focused on the application of a theory, rather than a discourse on the theory itself. I expect the candidate to not know the answer, but I need to see how they react when faced with a problem they can't solve. Kind of like a Kobayashi Maru* for software engineers.
<font size="1">*ugh, I'm such a geek.</font>
Admin
Actually, I kind of like that question. Its open-ended, which means you might get an answer that didn't come straight from the "Teach yourself visual basic in 24 days" book.
My two favorite interview questions are as follows:
1. If you could be any kind of fruit, what kind of fruit would you be? (I was actually asked this once as an undergrad!)
and the all time classic Microsoft interview question
2. Why are manhole covers round?
Admin
1. Uhh. I don't want to be a fruit. I'd rather be a nut. Specifically, a Beer Nut. (And if any biologist points out that nuts are fruit, I'll smash my head against my desk. It's been that kind of day, already).
2. Okay, is this a trick question? I mean, everyone knows that they're round so they won't fall in, right? Or am I the idiot?
Ugh. TGIF and all that. Too bad I'm on call this weekend.
Admin
I have no doubt that the purchasing power is similar, I was just arguing against your use of the word "free". TANSTAAFL and all that.
Admin
Unfortunately everyone knows this already.
But, some manhole covers are not round. What are some reasons you would *not* want a round manhole cover?
Admin
Actually there are three generally accepted answers to question 2. Yours is the one usually considered correct, but other equally valid answers are 1. So the manhole covers can be moved around by rolling them, and 2. Because the manholes are round.
Admin
Mikademus -
In my original post, I also said, "... this is part of our capitalist culture - the value we give to something is bound up in what we pay for it (or invest in it)."
My point there is that this is the system that works best for us (as a society) in our capitalist culture. When things are free, we (as individuals) take them too much for granted. (And yes, that's America).
And I'm not saying that simply charging for education improves its quality; again, in my original post, I mentioned that the people who had learned the least had gotten a free education (mainly via Parental Bank and Trust), even though they went to schools that weren't free. By not having to work out a way to pay for it (loans, grants, scholarships, sweat), they lacked the incentive to value the educational process, so they learned less. And that's a cultural issue that many of us don't (or refuse to) understand - I know I sure as hell didn't understand it when I was younger.
As for culture, I personally value education enough to send my 2 youngest to private school, even though I already pay for public school through my taxes (long story short, changing the public system from within takes too long - been there, done that). They get a better education; not because it's paid for, but because a private school, being agile and non- (or at least less-) beholden to federal funds, provides a better culture for learning. Again, the administration and staff have the incentive to make it a better place because they have to work to make it (the school and their jobs) happen, rather than having it provided for them.
And Sam (aka Anonoymous) -
I agree with you on public schools. One of my older sons missed out on 4th grade math because his teacher didn't like to teach math (this was in a highly regarded school district). So he didn't. NO math for almost an entire year. Arg. Since it was "free" to the other parents, and "free" to the administration, no one (except my wife and I) saw an incentive to make change happen. But I'm not bitter. :)
Admin
Well, its like an architect. The first one to build a bridge using half an ellipse shape for stability was very smart. The 10,000 architects that just do that because the book said it would work are just good at their job. But I wouldn't call it complex when they are just utilizing the framework. But like you said, its all just terminilogy.
Given a math background as you have, might just be very usefull for CS. The important thing is, you've problely learned that when it does get to 'complex', you formalize, and you can. My pop-quizz was only a reaction to all the 'im-not-educated-but-im-a-much-better-programmer-than-those-college-morans'. They just don't know _what_ it is they don't know. Doubt is the first sign of intelligence in POV.
Admin
Have you tried fitting a square man in a round manhole?
Admin
Re: Manhole question...
The obvious answer is, "so it can't fall in the hole."
Then the interviewer is supposed to ask, "well, why don't they use an equilateral triangle cover then?"
To which you can reply, "because it won't roll," or "because they'd have to use up more steel to be large enough so people can fit down them" or some other good reason.
The classic anecdote about why Microsoft stopped asking this question is that supposedly (I've never been there), the Microsoft campus is full of those hinged rectangular utility covers and not traditional manholes, and when the interviewer asked, "why are manhole covers round?" the interviewee pointed out the window at one of the utility covers and said, "they aren't!"
Admin
1. Because you have a manhole that isn't round ...
Admin
Because it saves resources to make them square or hexagonal?
Admin
Design Pattern...You keep using that word. I do not think it means what you think it means.
Admin
Just normal 'standard' CS study. I haven't ever worked on any game. My favorite subjects are functional higher order programming (haskell, scheme, etc.) .. and I like making my own compilers and interpreters, but I actually refrained to ask questions about that, because i would be too tempted to make the questions hard because I personally find it so interesting. So I actually choose the topics based on things I don't care about.
I don't really understand why this is associated with game-programming though, except the vector question.
- Things like hash-tables are the basic datastructure of languages like python, lua, php, well even javascript.
- Parsing XML is problely the most written parser the last few years due to the whole xml hype. Almost every language now has one, and any web programmer has used one at least.
- A* is what any route-finding software would use. You have a navigator in your car right? So you've used this algorithm too!
- Constraint-satisfaction-problems are AI, I agree, you use them to solve puzzles. OR: to deal with concurrency and distributed computation. Or: to implement a type checker. Any Java/C#/Haskell type checker essentially boils down to constraint-satisfaction.
But perhaps the focus on our University is very geared towards AI and am I just assuming all this stuff applies everywhere. They make us write our own java compiler (in Haskell thankfully) in the second year :-)
I wouldn't claim that writing compilers is something you would do often in your life, but the procces itself does teach you a lot of things that I will often use. Who figured that a compiler is just one big fold anyway ? Just slightly more complicated than summing up a list of numbers.
Admin
Umm... Because an equilateral triangle could fall through the hole.
Position it near one edge of the hole, with one side of the cover exactly vertical. The width of it will then be the distance from the center of the vertical edge to the opposite corner, which is 1/sqrt(2) or about 0.7. The edge is just under 1.0 long (considering there will be a lip). Poof, triangle slides right in.
Admin
When I use the word, I refer to how to abstract away the underlying problems. In other words, the preffered method of slicing a problem into a more general one, and its constants. Like a fold is a generalization of a map. But thats my definition, whats yours' ?
Admin
Actually, all that you've proven is that the hole can be at most 70% the width of the triangle.
Admin
Argh. My trig skills are rusty. :(
Replace 1/sqrt(2) in the above with sqrt(3/4) or about 0.86.. Doesn't change my point, just the number.
Admin
86%, due to my bad math.
But if you're going to take that approach, then the hole/cover can be any shape, since it's possible to shrink the hole enough that the cover won't fit no matter what the shape is, which completely ruins the point of the original question in the first place.
Admin
Very interesting, you make a very strong point here. Eventhough its hard to believe that a poor kid will get more out of his education than a rich kid, if only it was because he was working so hard to pay for his study. I know i've always taking it all for granted, but I know I few people that need to work lots and lots just to afford to go the college, not to mention, being socially accepted.
Not that i'm opposed to capitalism, i'm only opposed to kids starting off differently, although I can not come up with any solution for that, that doesn't the scare the shit out of me when I think it.
Admin
I was always nervous about that equilateral triangle. Thanks for confirming my fears. One minor correction: "distance from the center of the vertical edge to the opposite corner" is sqrt(3) / 2 or about 0.87. Your conclusion still holds, though.
Admin
They can. Some manhole covers are, in fact, square.
http://www.g4tv.com/screensavers/features/6282/Square_Manhole_Covers_and_Crazy_Questions.html
So it was basically a bogus question to begin with, like "why did all the coelacanths die out."
Admin
Another answer I don't think I've heard is "usability."
For a round shape, all you have to do is kick the cover towards the hole until it clicks.
For almost any other shape, you have to orient the thing correctly. And those things can be heavy.
Admin
The fact that you think anecdotal evidence regarding your "friends" has any place in this discussion shows your lack of knowledge. You should be ashamed.
sincerely,
Richard Nixon
Admin
Dammit Cecil Adams beat me to it.
http://www.straightdope.com/classics/a1_247a.html
Admin
My pop-quizz was only a reaction to all the 'im-not-educated-but-im-a-much-better-programmer-than-those-college-morans'. They just don't know _what_ it is they don't know. Doubt is the first sign of intelligence in POV.
I'm self-educated, not uneducated. So it's My Turn (tm):
1. How might a Hidden Markov Model be used in statisical NLP?
2. Assuming that a surjective and and injective function exists between the Power Set P(A) and N, what can be said about P(A)?
3. How does rebuilding an index in a database effect performance, if that index contains ~1.5 billion records with 10% deletions, assuming the index is implemented as a B*Tree?
4. Elaborate on why Knuth is able to give away money for bugs found in TeX?
5. Describe how a strike angle on a worm gear effects the force of the gear.
The bummer is that I'm not educated enough to use this forum software. So perhaps I should enroll at my local trade school.
Admin
Well, i'm just in my 2nd year, and am by no means the very best student there is at my college.
A* is the -fastest- heuristic search algorithm and knowledge about it is mandatory for every one. But since no one got the question about this one right: You can use any heuristic function as long as it never under-estimatest the value. As far as I know, A* is the only place and way to use heuristic functions. They were dealed with just after depth-first-search and breadth-first search.
So ehm, its mandatory: it did cover every ones curriculum and it did in the very first year in the same class where they also explain hash-tables, arrays, binary search trees, etc. Very common knowledge. The subject was called 'data-structures' and you're not even allowed to continue if you failed that subject.
Yeah, they do. But it was not mandatory, it is still very common knowledge.
And its being used everywhere, from determing wether or not a match will continue on Wimbledon (the tennis tournament) as for your spam filter, or to detect credit card fraud. Its also the core algorithm behind most marketing-collecting-datamining. Here in Holland, the biggest super-markets had special passes that give you discount. It helps them to know what you buy, where and when. Then they analyze that information using the very same Bayesian algorithm. The end-result is that most things I want to buy are actually laying next to each other.
Excellent choice of tool, but the tool doesn't solve the problem for you. Secondly because both Ml and Scheme are strict languages, any naive approach will be very slow. You would at least need to seperate generating from testing, but more preferebly seperate the searching.
Well, the assumption here is that the keys are actually well distributed.
ML or Scheme are both strict by default, although within Scheme working with lazy evaluation is not that hard. All imperative languages seem to be strict as well. Funcional programming languages like Miranda and Haskell are lazy by default. But don't forget the best known 'lazy' language in the world: math.
I thought so. But it seems here on WTF education itself is considered a WTF by some, which kind of got me started on these little questions.
Admin
Design patterns refer to (generally, object-oriented) ways of solving problems, not ways of representing them, which was my complaint with your original post. Constraint satisfaction is a representation of the problem you are solving, but it does not say anything about how you should minimize the number of unsatisfied constraints.
Traditionally design patterns are ways to genericize software engineering problems, not math problems like you are describing here, which is probably why I objected to your usage of the term. I would have used "problem representation," as you are not "designing" anything by saying "this is a SAT problem!"
Admin
yay you win at zim! :D
"THEN I WILL SERVE FOOD WITH MY IRON FIST! And I will work my way up until i rule you all with my iron fist!"
*is wearing invader zim tee today*