Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
 
  • Post
  • Reply
Chasiubao
Apr 2, 2010


HondaCivet posted:

So how bad is it to give up on a coding challenge? I got one commit in before I got super stuck and then turned into a ball of nerves and couldn't think straight anymore. Thankfully it was over email so no one had to see me flip out, haha. I just told him that the problem seemed to be a bit over my current abilities. I know you should normally just do as much as you can but I just couldn't because I'm terrible.

Next time, go over exactly where you're stuck, what solutions you've tried, and what you think might be the right solution and hey let's discuss this.

Adbot
ADBOT LOVES YOU

Stanos
Sep 22, 2009

The best 57 in hockey.
They aren't looking for perfection in a junior role, they're looking to see how you handle it after you get stuck. As long as you know where the problem is and can explain it or try to explain your thought process and that you don't just melt down and go into a fetal position when something goes wrong they shouldn't judge you too much. If they do, it's not a place to work anyway.

If you just sit there frozen and don't attempt to solve the issue, it's going to be a problem later if they hire you.

HondaCivet
Oct 16, 2005

And then it falls
And then I fall
And then I know


Really? You can do that? Huh. I have to admit that I didn't have to write any code in the interview to get my current job so I really don't know how they're supposed to go, especially if you have trouble. I kind of assumed that you were just boned if you didn't know how to do at least most of it off the top of your head.

He was nice about it at least but maybe he was just being nice. I hope not, it sounded like a really nice team/place and I'd like to apply there again sometime.

HondaCivet fucked around with this message at 19:39 on Sep 23, 2013

astr0man
Feb 21, 2007

hollyeo deuroga
The main point of programming exercises in interviews is to see your problem solving thought process in action. So yeah even if you don't know how to solve the problem, talking through it and explaining the parts you do understand and what you are not sure of is what the interviewer is looking for.

And yes there are things like Fizzbuzz where the interviewer might actually be expecting you to answer it correctly, but in general it is more about just seeing how you think.

Stanos
Sep 22, 2009

The best 57 in hockey.
I mean if it was something like Fizzbuzz and you struggled with it, obviously they're gonna tell you to have a nice day and never contact you again but if it's something more complex and maybe more involved it's going to look a lot better if you ask questions and try to work with it instead of freezing up and not doing anything. If a place hiring a junior isn't expecting to teach them, I would be very careful about what you're getting yourself into.

ManoliIsFat
Oct 4, 2002

astr0man posted:

And yes there are things like Fizzbuzz where the interviewer might actually be expecting you to answer it correctly, but in general it is more about just seeing how you think.
This is how I started beginning all of my interviews. We were a pretty straightword C# shop. For initial interviews, I did pen and paper, no computer help, show me a class Cat that inherits from Animal. Give me a FizzBuzz. What's the output of this program (which may be a little gotcha), show me a relational DB sketch of a library (books, members, transactions table). To me, you shouldn't be sending in your resume if this kinda stuff spooks you. These are the kinda questions I as your boss gotta KNOW you can do intuitively, without much thought. If you're StackOverflow looking for this kinda stuff, you're always gonna struggle.

Maybe it was just where I was when I was hiring these kids, but to me this is lower level than "right out of college", this is the kinda stuff they should be asking you in weeder classes freshman year. I was amazed how many people got filtered out by that first round of "where you awake in class". I was just running a team of programmers for an e-retailer, not the most complicated or glamorous work in the world. I can't imagine how brutal this kinda stuff is at a real company, where you've got guys with masters and phds in CS running around.

Coca Koala
Nov 28, 2005

ongoing nowhere
College Slice
About six pages ago I posted saying that I had gotten a job offer for 85k in the Mountain View area and asked how that stacked up against other salaries for the area, and whether or not I should ask for more money. The general advice was that it's not a terrible offer, but that I should ask for more money because asking for more money has literally no downside.

I went and read the Kalzumeus blog post on salary negotiation, and I responded to the offer today asking for another 10,000 in salary, expecting to do some negotiating. They accepted my counter offer immediately and sent me a revised offer letter within three hours.

If you get an offer, ask for more money. There's no downside to asking for more money. And read the stuff linked in the OP, because it's for real helpful.

Strong Sauce
Jul 2, 2003

