自2017年6月15日起，数据应用学院与你一起温习数据科学（DS）和商业分析（BA）领域常见的面试问题。从2017年10月4号起，每天再为大家分享一道Leetcode算法题。
希望积极寻求相关领域工作的你每天关注我们的问题并且与我们一起思考，我们将会在第二天给出答案。
Day 219
DS Interview Questions
What’s the “kernel trick” and how is it useful?
BA Interview Questions
SQL:Write a query that prints a list of employee names (i.e.: the name attribute) for employees in Employee having a salary greater than  per month who have been employees for less than  months. Sort your result by ascending employee_id.


The Employee table containing employee data for a company is described as follows:
where employee_id is an employee's ID number, name is their name, months is the total number of months they've been working for the company, and salary is the their monthly salary.
Sample Input：
Sample Output：
  Angela

  Michael

  Todd

  Joe
LeetCode Questions
Description:
Given a set of distinct integers, nums, return all possible subsets.
Input: [1,2,3]
Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
Assumptions:
The solution set must not contain duplicate subsets.
欲知答案如何？请见下期分解！
Day 218 答案揭晓
DS Interview Questions
How is KNN different from k-means clustering?
KNN needs labeled points and is thus supervised learning, while k-means doesn’t — and is thus unsupervised learning.

Reference:
K-Nearest Neighbors is a supervised classification algorithm, while k-means clustering is an unsupervised clustering algorithm. While the mechanisms may seem similar at first, what this really means is that in order for K-Nearest Neighbors to work, you need labeled data you want to classify an unlabeled point into (thus the nearest neighbor part). K-means clustering requires only a set of unlabeled points and a threshold: the algorithm will take unlabeled points and gradually learn how to cluster them into groups by computing the mean of the distance between different points.
BA Interview Questions
SQL: Write a query identifying the type of each record in the TRIANGLES table using its three side lengths. Output one of the following statements for each record in the table:
  • Equilateral: It's a triangle with  sides of equal length.
  • Isosceles: It's a triangle with  sides of equal length.
  • Scalene: It's a triangle with  sides of differing lengths.
  • Not A Triangle: The given values of A, B, and C don't form a triangle.
The TRIANGLES table is described as follows:
Each row in the table denotes the lengths of each of a triangle's three sides.
Sample Input:
Sample Output:
Isosceles

Equilateral

Scalene

Not A Triangle
Answer:

SELECT CASE WHEN A + B <= C OR A + C <= B OR B + C <= A THEN 'Not A Triangle'
           WHEN A = B AND B = C THEN 'Equilateral'
           WHEN A = B OR A = C OR B = C THEN 'Isosceles'
           ELSE 'Scalene'
       END
FROM TRIANGLES;
LeetCode Questions
  • Description:
    • Given a 2D board and a word, find if the word exists in the grid.
    • The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
  • Input: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED"
  • Output: true
Solution:
图上的搜索题，因为要搜索所有的组合， 所以推荐使用DFS， 利用回溯，只需要维持一个状态
注意点：
图上的遍历问题可以利用dx， dy数组来优化代码
把判断是否在边界内写成一个私有函数来优化代码
递归的出口的选择
Code:
Time Complexity: O(m * n)
DFS的时间复杂度是边的个数
Space Complexity: O(m ^ 2 * n ^ 2)
判断是否访问过的boolean数组，worst case 可能有 n ^ 2个
点击“阅读原文”查看数据应用学院核心课程
↓↓↓ 
继续阅读
阅读原文