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
UnfurledSails
Sep 1, 2011

Okay I've figured it out. Start at the bottom left, call it [0][0], check the number. If it's not equal to the target, compare [1][0], t, and [0][1]. If t is equal to any of them you are done. If t is between the two values then start over with [1][1]. If t is less than [1][0] start over with [1][0]. If t is larger than [0][1] start over with [0][1].

That's a conceptual explanation, of course. There are some edge cases, such as when you are checking the topmost row or the rightmost column, but those are easily handled. The loop never iterates more than m+n times.

I had the right idea, but was looking at the top left corner instead of the bottom left corner. drat.

Adbot
ADBOT LOVES YOU

Pseudo-God
Mar 13, 2006

I just love oranges!

UnfurledSails posted:

Okay I've figured it out. Start at the bottom left, call it [0][0], check the number. If it's not equal to the target, compare [1][0], t, and [0][1]. If t is equal to any of them you are done. If t is between the two values then start over with [1][1]. If t is less than [1][0] start over with [1][0]. If t is larger than [0][1] start over with [0][1].

That's a conceptual explanation, of course. There are some edge cases, such as when you are checking the topmost row or the rightmost column, but those are easily handled. The loop never iterates more than m+n times.

I had the right idea, but was looking at the top left corner instead of the bottom left corner. drat.
Top-left works fine too.

shrughes
Oct 11, 2008

(call/cc call/cc)

Skuto posted:

This needs some elaboration, behind spoiler tags if you want.

The 2D array is a topographical map.

Hiowf
Jun 28, 2013

We don't do .DOC in my cave.

Pseudo-God posted:

Top-left works fine too.

I'm not convinced that will still give you O(m + n), though. The problem at the top left is that both edges go up, and you don't know how to choose between them. If you guess wrong, you won't reach O(m + n). The bottom left or top right do not have this issue.

Pseudo-God
Mar 13, 2006

I just love oranges!
Now that I reread UnfurledSails' answer, I can understand the logic of starting at the bottom left. I was thinking of a different solution, that started from the top left. Mine was something like this:
code:
Start from x=0,y=0, aka the top-left.
Recursive begin:
if [x][y] equals the target, we are done
else if [x][y+1] is less than or equal to target, repeat the process, starting from [x][y+1]
else if [x+1][y] ls less than or equal to target, repeat the process, starting from [x+1][y]
else target is not in array
This is a recursive implementation. Not included in the algorithm are the bounds checking and the memoization. At a glance, the running time seems to be less than O(nm), but more than O(n+m). If the solution is at the bottom right, it will find it in n+m, but I have not checked the other possibilities.

EDIT: In my implementation, if all values in the array are smaller than the target, except for the bottom row, which are greater, and [0][m], which is the target, the algorithm will take O(nm) time. So I guess it's no better than the naive solution.

Pseudo-God fucked around with this message at 08:50 on Jul 2, 2013

Zhentar
Sep 28, 2003

Brilliant Master Genius

Zero The Hero posted:

I feel like if I list my major GPA and not my overall GPA, it's going to bring attention to the fact that I don't want to list my overall GPA(2.8).
No poo poo, the whole point of listing your major GPA is to pick a higher number that looks better. You're not exactly pulling a fast one on us here. We don't give a gently caress, the CS courses are the part we care about anyway.

Zero The Hero posted:

So in the case of my "major GPA", I can list 3.3 as my own calculation including only my CS courses, and none of the math courses that were part of the CS major? Since my transcript doesn't list my major GPA and only my overall GPA?

Yeah, sure. That's a reasonable approach (and probably the one most people take). It's not like there's an official, standardized definition of "major GPA" to go off of.

No Safe Word
Feb 26, 2005

Zhentar posted:

Yeah, sure. That's a reasonable approach (and probably the one most people take). It's not like there's an official, standardized definition of "major GPA" to go off of.
You mean you don't know about the GAGPAAP (Generally Accepted
Grade Point Average Accounting Principles)?