You know I am not really your father.





Coca Koala posted:

About six pages ago I posted saying that I had gotten a job offer for 85k in the Mountain View area and asked how that stacked up against other salaries for the area, and whether or not I should ask for more money. The general advice was that it's not a terrible offer, but that I should ask for more money because asking for more money has literally no downside.

I went and read the Kalzumeus blog post on salary negotiation, and I responded to the offer today asking for another 10,000 in salary, expecting to do some negotiating. They accepted my counter offer immediately and sent me a revised offer letter within three hours.

If you get an offer, ask for more money. There's no downside to asking for more money. And read the stuff linked in the OP, because it's for real helpful.

Probably could have asked for more if they were quick to agree, but congrats!

Generally the thing is to ask for more money and if they say, "no" you can decide if you want to work there or not. It's not as though they'll rescind an offer to a qualified applicant.

Which is generally why you shouldn't set a price on yourself because if you had originally given $85k as your expected salary, you look like a jerk asking for more.

Coca Koala
Nov 28, 2005

ongoing nowhere
College Slice

Strong Sauce posted:

Probably could have asked for more if they were quick to agree, but congrats!

Generally the thing is to ask for more money and if they say, "no" you can decide if you want to work there or not. It's not as though they'll rescind an offer to a qualified applicant.

Which is generally why you shouldn't set a price on yourself because if you had originally given $85k as your expected salary, you look like a jerk asking for more.

Yeah...my first thought was "Sweet!" and my second was "drat, I guess I should have tried to break six figures." But it's more than three times better than what I was making before I got into computer science, it should be enough to find a nice apartment and live comfortably, and the work is exciting. Even if I could have asked for more money, it's pretty hard for me to chalk this up as a loss.

Brannock
Feb 9, 2006

by exmarx
Fallen Rib
How much experience do you have Coco Koala?

HondaCivet
Oct 16, 2005

And then it falls
And then I fall
And then I know


It was a bit more complex than FizzBuzz. It was taking a CVS file and dealing with the input which is stuff I don't exactly do every day.

Surely I'm not the only dev who's had a problem with nerves when it comes to interviews? Does it just take more interview experience to get over it? Is there a way to get help with this stuff besides flunking dozens of interviews for the sake of experience?

greatZebu
Aug 29, 2004

HondaCivet posted:

It was a bit more complex than FizzBuzz. It was taking a CVS file and dealing with the input which is stuff I don't exactly do every day.

Surely I'm not the only dev who's had a problem with nerves when it comes to interviews? Does it just take more interview experience to get over it? Is there a way to get help with this stuff besides flunking dozens of interviews for the sake of experience?

