Newbie Programming Interviews/Get a Job Megathread: Fake it 'til you make it

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Newbie Programming Interviews/Get a Job Megathread: Fake it 'til you make it

«‹›728 »

Rello: Jan 19, 2010

edit: bleh

Rello fucked around with this message at 07:21 on Dec 14, 2012

# ? Dec 13, 2012 22:49

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 00:56

double sulk: Jul 2, 2010

Tomorrow is my meeting and I'm trying to think about a few issues. I effectively worked around the salary question in the phone screen with a rough answer of "I am open to a fair offer based on the market rate and cost of living," and it hasn't been brought up since. I was, as mentioned before, told I did a great job on the coding project. I'm not trying to over-think the situation, but I assume that they are very serious about bringing me on if they are having me make a two hour trip.

What I'm wondering (and have asked a few people though), and am not 100% certain about just yet, is what I should be looking for as far as salary goes, as well as dealing with the cost of relocation. Apartments are not cheap in either Manhattan or Brooklyn, which is where I would need to be; it costs about 1600-2400 a month for a studio. I would very strongly prefer to live alone so I can have my privacy, hence those rates. My official title, as far as I am aware, would be as a Junior (Rails) Developer, but I've heard varying numbers in regards to what I should be looking for. Some people have said 70k minimum, and others have said 90k. 70k after taxes is about $46,000, based on salary calculators, which seems somewhat difficult to get by on comfortably.

Anyone familiar with the area who can give some advice is appreciated. I really want to think that they are planning to actually make an offer and not waste my time, even if I'm not taking a flight to get there.

# ? Dec 13, 2012 22:56

NovemberMike: Dec 28, 2008

Maybe something like this? Assuming a sorted list.

code:

for(i = 0; i < list.length - 1, i++) {
  for(j = i + 1; j < list.length; j++) {
    if(list[j] + list[i] == x) return (x,y);
    if(list[j] + list[i] > x) break;
  }
}

Plus some other crap to check if the numbers are obviously too large or too small (ie. if list[0] * 2 > x or list[list.length-1] * 2 < x return null, not sure what else). I'm not really sure this is worth spending the time optimizing more than this, it's something that computers are generally pretty good at.

EDIT: I guess you could do this:

code:

j = list.length - 1
for(i = 0; i < list.length - 1, i++) {
  while(j > i) {
    if(list[j] + list[i] == x) return (x,y);
    if(list[j] + list[i] < x) break;
    j--;
    if(j <= i) return null;
  }
}

NovemberMike fucked around with this message at 23:15 on Dec 13, 2012

# ? Dec 13, 2012 23:09

Null Pointer: May 20, 2004; Oh no!

how!! posted:

He told me me that my solution is better, but theres an even more optimized solution. At that point I pretty much realized he was looking for someone who thinks exactly like him, and that even if I were to happen to get the same solution as him, he is not the kind of person I want to work for. It wouldn't bother me so much if it weren't for the face that literally 99% of phone interviews end up like this.

You should study for your next interview by solving this problem for three numbers in polynomial time.

# ? Dec 13, 2012 23:28

Rurutia: Jun 11, 2009

Shouldn't using a hash set give you an O(n) solution?

# ? Dec 13, 2012 23:36

Pweller: Jan 25, 2006; Whatever whateva.

The whole point is that the solution itself doesn't even matter at all so long as you explain what you're thinking along the way and don't give up until the interviewer is satisfied.

# ? Dec 13, 2012 23:47

No Safe Word: Feb 26, 2005

Pweller posted:

The whole point is that the solution itself doesn't even matter at all so long as you explain what you're thinking along the way and don't give up until the interviewer is satisfied.

Though of note: sometimes interviewers intentionally say inaccurate things and want you to catch them. I don't love it when they do it, and I don't do it personally in my interviews, but it is A Thing, and I've had to deal with it myself.

# ? Dec 13, 2012 23:51

NovemberMike: Dec 28, 2008

Rurutia posted:

Shouldn't using a hash set give you an O(n) solution?

I'm not really sure how a hash set helps you here.

# ? Dec 13, 2012 23:58

Null Pointer: May 20, 2004; Oh no!

Pweller posted:

The whole point is that the solution itself doesn't even matter at all so long as you explain what you're thinking along the way and don't give up until the interviewer is satisfied.