wolffenstein
Aug 2, 2002
 
Pork Pro
Personal anecdote: I've been contacted much more in one day after posting my resume on dice than any other site in over three months.

But holy poo poo dice's site blows rear end.

Safe and Secure!
Jun 14, 2008

OFFICIAL SA THREAD RUINER
SPRING 2013
So if I can't afford to relocate, do I try to get a job within a couple hours distance of my home and work that until I can afford to leave, or apply to jobs in cities where I wouldn't mind living and see if any offers include relocation? Is it common enough for companies to offer relocation assistance to mediocre, fresh graduates that my first priority shouldn't be to find a job as close as possible to where I live?

Bhaal
Jul 13, 2001
I ain't going down alone
Dr. Infant, MD

Pseudo-God posted:

Now that I reread UnfurledSails' answer, I can understand the logic of starting at the bottom left. I was thinking of a different solution, that started from the top left. Mine was something like this:
code:
Start from x=0,y=0, aka the top-left.
Recursive begin:
if [x][y] equals the target, we are done
else if [x][y+1] is less than or equal to target, repeat the process, starting from [x][y+1]
else if [x+1][y] ls less than or equal to target, repeat the process, starting from [x+1][y]
else target is not in array
This is a recursive implementation. Not included in the algorithm are the bounds checking and the memoization. At a glance, the running time seems to be less than O(nm), but more than O(n+m). If the solution is at the bottom right, it will find it in n+m, but I have not checked the other possibilities.

EDIT: In my implementation, if all values in the array are smaller than the target, except for the bottom row, which are greater, and [0][m], which is the target, the algorithm will take O(nm) time. So I guess it's no better than the naive solution.

code:
Target: 24

 1  4 12 22 40
 7 11 21 24 44
10 14 22 34 48
16 21 26 36 50
26 30 31 45 51 

Your algo. will walk down the left column 1 -> 7 -> 10 -> 16 and then walk down the 4th row to -> 21 and halt without finding 24. You could modify the aglo to recursively split at every ([x][y+1], [x+1][y]) branch that is less than the target. That would leave the permutation of walking the top row 1 -> 4 -> 12 -> 22, and then down to 24, but meanwhile you're effectively traversing every tile that is less than the target, and will have to further implement something to control traversing areas covered in other chains (eg. you'd actually hit 24 through 3 additional branches unless you checked for it). It's not a very mathy approach but more of a visual one to see that the algorithm is still going to be covering a lot of ground (ie. m*n) to find a target number.

Instead like shrughes said, imagine that matrix as a height/topo map. You're looking at a hill and need to find elevation X. The contour might have dips and bulges but overall you're guaranteed to be going up if you head either east or south. One nice property is the "L" path from top left down south, then east to the bottom right will be uphill the whole way. So you start in the bottom left which is the median of one full uphill slope, and then only move north or east from there. If the elevation you're at is too high, go north, if it's too low, go east. Repeat until you either find your target or have no legal move to make, which will be when you reach somewhere along the north/east edges and the next step to take is out of bounds.

Again, visual and not mathy, what you've done is traced a contour around the hill, staying as close as you can to elevation X with each step. Looking at the area covered it's only a single path and not a dimensional area searched. I believe it is O(m+n) or I'm not sure if that reduces to O( max(m,n) ) or something like that, my big-o algebraic skills are pretty rusty, but it's definitely not O(m*n)

Bhaal fucked around with this message at 01:31 on Jul 3, 2013

Cicero
Dec 17, 2003

Jumpjet, melta, jumpjet. Repeat for ten minutes or until victory is assured.

Safe and Secure! posted:

So if I can't afford to relocate, do I try to get a job within a couple hours distance of my home and work that until I can afford to leave, or apply to jobs in cities where I wouldn't mind living and see if any offers include relocation? Is it common enough for companies to offer relocation assistance to mediocre, fresh graduates that my first priority shouldn't be to find a job as close as possible to where I live?
The major tech companies (Google, Apple, MS, et al.) universally offer relocation assistance. It's likely that any other companies that offer salaries in the same ballpark do as well. As you go down in salary and also in size of company, likelihood of relocation assistance drops, but I think there's a lot of variance.

