|
I was implementing sorting algorithms in uni only last year, and I'm already unable to implement Quicksort without looking it up. The important thing I learned is that each sorting algorithm has its own best/worst/average case performance and memory usage complexity. So what will I do when (if) I have to write a sort function for my custom data structure? I'll go here, look at that big table in the middle of the page, compare the numbers to my requirements threshold, and implement the best fit. If I am a good developer, I will do this research regardless of whether I still remember Quicksort. So what was the point of remembering Quicksort? E: sorry for typos. MachinTrucChose fucked around with this message at 22:43 on Aug 20, 2011 |
#
?
Aug 20, 2011 22:36
|
|
|
|
| # ? Apr 29, 2024 12:57 |
|
|
don't be a sociopath, Samuelllllll
shrughes fucked around with this message at 23:21 on Aug 20, 2011 |
|
#
?
Aug 20, 2011 22:58
|
|
|
A better question than, "Do you remember X algorithm from a class you took 5 years ago?" might be, "So write me a sorting algorithm." Very open ended, lets the candidate ask lots of clarifying questions, see how they approach the problem. And if they do whip out quicksort, change the problem by giving them conditions that make quicksort particularly bad. Say one where mergesort is a better choice 
|
|
#
?
Aug 21, 2011 02:09
|
|
|
Chasiubao posted:A better question than, "Do you remember X algorithm from a class you took 5 years ago?" might be, "So write me a sorting algorithm." No, that's a worse question because you're going to be referencing a standard implementation 99.9% of the time for sorts. Knowing the difference is much more important than being able to write it, and even that is not all that important (but a dev should know the general concept and runtime of each).
|
|
#
?
Aug 21, 2011 13:48
|
|
|
TasteMyHouse posted:Quicksort isn't O(n*log n). It's O(n2) edit: Wikipedia confirms. Also in order to get the worst-case scenario you either have to have data explicitly designed to screw with quicksort or have astronomically terrible luck. Cicero fucked around with this message at 16:59 on Aug 21, 2011 |
|
#
?
Aug 21, 2011 16:57
|
|
|
Cicero posted:I thought it was O(n^2) in the worst case but O(nlogn) in the average? I was being pedantic, but since (by definition) big O notation is a specification of an upper-bound on the growth rate, if you don't specifically say "in the average case" you're automatically referring to worst case performance. Also I should note that depending on the implementation you can get worst-case performance on already-sorted lists with quicksort, which is not an astronomically unlikely case.
|
|
#
?
Aug 21, 2011 18:16
|
|
|
Technically, it can be made O(n log n) because there's a linear-time median algorithm. Nobody ever does this, though.
|
|
#
?
Aug 21, 2011 18:19
|
|
|
rjmccall posted:Technically, it can be made O(n log n) because there's a linear-time median algorithm. Nobody ever does this, though. I'd like to see that. Do you have a link?
|
|
#
?
Aug 21, 2011 18:20
|
|
|
I was taught to take the last, middle and first items and then use the median of those as a pivot, but it's possible to stack your list against that, if you try really really hard.
|
|
#
?
Aug 21, 2011 18:25
|
|
|
O notation describes functions, not algorithms, and if you want to talk about actual running time, the average running time of quicksort on inputs of size n (having some sane distribution of values) is O(n * (log n)^2).TasteMyHouse posted:I was being pedantic, but since (by definition) big O notation is a specification of an upper-bound on the growth rate, if you don't specifically say "in the average case" you're automatically referring to worst case performance. O notation is used to describe whatever function people have in mind. If somebody says quicksort is O(n log n) then obviously they're referring to the function describing the average number of comparisons it would take to sort some distribution of input values. The fact that people use O notation this way is proof that your definition of how big O notation should be used is just a fantasy.
|
|
#
?
Aug 21, 2011 20:52
|
|
|
Never mind.
|
|
#
?
Aug 21, 2011 20:57
|
|
|
shrughes posted:The fact that people use O notation this way is proof that your definition of how big O notation should be used is just a fantasy. Or that I learned big O from engineers, not CS professors. Thanks for the schooling.
|
|
#
?
Aug 21, 2011 21:06
|
|
|
shrike82 posted:When I switched between my first and second job, I ended up only having 2 weeks of vacation which I regret. If/when I leave my second job, I'm tempted to take a year off. Has anyone done that? I kinda have. I took nine months unpaid leave (if you're at a big company just ask hr/your manager, they will probably say yes if they don't want to lose you), and now I'm technically unemployed and plan on remaining so for the foreseeable future. If you have a good amount of experience (5 years+) and a good network I don't think it is that hard to find something if/when you want to go back.
|
|
#
?
Aug 21, 2011 21:15
|
|
|
I don't think it's an abuse of notation. When you say "This algorithm is O(f)" without any qualifiers you're just using some agreed upon defaults. First, you're talking about the running time of the algorithm rather and space or power consumption. Second, you're talking about the worst case running time over all possible inputs. If you want to talk about something else, like space complexity, average running time, or running time with high probability, then you should qualify it as such.
|
|
#
?
Aug 21, 2011 21:23
|
|
|
TasteMyHouse posted:I'd like to see that. Do you have a link? http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm and http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-four/ explains it fairly well towards the end of the video.
|
|
#
?
Aug 21, 2011 22:04
|
|
|
Eggnogium posted:Second, you're talking about the worst case running time over all possible inputs. But that's not what people are talking about. Even people who say they're talking about worst case running time often are not actually talking about worst case running time. Sometimes they're talking about the number of times a certain function is called, instead of the running time. Sometimes they're talking about the worst case amortized running time. Sometimes people simply have no choice but to talk about expected running time because the algorithm's behavior is randomized. For example, you can't talk about worst case running time over all possible arrays of n elements, because there's no upper bound on the running time. Yet people say that quicksort takes O(f(n)) worst case running time for some choice of f. For example, people say all the time that a vector's push_back operation takes constant time, but they really mean it takes constant time on average, or amortized over a bunch of operations. For example, people assume that picking a random number uniformly in the set {0, 1, 2} takes constant time, but really it takes expected constant time and it could never return. For example, people will say that quicksort will call the comparison function O(n log n) times if you pick the median as a pivot. Actually, most quicksorts will still take O(n^2) comparisons in the worst case with a median pivot. It's just a case that people didn't include in the set of cases they were talking about. For example, if somebody says that hash tables are better than BSTs because they take O(1) time, and then you correct them and say "NO, HASH TABLES TAKE O(n) TIME IN THE WORST CASE", you're a worthless rear end in a top hat.
|
|
#
?
Aug 21, 2011 23:09
|
|
|
shrughes posted:
I'm with you for most of what you said but if you're talking to someone who doesn't already know the time complexity of push_back and you don't say constant AMORTIZED time then you're the worthless rear end in a top hat.
|
|
#
?
Aug 22, 2011 00:08
|
|
|
TasteMyHouse posted:I'm with you for most of what you said but if you're talking to someone who doesn't already know the time complexity of push_back and you don't say constant AMORTIZED time then you're the worthless rear end in a top hat. That's not true. Stop saying wrong things.
|
|
#
?
Aug 22, 2011 00:14
|
|
|
on engineering quicksort: http://pauillac.inria.fr/~maranget/X/421/09/bentley93engineering.pdf i'd also like to mention dual-pivot quicksort here http://gdtoolbox.com/DualPivotQuicksort.pdf
|
|
#
?
Aug 22, 2011 08:15
|
|
|
Aight, if I can sidestep the  for a second - if I got asked in an interview for the key differences between quicksort and mergesort are they looking for "quicksort has better average performance but far worse worst-case performance, mergesort's performance is more even but requires double the space"? Or are they looking for more detail (i.e. picking pivots for quicksort, how an architecture with an expensive copy makes mergesort awful etc.)?
|
|
#
?
Aug 22, 2011 10:26
|
|
|
the biggie is that generally quicksort is unstable and in place and that mergesort is stable and uses temporary memory thing is i'd ask them what they are looking for - just start giving detail about what you know and if it is too much they will stop you.
|
|
#
?
Aug 22, 2011 10:37
|
|
|
So, I had a programming test with that place I mentioned earlier in the thread. I thought I passed with flying colors, but apparently there was a complaint about one of my solutions to word-wrapping a text file at 80 characters. It was going to take too long to code the logic myself, so I poked around the web and found the following regex: .{1,80}(\\s|$)|\\S+(\\s|$) It seemed to work fine, and the initial glanceover seemed headslappingly simple: greedy up to 80 characters w/a space or EOL at the end, or a word longer than 80 with a space or EOL at the end. I tested it, it worked, I moved on so I could get the rest of the test done. Apparently, the people reviewing the test weren't happy with it, as I was informed I would be "more closely scrutinized" during the followup interview (which is an hour and 45 minutes!) for using the regex.  Not getting a real good feeling about this interview all of a sudden.
|
|
#
?
Aug 22, 2011 16:47
|
|
|
well, depending on the job and potential co-workers, it may be as simple as a sanity check that you can explain what's going on in that regex and explain some variations on the problem based on other constraints. Regular expressions are (in my opinion) one of the easier things one could copy and paste after googling, without understanding what it actually is.
|
|
#
?
Aug 22, 2011 19:18
|
|
|
Lurchington posted:well, depending on the job and potential co-workers, it may be as simple as a sanity check that you can explain what's going on in that regex and explain some variations on the problem based on other constraints. Regular expressions are (in my opinion) one of the easier things one could copy and paste after googling, without understanding what it actually is. Yeah, that sounds fair, just seems sort of... passive aggressive. They call me at a job I'm happy with specifically to give me the hard sell, then tell me my fix is under "increased scrutiny" and I'm one of eight candidates in consideration. I'm kind of getting mixed signals here!
|
|
#
?
Aug 22, 2011 19:25
|
|
|
Chokes McGee posted:Yeah, that sounds fair, just seems sort of... passive aggressive. They call me at a job I'm happy with specifically to give me the hard sell, then tell me my fix is under "increased scrutiny" and I'm one of eight candidates in consideration. I'm kind of getting mixed signals here! You had the awesomest solution to the problem. You might be under "increased scrutiny" but that just means they're going to pay more attention to you, that you'll stand out more, and that they'll be more likely to hire you.
|
|
#
?
Aug 22, 2011 20:31
|
|
|
shrughes posted:You had the awesomest solution to the problem. You might be under "increased scrutiny" but that just means they're going to pay more attention to you, that you'll stand out more, and that they'll be more likely to hire you. I like the cut of your jib, sailor!  Thanks for the confidence boost. I interview tomorrow, so we'll see how it goes!
|
|
#
?
Aug 22, 2011 20:34
|
|
|
I'm soon to be applying for developer roles after finishing a one year MSc in CompSci, and whilst we covered sorts etc in algorithms, all this talk of algorithms is making me  I'd call myself quite a competent Java developer, but ask me to implement a sorting algorithm off the top of my head in an interview and I'll probably just break down there and then
|
|
#
?
Aug 22, 2011 22:42
|
|
|
iam posted:I'm soon to be applying for developer roles after finishing a one year MSc in CompSci, and whilst we covered sorts etc in algorithms, all this talk of algorithms is making me I don't think you need to know hot to implement quick sort (but who really forgets? It's not that hard), but it is important to understand the basic structure of nlogn sorting, just as it is important to understand logarithmic search and what it looks like in a structure, how to construct a dynamic programming solution to a problem, etc. For example, there is/was a Codility problem whose solution relies on the principles behind merge sort but is not actually an implementation of merge sort. If all you know is that quick sort sorts a list really fast, you probably won't see that structure immediately and poke around at the problem for far longer than you should.
|
|
#
?
Aug 22, 2011 23:03
|
|
|
iam posted:I'm soon to be applying for developer roles after finishing a one year MSc in CompSci, and whilst we covered sorts etc in algorithms, all this talk of algorithms is making me
|
|
#
?
Aug 22, 2011 23:05
|
|
|
Cicero posted:Was your BS in CS as well? I can't imagine being having a BS and MS in CS recently and being afraid of implementing any sorting algorithm on the spot. Agreed, when interviewing people straight out of uni, my expectations are very different to interviewing people who have been in industry for a couple of years. I'd expect uni grads to be shithot on stuff covered typically in the first year of uni, since they a) haven't had time to forget it, and b) haven't had exposure to enough large-scale software development to be able to do a design problem without prompting, so showing a good grasp of the fundamentals is even more important. If you're going to be applying for developer jobs soon, bone the heck up. I know there's a stereotype about Java programmers - especially when compared to the ubermensch .NET developers - but come on, no point tripping up on the basics. P.S. If you're applying for Java jobs, know how garbage collection works. Everyone *loves* to ask that question.
|
|
#
?
Aug 22, 2011 23:28
|
|
|
My undergrad was in Computer Networks, so other than a worthles Java course that we did during that, the first CS theory I've been introduced to was in the algorithms module this year. Dare I say it, 'bare-bones' algorithms don't really interest me, developing solutions/systems does, maybe that's bad  For example, I'm comfortable with: - OOP principles - I was raised by Josh Bloch and a healthy regimen of Effective Java - JUnit unit testing - Efficient logging mechanisms using log4j etc - Scheduling - Concurrency - JPA and other parts of J2EE etc etc etc And have a good number of projects under my belt, a couple commercial, a couple academic, and a good few 'hobby projects', that demonstrate the above - but as I say, quicksort, mergesort - in an interview That's not to say I couldn't knock up a palindrome algorithm, a linked list, or a basic sorting mechanism for an int array - but talking about the merits in terms of O complexity of one algo from another... Maybe it's time to pick up a book and brush up iam fucked around with this message at 23:55 on Aug 22, 2011 |
|
#
?
Aug 22, 2011 23:44
|
|
|
iam posted:For example, I'm comfortable with: That disqualifies you right there, nobody should be comfortable with concurrency.
|
|
#
?
Aug 23, 2011 00:03
|
|
|
Well when I say comfortable I mean I just make every class extend Thread and main just kicks everything off at once in an orgy of computation 
|
|
#
?
Aug 23, 2011 00:17
|
|
|
iam posted:Dare I say it, 'bare-bones' algorithms don't really interest me, developing solutions/systems does, maybe that's bad It's great knowing industry standard frameworks, but it can be important to know algorithms and data structures, depending on the types of job. There are many jobs where most of the time will be spent on configurations, plumbing code together, some slight customisation of mostly out of the box stuff. There's always a demand for it, both from enterprise and small businesses. You can solve those types of problems without having to have a compsci background. They can pay well, the hours are often not too bad. Then there's jobs where a big chunk of time will be spent on munging data together, performing calculations, doing heavy I/O and trying to get it all to complete before you die of old age. Knowing algorithms and data structures here is crucial. It will also tend to impact upon what the types of the members of your objects you make public look like (writing Get/Add/Delete methods can get old fast in this scenario). I've generalised here, but you get the point. If you're applying for the first type of role, knowing Compsci 101 won't hurt. If you're applying for the second role (and these do exist in Enterprise as well - I've done them), it's really vital.
|
|
#
?
Aug 23, 2011 00:26
|
|
|
Cheers for the feedback - on that basis, what sort of job titles would I be looking at for the former? And am I ever likely to get a job in IBM/Google/MS/'interesting' big corporate doing the more high-level stuff as I described? 
|
|
#
?
Aug 23, 2011 00:56
|
|
|
iam posted:Cheers for the feedback - on that basis, what sort of job titles would I be looking at for the former? And am I ever likely to get a job in IBM/Google/MS/'interesting' big corporate doing the more high-level stuff as I described? Milotic did a good job of explaining the two major groups of developers. One group has a heavy CS background and they know their algorithms and theory. The other group of developers have a better grasp on the concepts that you mention. Given enough time and experience anyone can acquire the skills that you mention but going the other way around is a lot harder without studying. As for getting a job at a big company, remember that the problems they are trying to solve aren't the kinds of things that a high level api will exist for. The skills you mention come into play when they're ready to create a product, but the ground breaking work that enables that product is usually a new algorithm. Knowing that, a big company is more likely to hire someone in the heavy CS camp with a pretty sure bet that they will learn the other skills in time. That doesn't mean that they will turn away a good developer with the skills that you mention, it's just that their is a greater supply of them. If heavy CS isn't your cup of tea then don't apply for those kinds of jobs, there are plenty of others that will suit your tastes, even at a big company.
|
|
#
?
Aug 23, 2011 02:44
|
|
|
I have a question regarding undergrad degrees. Right now, I am in a Computer Science and Engineering Technology (CSET) program at University of Toledo, but I am considering switching up to the actual Computer Science and Engineering (CSE) program. The webpage on the university's website is extremely vague about the differences between these two, and it basically just says that CSET is less math/science heavy and starts you with actual programming earlier than CSE. It goes on to say that both "engineering and engineering technology graduates may compete for the same jobs, at the same pay and with the same titles." The kind of job titles I'd be interested in as of now are Software Engineer in the game development field at a company like ArenaNet, Valve, etc or something in computer security, like a position at NSA or some defense contractor. Realistically, I am curious as to if any of you have heard of, or had any applicants from an engineering technology program that focuses on Computer Science. Would you prefer the math-intensive one over the other? Would you prefer a student with a 3.5 in a CSET program over someone with a 3.0 in a CSE program? Would you even care and just treat both as a 4-year CS degree considering you would probably have no idea as to how my school is and how good it's programs are? I am really worried about this. While I know I'd get a better GPA in the CSET program, I don't want to just take the path of least resistance and screw myself over 4ish years from now. I just want to get a job that pays well and at a company where I can do something that interests me. Here is the website I cited, in case anyone was interested. http://www.et.utoledo.edu/ jaffyjaffy fucked around with this message at 05:53 on Aug 23, 2011 |
|
#
?
Aug 23, 2011 05:25
|
|
|
jaffyjaffy posted:I have a question regarding undergrad degrees. Read the degree requirements! Read the course descriptions! How can you say the site is vague when it lists exactly what courses you need to take for the major? I would go into the CSE program. The only reason not to is if you're too dumb to get a real college degree. jaffyjaffy posted:Realistically, I am curious as to if any of you have heard of, or had any applicants from an engineering technology program that focuses on Computer Science. Would you prefer the math-intensive one over the other? Would you prefer a student with a 3.5 in a CSET program over someone with a 3.0 in a CSE program? Would you even care and just treat both as a 4-year CS degree considering you would probably have no idea as to how my school is and how good it's programs are? I would prefer a student who doesn't suck at programming, and I don't really care about his GPA. I looked at the programs on the website and I'd definitely expect a CSE person to be a better, more interesting candidate. The first programming class in CSET is "GUI Programming", and now I want to do violent things to people. But yes I'd prefer somebody who got a 3.0 in CSE to somebody who got a 4.0 in CSET, not that that fact gets any consideration after the resume screening phase. jaffyjaffy posted:I am really worried about this. While I know I'd get a better GPA in the CSET program, I don't want to just take the path of least resistance and screw myself over 4ish years from now. I just want to get a job that pays well and at a company where I can do something that interests me. There's no way you'll screw yourself (unless you go into game programming) but you can be sure that nobody will be impressed by a GPA that is padded by the crap that's in the CSET program. I really think the CSET program is targeted towards people who should not be getting a college degree in the first place. Keep in mind that I'm a masochist on other people's behalf when it comes to recommending their educational path, and I'm not really capable of commiserating with a distaste for classes that have math. But honestly the CSE program I see there is not some kind of torturous gauntlet set up to make you hate your life and expose how much you allegedly suck at math. You won't suck at math hard enough for it to be difficult. You might suck at programming though, that's the real danger. Edit: To be clear, I would be happy for you if you got a CSE program and got a 3.5 GPA, or a 3.0 GPA, and I would be happy if you went into CSE but failed out and committed suicide because you were one of the many starry eyed would-be game programmers or security whatchyamazits who actually suck at programming, too. I would be unhappy if you went into the CSET program no matter how well you did. My happiness function is not the same as your happiness function. shrughes fucked around with this message at 06:54 on Aug 23, 2011 |
|
#
?
Aug 23, 2011 06:49
|
|
|
shrughes posted:Edit: To be clear, I would be happy for you if you got a CSE program and got a 3.5 GPA, or a 3.0 GPA, and I would be happy if you went into CSE but failed out and committed suicide because you were one of the many starry eyed would-be game programmers or security whatchyamazits who actually suck at programming, too. I would be unhappy if you went into the CSET program no matter how well you did. My happiness function is not the same as your happiness function. shrughes posted:don't be a sociopath, Samuelllllll
|
|
#
?
Aug 23, 2011 08:07
|
|
|
|
| # ? Apr 29, 2024 12:57 |
|
|
iam posted:Cheers for the feedback - on that basis, what sort of job titles would I be looking at for the former? And am I ever likely to get a job in IBM/Google/MS/'interesting' big corporate doing the more high-level stuff as I described? goog tend to hammer people about algorithms in the hiring process. if you want to avoid learning about algorithms, try applying for jobs of 'middleware developer'
|
|
#
?
Aug 23, 2011 09:02
|
|