That, and it's a tractable instance of a well-known NP-hard problem with obvious applications (think finance and manufacturing). I can't say I'd be very impressed if someone I interviewed told me that the problem is unrealistic or can be avoided through architecture.

# ? Dec 13, 2012 23:58

how!!: Nov 19, 2011; by angerbot

shrughes posted:

You also pulled the whole "I don't see how this is the sort of thing I'd ever face in practice" line, which basically means you might as well just hang up the phone. I got pulled that line after an interview, and I replied "Yeah, they're simplified versions of problems we do face in practice," only not really, I was much more gracious and specific in my response. I'm guessing that's not true of many places, instead it's their stand-in for an intelligence test. I think the interview process has three main things: Are you comfortable writing clean and nonfragile code? Are you going to walk us into a corner with terrible design decisions? Are you going to fit in well with the team? I think you mostly hurt most strongly with regard to the third question. After all, everybody does badly on an algorithmic problem solving question or two. You're pretty good with the first, from what I remember.

Real world problem solving is about understand the context surrounding the problem. A problem without context is not a problem, its a pointless puzzle. Why do you have a list of 1,000,000 integers? Why do you need to get numbers that add up to another number? What possible purpose does this code solve? Too much lovely code comes from by programmers who just mindlessly write code without considering the best possible solution.

I think the reason why I hate these kinds of questions is because they assume a "mode of operation" that is completely different than how I solve problems. My way of solving problems is to always step up to a higher level and fix it there, instead of dropping down to a lower level to solve the problem.

I was once asked in another interview how database indexes work. I answered "thats how you speed up queries. You add an index to a column that you query against and it makes selecting against that column much faster. The trade-off is that is slows down writes". The interviewer then asked me how they are implemented. I said "low level computer sciency stuff, linked lists and big O trees and crap, idk" (in other words, "don't know don't care"). He then proceeded to practically lecture me (in a respectful way) on how important it is to understand stuff from a low level. I fundamentally disagree with this sentiment. He explained to me that indexes use "B+ trees". Awesome bit of useless trivial there. I'll kep that in mind next time I have to write a database engine from scratch, because obviously its a great idea to do that from time to time. Have a bunch of data? Why put it in a database, you know B+ TREES!! WRITE YOUR OWN!!! YAY! I'M SO SMART!

I have no loving clue how stuff works under the hood most of the time, and it has no effect on my ability to solve problems. I'd rather spend one hour learning how to use postgres better, than one hour learning how postgres is implemented. That is what makes projects like postgres so great. They handle all the complex stuff so I don't have to.

Pweller posted:

The whole point is that the solution itself doesn't even matter at all so long as you explain what you're thinking along the way and don't give up until the interviewer is satisfied.

Why does that matter? How does "showing your thinking process" solve business problems? In the real world, solutions matter, not thinking processes.

# ? Dec 14, 2012 00:06

NovemberMike: Dec 28, 2008

Oh god now I understand why everyone thinks you're an idiot.

# ? Dec 14, 2012 00:08

No Safe Word: Feb 26, 2005

how!! posted:

I was once asked in another interview how database indexes work. I answered "thats how you speed up queries. You add an index to a column that you query against and it makes selecting against that column much faster. The trade-off is that is slows down writes". The interviewer then asked me how they are implemented. I said "low level computer sciency stuff, linked lists and big O trees and crap, idk" (in other words, "don't know don't care"). He then proceeded to practically lecture me (in a respectful way) on how important it is to understand stuff from a low level. I fundamentally disagree with this sentiment.

Well this isn't going to win you any favor with interviewers (nor will it help your career).

Nobody's expecting you to write your own database, but understanding the mechanics behind them and the consequences of your actions allows you to make better decisions. Willful ignorance isn't a sought-after quality.

how!! posted:

Why does that matter? How does "showing your thinking process" solve business problems? In the real world, solutions matter, not thinking processes.

And, as you've pointed out, in an interview you're not solving a real world problem, so the solution is NOT the end-game.

# ? Dec 14, 2012 00:10

how!!: Nov 19, 2011; by angerbot

No Safe Word posted:

Well this isn't going to win you any favor with interviewers (nor will it help your career).

