《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1117|回复: 7
收起左侧

[其他] 一道Facebook DS SQL题

[复制链接] |试试Instant~ |关注本帖
bleuz 发表于 2017-6-13 13:41:09 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
Write an SQL query that makes recommendations using the pages that your friends liked. Assume you have two tables: a two-column table of users and their friends, and a two-column table of users and the pages they liked. It should not recommend pages you already like.

不知这个Query Work不?
Select b.users, b.pages from pages_table b
Where b.users in (
Select a.friends from friends_table a
Where a.users = my_id
) and b.pages not in (
select c.pages from pages_table c
where c.users = my_id
)

评分

1

查看全部评分

magicsets 发表于 2017-6-26 09:25:59 | 显示全部楼层
我觉得题主用的子查询没有问题,self join的效率应该是比这个使用in/not in的要低的。

对于多数商用数据库系统来说,其优化器(query optimizer)一般可以将单层嵌套子查询优化到最佳的query plan -- 除非是那些需要用window query(也就是使用了OVER (PARTITION BY ... ORDER BY ...))来表达以达到最佳效率的查询。

-- 那么题主的query一般会被怎么执行呢?
-- 这要看表上建了哪些索引。

单服务器规模的数据,可以假定pages_table和friends_table各建有对users的B-tree(或者hash)索引
那么query plan基本上是:
t1 = Index scan on friends_table
t2 = Hash aggregate (distinctify) on t1
t3 = Index nested loops join between t2 and pages_table
t4 = Index scan on pages_table
结果 = Hash anti-join between t3 and t4

时间复杂度是O(# of my friends + # of my friends' liked pages)

不使用子查询而用self join,可能会没有t2的步骤并需要在最后做distinctify(用于去掉重复的tuple),效率反而会低。

----
如果没有索引,那么需要全表scan + Hash semi/anti join,时间复杂度是O(# of rows in friends_table + # of rows in pages_table),对于这个问题来说是非常低效的 -- 而且没有任何一种query写法可以做到高效。

----
对于分布式数据库+海量数据,一般没有全局的索引,不过就这道题而言可以将两个表根据users进行sharding,然后使用局部索引,本质上和单机执行方案是差不多的。
回复 支持 1 反对 0

使用道具 举报

alpha8421 发表于 2017-6-13 15:27:41 | 显示全部楼层
应该是OK的吧。不过实际应用一般应该不推荐使用子查询吧,也可以自join USER_TABLE筛选
回复 支持 反对

使用道具 举报

屋大维 发表于 2017-6-13 20:13:27 | 显示全部楼层
本帖最后由 屋大维 于 2017-6-13 20:16 编辑

我是个新手,我的想法可能比较机械,想讨论一下:
user: user1,user2
like:user,page

1.left join两个table where u.user2=l.user,得到user1,user2,page   (page 可能是none)
2. group by user1,page (page肯定是好友点赞的),count(*)得到user1的好友对各个page点赞的count, order by count(*)desc,得到user1,page,like_count
3. 之后也可以操作得到每个user最推荐的page,利用最大like_count的row
————————————————————————————————————

呀,没考虑到不能是自己点赞过的。那么就是要再筛选一下page了~新手写得好烂,啊哈哈。。。
回复 支持 反对

使用道具 举报

iamchrisa 发表于 2017-6-19 01:57:10 | 显示全部楼层
这个是work的,但是有个问题是这样用b.users in () and b.pages not in()可能会非常非常慢一旦数据量非常大的时候。
回复 支持 反对

使用道具 举报

 楼主| bleuz 发表于 2017-6-21 13:03:15 | 显示全部楼层
iamchrisa 发表于 2017-6-19 01:57
这个是work的,但是有个问题是这样用b.users in () and b.pages not in()可能会非常非常慢一旦数据量非常大 ...

同意。谢谢。
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2017-6-25 23:29:34 | 显示全部楼层
本帖最后由 leonardcohen 于 2017-6-25 23:35 编辑

1 select page in (subquery) where page not in (second subquery) . this is the naive solution
2 if need frequency, just count(distinct page) order by 1 desc
3 The follow up must be "do not use subquery", (you can refer to glassdoor, this will be the follow up and we should not use subquery in production as it perform bad.)
4 So how to solve if no subquery? Always, and only, self join existing table.
(I am not sure whether below works or not? Hey, anyone solve this problem without subquery?)
select p1.page
from user table u1
join page table p1 on u1.friends = p1.uid
left join user table u2 on u1.uid = u2.uid
left join page table p2 on u2.friends = p2.uid
where u1.uid = @myuid and p2.uid != @myuid and p1.page != p2.page
5 Another way to avoid subquery is to use temp table, its performance is better than subquery.

I find a similar question:
https://stackoverflow.com/questions/7819654/sql-to-get-all-the-friends-of-friends-whos-not-my-friend


回复 支持 反对

使用道具 举报

leonardcohen 发表于 2017-6-25 23:30:44 | 显示全部楼层
alpha8421 发表于 2017-6-13 15:27
应该是OK的吧。不过实际应用一般应该不推荐使用子查询吧,也可以自join USER_TABLE筛选

could you provide the sql for 自join USER_TABLE筛选 solution? thanks.
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-23 15:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表