|
y****n
发帖数: 743 | 2 如果不考虑正负和溢出，一行代码的事。
public static int Div(Int64 a, Int64 b, ref Int64 m)
{
return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
>= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
}
public static Int64 Div(Int64 a, Int64 b)
{
if (b == 0)
throw new Exception("Div By 0");
else if ((a == Int64.MinValue) && (b == -1))
throw new Exception("Overflow");
bool neg = (Math.Sign(a) != Math.Sign(b));
Int64 mod = 0;
Int64 result = Div(a, b, ref mod... 阅读全帖 |
|
y****n
发帖数: 743 | 3 如果不考虑正负和溢出，一行代码的事。
public static int Div(Int64 a, Int64 b, ref Int64 m)
{
return a >= b << 1 ? (Div(a, b << 1, ref m) << 1) + Div(m, b, ref m) : a
>= b ? (m = a - b) > 0 ? 1 : 1 : (m = a) > 0 ? 0 : 0;
}
public static Int64 Div(Int64 a, Int64 b)
{
if (b == 0)
throw new Exception("Div By 0");
else if ((a == Int64.MinValue) && (b == -1))
throw new Exception("Overflow");
bool neg = (Math.Sign(a) != Math.Sign(b));
Int64 mod = 0;
Int64 result = Div(a, b, ref mod... 阅读全帖 |
|
y****n
发帖数: 743 | 4 改编成整数开方。算法复杂度说不清楚，远好于O(lgN)。
我只假设是O(lg(lgN))。
static Int64 SqrtInt(Int64 num)
{
Int64 maxRoot = (Int64)1 << 31;
Int64 root = 1;
Int64 oldDiff = Int64.MaxValue;
Int64 diff = num - root * root;
int loop = 0;
while ((loop < 2) || (Math.Abs((double)diff) < Math.Abs((double)oldDiff)
))
{
root = Math.Min(maxRoot, root + diff / root / 2);
oldDiff = diff;
diff = num - root * root;
loop++;
}
return (diff < 0) ? root - 1 : root;
} |
|
v***a
发帖数: 365 | 5 第一次出现理论题，好题目，
可以用XXX扫描法，名字忘记了，思想就是每次扫矩阵的一条斜线
核心程序如下：
int64 t(0LL);
for (int64 k = 0LL;;k++) {
for (int64 startpos = 0LL; startpos < k; startpos++) {
int64 speed = k - startpos;
for (int b = 0; b < 4; b++) {
int64 p = bias[b][0] * speed * t + bias[b][1] * startpos;
if (ask(p, t++) == false) continue;
...
试了所有 startPos -1000 to 1000, speed -1000 to 1000,
都可以在 1,000,000 步之内出解
试了下 start == speed == 12345
猜了 1,219,290,964 步
步数增长还是很快的，当然肯定不是指数了 |
|
d***n
发帖数: 832 | 6 第一题可运行C# code，题目给出的test cases都过
不过我觉得我理解有误，因为b是2的整数倍这条信息没有用到
public static Int64 GetNumber(Int64 a, Int64 b)
{
if (a <= b) return b;
Int64 rem = b-a%b;
if((Int64.MaxValue - rem) < a)
{
throw new ArgumentOutOfRangeException();
}
return a + rem;
}
第三题在windows叫access violation。segmentation fault应该是unix的概念而且很
老了。 |
|
b*****n
发帖数: 618 | 7 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refresh，但是每次refresh分四年给）
再上各个公司的面经和感受：
Yahoo：
最早面的公司，面的是Flurry Team，Yah... 阅读全帖 |
|
m******3
发帖数: 346 | 8 Facebook的这两个
6. system design - design facebook music system，只需要design service tier，
两个API
get_top_10_list_music_ids(int64 userid) - return top 10 most frequent
listened music ids for a given user last week. 这个call在load页面的时候要进
行，所以对latency要求比较高。
record(int64 userid, int64 musicid, int64 timestamp) - 每当user听一首歌，就
需要记录下来，这个可以asynch进行，需要eventually consistent，但不需要每听一
首歌马上就能反映到上一个call中。要做各种spec和resource的estimation。
7. 抄dropbox那个问题，get_hits_last_5mins(), record_hit()，但是后面又扯到
system design，如何thread saf... 阅读全帖 |
|
f*******r
发帖数: 976 | 9 恭喜，都是好包袱！
关键字: 面经
发信站: BBS 未名空间站 (Sat Jun 13 17:27:31 2015, 美东)
前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refres... 阅读全帖 |
|
w********p
发帖数: 948 | 10 public static int Div(Int64 a, Int64 b, ref Int64 m)
这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
写几行的好。
我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
code 要简洁加上易懂，易维护。
a |
|
w********p
发帖数: 948 | 11 public static int Div(Int64 a, Int64 b, ref Int64 m)
这个方程的实现很有可能被认为coding style 不好，看起来，改起来都麻烦。不如多
写几行的好。
我认识的人中确实有题都做出来，但是因为coding style被dream company拒掉的。
code 要简洁加上易懂，易维护。
a |
|
a****a
发帖数: 5763 | 12 2011年12月3日，LLVM 3.0正式版发布，完整支持所有ISO C++标准和大部分C++ 0x的新
特性， 这对于一个短短几年的全新项目来说非常不易。
开发者的惊愕
在2011年WWDC（苹果全球开发者大会）的一场与Objective-C相关的讲座上，开发者的
人生观被颠覆了。
作为一个开发者，管理好自己程序所使用的内存是天经地义的事，好比人们在溜狗时必
须清理狗的排泄物一样（美国随处可见“Clean up after your dogs”的标志）。在本
科阶段上C语言的课程时，教授们会向学生反复强调：如果使用malloc函数申请了一块
内存，使用完后必须再使用free函数把申请的内存还给系统——如果不还，会造成“内
存泄漏”的结果。这对于Hello World可能还不算严重，但对于庞大的程序或是长时间
运行的服务器程序，泄内存是致命的。如果没记住，自己还清理了两次，造成的结果则
严重得多——直接导致程序崩溃。
Objective-C有类似malloc/free的对子，叫alloc/dealloc，这种原始的方式如同管理C
内存一样困难。所以Objective-C中的内存管理又增... 阅读全帖 |
|
l*****d
发帖数: 359 | 13 first, you should know a 64-bit int has much larger range available than than 32-
bit int, right?
This kind of usage for portability. for example in a machine when 'int' is
4bytes and 'long' is 8bytes:
typedef int Int32
typedef long Int64
use Int32 and Int64 in your program.
When porting your program to a difference machine when 'int' is 8bytes, but
'short' is 4 bytes, you can just change the type define:
typedef short Int32
typedef int Int64
and you don't need to change anything in your program |
|
b***i
发帖数: 3043 | 14 怎么看到这段代码。有人说，nHeight是32位的，所以到了一定时候就变负数了。右移
负数位应该就不移动吧。这样，多少年后，比特币又重新增发了。
int64 static GetBlockValue(int nHeight, int64 nFees)
{
int64 nSubsidy = 50 * COIN;
// Subsidy is cut in half every 210000 blocks, which will occur
approximately every 4 years
nSubsidy >>= (nHeight / 210000);
return nSubsidy + nFees;
} |
|
|
r******r
发帖数: 700 | 16 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
r******r
发帖数: 700 | 17 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
w*****t
发帖数: 485 | 18 这样的话就是并行处理了， 每台机器先将本机的数据排好序，最后再做多机的两两归
并。
如果预先知道重复元素比较多的话，可以考虑用{int64 value:int64 count}来节省内
存占用。 |
|
f********t
发帖数: 6999 | 19 【 以下文字转载自 JobHunting 讨论区 】
发信人: mudhoof (正在长牙的羊), 信区: JobHunting
标 题: 这么热闹, 我也报Google offer
发信站: BBS 未名空间站 (Tue Feb 23 12:32:47 2010, 美东)
今天刚刚通知的, 特别感谢一起讨论的krone, geniusxsy, hnm, 特别是blaze教了我很
多, 还要特别感谢mitbbs59的总结帖
一起报offer, 好事成三, 大吉大利, 包子分光为止
贴下我的复习材料
题目大全:
http://www.spellscroll.com/viewquestions/?tag=algorithm
http://www.thecareerplus.com/?page=resources&cat=10
http://interviewcyclopedia.blogspot.com/
http://www.doctorinterview.com/A.html
http://toptechnotes.blogspot.com/search/label/algorith... 阅读全帖 |
|
H********g
发帖数: 43926 | 20 Int32 -- (-2,147,483,648 to +2,147,483,647) 如果存0.1分的话是正负2千万元
Int64 -- (-9,223,372,036,854,775,808 to +9,223,372,036,854,775,807) 如果存0.
1分的话是正负9千万亿元，可以精确到0.1分。对于国家银行来说应该够用了吧？
双精度浮点数大概有16位十进制有效数字:the total precision is therefore 53
bits (approximately 16 decimal digits, 53 log10(2) ≈ 15.955)，所以不如用
Int64有效率。 |
|
s**********o
发帖数: 14359 | 21 【 以下文字转载自 JobHunting 讨论区 】
发信人: rongxuer (蓉儿), 信区: JobHunting
标 题: 如何秒杀99%的海量数据处理面试题
发信站: BBS 未名空间站 (Thu Apr 5 02:08:57 2012, 美东)
海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的... 阅读全帖 |
|
N******K
发帖数: 10202 | 22 写一个类 然后两个变量
class int128
{
int64 High
int64 Low
}
怎么知道 Low这一位溢出？ 比如 Low +=1
有没有现成的这种东西 我觉得应该有吧 |
|
w***g
发帖数: 5958 | 23 我可能是在找骂。我的理解是一个startup的产品是需要很多iteration的。按那钱时间
分的话是
1. 拿angel fund之前：出一个糙快猛的demo，但是没有什么会最终保留到产品里。这
个阶段发挥作用的主要是founder，并不需要很好的代码质量。每个人拿的equity可能>
10%，没有工资。
2. 拿series A之前：有确定的磁盘数据结构(sql schema)和模块间的接口。最核心的
那些代码可能基本上finalize了，但是外围由很多还是糙快猛的东西。这个阶段需要一
两个技术大拿来确定基本框架，加起来可能有三五个全栈程序员以一当十把东西做出来
。这个阶段加入的人equity最多也就1~2%，一般可能也就0.x%。这时候加入的那些人基
本上确定了整个公司的culture，这些人几年之内不应该离职。
3. 拿到series A之后由足够的人力了，再精打细造各个模块和增加更多的模块。这时
候再加入，除非公司IPO或者卖大钱，equity实际上已经没太大意义了。这时候单个员
工做的东西和公司的生死存亡其实已经没太大关系了。
2之前最重要的是设计/架构而不是编码，2之后才... 阅读全帖 |
|
|
c****y
发帖数: 11 | 25 size_t带来很多不便，其实size用int或者int64最好。超出int64表示范围的大数字，
自己想办法。
+ |
|
x****k
发帖数: 2932 | 26 我同学在四线城市年终奖太多了，公司给他转账后银行余额直接变成负数了，一查，原
来是数额太大，int64溢出了。现在银行说过年放假没人，要等年后再改代码。一家人
钱也取不出来，这个年也没法过了。现在微信上找我借钱，我只好顾左右言其他。 |
|
i*****9
发帖数: 3157 | 27 因为出现了大量的 int64
：为啥屏蔽这个网站呢。。。为了训练码农独立思考的能力么？
： |
|
发帖数: 1 | 28 这个笑话好冷
[在 insect9 (insect9) 的大作中提到：]
:因为出现了大量的 int64 |
|
g*********s
发帖数: 1782 | 29
0~255 is for 1 byte. 64bit = 8byte.
unsigned char tab[256];
an int64 need 8 times of table lookup. |
|
s*****n
发帖数: 5488 | 30 两个int64或者long long就搞定了。 |
|
d****z
发帖数: 53 | 31 如果是字符的话，就int64的vector bit记录出现了哪些字符，然后两个and一下就知道
有没有duplicate了，O（1）space，linear time |
|
v***a
发帖数: 365 | 32 Define:
C[i]: Total different number of blocks when height_1 weight_i. Including non
-solid structure. Like Fibonacci, number:
C[i] = C[i - 1] + C[i - 2] + C[i - 3] + C[i - 4]
B[i]: Total different number of blocks when height_N weight_i. Including non
-solid structure. Please use the O(LogN) method to calculate power:
B[i] = power( C[i], N )
A[i]: Total different number of blocks when height_N weight_i. Only SOLID
structure.
A[i] = B[i] - Sum(A[j] * B[i - j] | for j = 1 to (i - 1, inclusive))
A... 阅读全帖 |
|
p*****2
发帖数: 21240 | 33
有道理。不过这个跟hashtable不一样吗？hashtable说不定比这个还省空间。而且如果
变成int64的话，空间不就增加了？
我怎么感觉应该用异或呢？不过我没导出来公式呢。 |
|
|
r*****e
发帖数: 792 | 35 先上个F的题吧：
第一个人，coding：
2sum，给了sort后2个ptr的解法，问还能更快吗？那就hash吧，但是
用了unordered_map,又问有别的container吗，才反映过来用hashset就够了。
然后是计算a^b%c， 假设a,b,c都很大，但都是int32.过程中因为他先提到了
prime number，以为是要计算prime，于是后悔好长时间没有看那个什么sieve的
算法了，导致有点精神不集中。回过神来以后做出来了，就是二分，但是
有个地方没注意temp结果应该用int64存一下，一再追问下答出来了。整体这轮
感觉还不错。说个题外话，面试的是个从google跳过去的胖子，好像是个东欧
人，在写题目的时候挺个大肚子，吭哧吭哧的，看得我想笑。 |
|
r*****e
发帖数: 792 | 36 正解。唯一要注意的就是乘法的结果要放在int64里。 |
|
p****n
发帖数: 4 | 37 Get the Sum of 对角线 of 螺旋（线) in n X n
Starting with the number 1 and moving to the right in a counter-clockwise
direction a 5 by 5 .
The issue is that the 1 is in the middle.
Normally:
for example :螺旋（线) (3X3)
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
[leetcode]Spiral Matrix II
(2013-03-12 15:14:57)
转载▼
标签：
分类： leetcode
Given an integer n, generate a square matrix filled with elements from 1 to
n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8,... 阅读全帖 |
|
w*****e
发帖数: 1050 | 38 sde intern
问简历的，说了十几分钟。
1.recursive 题目。 leetcode 类似题目。不难。
时间，空间复杂度。
2.实现 void Schedule(int64 timestamp, function* to_run) = 0;
多个模块会调用这个function*， 如何实现。
3.fibonacci
为啥不用recursive。分别的时间复杂度。空间复杂度，包含函数栈上的。
3.设计电梯系统。20层，3个电梯。
估计希望不大了。2、4答的不好。完全没准备过设计题，只刷了算法题。
求大牛指导如何准备。 |
|
s******d
发帖数: 424 | 39 是不是需要用priority_queue 保存 pair ，还应该用最小堆
RunSchedule 这样写可以吗
void RunSchedule()
{
while(true)
{
lockqueue.lock();
if(!runningtasks.empty())
{
// get all expired task, save functio* in a queue
// start another thread and pass the queue to it
}
lockqueue.unlock();
sleep(100);
}
} |
|
s********x
发帖数: 81 | 40 这是网上看到的别人的解答。
http://www.careercup.com/question?id=4827656025538560
Use a ring buffer (circular queue) of type Message of size 5000*60*10 which
is 3000000B or 3MB. The memory footprint will be 3MB*sizeof(Message) so that
gives us upper limit of 100MB (string ticker are no more than 4B and fixed
length for int64/double).
Maintain a rolling sum (type double) and every time adding a stock price,
add it to sum and subtract the last purged value.
Simply return sum/Total entries |
|
A*******e
发帖数: 2419 | 41 折腾一晚上才发现是这个问题。怎么C++的函数头给的是int？ |
|
A*******e
发帖数: 2419 | 42 26^7就大于INT_MAX了。有个测试例子用六位的串。在计算过程中可能溢出，取决于实
现。
如果溢出也是要考虑的一部分，这道题不该只是道简单题啊。 |
|
d*****c
发帖数: 605 | 43 如果你说你自己考虑，那确实是要考虑overflow。不过他的test case里面没有，int就
够过了 |
|
A*******e
发帖数: 2419 | 44 是我的方法不对。算"CFDGSXM"时用到(26^7-1)/(26-1)，就溢出了。
按照Z映射到10的方法，其实很简单，不用上面的指数运算，不会溢出。 |
|
m**c
发帖数: 22 | 45 近期面的湾区职位，两轮电面一轮算法一轮c++，然后被要求飞去西雅图总部面一天5轮
含一轮午餐闲聊。
onsite第一轮一个国人兄弟和远程视频的白人小妹，考了一个run length tree简单搞
定，自己修掉几个遗漏。被调戏说还有bug，结果提示少了一个分号。
第二轮一个白人大姐和白人大哥，白人大姐远程对我背景很感兴趣，帮她解答一些新技
术的疑惑。白人大哥很nice基本涉猎过我的领域。然后clone graph，提供两个版本，
简单聊了scale limitation。
第三轮吃午饭一个白人大叔总监和上海大姐闲聊，各自交换对方技术经验和各城市环境
评价，都很nice，影响不错。
第四轮一个白人大叔和印度小伙聊技术背景，query optimizer都用非常基本的优化，
给他们讲了一个中高级的技术，尽量通俗，感觉他们一知半解。然后迅速实现一个简化
版基于page_alloc的allocator，并建议了各种refine。
最后一轮面白人老头（在湾区的招聘经理）和白人大叔经理，以为胜利在望结果大意了
，被大叔埋坑问设计vending machine的public interfaces，也... 阅读全帖 |
|
m*****k
发帖数: 731 | 46 不允许溢出求无穷多数据的int64 avg算法题
请教这个咋做啊？ |
|
p**2
发帖数: 613 | 47 fuck their leadership principles +Int64.MaxValue
at
and
.
and
at
screen |
|
发帖数: 1 | 48 周末在家。 苦中作乐。 写个python script, poll 一把uscis case page.
看看到底多少cases 已经approved 了。
下面的结果 不一定 完全正确。 大家 看看. 参考 娱乐 一下。
Methodology:
download and parse application status between
EAC1718649100
and
EAC1718651099
and extract(deduce) its USCIS Accept and its Approval dates
* The status page of approved cases do not show when cases are Accepted.
Assuming case number is assigned in FIFO order, the Accepted date of an
approval case will be no earlier than that of the first non-completed case
came before it.... 阅读全帖 |
|
z**********e
发帖数: 22064 | 49 【 以下文字转载自 Military 讨论区 】
发信人: xykkkk (asdf), 信区: Military
标 题: Re: 国内表弟给我算了个账，说他过年造了两万多
发信站: BBS 未名空间站 (Sat Feb 13 16:50:22 2016, 美东)
我同学在四线城市年终奖太多了，公司给他转账后银行余额直接变成负数了，一查，原
来是数额太大，int64溢出了。现在银行说过年放假没人，要等年后再改代码。一家人
钱也取不出来，这个年也没法过了。现在微信上找我借钱，我只好顾左右言其他。 |
|
n******t
发帖数: 4406 | 50 很多2^50的数运算，int64不一定够。
2^50多大没什么意义,他又没说要干什么，也没说里面放了什么。
真是皇帝不急太监急。 |
|
