Let me know if I am in the wrong place
Just want to make sure this forum is appropriate for the question above - I've seen some people have looked at the problem but so far I garnered zero responses. This is not a homework problem.
Again, basically, given finite alphabet and a finite...
Hi,
Suppose we're looking at a random sequence of digits from 0 to 9. We start off reading the digits until every digit from 0 to 9 has been seen at least once and we mark the count of digits read up to that point (run length). We then reset the run length and continue until the whole random...
Specific Examples
Bill, just want to make sure we're on the same page here. I've read two books by Poundstone - one on Microsoft interviews and the other one about Google + some others. Those described some very specific questions which had right answers to them and presumably were asked on...
Specific Questions
Bhobba,
Could you provide specific examples? I love to hear actual programming interview questions which make you think intensely. If you could recall a few, that would be nice. Also, if you could recall how much time was given to a candidate, that would be awesome...
Concrete Interview Questions
Wolfmax, looks good, what are the answers to 2 and 3? I would appreciate more visitors posting similar questions - I know I should ideally consult literature but it's of no use, I better hear it straight from the source.
Over the years I've heard gruesome stories about engineering/science/tech interviews - questions that they expect you to get on the spot (or nearly so) but which would require me to spend a good day thinking. I've already read Poundstone's books but I have to say there are very few good ones...
Hi,
Knuth's TAOCP exercise 5.1.1-6 asks to construct an n-log-n algorithm which would generate an inversion table corresponding to a particular permutation.
My algorithm constructs inversion table for a random permutation of 1..N numbers (Knuth, Volume 3, exercise 5.1.1-6) using binary...
You seem to be so determined with engineering. What about outsourcing and offshoring? This happens a lot lately and I wonder how do you feel about that? How many of your colleagues at the place of internship actually speak about their jobs going overseas? What about the professors at your...
Hi guys,
I've been given the code below and asked to explain the data shown in the attached chart. Any ideas? The data shows periodicity, what could explain it? I know it has to do with memory.
-------------------------------------------------------
#include <iostream>
#include...
rcgldr great work! I'm learning a lot from you - the high performance timer I've never heard of! Looks very advanced.
And yes, the comparison routine does look broken, I'll ask professor next time if he has tempered with it.
I just looked at s0.cpp and it seems like you've changed the...
Yes, I understand your analysis and that's what the instructor was talking about as well - for you to gain confidence in the nature of the underlying algorithm, you have to look at the data. The data in the beginning (points 1 to 82) clearly suggest a quadratic shape, which (if I understand this...
This is great, but I guess the interviewer wouldn't have been impressed. If I got this right, there is something in the data that's supposed to reveal this dependency. Maybe try to fit parabola with n = 3? That one has nice pearson to it, and may be does suggest an additional quadratic...
Hi rcgldr,
Yes, I checked with professor, the graph title shouldn't have included word: "Size" though he did say the x-axis itself is labeled correctly, and ordinarily when presented with algorithm performance chart, the size of input implies count of elements, not bytes.
I got the...
Hi guys,
I just got the answer to the problem - it turns out the algorithm is a plain bubble sort with variable-length strings. The length of inputs varies with counts of elements in a linear fashion (inverse linear) so for small input sizes we've got long strings and for larger element...
You could be sure that the x-axis is the number of elements in the array, so yes, the chart should be renamed accordingly 'Clock Ticks' vs 'Count of Input Elements'. This was very apparent from the discussion in the class.
We're making good progress so far. The word 'complexity' still rings...
Ok, but what are your conclusions? What explains the observed dynamic? Are you analyzing data in Excel or just looking at the chart? I recall the Pr. saying that it's better to look at the data in Excel but I don't know why. You can easily paste the data from the time-series into Excel.
Why...
What I think is that there is a variation in how sorted is the array depending on array size. I believe that around 570 elements, the inputs (i.e. the array to be sorted) is becoming somewhat unsorted corresponding to the rise in the time to sort, but then that levels off because the inputs...
The performance doesn't seem to be linear in the input size, that's for sure. The speed up is not abrupt, as would be expected if there was a conditional, say like if an element to be sorted is longer than some cutoff value then disregard from the input, so that doesn't seem like an option. I...
Well he didn't say anything in addition, but I guess the idea was to gauge candidate's performance based on the questions s/he will ask the interviewer.
May be the extent to which the input is sorted is correlated with input size, i.e. larger input size - more sorted -> less time to sort...
I think it may be an O(n lg(n)) algorithm but I can't explain the downward trend observed in the end. It definitely doesn't look like it's linear in the input size.
Hi guys,
My professor recently asked a challenging question - he says it's been asked on an interview and he wanted to pose it as a homework.
Attached is the graph of sorting algorithm performance. The interviewer asks: "Tell me everything you can about this algorithm just by looking at...
Hello,
I don't really know if this is considered a challenging problem but this is not for homework:
You're given a set of numbers S of size n. From S, you draw a random sample A, |A| < n. From S, you draw a random sample B, |B| < n. Sampling doesn't remove items from S. What is the...
Hi guys,
I'm currently in computer science program and I have an urgent feeling that I need better exposure to math. I have taken Discrete Math, Calculus i, ii, iii and I've independently studied linear algebra. I guess my concern is lack of differential equations and numerical methods. In...
Hello Everyone,
The following is a subproblem of research project I'm working on, i.e. not a homework. Let's suppose you have a bounded 2d plane and n distinct probes that do random-walk in that plane. The world is closed in a sense that a probe going outside the border ends up being on the...
I know not everyone here is involved in making hiring decisions or recommendations, but let's say you were asessing two grads from relatively similar schools, both with masters degrees, one with thesis completed and one without. What is a general attitude (if it's a meaningful question) to...