Pseudo-God
Mar 13, 2006

I just love oranges!

Bhaal posted:

code:
Target: 24

 1  4 12 22 40
 7 11 21 24 44
10 14 22 34 48
16 21 26 36 50
26 30 31 45 51 

Your algo. will walk down the left column 1 -> 7 -> 10 -> 16 and then walk down the 4th row to -> 21 and halt without finding 24. You could modify the aglo to recursively split at every ([x][y+1], [x+1][y]) branch that is less than the target. That would leave the permutation of walking the top row 1 -> 4 -> 12 -> 22, and then down to 24, but meanwhile you're effectively traversing every tile that is less than the target, and will have to further implement something to control traversing areas covered in other chains (eg. you'd actually hit 24 through 3 additional branches unless you checked for it). It's not a very mathy approach but more of a visual one to see that the algorithm is still going to be covering a lot of ground (ie. m*n) to find a target number.

Instead like shrughes said, imagine that matrix as a height/topo map. You're looking at a hill and need to find elevation X. The contour might have dips and bulges but overall you're guaranteed to be going up if you head either east or south. One nice property is the "L" path from top left down south, then east to the bottom right will be uphill the whole way. So you start in the bottom left which is the median of one full uphill slope, and then only move north or east from there. If the elevation you're at is too high, go north, if it's too low, go east. Repeat until you either find your target or have no legal move to make, which will be when you reach somewhere along the north/east edges and the next step to take is out of bounds.

Again, visual and not mathy, what you've done is traced a contour around the hill, staying as close as you can to elevation X with each step. Looking at the area covered it's only a single path and not a dimensional area searched. I believe it is O(m+n) or I'm not sure if that reduces to O( max(m,n) ) or something like that, my big-o algebraic skills are pretty rusty, but it's definitely not O(m*n)
Due to the lovely pseudocode, the algorithm I wrote was not clear enough. The path it should take is 1 -> 7 -> 10 -> 16 -> 21 -> (back to 10)-> 14 -> 22 -> (back to 7) -> 11 -> 21 -> 24. Still O(nm).

Thanks for your explanation, I will check it out later.

Tres Burritos
Sep 3, 2009

Dear goons,

Doing my first ever fly out / stay at a hotel / do an interview. It's a relatively small company (30 people). Any advice?

baquerd
Jul 2, 2007

by FactsAreUseless

Tres Burritos posted:

Dear goons,

Doing my first ever fly out / stay at a hotel / do an interview. It's a relatively small company (30 people). Any advice?

Don't get drunk or do drugs in the hotel room. Don't crash your rental car, especially not while drunk. No prostitutes either. This is probably not the time to practice your auto-erotic asphyxiation routine. Don't bring a gun to the interview, but if you do, don't unholster it and show it to the interviewers. If you must kill someone in your hotel room, remember to have a plan to get rid of the body.

Also, get a good night's sleep, make sure your clothes are laid out for tomorrow morning, make sure you have directions to the interview place if they're not picking you up, plan to get there 15 minutes early and check if your route might have heavy traffic when you'll be driving, and relax. If you've prepped well this should be a night to briefly review things and then focus on getting comfortable and lots of rest. You might want to bring something to help you sleep if you're prone to insomnia when your mind may be racing.

Tres Burritos
Sep 3, 2009

baquerd posted:


Also, get a good night's sleep


Plane departs at 6:00AM

:suicide:

Chasiubao
Apr 2, 2010


Tres Burritos posted:

Plane departs at 6:00AM

:suicide:

Fly out the day before.

baquerd
Jul 2, 2007

by FactsAreUseless

Tres Burritos posted:

Plane departs at 6:00AM

:suicide:

Are they flying you out the day of the interview and then having you stay overnight then? That's rough.

Tres Burritos
Sep 3, 2009

