Search results

  1. M

    Random sequence - full alphabet run length

    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...
  2. M

    Random sequence - full alphabet run length

    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...
  3. M

    Hard Interview Problems

    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...
  4. M

    Hard Interview Problems

    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...
  5. M

    Hard Interview Problems

    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.
  6. M

    Hard Interview Problems

    Questions/Problems Can you mention some specific questions/problems/puzzles to get a feel for difficulty levels? Anything concrete would do.
  7. M

    Hard Interview Problems

    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...
  8. M

    Random Sampling: Set Inclusion

    Could you check your logic with the actual computation? I know the answer is correct, but I'm not quite sure it follows from your calculation.
  9. M

    TAOCP Exercise 5.1.1-6

    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...
  10. M

    Boring IT job is there something more? Am I in the wrong place?

    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...
  11. M

    Memory Investigation

    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...
  12. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  13. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  14. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  15. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  16. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  17. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  18. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  19. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  20. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  21. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  22. M

    Sorting Algorithm Performance - Interview-Based Problem

    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.
  23. M

    Sorting Algorithm Performance - Interview-Based Problem

    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...
  24. M

    Random Sampling: Set Inclusion

    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...
  25. M

    Numerical Methods vs Differential Equations

    Ok but which one is better for computer science major?
  26. M

    Numerical Methods vs Differential Equations

    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...
  27. M

    Random walk question

    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...
  28. M

    Master of Arts vs. Master of Science: Pros and Cons

    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...
Top