|
|
|
g*******y
发帖数: 1930 | 4 如果没有正数：找三个最小abs的负数
如果有正数：
最多需要找1个最大的正数 + 2个abs最大的负数(如果只有一个负数就直接扔了) + 3到5个(3个好像就够了?)abs最大的数，分析符号 |
|
j***n
发帖数: 301 | 5 这样行不行：当只给3个数的时候，最大的积只能是3个数相乘，记结果为current_max，
并且把这3个数也记下来，a1,a2,a3。从第4个数起(ai, i >= 4)，如果current_max大于
0，就看当前的这个数的绝对值是否大于min{|a1|, |a2|, |a3|}，如果是，就把最小的
那个换成ai.
如果current_max小于0，就看当前的这个数的绝对值是否小于max{|a1|, |a2|, |a3|}，
如果是，就把最大的那个换成ai. |
|
g*******y
发帖数: 1930 | 6 not work，你扔掉一个最大的绝对值的数，以后就找不回来罗。这个数有可能最后会被
用到的。
max，
大于
}， |
|
|
|
d*****g
发帖数: 766 | 9 If最小2个负数 is bigger, you should use the 第1大正数 |
|
l******n
发帖数: 641 | 10 should be 1st big positive, with
2,3 postive compared with 1,2 nagative. |
|
m*****f
发帖数: 1243 | 11 N是乘积不是n,
看清楚点再说好么, 别动不动教训人, 最烦这样的 |
|
l**a
发帖数: 43 | 12 来自主题: JobHunting版 - 也来道题吧 求给定数组里任意三个数乘积的最大值 |
|
p*****e
发帖数: 1611 | 13 这题可以扩展成n个孩子的乘积是m
写个递归就可以，同样注意要排序搜 |
|
|
x****r
发帖数: 99 | 15 有人有什么好办法么？
我说说唯一能想到的一点简单的优化
创建一个数组
B1 = A1
B2 = A1 * A2
Bn = A1 * ... * An
现在对每一个div看看bn能不能整除它
如果不行就直接跳过这个除数
如果可以的话，recursive找左右两部分
B(n/2) % div[XXX] = x;
(B(n) / B(n/2)) % div[XXX] = y;
如果x和y其中的任何一个不等于0，都可以排除
但是如果都是0，就继续recursive的找下去了
这样的话可以迅速踢掉一些不太可能的div，但是复杂度没有变（而且乘积和有可能
overflow）
觉得应该有什么好方法， 谁来说说？ |
|
|
b********a
发帖数: 5418 | 17 哦，所以不是加和或者乘积，是摆起来看着像？6可以当9用的吧？
我家以前有过一个台历就是这么设计的，两块立方体来回摆，小时候还好好奇的研究过，没想到面试还
能碰到。。 |
|
r*****t
发帖数: 68 | 18 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
phone interview
给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
排好序的
onsite
1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
3. 写一个二叉树遍历的iterator
4. design一个middle layer，在客户端跟搜索服务器之间 |
|
r*****t
发帖数: 68 | 19 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
phone interview
给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
排好序的
onsite
1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
3. 写一个二叉树遍历的iterator
4. design一个middle layer，在客户端跟搜索服务器之间 |
|
g**********y
发帖数: 14569 | 20 想法：
1. 把每个单词的score算出来，放在hashmap里。score的定义是：26位，某个字母出现
则该位为1. 判断两个单词是否有共同字母 = score(w1) & score(w2) > 0
2. 把单词长度对按乘积从高到低排序，然后按这个顺序搜单词库，找到的第一组满组
的单词对就是解。
Code在楼上 |
|
h**6
发帖数: 4160 | 21 提前写了大数类，往上一粘就可以了。
另外跟素不素数没有什么关系，如果分子分母不约分，最后乘积就会很大。我自己测试
程序的时候用的是
50 50 500 500 500 500 ... 500
得到结果 (499/500)^50
500^50 大约是10^135，为简化实现，可以用固定长度数组实现大数类。 |
|
|
d***n
发帖数: 65 | 23 第二题，第二问 是用1...n的合与1...n的积算出missing 的两个数的合与积然后解一
元二次方程吗？有没有更好的方法，感觉求乘积太容易overflow了。 |
|
c***g
发帖数: 472 | 24 software developer
预计2小时15分钟, 搞了三小时, 先45分钟c++纸上测试, 10道题目, 大概20页纸, 包括
写输出, 找错误, 怎么改进, 写code, 恰好做完, 稍微慢点就写不完了.
然后来一个人, 讨论做了啥, 问了一些C++的基本的, 然后问我, core code在product
machine上出现了bug, 你如何debug? 然后突然开始问我refrence counting的smart
pointer怎么写, 要我写一个, 这个要求太高了, 太突然, 写出来的说有问题, 然后
一起讨论, 基本跌跌撞撞的满意了; 然后我问一个算法题目, 就是给一个数组, 算另外一个数组, 每个对应的index的值是其他所
有的数的乘积, 不能用除法
这样大概搞了45分钟, 合起来一个半小时了.
后来来两个人, 一个老印, 一个白人, 说你要什么工作啊,我说我要chanllenge的, 其
中一个说, 好, 做题吧, 老印说, 我有很多chanllenge你的.
第一题, 老鼠测毒药题;
第二题, 给一个数, 输出excel里面对应的column的strin... 阅读全帖 |
|
N******r
发帖数: 26 | 25 能不能这样考虑呢：先获取所有元素的乘积，然后除以当前的元素就可以得到product
of all elements but A[k].
int product = 1;
for(int i = 0; i < A.length; i++)
{
product *= A[i];
}
for(int j = 0; j < A.length; j++)
{
B[j] = product/a[j];
}
不知道可不可行，请指教。。 |
|
l********t
发帖数: 123 | 26 给一个数组 里边都是整数 求最大乘积的连续子数组 |
|
g**********y
发帖数: 14569 | 27 最大乘积的连续子集，0，和{0,-3,0,-3,0}不是一样的吗？ |
|
m******n
发帖数: 6327 | 28 最大乘积一样，子集不一样。
所以按0分割成子集，有漏洞。 |
|
q*****9
发帖数: 85 | 29 有两种角色，公司和求职者，公司和求职者都有三个指标，智商，情商和经验，对个人
来说，这三个指标就是个人的指标，公司的这三个指标是对求职者的期望，match的程度
取决于个人与公司三个指标的乘积的和，假设有1000家公司和20000个求职者，必须要
保证把这20000个求职者平均的分配到1000家公司，即，每家公司20个人，求职者还有
一个dream companies 的列表，假设每个人后面有10个公司，这个是从感兴趣的程度
排序好的，即，最想去的公司，排在最前面，分配时要考虑雇佣match程度高的求职者，
要保证没有这种情况发生：一个求职者相较于现在被分配到的公司更喜欢另一个公司，
然而，那个公司却存在着比自己match程度低的人。设计出具体的数据结构和算法。
我觉得tricky的地方在于:
1. 原来可能在20个人范围以外的人，由于20个人中有人去了其他更想去的
公司而得到机会去这个公司。
2. 通过dream companies，去找是否公司可接受，如果公司不available，则要继续查看
第二想去的公司，以此类推，如果公司available，但是由于match程度去不了，只有... 阅读全帖 |
|
c*******n
发帖数: 63 | 30 http://www.interviewstreet.com
Find the no of positive integral solutions for the equations (1/x) + (1/y) =
1/N! (read 1 by n factorial) Print a single integer which is the no of
positive integral solutions modulo 1000007.
1 <= N <= 10^6
我一开始以为这题单纯是大数运算的问题，后来发现似乎不是
觉得解题的突破点应该是：
let p = n! --> 1/p - 1/(p+k) = k/(p(p+k))
p(p+k)/k is an integer, 1<= k <= p and the total solution of k is the unique
number of products of all combination of [1, n],
that is 1Cn + 2Cn + .... + (n-1)Cn + nCn - redundant ... 阅读全帖 |
|
g**********y
发帖数: 14569 | 31 不用那么复杂，这种题就是brutal force + DFS
public class Decompose {
private void decompose(int N) {
dfs(N, N, "");
}
private void dfs(int N, int hi, String s) {
if (N == 1) {
if (s.contains("*")) {
System.out.println(s);
}
else {
System.out.println(s + "*1");
}
return;
}
for (int i=hi; i>1; i--) {
if (N%i == 0) {
dfs(N/i, i, s.length(... 阅读全帖 |
|
s*******f
发帖数: 1114 | 32 int GetNextPrime(){ // substitute this with more excellent algorithm
static int primes[] = {2,3,5,7,11};
static int idx = 0;
return primes[idx++];
}
void PrintFactors(int n){
if (n < 0){
n = -n;
}
if (n == 0){
return;
}
int prime = 1;
while (prime <= sqrt(double(n))){
prime = GetNextPrime();
while (n % prime == 0){
printf("%d ", prime);
n /= prime;
}
}
if (n > 1){
printf("%d ", n);... 阅读全帖 |
|
a*****g
发帖数: 110 | 33 来自主题: JobHunting版 - 面经&感想 就是两个很大的整数用数组表示，求他们的乘积，存在另一个数组里 |
|
k******1
发帖数: 16 | 34 找工作两个多月，也积累了不少经验，以前求bless的时候说过拿到dream offer就写经
验和面经。现在拿到了，贡献出来希望以后的xdjm有用。包子发不了，老号伪币用来买
东西了。
1．背景
我以前学计算机的，phd毕业就在一家大投行前台做quant,辛苦做了两年，独立完成了
不少大的项目。结果去年年底效益太滥，公司裁了一堆quant,我也就经历了第一次下岗
。平心而论，虽然我刚开始还是很不爽，但是大投行给的平台还是很好的，而且学到很
多东西。我们组包括我一共走了两个phd。 我后来想想，老板决定谁走，你个人工作上
的能力，薪水只是一部分考量，有的老板很看重谁够political,甚至谁够brown nose的。
我当时的情况很被动，因为去年底很多地方hiring freeze，招人的经常放假进度都挺
慢；也没身份，只有garden leave加签证grace period几个月时间，如果这期间内找不
到工作只能回国。我后来第一个buy side offer是在redundancy接近两个月的时候拿到
的。希望能给不幸被雷的同胞一些鼓励，你们的大环境多半比我所处的好。
2. 关于猎... 阅读全帖 |
|
q****x
发帖数: 7404 | 35 原文长。
发信人: kknd2011 (kknd), 信区: JobHunting
标 题: 投行前台quant跳buy side quant经历
发信站: BBS 未名空间站 (Tue Jan 10 19:12:35 2012, 美东)
拿到dream offer写面经。
1．背景
以前学计算机，phd毕业在大投行前台做quant两年，去年年底下岗。我们组走了两个
phd。第一个buy side offer在redundancy近两个月时拿到。
2. 关于猎头
求职先更新简历，上linkedin,准备面试。背景还可以，会有不少猎头联系你。我的经
验：面试十多家，自投朋友投30%，猎头50%，公司HR自己联系的20%. 拿到的offer都是
猎头的，悲剧的多数是自己或者朋友投的，原因我感觉是公司hr常把简历转到不对口的
组，面试不易有共鸣。一个组fail了，hr就不发别的组。猎头比较清楚公司招人的职位
，会把简历直接转给hiring manager。比自投好得多。
猎头质量差别很大。一共4-5个猎头递过简历。好的猎头不乱来，就递几个地方且之前
先介绍清楚，争得同意。一般很快可以联系上... 阅读全帖 |
|
|
|
l***m
发帖数: 339 | 38 俺觉得 和相等，乘积相等应该就是最优的吧。XOR有很多特殊情况是处理不了的。比如
22222，33333。 |
|
w****o
发帖数: 2260 | 39 有两个疑问：
1. 你的题目中的 x, y是任意给的吗？很有可能 和是x, 乘积是y的subarray根本不存
在，对吧？！
2. 你说的那个变形题不就是著名的max sum subarray的题吗？难道有什么特别的吗？
不是有O(n)的算法吗？
谢谢！
product
with |
|
w****o
发帖数: 2260 | 40 能具体的讲讲这个题是什么东西吗？
是不是说给了两个字符串，每个都是代表了一个很长的10进制表示的数？
比如 char str1[] = "23456789009877666555544444"
char str2[] = "346587436598437594375943875943875"
最后求出他们的乘积？ |
|
t**********h
发帖数: 2273 | 41 1. 简历
2. inner join, out join 区别
3. 一个input array 比如是a = {4, 2, 3, 3},output array 为 b = {18， 36， 24
， 24}，输出array中每一个元素是a中除了下标和它对应的元素所有其他的元素的乘积
。写unit test cases
4. 有一个文件，每一行数字，最小的数为0，最大的数为10million，未排序，，每个
数字那么不出现，要么只出现一次。排序输出
5.接上题，其他条件一样，每一行有一个数字，还有一个String，排序输出
6.接第4题，其他条件一样（取消不重复的，即有重复），但是数据量很大，内存装不下，排序输出
7. 设计basketball game，写重要的class
8. AOP，bunisses delegate, facade, singleton, static用法, polimophism,
interface vs abstract class, javascipt, css, hibernate mapping, hibernate
package, jdbc(... 阅读全帖 |
|
h****e
发帖数: 928 | 42 题意很简单，就是给一组可正可负可零的整数，求出它们的乘积。
函数的声明如下：
int multiply(int numbers[], int N)
考点主要是在于处理overflow的情况。当overflow时，返回
INT_MIN或者INT_MAX。当然只要有任意一个数为0，结果就
应该是0。
请问有什么简便的办法吗。 |
|
K*****n
发帖数: 65 | 43 1)设计hang-man游戏。（跟非死不可对过去的那家）
要考虑扩展性。
2）类似vector >, 写hasnext(), getnext(),handle size=0
3) 把黑名单从总部服务器可靠地发送到全球各地的服务器；
4）有正负数的数组，找最大连续和；
然后找最大连续乘积（考虑：零，负数的个数是奇偶的情况）
电面是写句子单词翻转。 |
|
h****b
发帖数: 48 | 44 背景和经历：
国内名校混混，硕士混到之后又辗转混入微软中国，懵懂干了几年的测试，决心出国。
雷蒙德的卧佛拿了两个（办公室组和手机组），无奈国内极品老板不放人还给穿小鞋，
所以又去面了亚麻和狗狗，都是测试的位子，最后选了亚麻。
技术相关的面试总共经历了包括微软内的两个组各五轮，狗狗电话一轮国内三轮柯克兰
三轮，亚麻电话两轮西雅图四轮，小计二十三轮。因为签过恩地诶，所以题目要么不写
出处，要么细节做点变化，大家见谅。
关于准备：
简历里的闪光点要有针对性的挖掘。比如我用在微软内的简历里大吹特吹自己找八哥的
数据和一些特别经典的八哥；投给狗狗和亚麻的简历就强调自己写的自动化框架解决了
多大的问题。亚麻没找人内推，招聘官特意告诉我说我的简历和这个坑太匹配了。
对于要面试的组稍微做些功课也很重要。作为测试经理，对于一个用过自己产品，甚至
能提出一些主见的候选人自然是很喜欢的。在和办公室组聊的时候，我刚好之前把一些
私人表格从狗狗文档换到了微软的天盘，做了一些对比，老板听得很开心。。。
编程题的复习我是通读了150，编程珠玑和何海涛一百题，然后再浏览本版精华区，最
后几天去找点新题做做保持临场状态... 阅读全帖 |
|
d******a
发帖数: 238 | 45 1. 一个整数数组，可以有负数，0，正数，求连续子数组的最大乘积。
2. 打印二叉树的所有从root到叶节点的所有路径，不能用递归。
当时写bug-free的代码还是有些困难的，欢迎讨论并贴代码。 |
|
i***d
发帖数: 28 | 46 1。开放问题： 有些网络每天只允许有限次数的访问，设计一个抓取网页的Crawler 能
让搜索结果尽量的全面和新鲜。
不知道这个问题的考点是什么？ 设计Crawler 是考虑避免 infinite loop 还是
其他方面的；
请大家能不能帮忙看看， 怎么回答？
2。 两个排序数组的和 求第K个的数？ 以前好像讨论过； 好像是用最小堆来做的，
有没有 In place 的做法？ 如果换成数组的乘积求第K个的数是不是一样啊？
先谢谢了！ |
|
d******i
发帖数: 76 | 47 First Q:
一直数组: {2, 3, 4, 5}
要求返回一个数组: {60, 40, 30, 24}， 其中每个element是其他元素的乘积。
Second Q:
用OOD的知识设计一个服装店，要求能够判断时候某个号码的衣服是否存在 |
|
|
h****n
发帖数: 1093 | 49 两个string, 给出它们的两个substring, 定义它们的距离为distance=sum_i(s1[i]-s2
[i])，怎么找距离最大的两个substring?
根据距离的定义，应该是找两个长度相同的substring
咋做，穷举？
还有一道
一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
这个也只能穷举吗？ |
|
h****a
发帖数: 7 | 50 昨天去西雅图面的，office组测试职位。一共四轮，运气比较好都是白人，而且题非常
水。
第一轮，闲扯，问了你最常去的五个网站是什么。题是反转字符串里的单词并给测试用例
第二轮，替换给定文件中指定字符串并且输出并给出测试用例
第三轮，代码题，给定一个整数数组，找出任意三个数使其乘积最大。给定一个程序，
输入是一系列点，输出是两点间最短距离以及具体的点，要求给测试用例
第四轮，把1-8的数字填入给定格子，相邻的数字在格子里不能相邻，一共有几种填法
，垂直平行对角线都算相邻。不用写程序。
格子
*
* * *
* * *
*
如果左下角是1，那么2只能放下以下3个位置
* （2）
* * * * * （2）
* * * 1 * （2）
* *
代码题是合并两个排好序的数组。还有给出翻转字符串的测试用例。他居然有个程序直
接输入测试用例看是不是能找到问题。 |
|