baquerd posted:

Are they flying you out the day of the interview and then having you stay overnight then? That's rough.

Yeaaaahhh. I figure caffeine will be my greatest foe / ally.

Zero The Hero
Jan 7, 2009

I'm looking for some new personal projects to pick up that might help me get a better job. Something in C# probably, but I'm open to other things as well. What kind of projects impress employers, but are also plausible for someone to do on their own?

Stoph
Mar 19, 2006

Give a hug - save a life.

Zero The Hero posted:

I'm looking for some new personal projects to pick up that might help me get a better job. Something in C# probably, but I'm open to other things as well. What kind of projects impress employers, but are also plausible for someone to do on their own?

Over in web world a decent GitHub project is to build a gimmick SaaS with Stripe credit card integration. Bonus points if you build it as a single page application with a REST API. Bonus points if your repository provides bootstrap instructions with Vagrant and a configuration management tool like Chef.

DreadCthulhu
Sep 17, 2008

What the fuck is up, Denny's?!

Zero The Hero posted:

I'm looking for some new personal projects to pick up that might help me get a better job. Something in C# probably, but I'm open to other things as well. What kind of projects impress employers, but are also plausible for someone to do on their own?

Might also want to specify the kind of employers you're looking to impress and the kind of job you're looking for. The C# route is most direct for a generic Windows shop, but there are innumerable options depending what you want to do.

Zero The Hero
Jan 7, 2009

DreadCthulhu posted:

Might also want to specify the kind of employers you're looking to impress and the kind of job you're looking for. The C# route is most direct for a generic Windows shop, but there are innumerable options depending what you want to do.
I'm sorry, but I don't even know what you mean here. You mean that C# isn't specific enough? I don't really have a particular employer I'm trying to impress. I'm just trying to land an entry-level job where I can learn more about programming.

Stoph posted:

Over in web world a decent GitHub project is to build a gimmick SaaS with Stripe credit card integration. Bonus points if you build it as a single page application with a REST API. Bonus points if your repository provides bootstrap instructions with Vagrant and a configuration management tool like Chef.
This sounds good, but I don't know much about web. I've messed around with ASP.NET MVC, but I never used anything like GET or POST. I don't even know what that whole thing is. I'm not opposed to learning, but I don't know where to start, or if it's wise at this point in my not-yet-career. I kinda feel like I should just go with what I know best.

Zero The Hero fucked around with this message at 21:15 on Jul 7, 2013

Hughlander
May 11, 2005

DreadCthulhu posted:

Might also want to specify the kind of employers you're looking to impress and the kind of job you're looking for. The C# route is most direct for a generic Windows shop, but there are innumerable options depending what you want to do.

It's mostly a games thing but I find the exact opposite. Any time someone has C# on their resume I point blank ask, "Do you mean you used the .NET CLR or Unity 'scripting'?"

DreadCthulhu
Sep 17, 2008

What the fuck is up, Denny's?!

Zero The Hero posted:

I'm sorry, but I don't even know what you mean here. You mean that C# isn't specific enough? I don't really have a particular employer I'm trying to impress. I'm just trying to land an entry-level job where I can learn more about programming.

I think it just helps to know where you'd like to go when you're starting out and need to pick something. It'll help you focus on becoming as marketable as soon as possible, hopefully leading to a position somewhere. Maybe that's not the case with huge companies willing to invest in your over the years, but it won't hurt.

For example, if you want to work at a "cool web startup" in the Bay Area, you'll likely want to focus more on new web frameworks, various bash/ruby/python/JS etc. Becoming proficient in full-stack takes a while, so I'd probably just get one of those components down and start from there. E.g claim to be a front-end developer and spend your effort there at first.

Then again, if you want to do videogames at a big studio, there's a lot of focus on C++, OO, graphics programming and other stuff that doesn't overlap much with the web development world. E.g. the call of duty people use a custom brand of C, their own custom scripting language and occasionally some C# for tools, so you got to be pretty comfortable with low-level development.