The best thing to do is practice. Get some plausible interview coding questions (this book is a reasonable source: http://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/098478280X) and work them out on paper or at a whiteboard, explaining your thought process out loud as you go. It's embarrassing, but that's what you'll need to do when you're actually interviewing. After you have a solution, look through it carefully for bugs and missed corner cases. Then type it into a computer verbatim and see if what you wrote actually works. You'll be surprised at how much easier it gets after a week or two of practice.

Coca Koala
Nov 28, 2005

ongoing nowhere
College Slice

Brannock posted:

How much experience do you have Coco Koala?

Not an incredible amount. I have a bachelor's degree in an entirely unrelated field, and took a couple intro CS classes as an undergrad. I kept up with programming after college, and once I spent two years in a pit of unhappy employment, I started to look into the idea of post grad education. I lucked into a Master's program and started taking a mix of basic and advanced CS classes; I spent fall and spring semester of last year doing coursework, found a summer internship at the last minute, and ended up converting that internship position into a full time job offer.

If you've got more detailed questions, feel free to PM me; I'm by no means a powerhouse of the industry and I feel pretty lucky to have gotten where I am.

Edly
Jun 1, 2007

HondaCivet posted:

It was a bit more complex than FizzBuzz. It was taking a CVS file and dealing with the input which is stuff I don't exactly do every day.

Surely I'm not the only dev who's had a problem with nerves when it comes to interviews? Does it just take more interview experience to get over it? Is there a way to get help with this stuff besides flunking dozens of interviews for the sake of experience?

I'm going to enthusiastically second greatZebu's book recommendation. This year I interviewed at 3 out of the 5 "top" companies that book specifically targets (Amazon, Yahoo, Google, Microsoft, Apple). Cracking the Coding Interview was pretty much the only resource I used to prepare, and I felt well prepared. Every single interview question I got fell into one of the categories in that book. It gives you a lot of specific advice about what to do to prepare, and even how to proceed when you get stuck on an interview problem.

I absolutely had trouble with nerves during the process. A few times my mind went blank and I just couldn't think of a single thing to say. However, that's when I learned that just flatly giving up on the problem is the absolute worst thing you can do. I flunked one interview because of that. In future interviews, when I got stuck, I just told the interviewer I was stuck and asked for a hint, and that was enough to get me going again.

Having said that, reading input from a file is pretty basic. If I were an interviewer and a candidate said they just couldn't figure that out, there's no way I would consider them further. I recently worked with a junior dev who was extremely inexperienced, and would get stuck on a lot of things I considered basic. I told him that figuring out how to do things you've never encountered before is a fundamental skill for a developer, and Google is going to be your best tool there.

You mentioned that the interview was over email - is there any reason you couldn't have just Googled "how to read from a CSV in <language>" (or whichever part of the problem you were stuck on)?

Fuck them
Jan 21, 2011

and their bullshit
:yotj:
Going to chime in with it's probably a good idea to practice whiteboard coding, and for that matter, legibly writing on a vertical surface without an easy way to brace your elbow or forearm to do so.

I'm so used to text editors that trying to write things out by hand is a pain in the rear end at best. Then again I'm working at a place that didn't give me a written programming test (or a programming test at all!) so YMMV.

They did ask to see a code sample. I sent in an assembler I wrote in Java for a school project, and I suppose that's a bit more impressive than fizzbuzzing or a web app made with hipster.js.

HondaCivet
Oct 16, 2005

And then it falls
And then I fall
And then I know


Thanks guys. I did get that book and practice a bit but I'll step it up.

I got hung up on something that turned out to be really dumb. I did find out how to read a CVS file but I got confused about what the method was returning. Then I got too panicked to actually figure out the issue when my stuff kept breaking. :sweatdrop:

air-
Sep 24, 2007

Who will win the greatest battle of them all?

Practice, practice, practice. Don't beat yourself up too bad especially if it was your first time, chalk it up as a lesson learned and move on!

I barely have much experience with this interview style myself (I am a finance guy looking to move into technical work). I did decently last Friday, when I was put on a computer with an attached projector and the two interviewers were watching my every move. It helped that they said "Google it, we don't care" - and clearly they were more interested in seeing me adapt to the situation :downs:

e: forgot to say, talked with them today and was told to expect a written offer asap :toot:

air- fucked around with this message at 18:04 on Sep 24, 2013

smokyprogg
Apr 9, 2008

BROKEN DOWN!
MISSION FAILED
So, apparently non-CS GPA isn't a dealbreaker, as I have an interview with Microsoft tomorrow.

That being said, oh god i've never done an interview for anything cs related gently caress.

I feel firmly confident with implementation and using of the structures/algorithms in the 2nd post, and I am fine with coding. This is for an undergrad intern position. Anything in particular I should prep for past the aforementioned?

HondaCivet
Oct 16, 2005

And then it falls
And then I fall
And then I know


Congrats! :hfive:

I just feel bad because it seemed like a really cool job and I probably could have gotten through it had I had my wits about me. Oh well, at least I have some experience now.

JawnV6
Jul 4, 2004

So hot ...

HondaCivet posted:

I got hung up on something that turned out to be really dumb. I did find out how to read a CVS file but I got confused about what the method was returning. Then I got too panicked to actually figure out the issue when my stuff kept breaking. :sweatdrop:

I used to write emails to my mom when I'd get stuck, explaining the problem. Having to explain everything to someone nontechnical would often root out whatever faulty assumption I was making.

It's called "Rubber Duck Debugging" elsewhere, but when you're hung up on something like return type mismatched between your head and what's actually happening it's a useful tool. I also credit it with finding when I'd called the method OnPiant and was tearing hair wondering why it was never called.

ManoliIsFat
Oct 4, 2002

HondaCivet posted:

It was a bit more complex than FizzBuzz. It was taking a CVS file and dealing with the input which is stuff I don't exactly do every day.

Surely I'm not the only dev who's had a problem with nerves when it comes to interviews? Does it just take more interview experience to get over it? Is there a way to get help with this stuff besides flunking dozens of interviews for the sake of experience?

I experience is the only way to get comfortable with it. I interviewed a guy twice before. The first time, he was obviously flustered. Couldn't remember how to do a JOIN, which is gonna come up when all you do all day is mess with a DB. And that frustration breeds more frustration: if you think I think less of you because you can't answer a question I asked 10 mins in to the interview, you're just gonna feel awful until the interview is over.

I was one of his first interviews right out of school, so obviously he had no idea what to expect. He came back again like 3-6 months later, and blew me away. His second interview, we got passed all that little stuff and got to have a high level conversation about what we were trying to accomplish. He to this day is one of the best employees I've ever had.

HondaCivet posted:

I just feel bad because it seemed like a really cool job and I probably could have gotten through it had I had my wits about me. Oh well, at least I have some experience now.
Yup, that's tough, but all you can do is learn from it. Pretty soon (Especially with that book) you're gonna feel super comfortable with those types of questions. Another thing I'd suggest to brush up on is all your Intro To Data Structures stuff, people love asking about computational complexity and "make me a linked list" as those gatekeeper kinda questions.

HondaCivet
Oct 16, 2005

And then it falls
And then I fall
And then I know


JawnV6 posted:

I used to write emails to my mom when I'd get stuck, explaining the problem. Having to explain everything to someone nontechnical would often root out whatever faulty assumption I was making.

It's called "Rubber Duck Debugging" elsewhere, but when you're hung up on something like return type mismatched between your head and what's actually happening it's a useful tool. I also credit it with finding when I'd called the method OnPiant and was tearing hair wondering why it was never called.

I've heard of that before, I should actually try it one of these days.

Did you ever send one of the emails :v:


ManoliIsFat posted:

:words:

Thanks for that story, I feel less like an irredeemable failure now. :unsmith:

HondaCivet fucked around with this message at 21:06 on Sep 24, 2013

bonds0097
Oct 23, 2010

I would cry but I don't think I can spare the moisture.
Pillbug

smokyprogg posted:

So, apparently non-CS GPA isn't a dealbreaker, as I have an interview with Microsoft tomorrow.

That being said, oh god i've never done an interview for anything cs related gently caress.

I feel firmly confident with implementation and using of the structures/algorithms in the 2nd post, and I am fine with coding. This is for an undergrad intern position. Anything in particular I should prep for past the aforementioned?

Are you interviewing for PM, SD or SDET? And is this first-round or final round in Redmond?

smokyprogg
Apr 9, 2008

BROKEN DOWN!
MISSION FAILED

bonds0097 posted:

Are you interviewing for PM, SD or SDET? And is this first-round or final round in Redmond?

First, and not exactly specified yet for which position. I indicated I would prefer SDET > SD > PM on the application.

bonds0097
Oct 23, 2010

I would cry but I don't think I can spare the moisture.
Pillbug

smokyprogg posted:

First, and not exactly specified yet for which position. I indicated I would prefer SDET > SD > PM on the application.

You'll probably get some sort of design question (i.e. "Imagine you're designing a telephone for the visually impaired. What are some important features it should have?") so think about everyday objects and why they're designed the way they are.

There will certainly be a relatively simple code problem, so focus on explaining your thought process and not get flustered. They're not looking for an optimal algorithm necessarily but you should be able to describe how time and space efficient your solution is in Big-O Notation. You'll have something with string manipulation or linked list reversal or something along those lines, nothing super complicated.

And then of course some basic behavioral stuff (i.e. "think of a time when you solved a difficult technical problem in a team").

astr0man
Feb 21, 2007

hollyeo deuroga
Don't forget he's going for an undergrad intern position. They might not actually expect all that much technical knowledge.

bonds0097
Oct 23, 2010

I would cry but I don't think I can spare the moisture.
Pillbug

astr0man posted:

Don't forget he's going for an undergrad intern position. They might not actually expect all that much technical knowledge.

I interviewed with Microsoft as an undergrad for an internship position and am basing my advice off of that.

Pollyanna
Mar 5, 2005

Milk's on them.


How would the whole GPA thing work if you don't actually have a CS-based degree? Would an Engineering degree suffice?

No Safe Word
Feb 26, 2005

Pollyanna posted:

How would the whole GPA thing work if you don't actually have a CS-based degree? Would an Engineering degree suffice?

Well.. you still get a GPA, not all places (or even many places that I've seen) require that you list your GPA in your major, or even care if you do.

astr0man
Feb 21, 2007

hollyeo deuroga
I had a phone screen with google today that I guess I passed, but I'm going to get my rear end kicked in the actual first interview. Guess I should actually attempt to remember algorithms poo poo that I haven't had to think about since college :negative:

wolffenstein
Aug 2, 2002
 
Pork Pro
I'm looking for a critique of my resume and social profile. I haven't been contacted by a recruiter in about a month, and even when recruiters were contacting me, I never got a coding challenge or an interview with a manager. I'm looking for a junior iOS and/or Ruby on Rails position.

Website, Resume, GitHub

ILoveYou
Apr 21, 2010

If you want a iOS or Rails job then you're well-suited for one so long as you remove all that Desktop Support type experience from your resume. Your job title is programmer, but most of the experience you list matches what a very high-level Support Engineer would do and doesn't demonstrate any Obj-C or Rails experience. If you can't find any Obj-C or Rails type experience in those jobs then move those open source projects in front of your work experience. Maybe turn that website from HTML resume to mini-blog written in Rails and write some poo poo about how you love Rails/are learning Rails/go to bed and dream about Rails. When you make those changes, split the resume into two - one Rails focused and on Obj-C focused.

Good Will Hrunting
Oct 8, 2012

I changed my mind.
I'm not sorry.
I know it's been said here a lot that the whole "X+ years" can be HR drone bullshit, but as someone with under a year of experience how do I approach this? Do I just kinda throw applications out to places I'm interested in that I'm otherwise qualified for? (One place I'm interested in is an Amazon subsidiary so maybe someone knows a little about that process?)

Gazpacho
Jun 18, 2004

by Fluffdaddy
Slippery Tilde

wolffenstein posted:

I'm looking for a critique of my resume and social profile. I haven't been contacted by a recruiter in about a month, and even when recruiters were contacting me, I never got a coding challenge or an interview with a manager. I'm looking for a junior iOS and/or Ruby on Rails position.

Website, Resume, GitHub
Very nice resume overall. Some suggestions:

- Tables should be avoided for the benefit of automatic scanners. Use punctuation to separate information on the same line. Contact info is for human consumption and therefore an exception.
- Lead your jobs with the company/location, followed by the title/dates.
- Combine the two jobs sections.
- Retitle the projects section "Portfolio" and put the URL centered under the heading.
- Fiddle with the formatting and wording to get room for a job title under the contact information. Ideally it should match the title of each job you apply for.
- If you're open to web dev position, you should list more general web skills (HTML, CSS, Javascript, HTTP, REST etc. as appropriate)

Gazpacho
Jun 18, 2004

by Fluffdaddy
Slippery Tilde

Good Will Hrunting posted:

I know it's been said here a lot that the whole "X+ years" can be HR drone bullshit, but as someone with under a year of experience how do I approach this?
If an HR contact asks you for a number of years of experience with a technology and you have part of a year, answer "one." If you have academic or personal project experience with that technology and are prepared to describe that experience, then count it in your answer.

Gazpacho fucked around with this message at 08:39 on Sep 25, 2013

Linear Zoetrope
Nov 28, 2011

A hero must cook
I'm having a real issue getting a job. I've been out of school for about a year and I've applied to 10-15 places (the rest I didn't have the skillset for), but I've only gotten a couple interviews, none of which panned out.

