Microsoft Interview - I _had_ one! - Page 3
Blogs > CecilSunkure |
Pseudoku
Canada1279 Posts
| ||
Cambium
United States16368 Posts
I'm almost 100% certain that the guy is a program manager (rather than a project manager). Program manager, SDE and SDET are the three legs holding up the development tripod for Microsoft, and they claim that you can move roles very easily between them. I applied as a PM, but was told to interview as an SDET, and was offered a job as an SDE because they said it was a better fit. PMs are definitely a lot less technical than the other two despite what Msft may tell you, but they can definitely hold a conversation with a technical person (which is their role). | ||
Cambium
United States16368 Posts
On March 15 2013 13:23 Pseudoku wrote: Yeah, based on how he worded the question, I think a[i] = i (except for the duplicate), so just one pass is needed (O(n))? That's probably too simple. I'd imagine it's something like you have numbers 1 to n randomly distributed in an array of size (n+2). Two of which are dupes, find out what they are... Now, this would be an interesting question because the typical response would be: 1. O(n^2) runtime: two loops 2. O(n) memory: hash map 3. O(n log n): sort then traverse Then I would guess the interviwer would lead the interviewee towards an O(n) runtime solution without extra space: + Show Spoiler + think about it It's a big possibility that the interviewer screwed it up | ||
spinesheath
Germany8679 Posts
Also does your version lead to any problems with overflows as they came up in the follow-up question? + Show Spoiler [my idea for Cambium's version] + Actually, my idea would be to abuse the sign bit assuming we have signed integers (marking the array index for which we already found the corresponding value), and that obviously wouldn't work if we already have negative values due to overflow... But thanks to the value 0 that would be quite the hack, involving actual bit manipulation. Also: hilariously bad cache usage in the case of a very large array. | ||
Cambium
United States16368 Posts
On March 15 2013 17:29 spinesheath wrote: But "each slot's value is it's indexed position" strongly hints at a non-random relation between the value and its position... He would have messed up quite hard then. Unless of course he messed up a bit and then Cecil messed up some more while rephrasing it. Also does your version lead to any problems with overflows as they came up in the follow-up question? + Show Spoiler [my idea for Cambium's version] + Actually, my idea would be to abuse the sign bit assuming we have signed integers (marking the array index for which we already found the corresponding value), and that obviously wouldn't work if we already have negative values due to overflow... But thanks to the value 0 that would be quite the hack, involving actual bit manipulation. Also: hilariously bad cache usage in the case of a very large array. nice | ||
fonger
United Kingdom1218 Posts
On March 15 2013 17:04 Cambium wrote: That's probably too simple. I'd imagine it's something like you have numbers 1 to n randomly distributed in an array of size (n+2). Two of which are dupes, find out what they are... Now, this would be an interesting question because the typical response would be: 1. O(n^2) runtime: two loops 2. O(n) memory: hash map 3. O(n log n): sort then traverse Then I would guess the interviwer would lead the interviewee towards an O(n) runtime solution without extra space: + Show Spoiler + think about it It's a big possibility that the interviewer screwed it up Cleaned up per below: + Show Spoiler + I think this is O(n):
Example: + Show Spoiler +
| ||
spinesheath
Germany8679 Posts
Since you basically do a[k] = k once per iteration, and terminate if you ever come across a slot where a[k] == k, it should be O(n). Whether it is correct is a different story though... You cleverly avoided the issue of starting at a slot where a[k] == k already because the array is 1 larger than the largest value in the array, so I don't see a reason why it wouldn't be correct. It probably is correct. Also: use the "code" BB tag. | ||
CecilSunkure
United States2829 Posts
| ||
Glenn313
United States475 Posts
| ||
Alryk
United States2718 Posts
| ||
tuho12345
4482 Posts
| ||
Snipinpanda
United States1227 Posts
| ||
CecilSunkure
United States2829 Posts
On March 16 2013 11:04 Snipinpanda wrote: I don't particularly see why integer overflow matters. The difference should still be the correct answer. It won't be. For instance say our range is 7 to -7 for an integer. [0][1][1][3][4][5][6] We have a missing 2. To find it in decimal we do: (1 + 2 + 3 + 4 + 5 + 6) - (1 + 1 + 3 + 4 + 5 + 6), which is 2. Converting the numbers we have into binary gives: 0001 + 0001 + 0011 + 0100 + 0101 + 0110 + 0111 = 1100 which when you do 2's compliment: -0011 or -3. Our expected total also overflows, which gives us: 0001 + 0010 + 0011 + 0100 + 0101 + 0110 = 0101 which is 5. 5 minus -3 is 8, which overflows to 0. This is assuming I did the arithmetic correctly. | ||
Snipinpanda
United States1227 Posts
You seem to be doing (1+1+3+4+5+6+7) in your first calculations. Even so your calculations aren't quite correct. 1 + 1 + 3 + 4 + 5 + 6 = 20 = 0b10100 Since you ignore the highest bit(it over flowed), it's 0100 which is one less than the total you had for your other calculation. | ||
spinesheath
Germany8679 Posts
| ||
Snipinpanda
United States1227 Posts
On March 16 2013 16:07 spinesheath wrote: But then what if you have an array larger than max int? Possibly even max unsigned int? :p Then you are violating the premise that the array will only have one duplicate past max int+1 | ||
GeorgeyBeats
United Kingdom338 Posts
I am totally gutted for you as I know how much we can get our hopes up, but perhaps in the long run, it may have been a good thing you didnt get it so keep you head up and just keep applying for those dream jobs and I am sure you will get one of them. You also seem like a really nice guy, and that will go a long way in any industry. Secondly I will go on to my interview experience. Here in the UK I had my interview with microsoft this week as well. I too am less than satisfied with the interview structure and how things went overall. I applied for a Public Relations position and in previous rounds I had to answer skills based questions on certain things like leadership, working under pressure, etc. I also had to hand in my CV alongside all of these questions I answered on the form. Firstly I was interviewed by a man whose english was poor as it was definitely not his first language, which didn't set a great tone for the rest of the interview as I did have to ask for a lot of things repeated. He, like your interviewer, was not in my field, he was just a generic HR guy who didn't seem to have any idea about the role I was applying for. Before we started, he asked me, do you have any questions. I said yes 'What does the PR role actually involve, as there is very little detail on the ins and out of the role on the website, only the basic structure of any internship' to which he said we can come back to the question at the end, kind of a dodge. Then finally before we started, he said we were having a competancy based interview and he would have me to back up answers with times in my life I had solved certain problems, of course, most times you have used in your previous answers on the application form. He then told me he did not want me to use any of these times I had already talked about and use other times I had shown these skills. To me, this is ridiculous, you have either shown the skills or you haven't and if you struggle to answer a question because you aren't allowed to use a previous experience and look stupid, its not really your fault and you end up coming up with weaker answers. This threw all prep I had out the window. We then sort out basic formalities about checking exam results etc and then I got the same question about when I graduate. I am currently in the 3rd year of my integrated undergraduate masters degree in marine biology, this is basically a BSc and a MSc rolled into one course over 4 years, so I am still technically an undergraduate and I am in my penultimate year of my degree. He asked, 'are you on a year in industry course and do you graduate in 2015?' to which I replied, I am not but I have been allowed to look for an internship and should I find one, I will be able to defer my final year and then I shall graduate in 2015. Like you, I don't see how this is relevant. I am able to take the internship and I too am technically a sophomore within my degree programme. This really shouldn't count against me. The next question was 'what do you know about the PR internship programme?' Now here, I was losing my mind. That was my very first question which he refused to provide any detail, I then described what little there is on the intern web page and echoed my earlier thoughts. To which he said 'ok' and moved on. Really not helping the flow of the interview or making me feel comfortable. Generally, the actual skills based questions went ok. I wasn't really happy with not being able to use my best life experiences as I have already talked about them. None of the questions were related to PR or any PR experience, so I kind of felt short changed by the experience. The interview concluded I asked about the PR role, where I would be placed, what I would be expected of me. He said, after the final assessment stage, I could be placed in any PR department under any of microsofts brands but he didn't really know the actual ins and outs of the internship and what would be expected, which I felt was really poor. I haven't had a reply back from them yet, but I am certainly not confident of getting an internship. Perhaps my shitty experience with microsoft will give you a bit of comfort, as seeing that I was not the only one made me feel a little better. Take care cecil! | ||
CecilSunkure
United States2829 Posts
Thanks for sharing your experience! Yeah I think your interview went even worse than mine, haha. It's quite nice to hear other peoples' experiences. It must have been all the more nerve wracking for you, since I myself had about 10 other people I knew with very similar interviews to myself (since it was a 2 day interveiwathon). On March 16 2013 14:13 Snipinpanda wrote: It's 7 to -8. You seem to be doing (1+1+3+4+5+6+7) in your first calculations. Even so your calculations aren't quite correct. 1 + 1 + 3 + 4 + 5 + 6 = 20 = 0b10100 Since you ignore the highest bit(it over flowed), it's 0100 which is one less than the total you had for your other calculation. Ah yes, I overflowed incorrectly. I was incrementing by one during each addition instead of doing the calculation and truncating the extra bits off. Either way you can't just "ignore" bit overflow and solve the interview problem. | ||
Serpico
4285 Posts
| ||
GeorgeyBeats
United Kingdom338 Posts
On March 16 2013 18:18 CecilSunkure wrote: @GeorgeyBeats Thanks for sharing your experience! Yeah I think your interview went even worse than mine, haha. It's quite nice to hear other peoples' experiences. It must have been all the more nerve wracking for you, since I myself had about 10 other people I knew with very similar interviews to myself (since it was a 2 day interveiwathon). Maybe my view is slightly skewed by my saltiness on behalf of it not going too great :L But even if I get through to the final stage, my views on that shall remain the same. The fact you sound like an intelligent chap and then being told that the candidates didn't have the technical knowledge is a real kick in the nuts after being interviewed by someone not in the position you are going for. On March 16 2013 18:55 Serpico wrote: I just graduated from the U, gl to you in your future endeavors. I've been trying to get a good job with very little experience (and a very mediocre degree) with little success. I'll probably have to humble myself and start at the bottom somewhere. Keep trying, you have to remember that many, many people only succeeded because they were simply persistent. I could offer some advice, just try and drag in any contacts that you have. The sad thing is that its not what you know sometimes, it is who you know. Just ask around, does anyone you know someone in a company or sector you would like to work in, just ask for a phone number and have a chat on the phone. Most of all be nice. Its amazing how far it will get you. Best of luck buddy. | ||
| ||