Nobody's expecting you to write your own database, but understanding the mechanics behind them and the consequences of your actions allows you to make better decisions. Willful ignorance isn't a sought-after quality.

Theres a difference between knowing how to use technology and how technology is implemented.

Developer A know the ins and outs of Django's ORM. If Django's ORM can do it, he knows how. Developer A has absolutely no idea how the internals of Django's ORM works. All he knows is you construct the query object, cast it to a list, and then magic happens.

Developer B knows everything there is to know about linked lists and big O and B+ trees, but knows nothing about the Django ORM.

Which developer would you rather hire to be on your Django development team?

quote:

And, as you've pointed out, in an interview you're not solving a real world problem, so the solution is NOT the end-game.

Part of my real world problem solving process is to find as much context as possible. What problem are you solving? Where is this big list of integers coming from? How fast does it need to be? What is the time frame for a solution? Interview problems do not have answers for these types of questions.

# ? Dec 14, 2012 00:27

Null Pointer: May 20, 2004; Oh no!

how!! posted:

Real world problem solving is about understand the context surrounding the problem. A problem without context is not a problem, its a pointless puzzle. Why do you have a list of 1,000,000 integers? Why do you need to get numbers that add up to another number? What possible purpose does this code solve?

I have a mutual fund which holds 1,000,000 bonds of various values. A client wants to withdraw $k from the fund. What bonds do I sell?

What a contrived problem. :allears:

# ? Dec 14, 2012 00:28

No Safe Word: Feb 26, 2005

how!! posted:

Developer A know the ins and outs of Django's ORM. If Django's ORM can do it, he knows how. Developer A has absolutely no idea how the internals of Django's ORM works. All he knows is you construct the query object, cast it to a list, and then magic happens.

Developer B knows everything there is to know about linked lists and big O and B+ trees, but knows nothing about the Django ORM.

Which developer would you rather hire to be on your Django development team?

If Developer A continues to refuse to look under the hood of any other technology, then Developer B.

Disclosure: I do consulting work, so "knows the specific topic inside and out" is naturally not a hard requirement to me while "can quickly learn things" is far more desirable.

# ? Dec 14, 2012 00:30

Che Delilas: Nov 23, 2009; FREE TIBET WEED

how!! posted:

Why does that matter? How does "showing your thinking process" solve business problems? In the real world, solutions matter, not thinking processes.

So you go directly from "problem statement" to "finished solution" without any thinking? The point is that the interviewer needs to know that you're capable of going from the first thing to the second thing, even if the solution doesn't exist online somewhere.

Also it sometimes happens that the point is to suss out whether a candidate is an obstinate twat with no flexibility or ability to work with any other human being on the planet.

# ? Dec 14, 2012 00:34

how!!: Nov 19, 2011; by angerbot

Null Pointer posted:

I have a mutual fund which holds 1,000,000 bonds of various values. A client wants to withdraw $k from the fund. What bonds do I sell?

What a contrived problem.

Is this data in a database? What does the schema look like? The best way is to construct a query of some sort to get the data we need. Databases are great at doing that sort of thing. How often does this program need to run? What happens when there is no possible solution? What kind of hardware is this running on? How often is the database being written to?

Che Delilas posted:

So you go directly from "problem statement" to "finished solution" without any thinking? The point is that the interviewer needs to know that you're capable of going from the first thing to the second thing, even if the solution doesn't exist online somewhere.

Also it sometimes happens that the point is to suss out whether a candidate is an obstinate twat with no flexibility or ability to work with any other human being on the planet.

When you're asked a question over the phone, you're expected to have an answer without doing too much thinking. I don't think too well aloud. I even explained to the interviewer that I do my best thinking when I'm alone with my thoughts, not when I have a phone to my ear talking to a stranger. I can't tell you how many times I've solved a problem while standing in front of a urinal or on teh drive home, or some other place not in front of a computer.

how!! fucked around with this message at 00:41 on Dec 14, 2012

# ? Dec 14, 2012 00:37

Null Pointer: May 20, 2004; Oh no!

how!! posted:

Databases are great at doing that sort of thing.

Ah yes, the infamous SUBSET_SUM aggregation operator. I think they added that in SQL 2192.

# ? Dec 14, 2012 00:40