I did fine in school (3.68 GPA, graduated with honors), but I'm thinking maybe my skill set is just too technical? I did plenty of undergrad research (and in the long term, my ideal job is a research job), but everything I've found in my field is either "PhD strongly preferred" or "PhD required". All of my research was in machine learning, but not the marketable kind that prevents banks from getting hacked and allows Youtube to recommend cat videos to you. To give you an idea, my honors thesis was about Transfer Learning which is a dead-ish subfield of machine learning that deals with trying to get a computer to recognize when something it learned in a different context is applicable to its current context, and transfer that data.

The research didn't get as far as I would have liked, but I did get some basic similarity recognition running (it was on a small toy problem), though I ended up constrained by our choice of neural net algorithm (it turns out that transfer isn't too useful when the algorithm requires you to tell it all the actions it can do in advance anyway :eng101:). The other stuff I did were things like emulating emotions with an artificial agent and getting a computer to watch a physics engine and recreate the gist of the scene with a state machine, along with a little bit of computer vision and graphics.

More generally my focus was on CS, not software engineering. I was focused on automata, graphs, and support vector machines more than AGILE and memorizing design patterns. I was clearly doing something right, professors seemed to like me -- not just in the "he doesn't cause trouble and does his work" way so much as the "we're going to offer you positions we usually only offer to grad students" way. (I'm still one of the only undergrads in the department that's TA'd not just one but two 400-level courses; on AI and computer graphics). I've also been contributing to quite a few open source projects recently (an OpenGL port, though I have made a 3D linear algebra package akin to GLM and started/manage a numeric/scientific computing suite for a language that didn't have one yet).

Don't get me wrong, I don't think I'm hot poo poo. I know there's tons I need to learn and deal with when I do get a job. I don't expect myself to wow John Carmack into worshipping me. I still need to get a better foundation for some of the higher level math (probability and vector calc especially) -- and I'm going to have to learn to work on very large projects in diverse teams etc etc, and that production code is often different from research or school code. I'm just saying that I did things, and did them rather well I think, but it doesn't seem to really be paying off. Maybe I should bite the bullet and just learn web programming and deal with it? I've literally never touched web development, I have little interest in it, but it seems to be where all the entry level bachelors degree jobs are.

Maybe it's also my constraints, I really need to stay in Tucson or Southern Arizona-ish, mostly because I plan on going to grad school next fall and especially with typical apartment lease lengths it's really senseless and financially difficult to move halfway across the country only to move halfway across again to attend school in a year, but I really need something until then. I thought about freelancing, but again, people only really seem to hire freelancers for web stuff. I doubt many companies are trolling for machine learning/computer graphics freelancers. I really don't know what to do, any ideas? Is it maybe that I'm just in a poo poo situation, and even if I was God's Computer Hacker my other constraints and esoteric skill set have gimped me until I finish grad school?

Oh, and I did get one interview at a digital signal processing place a few weeks ago and got this interview question, I found it rather easy, but maybe it's secretly not. I'm pretty confident but does anyone see anything wrong with it? It's possible the answer is fine and I haven't heard back because they went with a PhD or something.

them posted:

In Java, C or C++, show me the largest 100 numbers in an unbounded stream of numbers.



I encourage you to write any limitations or assumptions you make about the problem or data set, etc.

me posted:

First assumption: We're using floats.

Second assumption: there exists a function called "insertionSort(float *nums, float toInsert, int listSize)" that performs an in-place descending order insertion sort, since insertion sort is a trivial implementation I won't waste time writing out. All it does is iterate over the existing list until it finds an element less than the input, shifts everything to the right, and places the input in that slot. If it's smaller than every element in the list it appends it to the end. The variable listSize should be at least one less than the actual array size since to insert into the list it needs to grow.

Third assumption: there exists a function called "float pollStream()" that returns the next number in the stream (if the stream is time-sensitive, we can assume it's buffered in another thread or something).

code:
int main( void ) {
    float numList[101];
    int arraySize = 0;
    while(true) { // Unbounded, so it goes forever
       float toInsert = pollStream();
       insertionSort(numList, toInsert, currSize);
       if(arraySize < 100) {
           ++arraySize;
       }
    }
}
The reasoning for this method is that insertion sort is O(SizeOfList) for an almost-sorted list. Since we're polling numbers off the stream all the time, the list should *always* be almost sorted (except for the newest element). Why is the array of size 101? The last slot is a "buffer" slot. If the element happens to be less than every other in the list, it gets inserted into the 101st spot, which we can happily disregard as junk data. Same if we find a new number in the max range, everything gets shifted to the right and the previous smallest number is now junk. Obviously the first 100 numbers are always the largest 100, hence the arraySize increment until it equals 100.

We could actually probably get a performance increase by using a linked list and simple inserting the new element to the middle rather than shifting all the data over in an array, but I figured a linked-list implementation would be non-trivial for a 30-minute question.

Of course, this just maintains the data. In a real scenario you'd want to print arraySize number of elements, or call the insertion function when you need it and then do something interesting with the data, rather than using a silly unbounded while(true) loop.

Or maybe I was too wordy? I tend to operate in words first and code later, I generally find it more useful to have a conceptual underpinning for what I'm doing than it is to have perfectly correct code on the first draft, because off-by-one errors are easier to fix than glaring conceptual problems, so when I'm asked code questions I tend to focus on comments, explanation, reasoning, and algorithm decisions above the code snippet itself.

Sorry for the huge post, I'm just really frustrated after going so long with nothing.

FamDav
Mar 29, 2008
they probably went with the person who used a heap.

sorry about it.

Tunga
May 7, 2004

Grimey Drawer
You don't actually need an insertion sort, you just need one iteration of the process. The existing list will be perfectly sorted except for the new element, so it just needs to look for the correct place to add that element. You could also potentially use a linked list to make the insertion part more efficient but it's pretty negligible on a small array like this.

Personally I would actually write the insertion method, or use something from the standard libs if it exists. In C# I'd probably find the location with LINQ but I'm not sure about the neatest way in Java. Right now what've you've done is said "I take the item from the stream and then have this other function handle it, writing that function is left as an exercise for the reader" which seems a bit silly to me.

Another assumption you're making is that we don't care about the original (relative) order of the 100 largest elements. Which I'd say is reasonable, but you may want to mention it.

There's no way in your solution to actually retrieve the numbers. Wrap it up as an object and provide some kind of accessor, nothing too complicated.

Minor complaint: you have inconsistent capitalisation on the start of your assumptions :eng101: .

Linear Zoetrope
Nov 28, 2011

A hero must cook
Well, it was in C, so there's no "object" to wrap it up in. The accessing is kind of just "access indices 0-arraySize". Such is the nature of C, even a struct wouldn't make sense there.

I do find the distinction between in-place insertion sort and an ordered list insertion basically meaningless. They seem to be equivalent statements to me (which is why I was clear it was an in-place sort, otherwise you're right). I felt "insertion sort" to be more evocative of the concept, but maybe I'm wrong.

I don't think C's standard library has collections built in, does it? I've always ended up writing them myself. I think if you want them you have to find packages like glib.

I guess part of my problem is that I think at an algorithmic level more than a code level? Now that you say it, I agree "the actual work is left up to the reader" is a bit silly, but I figured that insertion sort was such a bog-standard, common, implemented-everywhere algorithm that writing it would be "reinventing the wheel", which is a programming cardinal sin. In fact, I was worried that even explaining what it was would be patronizing to the interviewer. But I guess they asked me to do something so simple for a reason. And I did mention the linked list in the post-script :p.

As for the heap, I guess. I thought of it, since O(n) goes to O(log n) but a heap really seemed like overkill (unless that was a joke). I didn't want them to think I was overengineering it.

Edit: About insertion sort, I realize that strictly speaking it's actually a single step of insertion sort, rather than the full sorting algorithm, but a single step of an in-place insertion sort seems (to me) to be logically equivalent to an insertion sort assuming all the elements but one at a known position in the list are already ordered.

Linear Zoetrope fucked around with this message at 10:21 on Sep 25, 2013

Adbot
ADBOT LOVES YOU

FamDav
Mar 29, 2008

Jsor posted:

I guess part of my problem is that I think at an algorithmic level more than a code level?

are you sure about this?

quote:

I did mention the linked list in the post-script :p.

because this doesnt help you, asymptotically. in fact it might hurt you in actual measured performance depending on how you implement it.

quote:

As for the heap, I guess. I thought of it, since O(n) goes to O(log n) but a heap really seemed like overkill (unless that was a joke). I didn't want them to think I was overengineering it.

this, however, would. its the smart answer. keeping track of the "n most x things" is a task well suited to a heap.

would you have trouble writing a heap implementation in 5 minutes?

also you sound insufferable.

FamDav fucked around with this message at 10:33 on Sep 25, 2013

  • 1
  • 2
  • 3
  • 4
  • 5
  • Post
  • Reply