interview-and-career/interview-questions-and-answers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Various interview questions with answers.  Grouped by topic."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This question was asked by: Postmates\n",
    "\n",
    "There are four people on the ground floor of a building that has five levels not including the ground floor. They all get into the same elevator.\n",
    "\n",
    "If each person is equally likely to get on any floor and they leave independently of each other, what is the probability that no two passengers will get off at the same floor?\n",
    "\n",
    "Solution:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "The number of ways to assigning five floors to four different people is to get the total sample space. In this case it would be 5 * 5 * 5 * 5. For each person, they can choose one of five floors, which happens four times for four people. So the total number of combinations is 5^4.\n",
    "\n",
    "The number of ways to assign five floors to four people without repetition of floors is 5 * 4 * 3 * 2 because for the first passenger you have five different options. The second person has four, and so on. Note that this number counts all possible orders betwen passengers as well.\n",
    "\n",
    "The result is then 5/5 * 4/5 * 3/5 * 2/5 = 0.192"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## This question was asked by: Google\n",
    "\n",
    "Given X and Y are independent variables with normal distributions, what is the mean and variance of the distribution of 2X - Y when the corresponding distributions are X ~ N (3, 2²) and Y ~ N(1, 2²)?\n",
    "\n",
    "Solution:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "Because the linear combination of the two independent normal random variables is a normal random variable, we can solve the first problem of the mean by just substituting the given values into the formula for the existing two means in the problem statement.\n",
    "\n",
    "For the two variables X and Y, the mean is calculated simply by:\n",
    "\n",
    "2X - Y = 2(3) - 1 = 5\n",
    "\n",
    "The variance however is calculated differently. The variance of aX-bY is:\n",
    "\n",
    "𝑉𝑎𝑟(𝑎𝑋−𝑏𝑌) = 𝑎2𝑉𝑎𝑟(𝑋) + 𝑏2𝑉𝑎𝑟(𝑌) − 2𝑎𝑏 * 𝐶𝑜𝑣(𝑋,𝑌) where 𝐶𝑜𝑣(𝑋,𝑌) is the covariance between X and Y. The covariance between both X and Y is zero given the normal random variables. That way we can calculate this out:\n",
    "\n",
    "𝑉𝑎𝑟(𝑎𝑋−𝑏𝑌) = 𝑎2𝑉𝑎𝑟(𝑋) + 𝑏2𝑉𝑎𝑟(𝑌) − 2𝑎𝑏 * 𝐶𝑜𝑣(𝑋,𝑌)\n",
    "=4·𝑉𝑎𝑟(𝑋)+𝑉𝑎𝑟(𝑌)−0\n",
    "=4·4 + 4 = 20"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Programming"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "This question was asked by: Microsoft (Hard)\n",
    "    \n",
    "Given an array of words and a maxWidth parameter, format the text such that each line \n",
    "has exactly maxWidth characters. \n",
    "\n",
    "Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.\n",
    "\n",
    "Extra spaces between words should be distributed as evenly as possible. \n",
    "\n",
    "If the number of spaces on a line do not divide evenly between words, \n",
    "the empty slots on the left will be assigned more spaces than the slots on the right.\n",
    "\n",
    "Example:\n",
    "\"\"\"\n",
    "\n",
    "words = [\"This\", \"is\", \"an\", \"example\", \"of\", \"text\", \"justification.\"]\n",
    "max_width = 16\n",
    "\n",
    "output = [\n",
    "    \"This    is    an\",\n",
    "    \"example  of text\",\n",
    "    \"justification.  \"\n",
    "]\n",
    "\n",
    "# Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Since extra spaces between words should be distributed as evenly as possible, \n",
    "we need to implement round robin logic. Round robin logic can be implemented \n",
    "by iterating over each value in the array, checking if it is over the max width, \n",
    "and then adding spaces to the existing line if it has reached capacity.\n",
    "\n",
    "The following line implements the round robin logic:\n",
    "\n",
    "for i in range(maxWidth - num_of_letters):\n",
    "    cur[i%(len(cur)-1 or 1)] += ' ' \n",
    "    \n",
    "Once you determine that there are only k words that can fit on a given line, \n",
    "you know what the total length of those words is num_of_letters. Then the rest \n",
    "are spaces, and there are (maxWidth - num_of_letters) of spaces.\n",
    "\n",
    "The \"or 1\" part is for dealing with the edge case len(cur) == 1.\n",
    "\"\"\"\n",
    "\n",
    "def fullJustify(self, words, maxWidth):\n",
    "    res = []\n",
    "    cur= []\n",
    "    num_of_letters = 0\n",
    "\n",
    "    for w in words:\n",
    "        #check if existing words + new words are greater than max width\n",
    "        if num_of_letters + len(w) + len(cur) > maxWidth:\n",
    "            #implement round robin logic\n",
    "            for i in range(maxWidth - num_of_letters):\n",
    "                cur[i%(len(cur)-1 or 1)] += ' '\n",
    "            res.append(''.join(cur))\n",
    "            cur, num_of_letters = [], 0\n",
    "        cur += [w]\n",
    "        num_of_letters += len(w)\n",
    "    return res + [' '.join(cur).ljust(maxWidth)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## This question was asked by: Facebook\n",
    "There are two lists, list X and list Y. Both lists contain integers from -1000 to 1000 and are identical to each other except that one integer is removed in list Y that exists in list X.\n",
    "\n",
    "Write a function that takes in both lists and returns the integer that was removed in $O(1)$ time and $O(n)$ space without using the python set function.\n",
    "\n",
    "Solution:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "This question is a definition of a trick question. It's not really a python or algorithms question but more of a brain teaser meant to give you a problem to be solved in a creative way.\n",
    "\n",
    "The question is asking how you figure out the number that is missing from list Y, which is identical to list X, except that one number is missing. We could loop through one list, create a hashmap, and figure out which element doesn't exist but that wouldn't be done in O(1) time.\n",
    "\n",
    "Before getting into the coding, think about it logically - how would you find the answer to this?\n",
    "\n",
    "The quick and simple solution is to sum up all the numbers in X and sum up all the numbers in Y and subtract the sum of X from the sum of Y, and that gives you the number that's missing. Because the elements in the list are integers, it adds a different dimension to the problem in creativity rather than the typical approach of data structures and algorithms.\n",
    "\n",
    "```python\n",
    "def return_missing_integer(list_x, list_y):\n",
    "    return sum(list_x) - sum(list_y)\n",
    "```\n",
    "Always ask follow up questions when given constraints. The interviewer could be holding back assumptions that would not ever be known without asking for more clarification. Some example would be:\n",
    "\n",
    "- Is the list sorted?\n",
    "- Is one of the lists the set of all integers from -1000 to 1000?\n",
    "- Are any built in functions allowed besides the set function?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data science"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This question was asked by: Airbnb\n",
    "\n",
    "Pretend you have to analyze the results of an AB test. One variant of the AB test has a sample size of 50K users and the other has a sample size of 200K users.\n",
    "\n",
    "Given the unbalanced size between the two groups, can you determine if the test will result in bias towards the smaller group?\n",
    "\n",
    "Solution:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "There's a couple ways to test for bias but let's look at the size of each of the populations again. The interviewer in this case is trying to assess how you would approach the problem given an unbalanced group. We're not given context to the situation so we have to either:\n",
    "1. State assumptions or\n",
    "2. Ask clarifying questions.\n",
    "\n",
    "How long has the AB test been running? Have they been running during the same time duration? If the data was collected during different time periods then bias certainly exists from one group being from a different date period than the other.\n",
    "\n",
    "Let's assume that there is no bias when having unequal sample sizes because the smaller sample size is already very large. For even very small effects, 50K observations may confer quite a powerful test. The power of the test is heavily dependent on the smaller sample size. But since the sample size is large enough, power is not a concern here.\n",
    "\n",
    "If the test is run inappropriately, in which case the pooled variance estimate is more heavily weighted toward the larger group, and the variances between the two samples are largely different compared to their means, then we might see bias in the result effects. Otherwise given than 50K already confers a powerful enough test, we might not see bias if we can downsample the other test variation to 50K."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## This question was asked by: Ampush\n",
    "\n",
    "Let's say that you work for a software as a subscription (SAAS) company that has existed for just over a year. The chief revenue officer wants to know the average lifetime value.\n",
    "\n",
    "We know that the product costs 100 dollars per month, averages 10% in monthly churn, and the average customer sticks around for around 3.5 months.\n",
    "\n",
    "Calculate the formula for the average lifetime value.\n",
    "\n",
    "Solution:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "This is a trick question given that the candidate is given multiple pieces of supposedly relevant information. Let's break it down by looking at just the important pieces and zeroing in on what pieces of data we need for a calculation.\n",
    "\n",
    "The chief revenue officer wants to know the average lifetime value. Otherwise known as LTV, average lifetime value is defined by the prediction of the net revenue attributed to the entire future relationship with all customers averaged. Given that we don't know the future net revenue, we can estimate it by taking the total amount of revenue generated divided by the total number of customers acquired over the same period of time. Given it is a subscription business, we can use the information provided by product price and churn.\n",
    "\n",
    "In this case we are already given the average product value and churn. The product costs 100 dollars a month and the product averages 10% in monthly churn. Therefore we can calculate the expected value of the customer at each month as a multiplier of retention times the product cost.\n",
    "\n",
    "Let's look at this example.\n",
    "\n",
    "First month the expected value is 100 dollars with 100% of customers retained. The customer has to pay the entire value the first month and it's assumed they will pay upfront. The second month, since the company is dealing with average 10% churn, the company will retain only 90% of the customers. And so the expected value drops down on the second month to:\n",
    "\n",
    "Second Month EV = $100 * 90% = $90\n",
    "\n",
    "If N is the total number of months the company has been in business and will be in business, our calculation then becomes:\n",
    "\n",
    "LTV = 100*.9^(0) + 100*.9^(1) + 100*.9^(2) + ..... + 100*.9^(N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Supervised learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This question was asked by: Lyft\n",
    "    \n",
    "Let's say we have 1 million Lyft rider journey trips in the city of Seattle. We want to build a model to predict ETA after a rider makes a Lyft request.\n",
    "\n",
    "How would we know if we have enough data to create an accurate enough model?\n",
    "\n",
    "Solution:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "Collecting data can be costly. This question assesses the candidate’s skill in being able to practically figure out if a model needs more data. There are a couple of factors to look into.\n",
    "\n",
    "- Look at the feature set size to training data size ratio. If we have an extremely high number of features compared to training data, then the model inaccuracy will be prone to overfitting.\n",
    "\n",
    "- Create an existing model off a portion of the data, the training set, and measure performance of the model on the validation sets, otherwise known as using a holdout set. We hold back some subset of the data from the training of the model, and then use this holdout set to check the model performance to get a baseline level.\n",
    "\n",
    "- Learning curves. Learning curves help us calculate our accuracy rate by testing data on subsequently larger subsets of data. If we fit our model on 20%, 40%, 60%, 80% of our data size and then cross-validate to determine model accuracy, we can then determine how much more data we need to achieve a certain accuracy level.\n",
    "\n",
    "For example. If we reach 75% accuracy with 500K datapoints but then only 77% accuracy with 1 million datapoints, then we’ll realize that our model is not predicting well enough with it’s existing features since doubling the training data size did not significantly increase the accuracy rate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This question was asked by: Square\n",
    "\n",
    "Let's say that you work at a bank that wants to build a model to detect fraud on the platform. The bank wants to implement a text messaging service in addition that will text customers when the model detects a fradulent transaction in order for the customer to approve or deny the transaction with a text response.\n",
    "\n",
    "1. What kind of model would need to be built?\n",
    "2. Given the scenario, if you were building the model, which model metrics would you be optimizing for?\n",
    "\n",
    "Solution:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "1. Binary classifier. Given that fraud is binary, there either is a fradulent transaction or there isn't.\n",
    "\n",
    "2. There are a lot of different ways to analyze model performance but let's take into account what's specified. We know that in binary classification problems there are precision versus recall trade-offs.\n",
    "\n",
    "Precision is defined as the number of true positives divided by model predicted positives. In our example this would be the percentage of correct fradulent transactions out of predicted fradulent transactions.\n",
    "\n",
    "Precision = (True Positive / (True Positive + False Positive))\n",
    "\n",
    "Recall is defined as the number of true positives divided by number of actual true positives. In our example this would be the number of correct fradulent transactions out of actual fradulent transactions.\n",
    "\n",
    "Recall = (True Positive / (True Positive + False Negative))\n",
    "\n",
    "Given these two metrics for evaluating a binary classifier, which metric would a bank prefer to be higher? Low recall in a fradulent case scenario would be a disaster. With low predictive power on false negatives, fradulent purchases would go under the rug with consumers not even knowing they were being defrauded.\n",
    "\n",
    "Meanwhile if there was low precision, customers would think their accounts would be under fraud all the time. But since the question prompts for a text messaging service, this would be okay since the end customer would just have to approve or deny transactions that were false fraud transactions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This question was asked by: Facebook\n",
    "\n",
    "You are about to get on a plane to Seattle. You want to know if you should bring an umbrella. You call 3 random friends of yours who live there and ask each independently if it's raining. Each of your friends has a 2/3 chance of telling you the truth and a 1/3 chance of messing with you by lying. All 3 friends tell you that \"Yes\" it is raining.\n",
    "\n",
    "What is the probability that it's actually raining in Seattle?\n",
    "\n",
    "Solution:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "This question can be solved in two ways in the schools of thought: Bayesian or Frequentist. The frequentist method is probably the easiest.\n",
    "\n",
    "For example. The question prompt states, that each friend has a 2/3 change of telling the truth. Through logical transference, given that all of the friends have told you that it is raining, the question of \"what is the probability that it is not raining\" is the same thing as \"what is the probability that all of your friends are lying?\"\n",
    "\n",
    "P(Not Raining) = P(Friend 1 Lying) AND P(Friend 2 Lying) AND P(Friend 3 Lying)\n",
    "\n",
    "Given this logical expression. We can simply the problem to then to calculate the inverse of three AND functions. So the probability of it raining is then equated to:\n",
    "\n",
    "P(Raining) = 1 - P(3 Friend's Lying)\n",
    "\n",
    "Multiple of all independent probabilities:\n",
    "\n",
    "P(3 Friend's Lying) = 1/3 * 1/3 * 1/3 = 1/27\n",
    "\n",
    "P(Raining) = 1 - 1/27 = 26/27"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## NLP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "This question was asked by: Adobe\n",
    "    \n",
    "In data science, there exists the concept of stemming, which is the heuristic \n",
    "of chopping off the end of a word to clean and bucket it into an easier feature set. \n",
    "\n",
    "Given a dictionary consisting of many roots and a sentence, stem all the words \n",
    "in the sentence with the root forming it. If a word has many roots can form it, \n",
    "replace it with the root with the shortest length.\n",
    "\n",
    "Example\n",
    "\"\"\"\n",
    "\n",
    "# input\n",
    "roots = [\"cat\", \"bat\", \"rat\"]\n",
    "sentence = \"the cattle was rattled by the battery\"\n",
    "\n",
    "output = \"the cat was rat by the bat\"\n",
    "\n",
    "# Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "# At first it simply looks like we can just loop through each word and \n",
    "# check if the root exists in the word and if so, replace the word with the root. \n",
    "# But since we are technically stemming the words we have to make sure that the roots are \n",
    "# equivalent to the word at it's prefix rather than existing anywhere within the word.\n",
    "\n",
    "# We're given a dictionary of roots with a sentence string. Given we have to check \n",
    "# each word, let's try creating a function that takes a word and returns the existing word \n",
    "# if it doesn't match a root, or return the root itself.\n",
    "\n",
    "def replace(word, rootset):\n",
    "    #loop through each subsequent letter\n",
    "    for i in xrange(1, len(word)): \n",
    "        # if the word at the letter is equal one word in the rootset\n",
    "        # return the rootset word\n",
    "        if word[:i] in rootset: \n",
    "            return word[:i]\n",
    "    return word\n",
    "\n",
    "# Here we're going through each character in the word starting from the beginning and looping \n",
    "# through each letter until the resulting word is either equivalent or not to a root in the rootset. \n",
    "# We can create the rootset by just making the list into a set.\n",
    "\n",
    "def replaceWords(roots, sentence):\n",
    "    rootset = set(roots) #create a set\n",
    "\n",
    "    def replace(word):\n",
    "        for i in xrange(1, len(word)): \n",
    "            if word[:i] in rootset: \n",
    "                return word[:i]\n",
    "        return word\n",
    "\n",
    "    return \" \".join(map(replace, sentence.split()))\n",
    "\n",
    "# Given we've created the replace function, we can now just map it to splitting the sentence input and re-join the list back into a sentence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SQL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This question was asked by: Uber\n",
    "\n",
    "`transactions` table\n",
    "\n",
    "columns\ttype\n",
    "id\tint\n",
    "user_id\tint\n",
    "item\tvarchar\n",
    "created_at\tdatetime\n",
    "revenue\tfloat\n",
    "\n",
    "Given the revenue transaction table above that contains a user_id, created_at timestamp, and transaction revenue, write a query that finds the third purchase of every user.\n",
    "\n",
    "Solution:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "This problem set is relatively straight forward. We can first find the order of purchases for every user by looking at the created_at column and ordering by user_id and the created_at column. However we still need an indicator of which purchase was the third value.\n",
    "\n",
    "In this case, we need to apply the RANK function to the transactions table. The RANK function is a window function that assigns a rank to each row in the partition of the result set.\n",
    "\n",
    "RANK() OVER (PARTITION BY user_id ORDER BY created_at ASC) AS rank_value\n",
    "\n",
    "In this example, the PARTITION BY clause distributes the rows in the result set into partitions by one or more criteria.\n",
    "\n",
    "Second, the ORDER BY clause sorts the rows in each partition by the column we indicated, in this case, created_at.\n",
    "\n",
    "Finally, the RANK() function is operated on the rows of each partition and re-initialized when crossing each partition boundary. The end result is a column with the rank of each purchase partitioned by user_id.\n",
    "\n",
    "All we have to do is then wrap the table in a subquery and filter out where the new column is then equal to 3, which is equivalent for subsetting for the third purchase.\n",
    "\n",
    "SELECT *\n",
    "FROM ( \n",
    "    SELECT \n",
    "        user_id\n",
    "        , created_at\n",
    "        , revenue\n",
    "        , RANK() OVER (PARTITION BY user_id ORDER BY created_at ASC) AS rank_value \n",
    "    FROM transactions\n",
    ") AS t\n",
    "WHERE rank_val = 3;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This question was asked by: Tinder\n",
    "\n",
    "There are two tables. One table is called `swipes` that holds a row for every Tinder swipe and contains a boolean column that determines if the swipe was a right or left swipe called `is_right_swipe`. The second is a table named `variants` that determines which user has which variant of an AB test.\n",
    "\n",
    "Write a SQL query to output the average number of right swipes for two different variants of a feed ranking algorithm by comparing users that have swiped the first 10, 50, and 100 swipes on their feed.\n",
    "\n",
    "Tip: Users have to have swiped at least 10 times to be included in the subset of users to analyze the mean number of right swipes.\n",
    "\n",
    "Example Input:\n",
    "\n",
    "`variants`\n",
    "\n",
    "id\texperiment\tvariant\tuser_id\n",
    "1\tfeed_change\tcontrol\t123\n",
    "2\tfeed_change\ttest\t567\n",
    "3\tfeed_change\tcontrol\t996\n",
    "`swipes`\n",
    "\n",
    "id\tuser_id\tswiped_user_id\tcreated_at\tis_right_swipe\n",
    "1\t123\t893\t2018-01-01\t0\n",
    "2\t123\t825\t2018-01-02\t1\n",
    "3\t567\t946\t2018-01-04\t0\n",
    "4\t123\t823\t2018-01-05\t0\n",
    "5\t567\t952\t2018-01-05\t1\n",
    "6\t567\t234\t2018-01-06\t1\n",
    "7\t996\t333\t2018-01-06\t1\n",
    "8\t996\t563\t2018-01-07\t0\n",
    "Note: created_at doesn't show timestamps but assume it is a datetime column.\n",
    "\n",
    "Output:\n",
    "\n",
    "mean_right_swipes\tvariant\tswipe_threshold\tnum_users\n",
    "5.3\tcontrol\t10\t9560\n",
    "5.6\ttest\t10\t9450\n",
    "20.1\tcontrol\t50\t2001\n",
    "22.0\ttest\t50\t2019\n",
    "33.0\tcontrol\t100\t590\n",
    "34.0\ttest\t100\t568\n",
    "\n",
    "Solution:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "If you're a data scientist in charge of improving recommendations at a company and you develop an algorithm, how do you know if it performs better than the existing one?\n",
    "\n",
    "One metric to measure performance is called precision (also called positive predictive value), which has applications in machine learning as well as information retrieval. It is defined as the fraction of relevant instances among the retrieved instances. Given the problem set of measuring two feed ranking algorithms, we can break down this problem as measuring the mean precision between two different algorithms by comparing average right swipes for two different populations for the users first 10, 50, and 100 swipes.\n",
    "\n",
    "We're given two tables, one called `variants` that essentially breaks down which test variant each user has received. It has a column named `experiments` that we have to filter on for the `feed_change` experiment. We know we have to join this table back to the `swipes` table in order to differentiate both of the variants from each other.\n",
    "\n",
    "The other table, `swipes`, is a transaction type table, meaning that it logs each users activity in the app. In this case it's left and right swipes on other users.\n",
    "\n",
    "Given the problem set, the first step is to formulate a way to average the right swipes for each user that satisfies the conditions of swiping at least 10, 50, and 100 total swipes. Given this condition, the first thing we have to do is add a rank column to the swipe table. That way we can look at each user's first X swipes.\n",
    "\n",
    "WITH swipe_ranks AS (\n",
    "    SELECT \n",
    "        swipes.user_id\n",
    "        , variant\n",
    "        , RANK() OVER (\n",
    "            PARTITION BY user_id ORDER BY created_at ASC\n",
    "        ) AS rank\n",
    "        , is_right_swipe\n",
    "    FROM swipes\n",
    "    INNER JOIN variants \n",
    "        ON swipes.user_id = variants.user_id\n",
    "    WHERE experiment = 'feed_change'\n",
    ")\n",
    "Observe how we implement a RANK function by partitioning by user_id and ordering by the created_at field. This gives us a rank of 1 for the first swipe the user made, 2 for the second, and etc...\n",
    "\n",
    "Now our swipe_ranks table looks like this:\n",
    "\n",
    "user_id\tvariant\tcreated_at\trank\tis_right_swipe\n",
    "123\tcontrol\t2018-01-01\t1\t0\n",
    "123\tcontrol\t2018-01-02\t2\t1\n",
    "567\ttest\t2018-01-04\t1\t0\n",
    "123\tcontrol\t2018-01-05\t3\t0\n",
    "567\ttest\t2018-01-05\t2\t1\n",
    "567\ttest\t2018-01-06\t3\t1\n",
    "996\tcontrol\t2018-01-06\t1\t1\n",
    "996\tcontrol\t2018-01-07\t2\t0\n",
    "Notice how the rank value does not reach above 3 in our sample data. Since each user needs to swipe on at least 10 users to reach the minimum swipe threshold, each of these users would be subsetted out of the analysis.\n",
    "\n",
    "Constructing a query, we can create a subquery that specifically gets all the users that swiped at least 10 times. We can do that by using a COUNT(*) function or by looking where the rank column is greater than 10.\n",
    "\n",
    "SELECT user_id\n",
    "FROM swipe_ranks\n",
    "WHERE rank > 10\n",
    "GROUP BY 1\n",
    "Then we can rejoin these users into the original swipe ranks table and group by the experiment variant and take an average of the number of right swipes each user made where the rank was less than 10. Remember that we have to specify a filter for the rank column because we cannot analyze swipe data greater than the threshold we are setting since the Then we can rejoin these users into the original swipe ranks table and group by the experiment variant and take an average of the number of right swipes each user made where the rank was less than 10. Remember that we have to specify a filter for the rank column because we cannot analyze swipe data greater than the threshold we are setting since the recommendation algorithm is intended to move more relevant matches to the top of the feed.\n",
    "\n",
    "SELECT \n",
    "    variant\n",
    "    , CAST(SUM(is_right_swipe) AS DECIMAL)/COUNT(*) AS mean_right_swipes\n",
    "    , 10 AS swipe_threshold\n",
    "    , COUNT(DISTINCT user_id) AS num_users\n",
    "FROM swipe_ranks AS sr\n",
    "INNER JOIN (\n",
    "    SELECT user_id\n",
    "    FROM swipe_ranks\n",
    "    WHERE rank > 10\n",
    "    GROUP BY 1\n",
    ") AS subset \n",
    "    ON subset.user_id = sr.user_id\n",
    "WHERE rank <= 10\n",
    "GROUP BY 1\n",
    "Awesome! This should work. Notice this value gives us the value for only the threshold of rank under 10. We can copy most of the code and re-use it for 50 and 100 by unioning the tables together. Putting it all together now.\n",
    "\n",
    "WITH swipe_ranks AS (\n",
    "    SELECT \n",
    "        swipes.user_id\n",
    "        , variant\n",
    "        , RANK() OVER (\n",
    "            PARTITION BY user_id ORDER BY created_at ASC\n",
    "        ) AS rank\n",
    "        , is_right_swipe\n",
    "    FROM swipes\n",
    "    INNER JOIN variants \n",
    "        ON swipes.user_id = variants.user_id\n",
    "    WHERE experiment = 'feed_change'\n",
    ")\n",
    "\n",
    "SELECT \n",
    "    variant\n",
    "    , CAST(SUM(is_right_swipe) AS DECIMAL)/COUNT(*) AS mean_right_swipes\n",
    "    , 10 AS swipe_threshold\n",
    "    , COUNT(DISTINCT user_id) AS num_users\n",
    "FROM swipe_ranks AS sr\n",
    "INNER JOIN (\n",
    "    SELECT user_id\n",
    "    FROM swipe_ranks\n",
    "    WHERE rank > 10\n",
    "    GROUP BY 1\n",
    ") AS subset \n",
    "    ON subset.user_id = sr.user_id\n",
    "WHERE rank <= 10\n",
    "GROUP BY 1\n",
    "\n",
    "UNION ALL\n",
    "\n",
    "SELECT \n",
    "    variant\n",
    "    , CAST(SUM(is_right_swipe) AS DECIMAL)/COUNT(*) AS mean_right_swipes\n",
    "    , 50 AS swipe_threshold\n",
    "    , COUNT(DISTINCT user_id) AS num_users\n",
    "FROM swipe_ranks AS sr\n",
    "INNER JOIN (\n",
    "    SELECT user_id\n",
    "    FROM swipe_ranks\n",
    "    WHERE rank > 50\n",
    "    GROUP BY 1\n",
    ") AS subset \n",
    "    ON subset.user_id = sr.user_id\n",
    "WHERE rank <= 50\n",
    "GROUP BY 1\n",
    "\n",
    "UNION ALL\n",
    "\n",
    "SELECT \n",
    "    variant\n",
    "    , CAST(SUM(is_right_swipe) AS DECIMAL)/COUNT(*) AS mean_right_swipes\n",
    "    , 100 AS swipe_threshold\n",
    "    , COUNT(DISTINCT user_id) AS num_users\n",
    "FROM swipe_ranks AS sr\n",
    "INNER JOIN (\n",
    "    SELECT user_id\n",
    "    FROM swipe_ranks\n",
    "    WHERE rank > 100\n",
    "    GROUP BY 1\n",
    ") AS subset \n",
    "    ON subset.user_id = sr.user_id\n",
    "WHERE rank <= 100\n",
    "GROUP BY 1"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}