每日一练 | Data Scientist & Business Analyst & Leetcode 面试题 322
自2017年6月15日起，数据应用学院与你一起温习数据科学（DS）和商业分析（BA）领域常见的面试问题。从2017年10月4号起，每天再为大家分享一道Leetcode算法题。
希望积极寻求相关领域工作的你每天关注我们的问题并且与我们一起思考，我们将会在第二天给出答案。
Day 222
DS Interview Questions
Why is “Naive” Bayes naive?
BA Interview Questions
SQL: Query the list of CITY names ending with vowels (a, e, i, o, u) from STATION. Your result cannot contain duplicates.
The STATION table is described as follows:
LeetCode Questions
Description:
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
Input: 4 5 6 7 0 1 2, 5
Output: 2
Assumptions:
You may assume no duplicate exists in the array.
欲知答案如何？请见下期分解！
Day 221 答案揭晓
DS Interview Questions
What is Bayes’ Theorem? How is it useful in a machine learning context?
Bayes’ Theorem:
Bayes’ Theorem gives you the posterior probability of an event given what is known as prior knowledge.It’s expressed as the true positive rate of a condition sample divided by the sum of the false positive rate of the population and the true positive rate of a condition.
How is it useful:
Bayes’ Theorem is the basis behind a branch of machine learning that most notably includes the Naive Bayes classifier.
Reference:
https://betterexplained.com/articles/an-intuitive-and-short-explanation-of-bayes-theorem/
BA Interview Questions
SQL: Query the list of CITY names starting with vowels (i.e., a, e, i, o, or u) from STATION. Your result cannot contain duplicates.
The STATION table is described as follows:
where LAT_N is the northern latitude and LONG_W is the western longitude.
Answer:
select CITY
from STATION
where CITY REGEXP '^[AEIOU]';
LeetCode Questions
Description:
48 30564 48 14942 0 0 3348 0 0:00:09 0:00:04 0:00:05 3347Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Input: 1,2,3
Output: 1,3,2
Solution:
permutation中比较难的题， 这题先将排列的树画出来，找规律
A_NEXT一定与A有尽可能长的公共前缀。
如果元素从底向上一直处于递增，说明是对这些元素来说，是没有下一个排列的
从后向前比较相邻的两个元素，直到前一个元素小于后一个元素，停止，这样确保A_NEXT 与A有最长的公共前缀
下一步是找交换的点，必然是找从底部开始第一个大于停止的那个元素进行交换，能确保最小
如果从低到根都是递增，那么下一个元素就是reverse整个数组
文字解释有些难以理解，实际情况用实例将全排列的树画出来就能理解
Code:
Time Complexity: O(n)
看似是两重循环嵌套一个reverse，实际上第一个循环找到要交换的第一个点，第二重循环找到要交换的第二个点，对两点间进行reverse，实际是三个O(n)的操作
Space Complexity: O(1)
点击“阅读原文”查看数据应用学院核心课程