N台server，求median - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - N台server，求median

相关主题
● 这题怎么做啊？	● M大小的数组中选出前N个元素（如果M和N都很大）
● 问道大数据的题	● 找第K个最小的元素
● 说一下上周五狗狗家的面试另外求祝福	● 在线紧急求助一道system design面试题，面经内附
● 赛马题	● [quantcast面经] software engineer
● find median for k sorted arrays	● 一道貌似很凶残的g家题。
● 问一道google的题	● 求问一道MS面试题
● google老题：Find kth largest of sum of elements in 2 sorted array	● (昂赛特设计题)如何设计一个itunes/google play购买物品的系统
● 问个题	● 被Facebook的面试的一道题目难倒了

相关话题的讨论汇总
话题: median话题: server话题: 每台话题: central话题: response

进入JobHunting版参与讨论

(共1页)

b*********3
发帖数: 748

今天碰到一道题，觉得对方提示有点不可思议。
给定N台server，每台记录了X个response time。每台的X不一定一样。然后给一台
central server，求出所有response time的median。
先想了每台回复median，但这样俨然不对。然后就想都传给central server，但是这样
太浪费流量。对方提示每台都只给central发一次数据就求出来。还说想想average怎么
求的。但是average和median完全两码事，没任何联系啊。
谢谢！

I*********g
发帖数: 93

显然不可能。最简单的情况两台机器，同意大小n的排好序的数组，都需要o(logn)复
杂度

(共1页)

进入JobHunting版参与讨论

相关主题
● 被Facebook的面试的一道题目难倒了	● find median for k sorted arrays
● 2D median problem	● 问一道google的题
● Google Interview Question	● google老题：Find kth largest of sum of elements in 2 sorted array
● 两个sorted array找median	● 问个题
● 这题怎么做啊？	● M大小的数组中选出前N个元素（如果M和N都很大）
● 问道大数据的题	● 找第K个最小的元素
● 说一下上周五狗狗家的面试另外求祝福	● 在线紧急求助一道system design面试题，面经内附
● 赛马题	● [quantcast面经] software engineer

相关话题的讨论汇总
话题: median话题: server话题: 每台话题: central话题: response

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天