shrughes: Oct 11, 2008; (call/cc call/cc)

how!! posted:

I was once asked in another interview how database indexes work. I answered "thats how you speed up queries. You add an index to a column that you query against and it makes selecting against that column much faster. The trade-off is that is slows down writes". The interviewer then asked me how they are implemented. I said "low level computer sciency stuff, linked lists and big O trees and crap, idk" (in other words, "don't know don't care"). He then proceeded to practically lecture me (in a respectful way) on how important it is to understand stuff from a low level. I fundamentally disagree with this sentiment. He explained to me that indexes use "B+ trees". Awesome bit of useless trivial there. I'll kep that in mind next time I have to write a database engine from scratch, because obviously its a great idea to do that from time to time. Have a bunch of data? Why put it in a database, you know B+ TREES!! WRITE YOUR OWN!!! YAY! I'M SO SMART!

But understanding what B-trees are, how they work, and what their performance implications are, are very useful for imagining how an SQL engine might execute your query. If you have a query that's too slow and "adding more indexes" doesn't make it faster, what do you do? Somebody that understands how a join might be evaluated will much more quickly solve the problem.

# ? Dec 14, 2012 00:41

how!!: Nov 19, 2011; by angerbot

shrughes posted:

But understanding what B-trees are, how they work, and what their performance implications are, are very useful for imagining how an SQL engine might execute your query. If you have a query that's too slow and "adding more indexes" doesn't make it faster, what do you do? Somebody that understands how a join might be evaluated will much more quickly solve the problem.

I think thats a stretch to assume that. I've worked with CompSci people who had oceans of knowledge when it came to exotic data structures and low level things like that, but those guys never use that knowledge. Knowing Postgres specifics will do you much more good than knowing B+ trees.

# ? Dec 14, 2012 00:48

Zhentar: Sep 28, 2003; Brilliant Master Genius

I can state, from first hand experience, that it is not a stretch and understanding B-trees can in fact be beneficial to understanding weird edge-case database behavior.

# ? Dec 14, 2012 01:03

shrughes: Oct 11, 2008; (call/cc call/cc)

how!! posted:

I think thats a stretch to assume that. I've worked with CompSci people who had oceans of knowledge when it came to exotic data structures and low level things like that, but those guys never use that knowledge. Knowing Postgres specifics will do you much more good than knowing B+ trees.

Here you are saying sentences that are not even wrong. At what point does the marginal value/cost of the next bit of Postgres knowledge you might learn fall below that of understanding how B+ trees work?

If you were an opinion-haver that made sense, you would write your response in terms of that question. Instead you treat Postgres specifics as some complete, well-defined set of knowledge, as if it's more important to know that Postgres has two different factorial operators than it is understanding how B+ trees work.

I've never seen somebody argue so strongly about the unimportance of knowledge they don't have, and think they're winning this argument against people that do have that knowledge and find it to be quite useful.

# ? Dec 14, 2012 01:09

how!!: Nov 19, 2011; by angerbot

If you have a query that is slow, the only way to fix that problem is to tweak settings, or re-write your query. This is all high level stuff compared to B-trees and linked lists. You obviously not going to go into Postgres's code and rewrite the low level code that actually deals with the B+tree implementation. Postgres is open source, so you technically could, but I think doing that is the wrong way to fixing whatever problem is making your query slow. Just like I feel strongly against dropping down to raw SQL when using an ORM. Sometimes I feel like dropping down to a lower level to solve a problem is like taking the easy way out. It may seem clever at the time, but it increases complexity and makes for hard to maintain code.

# ? Dec 14, 2012 01:23

Smugdog Millionaire: Sep 14, 2002; 8) Blame Icefrog

how!! posted:

In real life, being faced with problems like these means you have bigger problems, IMO. Instead of trying to optimize through these types of algorithms, its best to redesign the system itself that makes this type of problem happen in the first place.

In real life, employers would like to hire engineers that can solve hard problems instead of saying "doing [X] is hard, can we do [Y] instead?" Sometimes [Y] simply isn't a substitute and you have to solve real algorithmic problems.

I work at a company that does this constantly, changing requirements to make it easier to build. We do it because profit comes from billing the client for the time it would take to build [X] but only taking the time to build [Y]. Also because we're lazy.

# ? Dec 14, 2012 01:26