Want enterprisey stuff? Then lean more on the Java/C# side of things with hefty frameworks like Spring. Want to be a mobile dev? etc etc. Obviously is super ballpark advice, but I'm just trying to give you an idea.

DreadCthulhu fucked around with this message at 21:39 on Jul 7, 2013

RICHUNCLEPENNYBAGS
Dec 21, 2010
Not really "getting a job," but it's probably OK to ask this here anyway. My employer is altering my role somewhat from sysadmin to a job that's a combination of a business analyst/requirements engineer/whatever other names they have for it and programmer/software engineer. I kind of get to participate in the crafting of a job description and all, which is great, but I'm stumped on one point: what kind of job titles make sense? It probably "shouldn't" matter but I imagine the title will have some influence on my future career trajectory. I've seen some job descriptions that sound similar with the title "Programmer Analyst," but is it even clear to people what that is?

NovemberMike
Dec 28, 2008

RICHUNCLEPENNYBAGS posted:

Not really "getting a job," but it's probably OK to ask this here anyway. My employer is altering my role somewhat from sysadmin to a job that's a combination of a business analyst/requirements engineer/whatever other names they have for it and programmer/software engineer. I kind of get to participate in the crafting of a job description and all, which is great, but I'm stumped on one point: what kind of job titles make sense? It probably "shouldn't" matter but I imagine the title will have some influence on my future career trajectory. I've seen some job descriptions that sound similar with the title "Programmer Analyst," but is it even clear to people what that is?

What percentage of each are you doing? Is it 50/50, 80/20, what? I'd be tempted to just call it "Lead Developer" or something, there's going to be an assumption that a developer is involved in at least some of the business planning and analysis.

coaxmetal
Oct 21, 2010

I flamed me own dad

Strong Sauce posted:

Whoa I am underpaid, and I am in SF!

coaxmetal
Oct 21, 2010

I flamed me own dad
I don't think entry level is quite 120 at most places. 90k is probably closer.

Cicero
Dec 17, 2003

Jumpjet, melta, jumpjet. Repeat for ten minutes or until victory is assured.

Ronald Raiden posted:

I don't think entry level is quite 120 at most places. 90k is probably closer.
I never said most places.

DreadCthulhu
Sep 17, 2008

What the fuck is up, Denny's?!
Btw people just starting out web development should checkout the Coursera Startup Engineering course going on right now. Everything in there looks very relevant, at least form the few lectures they posted so far.

RICHUNCLEPENNYBAGS
Dec 21, 2010

NovemberMike posted:

What percentage of each are you doing? Is it 50/50, 80/20, what? I'd be tempted to just call it "Lead Developer" or something, there's going to be an assumption that a developer is involved in at least some of the business planning and analysis.

I don't know exactly, but half-and-half is probably a fair guess. I think "Lead Developer" might be a little bit of a hard sell because 1) at some point I'll probably be producing requirements for things I'm not very involved in implementing (or just projects where the answer is to use an off-the-shelf solution and configure it) 2) my boss is also a developer and more experienced 3) the development team, such as it is, is basically me and my boss, so who am I leading?

kitten smoothie
Dec 29, 2001

DreadCthulhu posted:

Btw people just starting out web development should checkout the Coursera Startup Engineering course going on right now. Everything in there looks very relevant, at least form the few lectures they posted so far.

Yep. Even if you ignore the whole startup-oriented part of this, it's a pretty nice cursory introduction to git, Heroku, AWS, simple unix stuff, server-side JS, and web dev.

Good Will Hrunting
Oct 8, 2012

I changed my mind.
I'm not sorry.
Seconding this. It's very good. I am having trouble getting used to Emacs though.

Malcolm XML
Aug 8, 2009

I always knew it would end like this.
Importing this from the UKMT:

Basically I've got a London based offer (I'm a US citizen) for £49k salary, maybe £65k total comp if I'm feeling generous.

I also have an offer from a web based company in SF that's $100k salary, around $160k total compensation.

