Sample exercises and problems

Some of these problems are simple exercises that only require an answer. Still for some of them, you will be asked for a proof/explanation during the interview. More advanced problems require a formal proof.
  1. Compute $\lim\limits_{n \rightarrow \infty}(1-\frac{1}{\log_2n})^{\log_2n}$.
  2. Let $a_n$ be a bounded sequence of real numbers such that for any $n \in \mathbb{N}$, $|a_{n+1}-a_n|
  3. Define a continuous function in terms of $\varepsilon, \delta$.
  4. Give an example of a continuous function from $\mathbb{R}$ to $\mathbb{R}$ that has a derivative everywhere except for the integers.
  5. Consider a system of $10$ linear equations in $20$ variables. How many solutions can it have?
  6. A professor took two $5\times 5$ matrices $A$ and $B$ and filled in $10$ elements in both of them. A student then filled in all the remaining elements of these matrices. The professor does not know what numbers the student has put, but is able to guess the determinant of $A \times B$ correctly. Give an example of two such partially filled matrices.
  7. Find the value of $a_0$ if $1,2,3,\dots,n-1$ are roots of a polynomial $x^n+x^{n-1}+a_{n-2}x^{n-2}+\dots+a_0$.
  8. Compute the number of four-digit integers with digits increasing.
  9. What are the eigenvalues (with multiplicities) of an $n \times n$ matrix consisting of $n^2$ $1$'s?
  10. Explain in one sentence why there is a real number for which there is no program that can output it digit by digit in an infinite time.
  11. Give an example of a Boolean function $\{0,1\}^n \rightarrow \{0,1\}$ such that in any of its DNF representations all clauses have length $n$.
  12. Write a pseudocode of a function that shifts an array cyclically by a given amount. An input to a function is an array (that can be changed), its size $N$ and the size of shift $K$. Your function should have running time $O(N)$ and should use only $O(1)$ additional space.
  13. Prove that if a connected graph has an even number of vertices, its vertices can be split into pairs $(u_i,v_i)$ such that for each $i$, there is a path from $u_i$ to $v_i$, and all these paths have no common edges.
  14. What is the asymptotic rate of growth of $T(n)$ if $T(n)=3T(\lceil n/3 \rceil)+n$?
  15. Find a prime $p \in \mathbb{P}$ such that $p$ divides $99^{2k}+100^{22k}-2$ for any $k$.
  16. Compute $\sum_{k=1}^{7}\cos\frac{2\pi k}{7}$.
  17. Given a string $S$ over 4-letter alphabet {A, C, G, T} and an integer $K$, find the most common substring in $S$ of length $K$. How to find an average number of repetitions of substrings in $S$ of length $K$? Is it possible to do it faster than in time $O(K|S|)$?
  18. Given a group of N people. Each person in this group has a unique number between 1 and N. Some people know each other, some don't. There is exactly one special person (call her "star") which is known to anyone, but she doesn't know anyone. Assume you have a function
    bool first_knows_second(int first, int second)
    (with natural meaning). How many calls of these function are necessary and sufficient to find the "star" in the given group of people?