New Yorp New Yorp: Jul 18, 2003; Only in Kenya.; Pillbug

gucci void main posted:

Tomorrow is my meeting and I'm trying to think about a few issues. I effectively worked around the salary question in the phone screen with a rough answer of "I am open to a fair offer based on the market rate and cost of living," and it hasn't been brought up since. I was, as mentioned before, told I did a great job on the coding project. I'm not trying to over-think the situation, but I assume that they are very serious about bringing me on if they are having me make a two hour trip.

What I'm wondering (and have asked a few people though), and am not 100% certain about just yet, is what I should be looking for as far as salary goes, as well as dealing with the cost of relocation. Apartments are not cheap in either Manhattan or Brooklyn, which is where I would need to be; it costs about 1600-2400 a month for a studio. I would very strongly prefer to live alone so I can have my privacy, hence those rates. My official title, as far as I am aware, would be as a Junior (Rails) Developer, but I've heard varying numbers in regards to what I should be looking for. Some people have said 70k minimum, and others have said 90k. 70k after taxes is about $46,000, based on salary calculators, which seems somewhat difficult to get by on comfortably.

Anyone familiar with the area who can give some advice is appreciated. I really want to think that they are planning to actually make an offer and not waste my time, even if I'm not taking a flight to get there.

90k for a junior position is absurd even in NYC. 65-75 is pretty fair. I think your tax calculations are off, though. I don't get taxed anywhere near that much. I don't have the numbers in front of me, but I have about 28% of my paycheck deducted for taxes. I also don't live in NYC and make more than 70k, so your mileage may vary.

Consider living in Hoboken or Jersey city and commuting if you take the job. It will be a LOT cheaper. Or anywhere along the northeast corridor NJ Transit line; I used to live in New Brunswick and could be at penn station in an hour, which isn't bad. I paid $1150 for a pretty spacious one bedroom apartment there.

New Yorp New Yorp fucked around with this message at 01:33 on Dec 14, 2012

# ? Dec 14, 2012 01:27

it is: Aug 19, 2011; by Smythe

O(N) solution

code:

public boolean findSum(int[] ints, int sum) {
  HashSet<Integer> intSet = new HashSet<Integer>();
  for(int i : ints) intSet.add(i);
  for(int i : intSet) if(intSet.contains(sum-i)) return true;
  return false;
}

I have a significantly easier time with these questions than lots of my peers who are much better developers and have an easier time getting a job as a result. Learn your data structures! And get better at figuring out who crappy new hires are.

# ? Dec 14, 2012 01:32

Steve French: Sep 8, 2003

how!! posted:

I have no loving clue how stuff works under the hood most of the time, and it has no effect on my ability to solve problems.

How do you know you wouldn't be better at solving problems if you knew how stuff works under the hood if you haven't tried it?

how!! posted:

I'd rather spend one hour learning how to use postgres better, than one hour learning how postgres is implemented.

Maybe learning how postgres is implemented also learns you how to use postgres more betterer

how!! posted:

Developer A know the ins and outs of Django's ORM. If Django's ORM can do it, he knows how. Developer A has absolutely no idea how the internals of Django's ORM works. All he knows is you construct the query object, cast it to a list, and then magic happens.

Developer B knows everything there is to know about linked lists and big O and B+ trees, but knows nothing about the Django ORM.

Which developer would you rather hire to be on your Django development team?

Developer B, no question. He'll be able to pick up on Django a lot loving faster than developer A will be able to learn basic computer science.

# ? Dec 14, 2012 01:37

shrughes: Oct 11, 2008; (call/cc call/cc)

how!! posted:

If you have a query that is slow, the only way to fix that problem is to tweak settings, or re-write your query.

... Of course you rewrite the query! The question is, how do you rewrite the query? Guess what: people who have a general gasp at what a b-tree is are better at rewriting the query than you are.

# ? Dec 14, 2012 01:49

shrughes: Oct 11, 2008; (call/cc call/cc)

it is posted:

O(N) solution

Basically when you're given an algorithmic question you should always try to answer it twice. First, you answer the question, then you put on your hash table glasses and answer the question.

# ? Dec 14, 2012 01:54

how!!: Nov 19, 2011; by angerbot

Steve French posted:

How do you know you wouldn't be better at solving problems if you knew how stuff works under the hood if you haven't tried it?

Because there is always a high level work around that results in better, more maintainable code. For instance, right now I'm writing a python framework (https://github.com/priestc/giotto). I ran into a problem earlier today where I needed to write a MIME type parser. Instead of spending all day reading RFC's and technical documents on how MIME types are constructed, I found this: http://code.google.com/p/mimeparse/ which pretty much lets me nothink about how MIME types work at all. If, for some reason that library doesn't cut it, I may have no choice but to spend the hours becoming an expert on MIME types. This is not the best example because MIME types aren't really that complex...

I guess what I'm trying to say is that I have no idea how B+trees work because I've never had the opportunity to solve a problem that required B+ tree knowledge.

quote:

Maybe learning how postgres is implemented also learns you how to use postgres more betterer

Does learning the specific details on how Facebook stores their data help you better use the Facebook API?

quote:

Developer B, no question. He'll be able to pick up on Django a lot loving faster than developer A will be able to learn basic computer science.

Developer A learned Django ORM, what makes you think he couldn't learn "basic compsci"? Do you think compsci stuff is fundamentally harder to learn that 3rd party API?

# ? Dec 14, 2012 01:55

shrughes: Oct 11, 2008; (call/cc call/cc)

how!! posted:

Developer A learned Django ORM, what makes you think he couldn't learn "basic compsci"? Do you think compsci stuff is fundamentally harder to learn that 3rd party API?

If it's so easy, why do you suck at it?

# ? Dec 14, 2012 01:56

awesmoe: Nov 30, 2005; Pillbug

e: nm I kind of misread the point. However if you only learn things you're required to learn, why would someone want to hire you over someone else?

# ? Dec 14, 2012 02:03

Steve French: Sep 8, 2003

how!! posted:

Because there is always a high level work around that results in better, more maintainable code. For instance, right now I'm writing a python framework (https://github.com/priestc/giotto). I ran into a problem earlier today where I needed to write a MIME type parser. Instead of spending all day reading RFC's and technical documents on how MIME types are constructed, I found this: http://code.google.com/p/mimeparse/ which pretty much lets me nothink about how MIME types work at all. If, for some reason that library doesn't cut it, I may have no choice but to spend the hours becoming an expert on MIME types. This is not the best example because MIME types aren't really that complex...

I guess what I'm trying to say is that I have no idea how B+trees work because I've never had the opportunity to solve a problem that required B+ tree knowledge.

Does learning the specific details on how Facebook stores their data help you better use the Facebook API?

The thing you seem to be misunderstanding is that we're not saying you should know how B+ trees and database internals work so that you can solve problems with postgres by hacking postgres source code. Abstractions in real life are not perfect. There are performance (and other) implications of how you use things that are not necessarily exposed in an interface. We're suggesting that knowing how postgres works makes you more likely to understand why things are going wrong, and how to use it better.

Can knowing how CPU caching works help you write faster C code, even though that is not part of the C language and standard library interface? Yes
Can knowing how HDDs and SSDs work help you write faster database or filesystem code, even though that is not part of the block device interface? Yes

how!! posted:

Developer A learned Django ORM, what makes you think he couldn't learn "basic compsci"? Do you think compsci stuff is fundamentally harder to learn that 3rd party API?

Yes

# ? Dec 14, 2012 02:06

Strong Sauce: Jul 2, 2003; You know I am not really your father.

it is posted:

O(N) solution
code:
public boolean findSum(int[] ints, int sum) {
  HashSet<Integer> intSet = new HashSet<Integer>();
  for(int i : ints) intSet.add(i);
  for(int i : intSet) if(intSet.contains(sum-i)) return true;
  return false;
}
I have a significantly easier time with these questions than lots of my peers who are much better developers and have an easier time getting a job as a result. Learn your data structures! And get better at figuring out who crappy new hires are.

List: [1,3]
Find: 6

# ? Dec 14, 2012 02:12

FamDav: Mar 29, 2008

how!! posted:

If you have a query that is slow, the only way to fix that problem is to tweak settings, or re-write your query.

What Shrughes is arguing is that having knowledge of the underly mechanics of the particular database will help you solve this problem, usually in a more efficient manner. Moreso, it allows you to rigorous prove your claim that your solution is really better than the rest.