Same type of job, good companies in each case, good prospects for advancement etc.

From my experience in the UK £49k is excellent but it's like $73k in a major metropolitan city like SF which is peanuts compared to the other offer.

I'm obviously going to negotiate it up but is this normal?

Cicero
Dec 17, 2003

Jumpjet, melta, jumpjet. Repeat for ten minutes or until victory is assured.
UK salaries are definitely way lower than the US. Although US developer salaries are so high it's probably not that UK salaries are low in particular, I'd guess that they're not significantly lower than most other first-world countries.

I've never really heard a good explanation of why, though. UK tech companies are less profitable than US ones? UK has higher wages for lower-skilled jobs that flatten out the wage curve?

Cicero fucked around with this message at 01:57 on Jul 8, 2013

Malcolm XML
Aug 8, 2009

I always knew it would end like this.

Cicero posted:

UK salaries are definitely way lower than the US. Although US developer salaries are so high it's probably not that UK salaries are low in particular, I'd guess that they're not significantly lower than most other first-world countries.

I've never really heard a good explanation of why, though. UK tech companies are less profitable than US ones? UK has higher wages for lower-skilled jobs that flatten out the wage curve?

I'll add that this is with the UK branch of an American company so it's not like they can't afford it if they chose to.

Cicero
Dec 17, 2003

Jumpjet, melta, jumpjet. Repeat for ten minutes or until victory is assured.

Malcolm XML posted:

I'll add that this is with the UK branch of an American company so it's not like they can't afford it if they chose to.
I know someone who just went from working at a a major American tech company in Seattle to working at a different major American tech company in London and she had to take a 20% pay cut. Granted, that still puts her far above most other UK devs, but still, it's not like she'd be less effective as a developer in London, and London is a lot more expensive than Seattle, so...?

I just don't get it. My best guess is that since most of the really successful software companies are American their demand for devs is insatiable and they drive up the price of labor for the whole US software market.

NovemberMike
Dec 28, 2008

RICHUNCLEPENNYBAGS posted:

I don't know exactly, but half-and-half is probably a fair guess. I think "Lead Developer" might be a little bit of a hard sell because 1) at some point I'll probably be producing requirements for things I'm not very involved in implementing (or just projects where the answer is to use an off-the-shelf solution and configure it) 2) my boss is also a developer and more experienced 3) the development team, such as it is, is basically me and my boss, so who am I leading?

If you're writing code at least half the time I'd just call it a Senior Developer position or something similar. I guess the major thing would be whether you want to emphasize the sysadmin nature of it or the developer side. That's mostly going to be for future jobs so where do you want to go?

RICHUNCLEPENNYBAGS
Dec 21, 2010

Cicero posted:

I know someone who just went from working at a a major American tech company in Seattle to working at a different major American tech company in London and she had to take a 20% pay cut. Granted, that still puts her far above most other UK devs, but still, it's not like she'd be less effective as a developer in London, and London is a lot more expensive than Seattle, so...?

I just don't get it. My best guess is that since most of the really successful software companies are American their demand for devs is insatiable and they drive up the price of labor for the whole US software market.

I had the impression that this was a general phenomenon in the UK, that jobs simply paid less than American counterparts. I suppose this might be partially justified by more social services, but I don't know.

Adbot
ADBOT LOVES YOU

Safe and Secure!
Jun 14, 2008

OFFICIAL SA THREAD RUINER
SPRING 2013
Going through Coursera's old database class videos, and drat, my school sucked.

Homework assignments consisted of following instructions, step-by-step for each "problem". We would have dozens of such "problems", labeled by letter, with sub-steps labeled by numbers. For each instruction, we had to enter a SQL statement into MS SQL Server, take a screenshot of the results, resize that screenshot, and paste it into one big MS Word document for submission, since the program didn't have enough funding to justify offering a database course when the business school already had one.

We didn't even learn what indexes were. When we later implemented B-Trees for our actual CS classes, I heard that they were useful in database implementations, but I had no idea how they fit in.

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