[Phone interview]
1. Suppose you have a loop where a variable of type double is being incremented by one with each iteration. What would happen if the condition in the loop is never satisfied?
Sol: I didn't know at the time of the interview. Now I have some idea. It never stops, even though a double variable has bounds. Why? I don't know. Something about the number of bits assigned to this variable in memory being reached. All I know is that when I coded it, by printing the current value of the variable, it reaches a value that the computer (or the compiler?) calls inf (as infinity) with arithmetic inf + 1 = inf. Funny business :)
2. Consider the Poisson equation in two dimensions on the square [0,1]x[0,1]. Explain how to use finite differences to solve numerically this problem.
Sol: Poisson equation in two dimensions is
u_xx + u_yy = f
The most common approximation scheme I know is by doing a centered approximation for each u_xx and u_yy as follows. First, for u_x:
u_x ~ (u(x+h/2,y) - u(x-h/2,y))/h
and so for u_xx:
u_xx ~ [(u(x+h,y) - u(x,y))/h - (u(x,y) - u(x-h,y))/h]/h
u_xx ~ [u(x+h,y) - 2u(x,y) + u(x-h,y)]/h^2 =: approx(u_xx)
Similarly with u_yy...
3. What's the accuracy of that approximation?
Sol: I never remember. Fortunately, it's not hard to deduce. Doing a Taylor expansion for u(x+h) and u(x-h), one gets...
u(x+h) = u(x,y) + hu_x(x,y) + 1/2(h^2)u_xx(x,y) + 1/6(h^3)u_xxx(x,y) + 1/24(h^4)u_xxxx(x,y) + ...
u(x-h) = u(x,y) - hu_x(x,y) + 1/2(h^2)u_xx(x,y) - 1/6(h^3)u_xxx(x,y) + 1/24(h^4)u_xxxx(x,y) + ...
Hence,
approx(u_xx) = u_xx(x,y) + 1/12(h^2)u_xxxx(x,y) + ...
and so the accuracy of this approximation is of order two.
4. What kind of problem you need to solve at the end to find the approximate solution? How would you solve it?
Sol: A linear problem. It's a system of linear equations. After both [0,1] in x and in y are subdivided into n sub-intervals we would have a system of (n-1)^2 unknowns with (n-1)^ equations. That is we would need to solve a linear system of the form Ax = b where A is a square matrix of size (n-1)^2. To solve that problem, if n is not big, I would use Gaussian elimination, but typically n is large. In that case I would use a gradient descend method to find the minimum of the function g(x):=1/2|| Ax-b||^2. The gradient of g is A^t(Ax-b), so the gradient descend iteration is of the form
x_{n+1} = x_n - a(A^t)(Ax-b)
where a is a small positive constant (that might change with n).
5. Is the function g a convex function?
Sol: Yes, since the Hessian of g is the matrix (A^t)A which is a positive semi-definite symmetric matrix.
6. What test would you use to discard outliers in a sample?
Sol: I have no idea. Read about it on wikipedia if you dont know... as I did :)
7. Suppose the probability of getting a head (H) in a coin is p. What is the expected number of tosses until you get the first H?
Sol: Interviewers seem to like this question. I gave the rigorous answer by considering the possible scenarios for the number of tosses together with their correspondent probabilities, and then calculate the expected value. They wanted to hear the solution using conditional expectation. It's pretty much like I did it here. The expected number of tosses until you get the first H is 1/p.
8. In C, what's a structure? Give an example of code using one.
Sol: I wrote on my resume I know C and very basic C++, so I guess that's why he asked me for C. Anyway, I should know in C++ what a structure (and a class) is and do examples. Read it all here... yes, on wikipedia.
9. Consider the Fibonacci sequence. Write a code for generating the n-th term in this sequence.
Sol: Do not write the code I did. I wrote a very inefficient recursive algorithm (and very bad for allocating memory). Check out this link with four different functions for doing that. Which one is the best? P.S> I wrote fibonacci1a for the interview... ups.
10. Consider the numbers {1,2,...,n}. I take one of them and I give you the other (n-1) numbers ordered in any way I want to. Find an efficient algorithm to get the number that is missing.
Sol: Nice question. I couldn't get it right, or rather I couldn't suggest anything of order less than nln(n). The interviewer said there was one of order n and I couldn't believe it. He was right. Here is a clever way of doing it (suggested by my housemate): The sum of all {1,2,...,n} is n(n+1)/2 (three operations). Add all the given numbers (for which you make n-2 operations) and substract the result from n(n+1)/2. The result is the missing number! (and you made n+2 operations!). Simple and cool.
11. In C, what's a static variable?
Sol: This is what it is. I can't explain it better.
1. Suppose you have a loop where a variable of type double is being incremented by one with each iteration. What would happen if the condition in the loop is never satisfied?
Sol: I didn't know at the time of the interview. Now I have some idea. It never stops, even though a double variable has bounds. Why? I don't know. Something about the number of bits assigned to this variable in memory being reached. All I know is that when I coded it, by printing the current value of the variable, it reaches a value that the computer (or the compiler?) calls inf (as infinity) with arithmetic inf + 1 = inf. Funny business :)
2. Consider the Poisson equation in two dimensions on the square [0,1]x[0,1]. Explain how to use finite differences to solve numerically this problem.
Sol: Poisson equation in two dimensions is
u_xx + u_yy = f
The most common approximation scheme I know is by doing a centered approximation for each u_xx and u_yy as follows. First, for u_x:
u_x ~ (u(x+h/2,y) - u(x-h/2,y))/h
and so for u_xx:
u_xx ~ [(u(x+h,y) - u(x,y))/h - (u(x,y) - u(x-h,y))/h]/h
u_xx ~ [u(x+h,y) - 2u(x,y) + u(x-h,y)]/h^2 =: approx(u_xx)
Similarly with u_yy...
3. What's the accuracy of that approximation?
Sol: I never remember. Fortunately, it's not hard to deduce. Doing a Taylor expansion for u(x+h) and u(x-h), one gets...
u(x+h) = u(x,y) + hu_x(x,y) + 1/2(h^2)u_xx(x,y) + 1/6(h^3)u_xxx(x,y) + 1/24(h^4)u_xxxx(x,y) + ...
u(x-h) = u(x,y) - hu_x(x,y) + 1/2(h^2)u_xx(x,y) - 1/6(h^3)u_xxx(x,y) + 1/24(h^4)u_xxxx(x,y) + ...
Hence,
approx(u_xx) = u_xx(x,y) + 1/12(h^2)u_xxxx(x,y) + ...
and so the accuracy of this approximation is of order two.
4. What kind of problem you need to solve at the end to find the approximate solution? How would you solve it?
Sol: A linear problem. It's a system of linear equations. After both [0,1] in x and in y are subdivided into n sub-intervals we would have a system of (n-1)^2 unknowns with (n-1)^ equations. That is we would need to solve a linear system of the form Ax = b where A is a square matrix of size (n-1)^2. To solve that problem, if n is not big, I would use Gaussian elimination, but typically n is large. In that case I would use a gradient descend method to find the minimum of the function g(x):=1/2|| Ax-b||^2. The gradient of g is A^t(Ax-b), so the gradient descend iteration is of the form
x_{n+1} = x_n - a(A^t)(Ax-b)
where a is a small positive constant (that might change with n).
5. Is the function g a convex function?
Sol: Yes, since the Hessian of g is the matrix (A^t)A which is a positive semi-definite symmetric matrix.
6. What test would you use to discard outliers in a sample?
Sol: I have no idea. Read about it on wikipedia if you dont know... as I did :)
7. Suppose the probability of getting a head (H) in a coin is p. What is the expected number of tosses until you get the first H?
Sol: Interviewers seem to like this question. I gave the rigorous answer by considering the possible scenarios for the number of tosses together with their correspondent probabilities, and then calculate the expected value. They wanted to hear the solution using conditional expectation. It's pretty much like I did it here. The expected number of tosses until you get the first H is 1/p.
8. In C, what's a structure? Give an example of code using one.
Sol: I wrote on my resume I know C and very basic C++, so I guess that's why he asked me for C. Anyway, I should know in C++ what a structure (and a class) is and do examples. Read it all here... yes, on wikipedia.
9. Consider the Fibonacci sequence. Write a code for generating the n-th term in this sequence.
Sol: Do not write the code I did. I wrote a very inefficient recursive algorithm (and very bad for allocating memory). Check out this link with four different functions for doing that. Which one is the best? P.S> I wrote fibonacci1a for the interview... ups.
10. Consider the numbers {1,2,...,n}. I take one of them and I give you the other (n-1) numbers ordered in any way I want to. Find an efficient algorithm to get the number that is missing.
Sol: Nice question. I couldn't get it right, or rather I couldn't suggest anything of order less than nln(n). The interviewer said there was one of order n and I couldn't believe it. He was right. Here is a clever way of doing it (suggested by my housemate): The sum of all {1,2,...,n} is n(n+1)/2 (three operations). Add all the given numbers (for which you make n-2 operations) and substract the result from n(n+1)/2. The result is the missing number! (and you made n+2 operations!). Simple and cool.
11. In C, what's a static variable?
Sol: This is what it is. I can't explain it better.
No comments:
Post a Comment