Math/CompSci Interview Question - Thoughts?
in [Theory]
|
From: mike3 on 24 Nov 2009 20:34 On Nov 24, 6:32 pm, mike3 <mike4...(a)yahoo.com> wrote: > On Nov 21, 10:24 am, p...(a)informatimago.com (Pascal J. Bourguignon) > wrote: <snip> > > Not a single one. You have to develop your knowledge of algorithms, > > mathematics, your symbolic thinking and your imagination in these > > matters. > > You say not a "single" one, so does that mean no course would do it, > or > you'd need multiple ones? After all, courses and books (multiple) can > be used to increase the first 2 areas (knowledge of algorithms and > mathematics). > <snip> Oh yes, and I forgot to add: how does one train the "symbolic" thinking?
From: Richard Heathfield on 25 Nov 2009 01:52 In <805a7a21-f99b-4eb9-abb0-fbde47cb955e(a)k19g2000yqc.googlegroups.com>, mike3 wrote: <snip> > Oh yes, and I forgot to add: how does one train the "symbolic" > thinking? Step 1: obtain a pointy stick. -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within
From: John W. Krahn on 25 Nov 2009 02:06 Richard Heathfield wrote: > In > <805a7a21-f99b-4eb9-abb0-fbde47cb955e(a)k19g2000yqc.googlegroups.com>, > mike3 wrote: > > <snip> > >> Oh yes, and I forgot to add: how does one train the "symbolic" >> thinking? > > Step 1: obtain a pointy stick. Or some fresh fruit. John -- The programmer is fighting against the two most destructive forces in the universe: entropy and human stupidity. -- Damian Conway
From: mike3 on 25 Nov 2009 02:11 On Nov 25, 12:06 am, "John W. Krahn" <some...(a)example.com> wrote: > Richard Heathfield wrote: > > In > > <805a7a21-f99b-4eb9-abb0-fbde47cb9...(a)k19g2000yqc.googlegroups.com>, > > mike3 wrote: > > > <snip> > > >> Oh yes, and I forgot to add: how does one train the "symbolic" > >> thinking? > > > Step 1: obtain a pointy stick. > > Or some fresh fruit. > What's the point here?
From: Pascal J. Bourguignon on 25 Nov 2009 04:32
mike3 <mike4ty4(a)yahoo.com> writes: > On Nov 21, 10:24�am, p...(a)informatimago.com (Pascal J. Bourguignon) > wrote: >> Andrew Tomazos <and...(a)tomazos.com> writes: >> > I was posed the following question in a technical interview for a >> > Software Engineering position by a major multinational NASDAQ company: >> >> > [Paraphrasing] �"You are given an array of 1,000,000 32-bit integers. >> > One int value x occurs 500,001 times or more in the array. �Specify an >> > algorithm to determine x." >> >> > The assumption being extra points for efficiency. >> >> > I initially came up with a linear space, linear time solution. �With >> > some prompting and hints from the interviewer we worked our way to a >> > smaller constant space and linear time algorithm. �That being >> > basically: >> >> > int findmode(int* p, int n) >> > { >> > � � int count[32]; >> > � � for(int i = 0; i < 32; i++) >> > � � � � count[i] = 0; >> >> > � � for (int i = 0; i < n; i++) >> > � � � � �for (int j = 0; j < 32; j++) >> > � � � � � � � �if (p[i] & (1 << j)) // if bit j is on >> > � � � � � � � � � � count[j]++; >> > � � � � � � � �else >> > � � � � � � � � � � count[j]--; >> >> > � � int x = 0; >> > � � for (int i = 0; i < 32; i++) >> > � � � � if (count[i] > 0) >> > � � � � � � x = x | (1 << i); >> >> > � � return x; >> > } >> >> > The idea here is to count the frequency of each of the 32 bits in the >> > array separately, knowing that these bit counts will be dominated by >> > the mode. >> >> > The interviewer already knew the answer, so I can only assume the test >> > was based on how much help he had to give me to arrive at it. >> >> > My question about this is as follows. �I, perhaps boldly, claim to >> > employers to have a "masters-equivalant" experience/knowledge of >> > computer science and math. �Should I have been able to come up with >> > this solution without prompting or help? >> >> If what you're asking is whether anybody having a master in CS and >> maths would have been able to come up with this solution in the >> interview time, I guess we can answer that definitely no, otherwise >> there would be no point in trying to select candidates with this test. >> >> Obviously, it's because some people (with or without a master diploma, >> this really isn't relevant) get or don't get it, that this test is >> useful for the recruiter. >> >> Now if you want this kind of jobs, yes you should better be able to >> come up with smart solutions to little puzzles like this in >> interviews. >> > > You mean he should be able to come up with them without prompting, > right? Put yourself in the place of the employer! Between a guy who will find the solution with two clues, and one who will find it alone, in the same time, who will you hire? What I'm saying here is tautologic: if you want the job that is selected by this filter, then you better have to pass this filter! (It's up to the employer to ensure that the filter matches the requirements of the job). >> > Would you expect someone with a CompSci Masters or PhD from some major >> > ivy league university to be able to come up with this solution without >> > help? >> >> > If so in what course or from which book would you expect to learn the >> > required knowledge to come up with the above solution? >> >> Not a single one. �You have to develop your knowledge of algorithms, >> mathematics, your symbolic thinking and your imagination in these >> matters. >> > > You say not a "single" one, so does that mean no course would do it, > or > you'd need multiple ones? After all, courses and books (multiple) can > be used to increase the first 2 areas (knowledge of algorithms and > mathematics). The later of course. >> > Is the skill to be able to come up with such an algorithm something >> > that is learned by studying lots of algorithms and being able to mix >> > and match the "tricks"? � >> >> That could help yes. �I'd tend to think that imagination is the most >> important ingredient here, to be able to come with a possible solution >> fast enough. >> > > And how does one develop that? More specifically, the "speed" of > coming up with the solution, not just being able to come up with > one. Learning, training, repeatition. Some say the brain is like a muscle, you have to train it. Basically, it is a kind of "intelligence", which you want to improve. >> Also, don't limit yourself to CS and maths, there are ideas to be >> taken from other domains too. >> > > What would that be? We cannot know in advance. The point here is that between somebody who spends 100% of his time learning CS, and somebody who spends 90% of his time learning CS, and 10% of his time 'learning' something else, the later will probably be able to invent algorithms that the first one won't. For example, in the domain of artificial intelligence, it is worthwhile to have some idea of neurobiology... >> > If so, what is a similar commonly known >> > algorithm(s) on which the above solution could have been based? >> >> > Or, is the ability to invent such a solution simply a matter of IQ? >> >> CS IQ, yes, if such a IQ test exists. >> > > Heh. > >> > Some people have the talent to solve the puzzle, see the pattern and >> > come up with the solution - and some just don't? >> >> It seems so. �At least, in a given time. >> > > Hmm. -- __Pascal Bourguignon__ |