d*******8
发帖数: 785 | 1 interger是第一位1，0表示负的，一般int 4个bytes,不过可能就前2位或者后两位放值
short int 2 bytes,
如果只给其中一个byte,
倒不知道怎么搞了，求答案 |
|
b******v
发帖数: 1493 | 2 由题目条件可以知道mu/sigma = qnorm(0.16)
而四个quarter之和是一个N(4mu, 2sigma)的正态分布
根据积分里换元法，它为负的概率是pnorm(2*qnorm(0.16)) = 0.023355
以上qnorm和pnorm都是统计软件R里的函数 |
|
w**********i
发帖数: 36 | 3 ms in cs, 有两三年C#经验, prefer project management经验，小公司，所以会是全
面负
责。 |
|
|
f****4
发帖数: 1359 | 5 MBA的朋友告诉我，问你weakness的时候，要负负得正的说
比如说 很久以前，做事情没有规划，弄到后面deadline就很忙；但是，后来我发现可
以做一个time schedule，照着它做，就能很好的完成任务，从那以后，再也没在
deadline乱忙过。
所谓的负，一定要是已经被改正的weakness；一定要有“但是”，这个但是就是说你现
在已经改正了。改正的结果就是所谓的正，这个正就是你的强项！！！
hr这么问你，不是要听你的weakness，而是要听你的strongness |
|
s*********t
发帖数: 1663 | 6 一共遍历n个元素，o(n)
想想那个连续子序列最大和的题，只要出现负的就跳过中间所有的从下一个元素开始 |
|
r****o
发帖数: 1950 | 7 多谢，这题是不是可能有多解，只要找到一个就可以了?
一共遍历n个元素，o(n)
想想那个连续子序列最大和的题，只要出现负的就跳过中间所有的从下一个元素开始 |
|
h**6
发帖数: 4160 | 8 显然不能计算达到加油站加油之后的油量，因为需要的是成功达到下一个加油站，也就
是加油之前剩油非负。
看下图：
(2) (4)
A-----B
| |
| |
| |
| |
C
(6)
存油A2，B4，C6，距离AB5，BC3，CA4，限定顺时针行驶，那么显然应该由B出发而不是
由C出发。 |
|
y*c
发帖数: 904 | 9
1000 - 1 其实是 1000 + 1111 = 0111 加一个溢出位。既然我们用了最高位来表示正
负，就不能用它来做有溢出的运算了
用取反运算就明确是对位操作，而不是算术操作。 |
|
z****n
发帖数: 1379 | 10 靠，我自己写过一个出去玩以后回来分账还钱的程序，核心问题就是这个，老美不都是
当场aa吗，居然google能问到这个。。。
就是算一下每个人总共欠别人多少刀就行（欠款为负就表示别人欠他），跟楼下给的算
法思路差不多 |
|
h**6
发帖数: 4160 | 11 不需要排序，遍历两次数组即可。第一次把沿负的传递一遍，第二次沿正的传递一遍。 |
|
j**l
发帖数: 2911 | 12 除了时间复杂度外，至少还有处理溢出的问题，负指数的问题，结果用int存还是
double存的问题，能否用数组表示大整数作乘方的问题，各种test cases的问题，要考
虑得很多 |
|
t******3
发帖数: 29 | 13 今天的比较简单，基本的问题只问了两个
1、三端NMOS，Gate接偏置电压Drain接R到VCC，Source接Current source(DC),问从
Source看进去的阻抗是多少？做了什么假设
2.三端运放，负端接OUT，电源电压是1.8V，正端接STEP电压源，0.8V～1.3V，问输出
是什么，做了什么假设 |
|
c*****e
发帖数: 74 | 14 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
次都只做了一道题，太慢了，看看别人都是好几道题。 |
|
g*********s
发帖数: 1782 | 15 正整数系数多元一次方程，求所有非负整数解？
这不就是print_all_coin_combination()吗？ |
|
c*****e
发帖数: 74 | 16 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
次都只做了一道题，太慢了，看看别人都是好几道题。 |
|
g*********s
发帖数: 1782 | 17 正整数系数多元一次方程，求所有非负整数解？
这不就是print_all_coin_combination()吗？ |
|
f*********i
发帖数: 197 | 18 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
报版上，顺便求祝福。
第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
string 中reverse word， 就是把how are you => you are how，reverse+reverse，
没有什么tricky的，写程序的时候有点麻烦，不过没有出错。
第四轮：老印，这个人是最tough的... 阅读全帖 |
|
z****o
发帖数: 78 | 19 存储city之间的距离的题目，可以有一下两个假设：
1. city1 到 city2 = city2 到 city1
2. city1 到 city2 距离是非负的。
这样的话，可以计算 cityi 到 cityj 的最短路径的边集S(i,j) = { e1,e2,e3..}
S = S(0,1) U S(0,2) U S(0,3) ..... U S(1,2) U S(1,3) U ..... U S(i,i+1) U S
(i,i+2) U ...
最后存下来S就可以了。这种存法的空间是 |S|*( 2*sizeof(int) + 1* sizeof(double
) );
这个空间去和 ((n-1)+(n-2)+(n-3)+...+2+1)*sizeof(double) 的矩阵存法比较一下，用
空间使用比较省的一种来存。|S|够小的时候用第一种比较好，比如所有的city在一条
线上。
|S|不小的时候用第二种比较省，比如city均匀分布在圆上。 |
|
a********e
发帖数: 508 | 20 原来那个没问题吧
全负的数组，结果取空集，题目里有写
rather |
|
c******t
发帖数: 391 | 21 刚才那个例子不是全负，{-4,-3,-2,1}，会返回(-3+1)=-2 |
|
g*****x
发帖数: 799 | 22 其实很简单，reverse indexing
还是以{1, 1, 2, 4, 4}为例，reverse indexing后得到新数组rev_index {-1, 0, 2,
-1, 3}, 其中rev_index[i] == n表示 i 第一次在原数组中出现的位置，那找到rev_
index[1]和rev_index[4]，都!=-1表示他们都出现过，即返回{0, 3}。。。缺点是如果
sum=999999而且假设数组中元素都非负，那就要建一个1000000大的rev_index |
|
l********t
发帖数: 123 | 23 签了nda,phone和onsite写一起了
1.把一个字符串转成float,字符串可能是负的一百点三还有个指数E-09这样的
2.反转单链表..
3.给一个整数，求next permutation 就是数字组成一样的 但是比这个数大的最小的一
个数
4.一个很大的文件 怎么去掉duplicate
5. circular sorted array找元素
6.分层打印tree
7.一个字符串，每个字符可以替换成好多其他字符，打印所有可能
8.很简单的一个题，就是会用vector, set, map, pair这些玩意就行了
9.应该还有一个题，不难，但是怎么都想不起来了...
效率很高，拒信很快，move on啦~~ |
|
d*******l
发帖数: 338 | 24 对于每个非叶节点，算出对应的maxValue，这个可以O(n)做到。
对于每个非叶节点，用maxValue(leftChild)+maxValue(rightChild)去更新当前最大值
。也可以O(n)做到。
其实本质上就是wwwwar3的方法，保存每个节点的maxValue用到hashmap，如果是完全二
叉树也可以考虑用数组，那这个问题就非常像DP了。
wwwwar3的方法中对于null返回0感觉值得商榷，如果认为X和Y可以是同一个节点那可以
这么做，否则返回负无穷比较合适。 |
|
d*******l
发帖数: 338 | 25 我觉得如果root==null返回负无穷的话，就不一定需要complete binary tree |
|
c*********t
发帖数: 2921 | 26 来自主题: JobHunting版 - 问个面试题 是不是这个题要假设所有的数都是正的。负的话，你的算法很难work。 |
|
b******t
发帖数: 965 | 27 没有负的边 all pairs shortest path就是DP
只是复杂性大一点而已
,0
的情况 |
|
b******t
发帖数: 965 | 28 没有负的边 all pairs shortest path就是DP
只是复杂性大一点而已
,0
的情况 |
|
|
|
l**********1
发帖数: 415 | 31 向大牛们求教：
1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
有求一条路的。那位牛人给个所有路径的code？
2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
max.
谢谢！ |
|
|
r********g
发帖数: 1351 | 33 第一题记得是用两个list来记录正的最大值和负的最大值。但是corner case不是很清
楚：
比如：如果只有一个元素，是负数，那返回这个负数，还是返回0呢？（0的意思可以理
解成0个连续元素）。
int maxSubArray(int A[], int n) {
if(n == 0) return 0;
//init
int *minList = new int[n];
int *maxList = new int[n];
memset(minList, 0, sizeof(int)*n);
memset(maxList, 0, sizeof(int)*n);
int maxP = 0;
if(A[0] > 0) {
maxList[0] = A[0];
maxP = A[0];
}
else minList[0] = A[0];
//compute
for(int i = 1; i < n; i++){
if(A[i] == 0)... 阅读全帖 |
|
f*****e
发帖数: 2992 | 34 知道,boyd那本书上有这题。最简单的方法就是分段看斜率，一开始斜率为负，后来斜
率为正。就是一个拔河的过程。其实看到|xi-x|是凸的，n个凸函数的和任然是凸函数
，心里就有谱了。 |
|
t****a
发帖数: 1212 | 35 好思路阿。不过有非负整数的系数约束条件。还是只能DP。
等牛人出手！ |
|
O******i
发帖数: 269 | 36 确实是只有删除了。
现在才知道这题应该这样分析才有冷静的思路
1) 读入初始数据后，就是正数轴上以非负整数为端点的一系列排序好且不相交的线段
，有些线段退化为单个的离散点
2) 给定的x, 必须位于某条线段上
3) 下一个数，就是扩展x所在线段(长度增加1）后新的右端点
4) 线段扩展后，填补了gap,可能导致两条相邻的线段合并为一条更长的线段
5) 如果我们用有序数组(每个元素是一个区间)表示这些线段，就是经典的合并区间那
道题，但是考虑到删除两个区间为一个区间会引起其他元素的O(N)移动，改用平衡BST,
可以把这个操作降为O(logN)
这道题的核心，一个是“以线代点", 另外一个是“以树代替数组”
可惜我明白的太晚了，虽然区间合并题和BST都知道，就是没有想到把这两个结合起来。 |
|
D**********d
发帖数: 849 | 37 我想到的是 O(nlgn) 区间合并问题：
1. sort 所有端点 O(nlgn).
2. 扫描所有端点一次 O(n) 左正右负. |
|
l*******0
发帖数: 63 | 38 为啥我感觉，应该是a是非负，b是非正时说明存在呢？请您在解释一下？谢谢。
E |
|
X******2
发帖数: 5859 | 39 取自若干个公司，名字就不说了，不少题是陈题。
1）用biased coin实现uniform sampling，如何有效实现？
2）一个超大的TABLE（大小在BILLION级别），不知大小内存也放不下，
如何从中随机抽样出百万条记录？
3）有一个数组其中存放整数，有正有负，找出其中连续的和为0的数字。
要求线形算法。
4）2-SUM （数组已经排好序）
5）一个数组，找出最大连续和
6）两维数组（行列均已排序）查找
7）给出一个单词之间未加空格的句子，加空格
8）有很多点，找出离原点最近的K个
9）说明对于任何大于2的素数，P*P-1可以被24整除
10）对LOGISTIC REGRESSION（变量很多）编程求解 |
|
e********r
发帖数: 24 | 40 最后一个题意不明，如果是“保证”，是不是应该求负得最多的那条路？
of
,3 |
|
d*****0
发帖数: 72 | 41 May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1()：能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
，注意edge case
2. given 一个字符串，这个字符串是一个算式，包含加减乘除，没有括号，符号和数
字之间以一个空格格开，比如：“1 + 2 * 4 / 5”，return算式的结果
3. given两个字符串，分别表示两个元素等和不等，比如：
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾，这个例子就有矛盾：A!=C
given提取元素的method: getID(..)，这个不用自己写：String[] sarr = getID(arr1
[0]) --> sarr {A, B... 阅读全帖 |
|
d*****0
发帖数: 72 | 42 May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1()：能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
，注意edge case
2. given 一个字符串，这个字符串是一个算式，包含加减乘除，没有括号，符号和数
字之间以一个空格格开，比如：“1 + 2 * 4 / 5”，return算式的结果
3. given两个字符串，分别表示两个元素等和不等，比如：
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾，这个例子就有矛盾：A!=C
given提取元素的method: getID(..)，这个不用自己写：String[] sarr = getID(arr1
[0]) --> sarr {A, B... 阅读全帖 |
|
m***a
发帖数: 152 | 43 说得太对了，第一次人家问我challenge project, 我一激动开始跟人家讲论文里的
math,一直讲到interviewer打断我。。。现在想起来那个十分钟效果等于零，甚至是负的 |
|
m*****n
发帖数: 2152 | 44 C++用map插入就是nLog(n)，好处是不用排序。
用unordered_map插入式O(n)，但是之后要导入sequence container排序，还是nLog(n)。
这题最好的解法应该还是hash table。
不过为了避免rehash，可以traverse tree 一次找出最小和最大的column ID。
然后平移[min, max] -> [0, max-min] (min是负的)， root column ID就是-min了。
同vector >(max-min)，可以用level traverse tree，插入每个节点，
这样可以保持vertical的顺序。最后O(n) 遍历一下vector，以及下面的list就搞定了。
最后是time complexity 3*n，勉强也算O(n)吧。
treeset |
|
l*******0
发帖数: 95 | 45 我上面的solution有个假设: A中元素的取值范围是非负的，也就是大于或者等于0. 如
果感兴趣，你可以试着自己改一下程序，让它能够handle包括负数的情况。
另外，这个题现场不会做也没啥，的确要花些时间想想。 |
|
c*****y
发帖数: 27 | 46 我见过的例题是说array全非负。如果有负数，我先想想。 |
|
|
b******i
发帖数: 914 | 48 谢谢
onsite 1）我的大体思路和你差不多，除了的第二问，query的话我就想到从头开始++
--。不知道你binary search以后算这个位置左边几个正几个负怎么preprocess？ |
|
i****7
发帖数: 26 | 49 preprocess就是sort以后走一遍，每个点左边几个正的，几个负的都记录一下。
如果没有preprocess，每次query都数一下，复杂度是O(n)
有了preprocess，每次query只有binary search，复杂度是O(logn)
+ |
|
d***b
发帖数: 8 | 50 算Sprague Grundy值吧，Game Theory的题。
预先算好长度为len的连续“-”的sg值。
sg[0] = 0, sg[1] = 0, sg[2] = 1, sg[3] = 1，sg[4] = 2，etc。
对sg[x]（x>4）来说，尝试所有可能的move，每个move会把游戏分成两个子游戏（长度
为a和x-2-a），对他们的sg值做异或得到一个值。第一个没有出现的非负整数就是sg[x
]的值。
把游戏通过“+”分成n个子游戏，把所有子游戏的sg值做异或。如果最终结果不为0，
先手获胜。反之后手获胜。
move |
|