Also, for everybody giving bad answers to the interview problem:

given list L, sort L. Let A,B be bidirectional iterations pointing to the first and last elements of L respectively. We then find if there exist two elements a,b in L such that a+b=c by:

code:

While *A < *B:
  if *A + *B = c then return (*A,B)
  else if *A + *B > C then B--
  else A++
end

return false

The binary search doesn't hurt your performance in terms of algorithmic complexity, but you don't have to.

# ? Dec 14, 2012 02:13

Null Pointer: May 20, 2004; Oh no!

Computer Science degrees are useless because as far as I could tell the people I used to work with (before I got fired for incompetence) never used their degrees for anything. That's why I deserve a pass for not understanding basic theory, or even giving enough of a poo poo about my own field to pick up a copy of CLRS. Also, you know, CLRS is a really heavy book, and it's all the way on the top shelf, so it's totally unreasonable for you to expect me to learn any of it.

Sigh. Well, if you're going to insist on asking me a theory question, at least give me a few hours to look it up on Google first.

# ? Dec 14, 2012 02:13

shrughes: Oct 11, 2008; (call/cc call/cc)

FamDav posted:

Also, for everybody giving bad answers to the interview problem:

That's already been mentioned upthread.

# ? Dec 14, 2012 02:17

FamDav: Mar 29, 2008

Null Pointer posted:

Computer Science degrees are useless because as far as I could tell the people I used to work with (before I got fired for incompetence) never used their degrees for anything. That's why I deserve a pass for not understanding basic theory, or even giving enough of a poo poo about my own field to pick up a copy of CLRS. Also, you know, CLRS is a really heavy book, and it's all the way on the top shelf, so it's totally unreasonable for you to expect me to learn any of it.

Sigh. Well, if you're going to insist on asking me a theory question, at least give me a few hours to look it up on Google first.

https://github.com/priestc/interview-crap/blob/master/hiring-outline.txt

# ? Dec 14, 2012 02:29

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

how!! posted:

Is this data in a database? What does the schema look like? The best way is to construct a query of some sort to get the data we need. Databases are great at doing that sort of thing. How often does this program need to run? What happens when there is no possible solution? What kind of hardware is this running on? How often is the database being written to?

I know you're just being an obstinate idiot, but I'm curious if there's a point at which you would intend to stop being useless and actually answer the question, so I'll bite.

Let's say you're interviewing with me, and you asked all those context questions, and for some reason instead of booting you straight out the door I just grabbed a laptop and setup an environment for you.

Here's a schema:

SQL code:

create table bonds ( bond_name text not null unique, bond_value int not null );
create index bonds_value on bonds ( bond_value );

This is actually running on a Postgres database on my laptop, with ten thousand rows in the bonds table. The laptop is a few years old, and there's other crap running on it right now. I won't be making any more writes to it, and the two indexes have up-to-date statistics, and the table is vacuumed and contiguous and clustered on the unique index. Column bond_name is 8-alphanumeric-character approximately uniformly distributed random strings, column bond_value is approximately gaussian distributed random numbers with μ=1000 and σ=200.

I want a query that will, given a goal value as a parameter, return a row with two columns, each a value from the bond_name column of the table, such that the sum of the bond_values that correspond to those bond_names adds to the goal. If there are multiple solutions possible, you may provide them as extra rows if you want. If there is no solution possible, you may either provide no rows or you may provide a row with two NULL values; I don't care which.

I have PL/pgSQL, PL/Tcl, PL/Perl, PL/Python, and PL/R installed. If you want a different language installed, I'll be happy to do so.

Would this be enough for you to answer a simple interview question? Do you really think your answer to this particular question is going to be any more interesting to an interviewer than solving the same algorithm on arrays? Do you honestly expect that any interviewer would put up with wasting the time to setup such an environment for someone who can't answer a basic computer science question?

# ? Dec 14, 2012 02:29

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 00:56

Rothon: Jan 4, 2012

Strong Sauce posted:

List: [1,3]
Find: 6

You can easily modify that solution to properly detect repeated digits.

# ? Dec 14, 2012 02:38

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Newbie Programming Interviews/Get a Job Megathread: Fake it 'til you make it

«‹›728 »