ds-interview-exam.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"clearfix\" style=\"padding: 10px; padding-left: 0px\">\n",
    "<a href=\"http://bombora.com\"><img src=\"https://app.box.com/shared/static/e0j9v1xjmubit0inthhgv3llwnoansjp.png\" width=\"200px\" class=\"pull-right\" style=\"display: inline-block; margin: 5px; vertical-align: middle;\"></a>\n",
    "<h1> Bombora Data Science: <br> *Interview Exam* </h1>\n",
    "</div>\n",
    "\n",
    "<img width=\"200px\" src=\"https://app.box.com/shared/static/15slg1mvjd1zldbg3xkj9picjkmhzpa5.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Welcome\n",
    "\n",
    "Welcome! This notebook contains interview exam questions referenced in the *Instructions* section in the `README.md`—please read that first, *before* attempting to answer questions here.\n",
    "\n",
    "<div class=\"alert alert-info\" role=\"alert\" style=\"margin: 10px\">\n",
    "<p style=\"font-weight:bold\">ADVICE</p>\n",
    "<p>*Do not* read these questions, and panic, *before* reading the instructions in `README.md`.</p>\n",
    "</div>\n",
    "\n",
    "<div class=\"alert alert-warning\" role=\"alert\" style=\"margin: 10px\">\n",
    "<p style=\"font-weight:bold\">WARNING</p>\n",
    "\n",
    "<p>If using <a href=\"https://try.jupyter.org\">try.jupyter.org</a> do not rely on the server for anything you want to last - your server will be <span style=\"font-weight:bold\">deleted after 10 minutes of inactivity</span>. Save often and rember download notebook when you step away (you can always re-upload and start again)!</p>\n",
    "</div>\n",
    "\n",
    "\n",
    "## Have fun!\n",
    "\n",
    "Regardless of outcome, getting to know you is important. Give it your best shot and we'll look forward to following up!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exam Questions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Algo + Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 1.1: Fibionacci\n",
    "![fib image](https://upload.wikimedia.org/wikipedia/commons/thumb/9/93/Fibonacci_spiral_34.svg/200px-Fibonacci_spiral_34.svg.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.1.1\n",
    "Given $n$ where $n \\in \\mathbb{N}$ (i.e., $n$ is an integer and $n > 0$), write a function `fibonacci(n)` that computes the Fibonacci number $F_n$, where $F_n$ is defined by the recurrence relation:\n",
    "\n",
    "$$ F_n = F_{n-1} + F_{n-2}$$\n",
    "\n",
    "with initial conditions of:\n",
    "\n",
    "$$ F_1 = 1,  F_2 = 1$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.1.2\n",
    "What's the complexity of your implementation?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.1.3\n",
    "Consider an alternative implementation to compute Fibonacci number $F_n$ and write a new function, `fibonacci2(n)`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.1.4\n",
    "What's the complexity of your implementation?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.1.5\n",
    "What are some examples of optimizations that could improve computational performance?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 1.2: Linked List\n",
    "![ll img](https://upload.wikimedia.org/wikipedia/commons/thumb/6/6d/Singly-linked-list.svg/500px-Singly-linked-list.svg.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.2.1\n",
    "Consider a [singly linked list](https://en.wikipedia.org/wiki/Linked_list), $L$. Write a function `is_palindrome(L)` that detects if $L$ is a [palindrome](https://en.wikipedia.org/wiki/Palindrome), by returning a bool, `True` or `False`.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.2.2\n",
    "What is the complexity of your implementation?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.2.3\n",
    "Consider an alternative implementation to detect if L is a palindrome and write a new function, `is_palindrome2(L)`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.2.4\n",
    "What's the complexity of this implementation?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q 1.2.5 \n",
    "What are some examples of optimizations that could improve computational performance?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Prob + Stats"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 2.1: Finding $\\pi$ in a random uniform?\n",
    "<img src=https://www.epicurus.com/food/recipes/wp-content/uploads/2015/03/Pi-Day.jpg width=\"480\">\n",
    "\n",
    "Given a uniform random generator $[0,1)$ (e.g., use your language's standard libary to generate random value), write a a function `compute_pi` to compute [$\\pi$](https://en.wikipedia.org/wiki/Pi)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 2.2: Making a 6-side die roll a 7?\n",
    "\n",
    "Using a single 6-side die, how can you generate a random number between 1 - 7?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 2.3: Is normality uniform?\n",
    "\n",
    "<img src=https://rednaxela1618.files.wordpress.com/2014/06/uniformnormal.png width=\"480\">\n",
    "\n",
    "\n",
    "Given draws from a normal distribution with known parameters, how can you simulate draws from a uniform distribution?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 2.4: Should you pay or should you go?\n",
    "\n",
    "![coin flip](https://lh5.ggpht.com/iwD6MnHeHVAXNBgrO7r4N9MQxxYi6wT9vb0Mqu905zTnNlBciONAA98BqafyjzC06Q=w300)\n",
    "\n",
    "Let’s say we play a game where I keep flipping a coin until I get heads. If the first time I get heads is on the nth coin, then I pay you $2^{(n-1)}$ US dollars. How much would you pay me to play this game? Explain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 2.5: Uber vs. Lyft\n",
    "\n",
    "![uber vs lyft](http://usiaffinity.typepad.com/.a/6a01347fc1cb08970c01bb0876bcbe970d-pi)\n",
    "\n",
    "You request 2 UberX’s and 3 Lyfts. If the time that each takes to reach you is IID, what is the probability that all the Lyfts arrive first? What is the probability that all the UberX’s arrive first?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 2.6: Pick your prize\n",
    "<img src=https://miro.medium.com/max/1100/1*m5b3O9sE68UCXjLw5oxy2g.png width=\"480\">\n",
    "\n",
    "A prize is placed at random behind one of three doors and you are asked to pick a door. To be concrete, say you always pick door 1. Now the game host chooses one of door 2 or 3, opens it and shows you that it is empty. They then give you the option to keep your picked door or switch to the unopened door. Should you stay or switch if you want to maximize your probability of winning the prize?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Conceptual ML"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 3.1 Why study gradient boosting or neural networks?\n",
    "\n",
    "Consider a regression setting where $X \\in \\mathbb{R}^p$ and $Y \\in \\mathbb{R}$. The goal is to come up with a function $f(X): \\mathbb{R}^p \\rightarrow \\mathbb{R}$ that minimizes the squared-error loss $(Y - f(X))^2$. Since X, Y are random variables, we seek to minimize the expectation of the squared error loss as follows\n",
    "\\begin{equation}\n",
    "EPE(f) = \\mathbb{E}\\left[(Y-f(X)^2\\right]\n",
    "\\end{equation}\n",
    "where EPE stands for expected prediction error. One can show that minimizing the expected prediction error leads to the following _regression function_\n",
    "\\begin{equation}\n",
    "f(x) = \\mathbb{E}\\left[Y|X=x\\right]\n",
    "\\end{equation}\n",
    "\n",
    "The goal of any method is to approximate the regression function above, which we denote as $\\hat{f}(x)$. For example, linear regression explicitly assumes that the regression function is approximately linear in its arguments, i.e. $\\hat{f}(x) = x^T\\beta$ while a neural network provides a nonlinear approximation of the regression function. \n",
    "\n",
    "The simplest of all these methods is [k-nearest neighbors](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm). Given $x$ and some neighbourhood of $k$ points $N_k(x)$, $\\hat{f}(x)$ is simply the average of all $y_i|x_i \\in N_k(x)$.  Let $N$ denote the training sample size. Under mild regularity conditions on the joint probability distribution $Pr(X, Y)$, one can show that as $N \\rightarrow \\infty$, $k \\rightarrow \\infty$ such that $k/N \\rightarrow 0$, then $\\hat{f}(x) \\rightarrow f(x)$ where $\\rightarrow$ means approaches or goes to. In other words, the k-nearest neighbors algorithm converges to the ideal solution as both the training sample size and number of neighbors increase to infinity.\n",
    "\n",
    "Now given this _universal approximator_, why look any further and research other methods? Please share your thoughts.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q 3.2 Model Selection and Assesment\n",
    "\n",
    "Consider a multiclass classification problem with a large number of features $p >> N$, for e.g $p=10000, N=100$ The task is threefold\n",
    "1. Find a \"good\" subset of features that show strong _univariate_ correlation with class labels\n",
    "2. Using the \"good\" subset, build a multi class classifier\n",
    "3. Estimate the generalization error of the final model\n",
    "\n",
    "Given this dataset, outline your approach and please be sure to cover the following\n",
    "- Data splitting\n",
    "- Model Selection: either estimating the performance of different classifiers or the same classifier with different hyperparameters\n",
    "- Model Assessment: having chosen a classifier, estimating the generalization error\n",
    "\n",
    "Assume all features are numerical, the dataset contains no NULLS, outliers, etc. and doesn't require any preprocessing.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:bombora-datascience-exam]",
   "language": "python",
   "name": "conda-env-bombora-datascience-exam-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}