|
FamDav posted:well, he says he wants the total amount of water left. you're going to need to store at list one extra number per column, so if thats not your output then yeah youre gonna need extra space. I think usually the idea is you just want the total units of water held in the shape at the end so you don't need any sort of output array just for the record here's a quick dirty linear-time constant-space solution I threw together Python code:
|
#
?
Feb 13, 2014 19:12
|
|
|
|
| # ? Jun 3, 2024 16:55 |
|
|
Steve French posted:I wonder how a solution that just counts overflows would compare, performance-wise. What exactly do you have in mind here?
|
|
#
?
Feb 13, 2014 20:13
|
|
|
Just had my two Amazon interviews. I think they went great. I answered all questions except one quickly and the interviewers seemed pleased with my answers. I created a bad O(n^2) solution to a string problem in the second interview, but when the interviewer said "think back to your first attempt and try to alter it", I got the O(n) answer instantly. They seemed interested in my projects and we had good dialogue at the end. If I don't get the job I'll be surprised and disappointed, but it's all up to Yeezus now. Shout out to Cicero for helping me prepare.
|
|
#
?
Feb 13, 2014 21:28
|
|
|
Isn't it a rite of passage to first give a O(n^2) answer then go "oh, duh" and actually do a dynamic programming, or sort the drat thing first?
|
|
#
?
Feb 13, 2014 21:33
|
|
|
2banks1swap.avi posted:Isn't it a rite of passage to first give a O(n^2) answer then go "oh, duh" and actually do a dynamic programming, or sort the drat thing first? Or use a hash table, but that's mostly for dorpping of a log n factor.
|
|
#
?
Feb 13, 2014 21:34
|
|
|
Skuto posted:What exactly do you have in mind here? If I had the time and energy I'd actually write up some C code, but I don't so I'll hastily describe it instead! Apologies for any mistakes or glaring omissions. At a high level it's the same general idea though, keeping a remainder and a dividend; except in this case the remainder is the running sum, the dividend is the number of overflows, and the divisor is the maximum integer value + 1. You can detect overflows when adding values A and B; if B is positive and A + B < A, there's an overflow. If B is negative and A + B > A, there was an underflow. On overflow, increment the overflow count, on underflow decrement it. Once you're done, you have the resulting sum, the number of overflows - underflows, and the number of values. Knowing the maximum integer value, you can then determine the average from that. As already mentioned, the details of this are architecture and implementation specific; you have to know the *actual* maximum integer value, maybe 2's complement isn't being used, the minimum value is probably off by one, etc etc. I should probably clarify (given some past discussions in this thread) that I'm not advocating this as a good answer to the interview question or as an implementation to be seriously used, but merely a point of curiosity. Steve French fucked around with this message at 22:39 on Feb 13, 2014 |
|
#
?
Feb 13, 2014 22:32
|
|
|
Rello posted:Just had my two Amazon interviews. I think they went great. 
|
|
#
?
Feb 13, 2014 22:37
|
|
|
shrughes posted:Or use a hash table, but that's mostly for dorpping of a log n factor. Or radix sort, always a fun trick to pull when you have an upper bound on bit length
|
|
#
?
Feb 13, 2014 22:40
|
|
|
Steve French posted:You can detect overflows when adding values A and B; if B is positive and A + B < A, there's an overflow. If B is negative and A + B > A, there was an underflow. On overflow, increment the overflow count, on underflow decrement it. Well in C or C++ check A > INT64_MAX - B and A < INT64_MIN - B instead. Afaict you're just describing a two digit base-2^64 number. (Or one with digit values ranging between INT_MIN and INT_MAX like the way balanced ternary does, which is acceptable.)
|
|
#
?
Feb 13, 2014 22:57
|
|
|
shrughes posted:Well in C or C++ check A > INT64_MAX - B and A < INT64_MIN - B instead. Yes, that's exactly it, and probably a better description than I gave. Your suggestion also avoids actually causing the overflow, which is much better, but would also result in more arithmetic operations? Probably insignificant. Also worth pointing out that if we're allowed to assume a 64-bit architecture, then it's important to consider whether we need to handle more than 2^32 numbers. If not, then just doing the simple naive thing works great; if we do, then it's also important to note in any other solution that uses the number of values directly must either assume a 64-bit architecture as well, or explicitly handle that case.
|
|
#
?
Feb 13, 2014 23:07
|
|
|
Steve French posted:If I had the time and energy I'd actually write up some C code, but I don't so I'll hastily describe it instead! What you described matches what I thought you had in mind. This is equivalent to just using 64-bit integers, unless I missed anything. There's a few cases where that is preferable to the interviewers solution, if the number of values exceeds (U)INT_MAX/2 you have no risk of overflow in the remainder part. Basically, 64-bit integers FTW.
|
|
#
?
Feb 13, 2014 23:09
|
|
|
Skuto posted:What you described matches what I thought you had in mind. This is equivalent to just using 64-bit integers, unless I missed anything. Yeah, I was writing it with the assumption that for whatever reason 64 bit integers weren't available for use; otherwise it's a sorta silly interview question, unless the solution has to handle an arbitrarily high number of 32 bit integers. But then the idea of having a machine that can only handle 32 bit integers but can somehow handle more than 2^32 of them is a bit odd (unless the context is some long running stream of numbers from some input device).
|
|
#
?
Feb 13, 2014 23:17
|
|
|
It's reasonable that the numbers would be 32-bit in order to save space. If you'd be using over 16GB of 32-bit integers, you probably don't want to change the code to use over 32GB of 64-bit integers instead. Suddenly computers get expensive.Steve French posted:Your suggestion also avoids actually causing the overflow, which is much better, but would also result in more arithmetic operations? Probably insignificant. More importantly it would avoid the undefined behavior and the likely optimization taking advantage of said behavior.
|
|
#
?
Feb 13, 2014 23:35
|
|
|
shrughes posted:It's reasonable that the numbers would be 32-bit in order to save space. If you'd be using over 16GB of 32-bit integers, you probably don't want to change the code to use over 32GB of 64-bit integers instead. Suddenly computers get expensive. Both given solutions use 2x32-bit integers, so it is the same. You can truncate the solution to 32-bits after calculating it in both circumstances. The interviewers solution doesn't use all 64-bits optimally, and gets into problems with more than (U)INT_MAX/2 inputs as described. The (IMHO) simpler solution of using 64-bit integers or emulating them as Steve French described does. My point is that these interview questions rely on the interviewee finding a "trick". This already sucks. It sucks even more if "trick" is worse than a native solution.
|
|
#
?
Feb 14, 2014 00:02
|
|
|
No, you misunderstand. Emulating 64-bit integers is not a correct solution. You need to emulate larger numbers than that.
|
|
#
?
Feb 14, 2014 00:10
|
|
|
The given (modulo/remainder) solution starts overflowing in the remainder if there's more than UINT_MAX/2 inputs, and given that each is an integer, that sums to UINT_MAX*UINT_MAX/2 at most. This is less than 64-bits. So using 64-bit arithmetic beats it. Am I totally missing something here? Hiowf fucked around with this message at 00:17 on Feb 14, 2014 |
|
#
?
Feb 14, 2014 00:15
|
|
|
Skuto posted:The given (modulo/remainder) solution starts overflowing in the remainder if there's more than UINT_MAX/2 inputs, and given that each is an integer, that sums to UINT_MAX*UINT_MAX/2 at most. If you're saying that having a 64-bit integer, or emulating a 64-bit integer, as Steve French does, suffices, then you are. You need to emulate a 64 + N bit integer for some large enough N. With just a 64 bit integer, you could overflow after you exceed 2^32 elements, i.e. a mere 16 GB array. So you need to use a two 64-bit integers, or three 32-bit integers, or in general one 64 + N bit integer, so that you don't overflow until after exceeding (16 * 2^N) GB. Pick a value of N that's reasonable. N=0 isn't (or is it?). N=1 might be (on most quad-core consumer procs that are limited to 32GB). N=6 would work if you only have 1 TB of RAM. Of course N is cheap, you've got a 64-bit word size, so just pick N=64, and do what Steve French said with two 64-bit integers instead of two 32-bit integers.
|
|
#
?
Feb 14, 2014 00:39
|
|
|
shrughes posted:With just a 64 bit integer, you could overflow after you exceed 2^32 elements, i.e. a mere 16 GB array. Right, I fully agree here. But the point is that the solution proposed by the interviewer will overflow after 2^31 elements, so it's worse given the same storage. Consider summing a total of 2^31+epsilon values, each value being UINT_MAX. The sum of UINT_MAX mod (2^31+eps) + UINT_MAX mod (2^31+eps) overflows the remainder storage. The naive, no tricks, solution only overflow after 2^32 elements.
|
|
#
?
Feb 14, 2014 01:07
|
|
|
shrughes posted:It's reasonable that the numbers would be 32-bit in order to save space. If you'd be using over 16GB of 32-bit integers, you probably don't want to change the code to use over 32GB of 64-bit integers instead. Suddenly computers get expensive. The last bit was just pointing out that it would seem silly to be restricted to 32-bit integer types while also having to deal with the possibility of more than 2^32 of them, since they would presumably not fit into memory. Hence the bit about a long running stream of numbers to allow for the possibility of more numbers than would fit in memory. In that case, we would obviously need a more robust solution that could handle an arbitrarily large number of inputs. In other words, at least one of the following must be true in order for the question and answer to make any reasonable sense: 1: we can use 64 bit integers 2: we don't have to worry about more than 2^32 inputs 3: we cannot assume that all integers fit into memory at once unless things are really weird and the computer can use >32-bit pointers and we can't use >32-bit integers. shrughes posted:More importantly it would avoid the undefined behavior and the likely optimization taking advantage of said behavior. Thanks, that's exactly what I meant. I know that it's undefined behavior, hence the disclaimer in my initial explanation. That said, since I can't help myself, what you said, strictly speaking, actually *almost guarantees* undefined behavior: shrughes posted:Well in C or C++ check A > INT64_MAX - B and A < INT64_MIN - B instead. 
|
|
#
?
Feb 14, 2014 01:26
|
|
|
INT64_MIN - B is what you want when B is negative.
|
|
#
?
Feb 14, 2014 01:42
|
|
|
shrughes posted:INT64_MIN - B is what you want when B is negative. Yeah, I know. I'm just saying you only want to do one or the other, depending on the sign of B, not both (as implied by your use of the word and). If B is negative, then INT64_MAX - B is undefined, otherwise INT64_MIN - B. And I'm also sure that you didn't actually mean that both should be calculated. I'm just heckling because I love you.
|
|
#
?
Feb 14, 2014 01:47
|
|
|
Steve French posted:(as implied by your use of the word and) Question time. What should I read to learn about making good architectural decisions? I'm good at fixing bugs and adding stuff to an existing codebase but I struggle to get new projects off the ground because I just sit there trying to figure out how it should all fit together and I don't really know. Specifically interested in Android but anything more general would be fine too. Tunga fucked around with this message at 02:40 on Feb 14, 2014 |
|
#
?
Feb 14, 2014 02:36
|
|
|
Holy crap. Just got my Amazon acceptance that was loving fast. Just told my brother, I didn't practice so hard because I wanted the money, that it was really good for my career, or to make my parents proud, but because some random guy on the internet took two and a half hours of his day to do a mock interview with me and help me prepare. So again a big thanks to Cicero.
|
|
#
?
Feb 14, 2014 02:40
|
|
|
Anyone have any tips on what to be prepared for with a remote pair programming session/interview thing? I'm sure it's a little bit out of the ordinary (although honestly it sounds like a great way to assess and applicant). It's for a Rails shop (hashrocket). I'm not too stressed about it, I just want to give myself any edge I can. They said all I needed is a computer with SSH. I'm not sure if they're just going to have me open a tunnel or if I should expect to be programming in VIM while they keep track of what I'm doing in a screen session or something. Also: Rello posted:So again a big thanks to Cicero.
|
|
#
?
Feb 14, 2014 02:45
|
|
|
Rello posted:Holy crap. Just got my Amazon acceptance that was loving fast. I just had the exact opposite experience. I first responded to an Amazon recruiter on LinkedIn on November 6. I had 3 phone interviews and then my on-site interviews two weeks ago. A week after those interviews I emailed the external recruiter (there were 3, the linkedin one, the external one that arranged all of the interviews, and then an internal one that I met with at amazon for a half hour) asking if a decision was made. He emailed back saying the team was meeting that day and I should hear back later that day, a Friday, or early next week. Cicero had said that typically the team gets together the next business day to make a decision. These people took a whole week. I wonder if they even remembered who I was. They didn't contact me that day or on Monday. Tuesday morning I sent an email to the internal recruiter. Wednesday nothing. Today I sent another email then went home from work sick. After a nap I decided that I finally completely fed up and called the internal recruiter. There was no answer and I had to leave a message. I also sent an email to the external recruiter asking if he could try contacting the internal recruiter for me, but I got a vacation auto-response. Finally an hour or so later the internal recruiter calls me and says they're not interested. This dude could've taken the 5 minutes to send me a form email saying this on the Friday that they made the decision, but instead waited nearly a week while ignoring my emails. This whole process was so drawn out (when scheduling phone interviews they always picked dates 1-2 weeks past my first available one and they picked an on-site a month and a half out) that I got a LinkedIn message from the first recruiter asking if I'm interested in jobs with Amazon's Logistics group (the same group as before)  .
|
|
#
?
Feb 14, 2014 03:19
|
|
|
seiken posted:I think usually the idea is you just want the total units of water held in the shape at the end so you don't need any sort of output array Ah, of course, that makes sense. I was going forwards and storing it all, then going backwards and storing it all. Then for each bar I took the minimum between the two passes. For my second approach I created a method that used a stack because I had just done the problem with the largest rectangle under a histogram, so I was convinced that the best solution to this one would be similar. Thanks!
|
|
#
?
Feb 14, 2014 03:32
|
|
|
perfectfire posted:I just had the exact opposite experience.... Ah, I'm sorry to hear that. I had an on campus interview for an internship position so I guess the decisions are much more streamlined :/.
|
|
#
?
Feb 14, 2014 04:49
|
|
|
perfectfire posted:I just had the exact opposite experience. I first responded to an Amazon recruiter on LinkedIn on November 6. I had 3 phone interviews and then my on-site interviews two weeks ago. A week after those interviews I emailed the external recruiter (there were 3, the linkedin one, the external one that arranged all of the interviews, and then an internal one that I met with at amazon for a half hour) asking if a decision was made. He emailed back saying the team was meeting that day and I should hear back later that day, a Friday, or early next week. Cicero had said that typically the team gets together the next business day to make a decision. These people took a whole week. I wonder if they even remembered who I was. I'm not sure you did yourself any favors by following up so aggressively, it sounds like you might have made a bad impression. Some good advice I read is that the hiring process feels much slower on your end than it does for the employees of the company you're interviewing with. It's probably a good idea to give them a few days before following up, and in the meantime continue your job search elsewhere so you're not obsessing over one opportunity. Having said that, I do sympathize. Some recruiters, even at awesome companies, are just legit bad. My first interview experience with Google was awful, the guy I did my first phone interview took *2 months* to submit his feedback, there's no way he remembered our interview. My recruiter was unresponsive, getting back to me days or weeks after she said she would. After a few weeks I had just written it off, then one day I randomly got a call saying the guy submitted his feedback and they wanted to do another phone interview, which I bombed. Then a different (awesome) Google recruiter contacted me a couple weeks later and skipped me ahead to an in person interview and the whole process took a couple weeks! So it definitely depends on your recruiter.
|
|
#
?
Feb 14, 2014 04:49
|
|
|
How many weeks should I wait to contact a recruiter so as not to give a bad impression?
|
|
#
?
Feb 14, 2014 05:29
|
|
|
Following up like that is fine. Saying that there'll be a decision made at a certain time and then not communicating for days after the target date is unprofessional, and it's completely reasonable for a candidate to ask for a response.Rello posted:Holy crap. Just got my Amazon acceptance that was loving fast. quote:Just told my brother, I didn't practice so hard because I wanted the money, that it was really good for my career, or to make my parents proud, but because some random guy on the internet took two and a half hours of his day to do a mock interview with me and help me prepare. edit: of course what I really mean is that you're obligated to spy on Amazon for me for my new Googly overlords. Hope you're comfortable with that. Cicero fucked around with this message at 06:12 on Feb 14, 2014 |
|
#
?
Feb 14, 2014 06:07
|
|
|
Cicero posted:edit: of course what I really mean is that you're obligated to spy on Amazon for me for my new Googly overlords. Hope you're comfortable with that. Can't you assholes do that yourselves 
|
|
#
?
Feb 14, 2014 06:49
|
|
|
perfectfire posted:How many weeks should I wait to contact a recruiter so as not to give a bad impression? Personally I think it's fine to contact them the day after you were expecting to hear back and didn't. But, if they don't respond immediately, I assume they are busy/lazy/a jerk and wait until the following week to try again. I agree with Cicero that it's super unprofessional for a recruiter not to contact you when they said they would - it seems like a central function of their job. But if they're ignoring your emails, emailing them every day just risks making you look pushy.
|
|
#
?
Feb 14, 2014 07:50
|
|
|
Motivated. It makes you look motivated.
|
|
#
?
Feb 14, 2014 13:42
|
|
|
perfectfire posted:How many weeks should I wait to contact a recruiter so as not to give a bad impression? I think you should maybe have called sooner. At the end of the interview or screen, they should say, "we'll get back to you in X days." If they don't, then part of your follow-up thank-you email should be, "what would you like our next step to be?" If they said they'd get back to you in a week, then I think you were completely justified in waiting a week and then badgering a bit for some kind of response. It's lovely when a company strings you along because maybe you're their 15th-best choice. Definitely don't slow down or halt your job search unless you've got a clear, "we're working on the offer letter and will have it for you in 2 days" kind of thing.
|
|
#
?
Feb 14, 2014 15:27
|
|
|
Last company I interviewed at told me three times that they would called me, including an email that said "I will call you right now" and I never heard back. I knew that it went badly so I just gave up. A week later they apparently remembered to remove my access from the BitBucket repo that was used for the programming exercise but still didn't bother to call me (and yes, it was the same person).
|
|
#
?
Feb 14, 2014 18:14
|
|
|
Cicero posted:of course what I really mean is that you're obligated to spy on Amazon for me for my new Googly overlords. Hope you're comfortable with that. 
|
|
#
?
Feb 14, 2014 18:35
|
|
|
Ugh, made a rookie mistake on N-queens; used a 2d array of cells instead of just maintaining a list of queens  Would you guys hold it against me if I just implemented backtracking instead of dancing links, which I didn't know well enough to suggest?
|
|
#
?
Feb 15, 2014 01:05
|
|
|
N-queens seems like a lousy interview question. You either know how to solve it and it's rote, or you don't and you make a 2d array. Unless you're requiring that the candidate have an AI background, what does that get you? Anyway, I think backtracking is perfectly fine.
|
|
#
?
Feb 15, 2014 02:20
|
|
|
Basically anybody worthwhile can figure it out if they haven't seen it, the trouble is the false positive rate with mediocre people that have seen it.
|
|
#
?
Feb 15, 2014 02:42
|
|
|
|
| # ? Jun 3, 2024 16:55 |
|
|
shrughes posted:Basically anybody worthwhile can figure it out if they haven't seen it, the trouble is the false positive rate with mediocre people that have seen it. Can everyone worthwhile who hasn't seen/isn't familiar with it figure it out in less than 30 minutes? I'm actually in the market for a new standard interview question (one of several technical in-person people), and this just doesn't seem like it meets the requirements of being simple enough to derive if you're pretty good but have no familiarity with the problem.
|
|
#
?
Feb 15, 2014 02:48
|
|
