Algorithm Engineer Interview Questions
596
Algorithm Engineer interview questions shared by candidates
what kind of researches you've ever involved in
7 Answers
We draw a person at random from the street. Then we keep drawing people until we find someone taller than the first person. What is the expected number of draws we have to wait?
5 Answers↳
Intuitively the answer could be infinity if the first person we draw is the tallest man on earth. But the probability of this event will be small. So just model the distribution P(X) of heights and simulate draws from it. With a bit of math (integrating 1/f(x) gives log(x)) you get that the answer is indeed infinity. Less
↳
Take X_1 be r.v. of height of first draw, X_2 to be r.v. of height of second draw and so on. For one draw, we want P(X_1 < X_2) = P(X_1 - X_2 < 0). Assume X_1, X_2 to be i.i.d., so X_1 - X_2 := Z is N(0, 2*sigma^2). So P(1st draw successful) = P(Z<0). Define this to be p. Therefore the expectation is: E = sum from i=1 to infinity of i*(p^i) This solely depends on the variance of the distribution of the heights, not the mean. To comment on the above message saying that it is infinity, this may be true in practice, but as we model this with a normal distribution (which is reasonable due to Central Limit Theorem), we assume that there is no "tallest man". Instead what one does is to choose the variance such that the probability of drawing a height taller than, say, 7ft6 is basically 0 (10^-6 or so, sigma comes from experimental data so I don't know the exact number here). This has to do because the normal is supported on the real line. One can of course truncate the normal and renormalise the distribution (i.e. say that we can only draw from values between 3ft and 7ft6) but then the problem because more complex, and I am not so sure how it would be done as I am not familiar with truncated normals. Best, Carlos Less
↳
Some comment to my answer above; I foolishly forgot that as we are dealing with P(Z<0) and E(Z) = 0, this will be 0.5. Then the sum will be sum from k=1 to infinity of k*(0.5)^k = 2 as this is just equal to 1/2 * (1/(1-(1/2)^2)) using the power expansion of 1/(1-x^2), so the answer is 2, when using standard normals. Less
If I have a jar with 1000 coins and one is double headed and I pick one coin randomly and flip 10 heads what is the probability it is the double headed coin?
4 Answers↳
You can use Bayes to get the real number, which is close to 0.5 (which you can see intuitively) . They wanted the exact number. Less
↳
@ Feb 4, You formula is correct, looks like typo. because 2^10=1024 so 1/(1+999/1024) ~= 1/2 (1*1/1000)/(1*1/1000+(1/2^10)*999/1000) Less
↳
Bayes. 10^-3/(10^-3 + 1/2^10 * (1-10^-3))
Pretty much the same thing as the Microsoft one in this link. I wasted too much time on question 2 and didn't get a chance to submit an answer but I finished it for fun after the test. https://webcache.googleusercontent.com/search?q=cache:KocTw550s_UJ:https://leetcode.com/discuss/interview-question/760379/Microsoft-or-OA-2020-or-Word-Machine+&cd=1&hl=en&ct=clnk&gl=ru&client=safari
4 Answers↳
what was your aggregated total score? it shows on the codility report page like 30min after you finish Less
↳
37 aggregated total score
↳
yea codility is such bullcrap, i got all of them right on the surface, but i ended up with 78 agg score. they need to use hackerrank or something, codility just hides too much and we can't even see what we're doing wrong smh Less
Asked how to find the kth largest element of a sequence of n elements.
3 Answers↳
First algorithm: sort the sequence in O(n log n) time and select the kth element. Second algorithm: construct a max-heap out of the n elements, which can be done in O(n) time and then repeatedly remove the largest element until you reach the kth element. This step takes O(k log n) time and so overall the algorithm runs in O(n + k log n) time. Third algorithm: Use quick select: partition the sequence using a random element as the pivot and recurse on the partition that contains the kth element, which you can determine based on the sizes of the two partitions. This runs in expected time O(n) and runs with high probability in O(n) time. It is also possible to extend this algorithm to run deterministically in O(n) time (see Deterministic Selection algorithm). Less
↳
The third algo is O(n)
↳
we can maintain a min-heap of size k, each time if new element is larger than min element in the heap, remove the root and heapify, otherwise don't update Less
How do you find the pdf of the sum of two independent random variables?
3 Answers↳
Two integrals along the joint distribution of the the two random variables.
↳
Computing the convolution of the pdf of both random variables.
↳
Hey! Thanks for sharing your experience. I have this interview at the location, can you please tell more about the onsite questions? It will be great if you could kindly tell about the questions focusing on coding(was it all in C?), DSP, image processing and ML. Less
phone interview: (1) 3x3 large square, the surface is painted in red. After cutting into 27 pieces, just take one piece and throw it on the table. Five sides are white and white. Ask the probability that the last face is red. (2) X = the sum of 100 rolls of dice, Y = the number of heads of 600 coin flips, ask Pr (X>Y) (3) N points randomly in a circle. The probability that all of them lie in a semicircle
3 Answers↳
1. Not so trivial but idk P(5W 1R | 5W up) = P(5W up | 5W 1R) * P(5W 1R) / P(5W Up) = (1/6 * 6/27) / (1/6 * 6/27 + 1/27 * 1) = 1/2. 2. Helpful to remember that mean of die roll is 3.5 and variance is 35/12 ~= 3. Hence using CLT, the sum of 100 die rolls is approx. N(350, 300). Similarly, for a coin flip the expected number of heads is 1/2 and variance is 1/4, so the number of heads of 600 flips is approx. N(300, 150). So, X - Y ~ N(50, 450), and the probability this is greater than 0 is something like 99%. (sqrt(450) ~ 21, so X - Y would need to be over 2 standard deviations to the left). 3. As others have shown, answer is N(1/2)^(N - 1). Very common quant problem. A variation is: what is the probability 3 points on a circle form a triangle which contains the center? Notice that this is the complement of all 3 points lying on the same semi-circle (i.e. 1/4). Less
↳
1. Conditional probability. Trivial. 2. The mean and variance for X and Y are easy to calculate, approximately Gaussian with CLT. So mean and variance of X-Y is calculable. You can then get a quite good estimation of that probability with pen and paper without help from numerical simulations. 3. Pick any point, the probability of all the remaining n-1 points being on the semi-circle clockwise following this point is 1/2^(n-1). The total probability is the union of all n points being picked as the first point and they are actually mutually exclusive. So n*(1/2)^(n-1). Less
↳
1. 6/7 - There are 7 cubes which have 5 white sides - the center cube of each face and the center of the overall cube. Of those, the cubes on each face each have 1 red side. So, 6/7 2. This problem is on stack overflow and basically needs to be simulated, cannot solve intuitively. 3. n * (.5)^n-1, see stack overflow for explanation. Less
Homework: Derive group delay of a non linear phase filter Write a program to shuffle cards in a particular manner until original order of cards has been reinstated.
2 AnswersSpaghetti in a bowl question. (Pick up one end of a spaghetti and you can either join it to the other end of the spaghetti you are holding which created a loop or you can pick any other end in the bowl and join it to that. Find the expected number of loops.) Another spaghetti question (I think the interviewer loved spaghetti): You have a plate of spaghetti in front of you (no sauce!). You pick two ends and tie them together. Then you pick two more ends and tie them together. Continue until there are no free ends left. If there were n spaghettis originally, what is the probability that you now have a single giant loop consisting of all the spaghettis?
2 Answers↳
^ how does this comment help anyone?
↳
Standard question. Just google it. I had seen this question while practicing some questions on the internet before the interview. Less