|
Steve French posted:Also, your proposed partial solution doesn't handle multiple concatenations in a row (e.g 123 +/- 4, etc) When I mentioned it was the time the interviewer realized we needed to move on to more mundane stuff like "prove you can do knockout" and "can you do markup." But that DOES limit the problem space a little! Is this a subset of the knapsack problem?
|
#
?
Oct 30, 2014 03:09
|
|
|
|
| # ? Apr 23, 2024 15:33 |
|
|
Yeah basically between each number you have the choice of three operations - concat, plus, or minus, meaning that it's definitely 3^n operations (n being the number of digits minus one - you'd be evaluating n^8 paths in the original 9-digit problem) for the brute force solution. It seems like a really tough question to find a better solution for. My first inclination is to somehow optimize around the ones digit evaluating to zero - like, you know that an odd number of the odd numbers will have to be in the tens or greater digit for a concatenation. But then I'm stuck for now, outside of other chickenshit optimizations (like not being able to concatenate more than three digits at a time). No Wave fucked around with this message at 03:39 on Oct 30, 2014 |
|
#
?
Oct 30, 2014 03:25
|
|
|
No Wave posted:Yeah basically between each number you have the choice of three operations - concat, plus, or minus, meaning that it's definitely 3^n operations (n being the number of digits minus one - you'd be evaluating n^8 paths in the original 9-digit problem) for the brute force solution. IIRC you can only concat two at a time before you had to have a plus or minus in between. One idea I had is as you went down the sequence, keep track of paths that add up to a given number, and from there think "do I need to go up" or "do I need to go down" to reach 100, or any other number. Is this practical with going down a tree?
|
|
#
?
Oct 30, 2014 03:44
|
|
|
gently caress them posted:IIRC you can only concat two at a time before you had to have a plus or minus in between. 123 - 4 - 5 - 6 - 7 + 8 - 9 = 123 - 22 - 1 = 123 - 23 = 100
|
|
#
?
Oct 30, 2014 03:48
|
|
|
Jsor posted:123 - 4 - 5 - 6 - 7 + 8 - 9 = 123 - 22 - 1 = 123 - 23 = 100 I mean in the problem space you're not allowed to cat 3 together, not that you couldn't do it and get to 100.
|
|
#
?
Oct 30, 2014 03:50
|
|
|
Dynamic programming and meet-in-the-middle are straightforward optimizations to make.
|
|
#
?
Oct 30, 2014 03:55
|
|
|
sarehu posted:Dynamic programming and meet-in-the-middle are straightforward optimizations to make.
|
|
#
?
Oct 30, 2014 03:58
|
|
|
undo, concat, redo
|
|
#
?
Oct 30, 2014 04:09
|
|
|
No Wave posted:How would you do it? I'm having trouble figuring out how it would work with the concat. Keep trying!
|
|
#
?
Oct 30, 2014 04:21
|
|
|
Seems like meet-in-the-middle makes the correct solution obvious, especially given:gently caress them posted:IIRC you can only concat two at a time before you had to have a plus or minus in between. But I wouldn't have figured it out had shrughes not suggested it, because this is the first time I've heard of meet-in-the-middle and I googled what it meant, which led to a subset sum solution. I'm guessing my education was basically substandard, though.
|
|
#
?
Oct 30, 2014 04:43
|
|
|
This isn't a great interview response, but for a problem like that gently caress the optimizations. 3^9 is 19683. You'll spend more time on one optimization than it will take to run the whole program.
|
|
#
?
Oct 30, 2014 04:49
|
|
|
Bognar posted:This isn't a great interview response, but for a problem like that gently caress the optimizations. 3^9 is 19683. You'll spend more time on one optimization than it will take to run the whole program. And if the interviewer really wants to get into the optimizations, they'll tell you to do it in base 25 or something with minimal runtime. I do something like that where I permute the parentheses problem into a multi-threaded problem that would only make sense in very specific hardware circumstances which aren't practical. Interviewees get points for noting that it doesn't normally make sense.
|
|
#
?
Oct 30, 2014 04:55
|
|
|
Bognar posted:This isn't a great interview response, but for a problem like that gently caress the optimizations. 3^9 is 19683. You'll spend more time on one optimization than it will take to run the whole program. If I wanted this to work for any number of digits that optimization might matter. 3^n can get big p fast. But for 3^9 yeah, who cares.
|
|
#
?
Oct 30, 2014 04:57
|
|
|
Is there a real-world application to that type of problem, or is it just something that interviewers do to see how you solve problems?
|
|
#
?
Oct 30, 2014 05:30
|
|
|
Odette posted:Is there a real-world application to that type of problem, or is it just something that interviewers do to see how you solve problems? The latter, with "I don't expect you to solve it, I couldn't" and "I want to see how you approach something I can't help you with since I can't do it either" being explicit parts of the whole deal so I don't freak out trying to solve it.
|
|
#
?
Oct 30, 2014 05:43
|
|
|
Odette posted:see how you solve problems? Oh, this reminds me of something I've been wondering. I used to see this thrown around a lot (not so much anymore), that questions get asked to see "how you solve problems", but really, the vast majority questions you get asked are going to be of the form "recognize which algorithm(s) or algorithm design technique(s) can be used to solve this problem, then implement it in an actual programming language", aren't they? Basically, I get the impression that "seeing how you solve problems" is kind of misleading. If an interviewer asks how you would sort a list in language X (e.g., "I would use someList.sort()!"), then how you would implement a sort function, then how you would sort a list from a file that is ten times bigger than memory, then how you would sort a dataset consisting of millions (billions?) of records on multiple machines, they're asking you questions for which solutions exist and are commonly used. You could be the candidate who goes "here's how I solve problems... hm. a big file, huh." or you could be the candidate who actually knows how stuff works. I feel like being the second one is going to be scored better in any interview. Safe and Secure! fucked around with this message at 05:49 on Oct 30, 2014 |
|
#
?
Oct 30, 2014 05:44
|
|
|
bleh
Linear Zoetrope fucked around with this message at 06:35 on Oct 30, 2014 |
|
#
?
Oct 30, 2014 06:02
|
|
|
Safe and Secure! posted:Oh, this reminds me of something I've been wondering. I used to see this thrown around a lot (not so much anymore), that questions get asked to see "how you solve problems", but really, the vast majority questions you get asked are going to be of the form "recognize which algorithm(s) or algorithm design technique(s) can be used to solve this problem, then implement it in an actual programming language", aren't they? Some people actually believe they're "seeing how you solve problems" but that's bullshit because that explanation could be used for any stupid problem you might ask. ("Seeing how you think" is the more generic version.) Really they are interested in whether you can do basic CS data structurey things. Many companies would be better off giving an IQ test, because that correlates very well with employee performance, and because it would be a much more objective measurement of candidates than what they usually pull. But that's quasi-illegal in the USA because IQ is correlated with race. So instead they have this CS question live programming facsimile. It's not very objective. For example, many more people can answer a certain interview question when I pose it than when a coworker of mine poses it.
|
|
#
?
Oct 30, 2014 06:51
|
|
|
Safe and Secure! posted:You could be the candidate who goes "here's how I solve problems... hm. a big file, huh." or you could be the candidate who actually knows how stuff works. I feel like being the second one is going to be scored better in any interview. Probably they will score better, because it's hard to give an objective interview. But there's some correctness to that, too: if you have a bunch of algorithms in your pocket and you know all the good libraries for your language and you keep up with current technology then you're probably a better candidate than the applicant who's smarter but somehow doesn't do any of those things. But the main thing I'm looking for when I ask coding questions (besides "can code yes/no") is the ability to explain your code. You can code by searching Google and then copy/paste from Stack Overflow, but I think it's important to understand why and how the code your pasting works and to be able to explain it in your own words when a coworker asks about it.
|
|
#
?
Oct 30, 2014 12:34
|
|
|
sarehu posted:Some people actually believe they're "seeing how you solve problems" but that's bullshit because that explanation could be used for any stupid problem you might ask. ("Seeing how you think" is the more generic version.) Really they are interested in whether you can do basic CS data structurey things. Some companies do this. However, it's not actually very meaningful because more recent studies have shown that the difference (which is a small one) stems more from sociological factors than the candidate themself. For example, in countries where IQ isn't seen as a big deal (i.e. not the US), they found no link between IQ and performance because all candidates receive the same education. So really, you should be testing for better K-12 education if anything.
|
|
#
?
Oct 30, 2014 14:04
|
|
sarehu posted:Many companies would be better off giving an IQ test, because that correlates very well with employee performance, and because it would be a much more objective measurement of candidates than what they usually pull. Do you have some support for this?
|
|
|
#
?
Oct 30, 2014 16:26
|
|
|
down with slavery posted:Do you have some support for this? 'very well' is quite the exaggeration but the link between work performance and IQ is certainly documented, albeit disputed with more recent evidence. Wikipedia has plenty of good refs for this: http://en.wikipedia.org/wiki/Intelligence_quotient#Job_performance New stuff: http://www.eurograduate.com/arch_article.asp?id=3628 http://edition.cnn.com/2011/BUSINESS/02/28/iq.jobs.study/
|
|
#
?
Oct 30, 2014 18:58
|
|
bonds0097 posted:'very well' is quite the exaggeration but the link between work performance and IQ is certainly documented, albeit disputed with more recent evidence. Thanks for this, interesting stuff.
|
|
|
#
?
Oct 30, 2014 20:37
|
|
|
FamDav posted:undo, concat, redo
|
|
#
?
Oct 30, 2014 21:24
|
|
|
The values are concatenated 3 wide at most, so you might have to meet in several middles but you're still doing O(3^(n/2)) work.
|
|
#
?
Oct 30, 2014 22:06
|
|
|
Anyone ever done an interview for a customer/partner facing dev-support/consultancy type role with Google? I gather it will be somewhat less technical than their dev interviews but still somewhat terrifying and I can't find much discussion online about what they might cover :/ .
|
|
#
?
Oct 30, 2014 22:29
|
|
|
No Wave posted:I'm not understanding here. I thought that the advantage of meet in the middle was that you could theoretically get numerical values for the first half and the second half - but a concat occuring in the middle would screw that up. sarehu posted:The values are concatenated 3 wide at most, so you might have to meet in several middles but you're still doing O(3^(n/2)) work. Wait, why are we worried about concats in the middle? We should never have one. 1 (+/-/c) 2 (+/-/c) 3 (+/-/c) 4 (+/-/c) 5 (+/-/c) 6 (+/-/c) 7 (+/-/c) 8 (+/-/c) 9 On the first half, we calculate all possible values of: 1 (+/-/c) 2 (+/-/c) 3 (+/-/c) 4 (+/-/c) 5 On the second half, we calculate all possible values of: 5 (+/-/c) 6 (+/-/c) 7 (+/-/c) 8 (+/-/c) 9 We divide the operators in half - not the numbers. There's a number on each side of each operator, so you're never have a concat occurring in the middle. And you store the operator combinations with the different possible values, so that when you take a right-side value of the form c(+|-|c)(+|-|c)(+|-|c), you just don't compare it to any left-side values of the form (+|-|c)(+|-|c)(+|-|c)c. Am I wrong?
|
|
#
?
Oct 31, 2014 02:23
|
|
|
Safe and Secure! posted:Am I wrong? No, for some reason I was being a pissant about the state space being (sum, current-concatenation) instead of just (sum).
|
|
#
?
Oct 31, 2014 02:57
|
|
|
Safe and Secure! posted:Am I wrong?
|
|
#
?
Oct 31, 2014 11:31
|
|
|
Safe and Secure! posted:Wait, why are we worried about concats in the middle? We should never have one. One answer: 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100 So for your two algorithms, we get: 1 + 2 + 3 - 4 + 5 = 7 5 + 6 + 78 + 9 = 98 And the answer is 105? And if 4 and 5 are concatenated - you have 45 in one equation, and 5 in the other? I'm really not understanding the above approach at all. I think instead you'd want to calculate: First half: 1 (+/-/c) 2 (+/-/c) 3 (+/-) 4 (c) 5 Second half: (+/-) 6 (+/-/c) 7 (+/-/c) 8 (+/-/c) 9 Find the results where first half + second half = 100 And then: First half: 1 (+/-/c) 2 (+/-/c) 3 (+/-/c) 4 Second half: (+/-) 5 (+/-/c) 6 (+/-/c) 7 (+/-/c) 8 (+/-/c) 9 Find the results where first half + second half = 100 Throwing out any result where more than concat occurs in a row. The first two-part calculation calculates all the values where a concat occurs between 4 and 5 - the second calculates any other one. This solution will only work for max concat lengths of one (two digits long). No Wave fucked around with this message at 19:54 on Oct 31, 2014 |
|
#
?
Oct 31, 2014 12:01
|
|
|
for anybody who wants a more straightforward example of this kind problem: given a list L of N numbers, find 4 numbers in L whose sum is 0 (or determine that no such quartet exists). you can assume repeats are or aren't allowed.
|
|
#
?
Oct 31, 2014 18:20
|
|
|
I'm not sure if this is the right place for it, but why not. I'm a newbie iOS developer of about 2 years. I'm pretty fresh off the block. It's nothing short of a miracle I'm even here - I'm a college dropout who used to know nothing about Apple development and very little about programming at all before my first job. Over the years I've worked at small startups and bigger companies stationed all over, so I have a pretty hefty list of projects I've been a part of. I recently had to take a drastic change in my lifestyle for better or worse and I'm a little confused on where I should go from here. I don't have a Macbook or iPhone anymore and I haven't for almost all of 2014 so I'm a little wary to continue applying to iOS jobs anywhere. Instead, I've been taking the time to learn frontend web stuff, since I've always wanted to create a portfolio page sometime. It's a lot of fun, and I like it! But I'm still not very good at it and I'm not very familiar with the tech yet. I can tell you why jQuery is nice but that's about it. So, I don't feel very comfortable applying to thos Javascript/html job listings, either. What would be a good course of action for me to take? I'm not really doing anything right now - my days are odd jobs in a podunk town in Florida. Ideally, I'd like to relocate to a hub somewhere but my confidence is weak and I am not so sure anyone's willing to take that risk on someone who's so out of practice. Advice?
|
|
#
?
Nov 1, 2014 07:52
|
|
|
Is there some reason why the drastic lifestyle change stopped you from doing iOS development? I'd focus on getting another iOS job even if you don't have the equipment right now so that you're at least employed and financially stable until you're ready to switch careers. Hell, I want an iOS job so then I can get out of web development with PHP, and I have a CS degree. How can I get some of your luck to rub off on me? Even if you don't have the equipment, you still have the knowledge and experience. Also if your situation was anything like mine a year ago, please see a counselor or any professional help. They'll help you with your confidence better than any of us can. wolffenstein fucked around with this message at 12:36 on Nov 1, 2014 |
|
#
?
Nov 1, 2014 12:32
|
|
|
Just some catastrophic things with money, is all. I don't make anywhere near enough anymore to even consider apple electronics at this point, and the last assessment I tried to do was hell (and promptly denied within the hour, lol).
|
|
#
?
Nov 1, 2014 13:07
|
|
|
Maleficent posted:I'm a newbie iOS developer of about 2 years ... Over the years I've worked at small startups and bigger companies ... I have a pretty hefty list of projects I've been a part of ... I don't have a Macbook or iPhone anymore and I haven't for almost all of 2014 so I'm a little wary to continue applying to iOS jobs anywhere. This is very confusing. Posting a resume might help. It sounds like you're saying that you've been an iOS contractor for 2 years. That should make you pretty hirable. You've spent 10 months without personally owning any Apple products, which is completely irrelevant. A good number of successful iOS developers I know have Android personal phones and non-Apple home computers. Their job buys a top-end Mac for development and at least one of every iOS device they want to build for.
|
|
#
?
Nov 1, 2014 15:53
|
|
|
The only time what equipment you personally own is relevant is if you're working as an independent contractor.
|
|
#
?
Nov 1, 2014 20:24
|
|
|
Maleficent posted:I'm an iOS developer of about 2 years. Over the years I've worked at small startups and bigger companies stationed all over, so I have a pretty hefty list of projects I've been a part of. I've been taking the time to learn frontend web stuff, since I've always wanted to create a portfolio page sometime. It's a lot of fun, and I like it! I can tell you why jQuery is nice. There. I cut out everything about your post that you shouldn't be focusing on. This is the message you present to prospective employers, not all that poo poo about your weaknesses or the fact that you're a college dropout (anyone will be able to figure that out from you resume's education section, but never use the word "dropout" whenever it comes up, it's just too negative) or the fact that you don't have a lot of confidence. I'm completely serious when I say that the worst thing about your situation is that you're dwelling on why someone would NOT want to hire you. Stop it. There's no reason to restrict yourself from iOS jobs just because you haven't been developing for iOS in the last not-very-long-time-period. You have 2 years of experience. Technology moves fast but the platform isn't going to completely transmogrify in that period of time to the point where nothing you did before applies. You'll have to do a BIT of catch-up but most likely it would take you just as long to get settled in with a new company and the way they do things anyway, even if you didn't have that gap. An interviewer might ask you to explain the time gap. You had a personal/family crisis that you had to take time to deal with. That's it, you don't need to give any more detail and if they press, tell them it's very personal, sorry, but the important thing is that it's over with now and won't interfere with the work I do for YOU 
|
|
#
?
Nov 1, 2014 20:28
|
|
|
Yeah, you're right. Most of my phone interviews for iOS jobs have not been very good, actually! Maybe that's why I'm so discouraged. People have been asking me if I know anything about Swift and I don't, to which they respond pretty disappointed. Stuff like that gets me all psyched up and nervous. This is my resume right now! It's plain but has done me well enough up to this point. Maleficent fucked around with this message at 23:25 on Nov 1, 2014 |
|
#
?
Nov 1, 2014 22:47
|
|
|
Maleficent posted:People have been asking me if I know anything about Swift and I don't, to which they respond pretty disappointed. Sounds like you should start learning about Swift. Interviewers like to see passion and dedication to self-education. [edit] Also, I strongly recommend redacting your personal information. You have like 8 different languages under "skills", but you only mention a few of them under your professional experience. Are these languages that you've actually worked with on some sort of real project? If so, talk about those projects. If not, don't include the languages. "C/C++" will get some people riled up because they are not the same thing at all and is a pretty strong indicator that you've never worked with either of them. New Yorp New Yorp fucked around with this message at 23:10 on Nov 1, 2014 |
|
#
?
Nov 1, 2014 23:05
|
|
|
|
| # ? Apr 23, 2024 15:33 |
|
Maleficent posted:Yeah, you're right. Most of my phone interviews for iOS jobs have not been very good, actually! Maybe that's why I'm so discouraged. People have been asking me if I know anything about Swift and I don't, to which they respond pretty disappointed. Stuff like that gets me all psyched up and nervous. A few notes: 2 jobs = 1 page resume, way too much text for your creds if you're going to jack a top rated resume template from google docs, might I suggest at least changing the color scheme? Operating systems is a silly technical skill to list. ActionScript3 is an effectively dead technology and just demonstrates that you haven't done much recent web dev. Learn swift, it's easy Repeat after me... "references available upon request" don't just push your contacts personal info into the wind (and I would definitely hide your own if you're going to post it pubically here)
|
|
|
#
?
Nov 1, 2014 23:06
|
|