x****g
发帖数: 1512 | 1 内容是整型你比较容易解决，大不了判定一下啊当前值为INT_MAX,右结点必须为空，否
者错。
问题的引起是因为root->val+1划定下界引起的。
如果是浮点，你就不能定值了。
可以这样解决，其实并不需要判断每个结点的上下界。像单边，只要判单界即可。
就像根节点不用判，初始值随意。
bool isValidBST(TreeNode* root)
{
return BST_Helper(root,0,false,0,false);
}
bool BST_Helper(TreeNode* root, int low, bool checkLow, int high, bool
checkHigh)
{
if(root == NULL) return true;
if(checkLow)
{
if(root->val <= low) return false;
}
if(checkHigh)
{
//if(root->val > high) return false; //if BST support same value at
left ... 阅读全帖 |
|
x****g
发帖数: 1512 | 2 这个思路应该是正确方向。
取2个数，用+-*/操作，注意-/有2个方向，把结果放回剩下的k-2变成k-1子问题递归。
不过/如果不是整形操作，中间结果是浮点的话，精度损失又是个问题。
面试真是苦逼没用的事，遇上这种题，估计10有9挂，恶心啊。 |
|
c*******r
发帖数: 610 | 3 当一个坐标值为整型，另一个为浮点型的时候可以吧？
不清楚什么特别的好处， 同问。 |
|
w********s
发帖数: 1570 | 4 我试过人家什么dp的算法也就比我的n3解法差不多快。
关键是这个虽然是on3，但没有除法，没有浮点，只有整数，速度不慢。
bool online(const Point& p1, const Point& p2, const Point& p3)
{
int dy1 = p2.y - p1.y;
int dy2 = p3.y - p2.y;
int dx1 = p2.x - p1.x;
int dx2 = p3.x - p2.x;
if (dy1 * dx2 == dy2 * dx1) return true;
return false;
}
int maxPoints(vector &points) {
int s = points.size();
if (s < 3) return s;
int max = 1;
... 阅读全帖 |
|
w********s
发帖数: 1570 | 5 没有线性解法，dp还是n^2的，但比n^3看上去好，但实际上也不快。
hashmap和浮点都是要花不少时间的。 |
|
p****e
发帖数: 3548 | 6 A,B,C的解法更局限一点吧，因为只适用于整数情况
如果点是浮点的话，还是要考虑精度问题 |
|
h*******e
发帖数: 1377 | 7 浮点要考虑精度问题的而且这时候要重写 unordered_map的equal函数了， 我现在还
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过 搜了一下发现叫做全特化模板。 |
|
p****e
发帖数: 3548 | 8 A,B,C的解法更局限一点吧，因为只适用于整数情况
如果点是浮点的话，还是要考虑精度问题 |
|
h*******e
发帖数: 1377 | 9 浮点要考虑精度问题的而且这时候要重写 unordered_map的equal函数了， 我现在还
没想清楚为什么这个 哈希函数一定要外面加个namespace std才能通过。
这种template我之前也没见过 搜了一下发现叫做全特化模板。 |
|
s**x
发帖数: 7506 | 10 sigh, 唯一的 trick 就是第六步。 写个浮点数 -123.E+5 , 一清二楚阿。
这个是最直接明了的土办法了。 我是慢慢琢磨出来的， 老觉得网上给出的算法都很坑
爹。 面试高度紧张， 好几个变量直接歇菜。 |
|
s**x
发帖数: 7506 | 11 sigh, 唯一的 trick 就是第六步。 写个浮点数 -123.E+5 , 一清二楚阿。
这个是最直接明了的土办法了。 我是慢慢琢磨出来的， 老觉得网上给出的算法都很坑
爹。 面试高度紧张， 好几个变量直接歇菜。 |
|
|
s****d
发帖数: 56 | 13 Sqrt(a)可以用牛顿法公式迭代得到：
x=(x+a/x)/2.0 （1）
我用Java实现时，用了另一个“等价”公式：
x=(x*x+a)/(2.0*x) （2）
x我用的时double，leetcode测试表明公式(1)总是能收敛到一个固定的value，而公式(
2)却有时会出现最后在两个value跳跃的情况。
比如sqrt(3)，用公式(1)的收敛序列是：
3.0 2.0
2.0 1.75
1.75 1.7321428571428572
1.7321428571428572 1.7320508100147274
1.7320508100147274 1.7320508075688772
1.7320508075688772 1.7320508075688772
sqrt(3)，用公式(2)最后在两个值之间跳跃：
3.0 2.0
2.0 1.75
1.75 1.7321428571428572
1.7321428571428572 1.7320508100147274
1.7320508100147274 1.7320508075688772
1.732050807... 阅读全帖 |
|
s****d
发帖数: 56 | 14 试了(x*x*x+a*x)/(2.0*x*x)，最后也是在两个value跳动：
3.0 2.0
2.0 1.75
1.75 1.7321428571428572
1.7321428571428572 1.7320508100147274
1.7320508100147274 1.7320508075688772
1.7320508075688772 1.7320508075688776
1.7320508075688776 1.7320508075688772
1.7320508075688772 1.7320508075688776
>>x*x然后再除以x导致误差扩大，因为两个数的乘积只能保留前面一部分小数，四舍五入
>>后最后一位可能在两个数字之间跳动。
恩，有道理。
同样是浮点运算，为什么 x=(x+a/x)/2.0 能保证不会出现四舍五入导致的跳动呢 (除
法也有四舍五入啊)？ |
|
|
A*******e
发帖数: 2419 | 16 结果是浮点数，怎么还会有最小比最大差1的问题？ |
|
m******3
发帖数: 346 | 17 感谢面经！
square root of a double number with providing precision, 计算
时间复杂度，注意这里是double，要小心；
这里有什么要注意的么，是不是判断浮点数相等不能直接用==比较？
max points of a line，经典题，但烙印哥
希望的是o（n^2)的hashmap做法
是不是用个map, key就是斜率，value是在这条线上点的个数？
另外design 经典的web calendar,楼主能多说说么，到底什么要求啊，OO design还是
system design?这个题老出现，但是没有很详细的说明到底要求什么。 |
|
Q**F
发帖数: 995 | 18 1. 二维matrix，含0，1。 1是障碍。
00011
11100
从左上角出发到右下角， 可以往上，往下，往右移动。
把1变成0，使得你可以从左上角到右下角。
求最小的变化数字。
2。 两个区间，左闭右开。数字可以是整数或者浮点，
要你判断两个区间是否相交。
特殊例子需要你自己定义。 |
|
c***t
发帖数: 50 | 19 第一题：
应该就是BFS加染色就行了。
第二题：
这题考点在哪？难道是说有可能一个区间是整型和另一个是浮点区间比较？为啥开区间
的数字不能用来比较？ |
|
D*****r
发帖数: 133 | 20 有硬件背景， 和一些系统底层开发的经历， 可能和一般的纯软件面试有点不太一样。
Recruiter说要找背景相近的人面试。没有碰到印度人面试官
1。 面试官对我以前读书时的一个课题比较感兴趣，聊了一会儿。确认我要面试软件职
位后，出了一道题。有一个3维矩阵，从原点开始遍历所有的点。随便怎么走都可以。
2。 算数据流最近N个数的平均值。 接着分别讨论整型溢出的情况和浮点数精度丢失的
问题。
3。 实现一个内核的延时任务处理功能。就是可以注册将来要处理的一些任务，时间中
断发生时，执行那些到时的任务。实现任务注册函数和时间中断处理函数。
4。 A） 写函数实现32位数的位异或操作 （算奇偶校验位）
B） 模拟普通电梯的运行，实现一个电梯控制器
5。 有一个分布式系统，提供一个返回64位数的服务。有两个要求： 1。所返回的数是
唯一的。 2。所返回的是一个近似递增序列。如何实现使得要求1必须满足，要求2不严
格要求，但越接近越好。同时对用户的响应延迟要越短越好。 |
|
c***G
发帖数: 88 | 21 这两年毕业找工作找得很磕磕碰碰，很感谢版上的国人的面经让我最终找到了工作。在
这贴些这两年面过的几家公司一些面积，很惭愧，这些全都跪了。
板上和LeetCode上有的就都不提了，就贴几个我觉得在这个版上不常见到的题目吧。
Pure Storage
i = 0;
五个进程同时run
for (int k = 0; k < 5; k++)
++i;
i最后可能的最大值和最小值。
Tintri
print（x,y,z）函数的参数在堆栈上的顺序, 是x,y,z 还是z,y,x
Google
用正则表达式表达浮点数
i = 0;
五个进程同时run
while(true) {
++i;
print i;
}
所有可能打印的sequence。（瞬间跪了，我至今都不知道这个要怎么回答）
好像还问了个如果是2个进程的话，可否出现打印序列是1,2,2,3,3,3,4，，，
Vmware：
Page Fault的原理
GDB的原理
解释下当你在电脑上输入www.google.com后，从开始请求到最后返回结果的整个过程。 |
|
|
c*******t
发帖数: 123 | 23 那道题目根本就不需要浮点数。
只用整数就够了。 |
|
n*******s
发帖数: 17267 | 24 浮点误差一般是上BigInteger 吧，太久没搞这个了，依稀有点印象 |
|
c*******t
发帖数: 123 | 25 来自主题: JobHunting版 - U电面经历 我说的是0.01毫秒，不是0.01秒。你怪别人看你代码不仔细，你就不能仔细看看别人说
的？
你那个确实是bug. 没有什么real time kernel那么复杂，程序执行有一个特征时间，
比如一次程序执行的特征时间是千分之一毫秒，你时间window判断的浮点数误差只要小
于这个特征时间，
就可以排除这个bug.
楼主缺乏精益求精的科学态度。 |
|
g*******e
发帖数: 140 | 26 难度应该是中等偏下，发挥一般，顺求bless
一共4轮技术面试，HM生病了，没见着。每轮2个工程师，一般是一个本地 + 一个远程
1st: 亚裔小弟弟+英式口音的大姐：
1. 项目自我介绍
2. 浮点bst，找greatest one in the tree that's smaller than the target，
二分搜索简单变形。我犯了个错误，但是自己dry run测试用例的时候发现更正了。另外
一个小问题要注意的就是处理查找结果不存在。
3. 类似utf8字符串(一个字符是单字节还是双字节取决于第一个字节的首bit)，给定中
间一个字符，删除前面一个。在这道题上卡了一会，关键是弄明白向前查找的终止
条件是什么。
2nd: 一位老美大叔+老美小弟弟
1. 项目介绍
2. 从stream中找到top-k frequent items 用hash-table + priority queue解即可,
解释了一下时间复杂度。问了一下写什么测试用例来测试代码。
3. 扩展到多机器大数据上500mm数据，500台机器，怎么解。就是用hash mapping分散
数据到500台机器上，分... 阅读全帖 |
|
w****e
发帖数: 586 | 27 就是经典的token bucket啊，只要存两个数，一个是上次request的timestamp，一个是
当前的token数（浮点数）。
初始化token为50（或者0，取决于面试官要求），上次request的timestamp为开始时间
每次request进来，先用当前时间和上次request时间计算该加多少token，即(
timestamp_now - timestamp_last) * 50, 并且保证token数capped by 50
然后只要token数>=1，就允许这次操作，并token减去1
最后timestamp_last = timestamp_now
一共没几行code，O(1)，没有request也不需要弄个timer在那计时加token，反正下个
request进来的时候会先补token |
|
w****e
发帖数: 586 | 28 不明白你的限制和精度要求。如果就一般双精度浮点都能溢出的话，你算的是啥天文数
字。。
把所有数都归一化到10^200以下，你还能有10^100个数不成
如果要求超高精度，什么几十上百个有效数字，那就另说了 |
|
|
a*******g
发帖数: 1221 | 30 好几年前被考过这道题，当时电面，我先求的斜率，写得乱七八糟的，但也给onsite了
。后来想了想，这个得用向量做。假设输入是两个点(x1, y1), (x2, y2)，然后核心算
法是一个大循环
for (x = 最小的X; x <= 最大的X； ++x) {
利用 (y-y1)/(x-x1) = (y2-y)/(x2-x)
求出 y=(x*y1-x*y2+x1*y2-x2*y1)/(x1-x2)
这时(x,y)是浮点数，如果(x,y)在屏幕内，
打印出离(x,y)最近的整数像素点
}
有些corner case处理一下，譬如AB两点在同一条竖线上。能想到的优化就是有些常数
提前计算好了；再就是可以先算下斜率，如果是线接近水平的话循环X，如果线接近竖
直的话循环Y；再一个优化就是可以先在循环前先求一下X的范围，不必要把X的所有可
能都试一遍。
当然画两点间的线段和两点间的直线不同，线段简单些。 |
|
c***m
发帖数: 104 | 31 如何写一个函数ftos()，转换浮点数为字符串。 |
|
k******a
发帖数: 44 | 32 扫描set，将字符出现频率排序, 然后做一个frequency data的数组，
[{0.0, 0.3, a}, {0.3, 0.5, b}, {0.5, 0.6, c}, {0.6, 0.7, d}, ....]
然后随机产生0-1的浮点数，然后找个数组扫。数组最大是256个items
有点无脑？
不知道follow up是什么样子 |
|
t*******r
发帖数: 22634 | 33 程序有各种各样的吧，non-linear programing 全部都是在算浮点矩阵，
DSP 也算一大堆，就算很多离散的 tree graph 算法也是要算在各个
node 上的 weight 的。 |
|
t*******r
发帖数: 22634 | 34 微积分的问题，其实说白了还是“肉算vs电算”的变革。。。肉算微积分再牛鼻，
撑死也就能造出比如 F-117 这样的诡异形状。。。现在谁会出钱买那破玩意儿？
电算微积分的话，比如有限元啥的，主要还是建模要建好（否则不 converge
算死没商量）。。。至于计算复杂度基本是个已知范围的东东，搞小 trick
的话，INTEL 下一代处理器多装几个浮点啥部件，玩个球。。。
抽象代数倒是没啥办法，不是 NP hard problem 基本不好意思跟人打招呼。
但其实大家解那些 NP hard problem，工业界的大伙儿基本就是刷墙行为，墙
给刷满了看不见窟窿就出货，甭说啥狗屁数学美。连内部分析 tool 的惨不忍睹
的结果基本也没啥好看。。。当然理论没突破，大伙儿也就只能就这样混日子混
饭吃。。。
所以抽象代数当今要从幼儿园 toddler 班抓起，没错的。。。// super fast run |
|
t*******r
发帖数: 22634 | 35 人家每个变量是个浮点数。。。就算是 6 个变量，你穷举 NP 的话，那花都谢了。。。 |
|
t*******r
发帖数: 22634 | 36 另外 “明白” 这个字，也取决于将来用到多少。。。一般人可能会觉得 “数的本身”
vs “数的表达（记数法）” 是简单问题复杂化。。。但在马工课里，负数如果
用 1 的补数系统 encoding 的话，零会有两个 encoding。也就是有两种表达，
但零本身只有一个。。。而 IEEE 浮点数标准里，NaN (Not-A-Number) 实际上
有两个，quiet NaN 和 signaling NaN，这就不仅仅是 encoding（表达）的差别了，
实际的效果不一样。（特么一个静悄悄，另一个直接吼一嗓子中断了，能一样么？）
所以，区分 “数的本身” vs “数的表达（记数法）”，对许多人确实是脱裤子放屁。
但对现代信息学还真的是概念上 simplistic modelling (occam's razor)。
这里最最重要的问题是，这玩意儿的概念，对于大多数普通娃，是不是要在八年级
以前确保建立概念的问题。。。根据大脑灰质剪枝理论，如果进高中如果还没建立
概念的话，那废柴是不是还能回炉，that is the question。。。 |
|
e*i
发帖数: 10288 | 37 ShadowsocksR 耗资源很少。我家的装在一个很老的 arm 小盒子上， dockstar，
内存才 128M， cpu 1.2G，连浮点都没有的。
随便折腾一个 Raspberry Pi 0 （当年 sale 时才99c )，再连接一个 usb-ethernet
adaptor 也可以。
豪华点的，直接整一个 Raspberry Pi 3 model B。
或者整个现在五块钱的 Raspberry Pi 0 W 也成，不过用无线提供服务总觉得
怪怪的。 |
|
t*******y
发帖数: 57 | 38 nope,intel上层头痛的狠.老早amd64位速度就做的超过intel了,不过amd低调,把主频
都标的比较低.大概是半年前的报道,大概是P4最快频率还只有3G的时候.现在咋情形
不清楚.不过不管霎时候同样频率的intel浮点都跑不过amd呀 |
|
g****o
发帖数: 265 | 39 多媒体编辑属于整点
这是好玩，k6-2时代是整数强，浮点弱，
现在反过来了 |
|
|
g******z
发帖数: 5809 | 41 Nehalem在流水线中实现的又一重大变化是重新引入了SMT。SMT最早在Intel Netburst
微架构的P4处理器中出现，并命名为超线程（Hyper Threading）。从技术角度而言，
在Intel引入HT之前学术界和工业界都对基于多线程技术的处理器性能进行过广泛研究
，并且大多认为多线程技术的处理器是今后处理器发展的重要方向。Intel在桌面处理
器中引入多线程技术可谓众望所归，影响深远。但是Intel当时的超线程技术在现实应
用中的表现并不尽如人意。一方面原因是由于超线程需要发挥作用需要CPU、芯片组、
操作系统、驱动、应用软件等诸多方面的支持，而当时各方面对超线程并没有做好足够
的准备，多线程应用相对匮乏；另一方面原因则是Pentium 4当初对于HT技术实现的不
够完善，对于一些单线程的多媒体以及游戏等注重浮点的应用而言，处理器在打开HT之
后的性能提升微乎其微，甚至性能下降。由于Intel在HT上市前进行了大量宣传，用户
对于HT技术期望很高。Pentium 4在打开HT后并没有带来用户期望的性能提升，必然引
起了很多用户的不满。
Core i7终极全面测试
SM |
|
g******z
发帖数: 5809 | 42 这个数据比较有说服力吧。
纯粹浮点运算能力
9400M: 54G flops
GTX 295: 1788.48G flops
HD 5970: 4640 G flops |
|
t**t
发帖数: 27760 | 43 第一次听说用浮点运算比较GPU性能的。又不是GPUPU。 |
|
t**t
发帖数: 27760 | 44 GPU并不是说不能算浮点。但不是GPU的重点。
8600GT/HD3870就不支持计算，是不是说9400M比8600GT/HD3870要强无穷倍。 |
|
n**********e
发帖数: 438 | 45 VIDIA今天正式宣布推出基于Fermi新架构的Quadro专业显卡产品，号称将为设计师、工程师、动画师、研究人员开启计算虚拟化工作站新时代。
Fermi Quadro家族首发成员共包括五名成员，分别是计算系统Quadro Plex 7000、高端桌面型号Quadro 6000/5000/4000、高端移动型号Quadro 5000M，大部分支持ECC错误校验、双精度浮点、新发布的3D Vision Pro立体技术，3D性能最高可达前辈的五倍，模拟性能作多可达八倍，同时还有惊人的几何性能，当然还有OpenGL 4.1、DirectX 11、DirectCompute 2.0、OpenCL 1.0等技术。
Fermi Quadro系列还具备NVIDIA可扩展几何引擎(SGE)和新发布的应用加速引擎(AXE)，可为CAD、DCC、虚拟化应用等带来最快性能，原始三角形输出率最高达每秒钟13亿个。
Quadro Plex 7000 = 集成两块 Quadro 6000
Quadro 6000：
源于GeForce GTX 470，448个流处理器(CUDA核心)，384-bit 6GB G |
|
f*******y
发帖数: 2368 | 46 GPU的计算高度并行，所以非常快。
但缺点是limited instruction set,所以你必须用它提供的API编程，
其次浮点数的运算精度也会有限制。如果有很多双精度的除法，
以及非整指数的开方，乘方，就很难用GPU算。 |
|
F**D
发帖数: 6472 | 47 连converter一起送，再配个有浮点的牙刷头，可以送给朋友自慰用。 |
|
D*****i
发帖数: 8922 | 48 要公平比较的话，要用“性能功耗比”（性能功耗比=每秒浮点计算量/动态功耗）。如
果这个性能功耗比差不多的话，那他们的动态水平差不多。
接下来比静态功耗。静态功耗还跟MOSFET阈值电压有指数关系，大体上阈值电压每增加
80-100mV，静态功耗下降一个数量级，同时性能损失20%左右。所以可以用牺牲性能来
大幅降低静态功耗。ARM可能用了这个办法吧。
还有就是前面提到的电路设计考虑了。为什么现在CPU都用多核呢？因为在不需要最大
性能时，CPU可以把不用的核心关掉以达到省电目的。 |
|
B****t
发帖数: 3129 | 49 嗬嗬，还带刺激浮点的。
头头不够大，不够标准啊。 |
|
|
