“

每

日

一

練

”

May.

6

Data Application Lab 自2017年6月15日起，每天和你分享討論一道數據科學(DS)和商業分析(BA)領域常見的面試問題。

自2017年10月4日起，每天再爲大家分享一道Leetcode 算法題。

希望積極尋求相關領域工作的你每天關注我們的問題並且與我們一起思考，我們將會在第二天給出答案。

Day

505

DS Interview Question

Describe the basic steps to do the PCA (Principal Components Analysis)

BA Interview Question

Write a query in SQL to Obtain the names of all patients who had at least two appointment where the nurse who prepped the appointment was a registered nurse and the physician who has carried out primary care.

LeetCode Question

Word search

Deion:

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

Day

504

答案揭曉

DS Interview Question & Answer

Talk about how K-D Tree improve the KNN.

Answer:

The k-d tree is a binary tree in which every node is a k-dimensional point. Every non-leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as half-spaces. Points to the left of this hyperplane are represented by the left subtree of that node and points right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension's axis.

Basically, K-D Tree divides the dataset into several regions, and this time when we calculate the distances of the query instance, instead we calculate its distances to all the other data points, we only calculate the distances to all the data which in the same region with the query instance, thus reduce the calculation time complexity.

BA Interview Question & Answer

Write a query in SQL to obtain the names of all patients who has been undergone a procedure costing more than $5,000 and the name of that physician who has carried out primary care.

Answer:

SELECT pt.name AS "Patient",

p.name AS "Primary Physician",

pd.cost AS "Procedure Cost"

FROM patient pt

JOIN undergoes u ON u.patient=pt.ssn

JOIN physician p ON pt.pcp=p.employeeid

JOIN PROCEDURE pd ON u.procedure=pd.code

WHERE pd.cost>5000;

https://www.w3resource.com/sql-exercises/hospital-database-exercise/sql-exercise-hospital-database-37.php

LeetCode Question & Answer

Subsets

Deion:

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:a

The solution set must not contain duplicate subsets.

Solution:

子集問題就是隱式圖的深度優先搜索遍歷。因爲是distinct，所以不需要去重。

Code:

Time Complexity: O(2 ^ n)

Space Complexity: O(n)