|
|
i**********e
发帖数: 1145 | 3 My solution using a heap and an array that maps indices from A to B.
const int MAX_M = 100;
const int MAX_N = 100;
typedef pair Pair;
int findKthLargestSum(int A[], int m, int B[], int n, int k) {
priority_queue Q;
int AToB[MAX_M] = {0}; // keep track of each col's indices that's
traversed.
// pushes all elements of the first row into heap
for (int i = 0; i < m; i++)
Q.push(Pair(A[i]+B[0], i));
// loop k-1 times to find the first k-1 elements
for (int i = 0; i < ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 4 To answer your question, No.
Counter example:
A = [9 8 7 6]
B = [9 7 2 1]
9 8 7 1
9 18 17 16 10
7 16 15 14 8
2 11 10 9 3
1 10 9 8 2
The 4th element (16) is not on any of A[4,1], a[3,2], a[2,3], a[1,4].
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 5 LZ 谢谢分享。
我能想到的是用一个 table + double ended queue，O(n)，不知道还能不能更优化.
table 用来记录当前的字符访问过没.
每遇到一个不曾碰过的字符就 push 到 queue 的后边，然后纪录在 table 里.
如果字符被访问过了，就 update 一下 maximum length，然后一个一个从前头 pop，
直到 pop 出来的字符和此字符相等. 每次 pop 的时候也要更新 table.
总复杂度应该是 O(n)，因为每个字符最多被 push 和 pop 各一次.
解法有点类似于 google 的 sliding window 经典题.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
|
|
|
i**********e
发帖数: 1145 | 10 代码虽然对了，但是你这个不用 table 复杂度是很高的。
你不用表的话，就只有每次前进都从前指针一直往后扫，直到碰到后指针为止。这复杂
度没法做到 O(N)。
简单来说，不用表的复杂度是 O(N^2)，N 为字符串长度。（循环基本跟冒泡排序差不
多，你可以比较一下）
虽说表利用空间换取速度，但这问题区区那么一点空间，是非常值得的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 11 呵呵，
想说 O(N^2) 和 O(N) 的复杂度相差不大，有没有搞错？
不过这问题由于局限于26个不同的字母，所以可以保证过了26个字母就会有至少一个重
复的。
万一如果没有这样的局限，你的代码肯定会跑得更慢了。。只要一直没遇到重复的，你
的指针就一直要从头开始扫描.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 12 4. 很久以前写的大数 class. 基本思路很简单，就是小学的乘法 + carry.
BigInt BigInt::multiply(const BigInt &b) const
{
BigInt answer;
BigInt temp;
int carry = 0;
for (int i = 0; i < b.numDigits; i++)
{
temp.numDigits = this->numDigits + 1;
int down = b.digits[i];
for (int j = 0; j <= this->numDigits; j++)
{
int up = (j < this->numDigits) ? this->digits[j] : 0;
int tempDigit = up * down + carry;
temp.digits[j] = tempDigit % 10;
carry = tempDigit / 10;
}
temp.s... 阅读全帖 |
|
i**********e
发帖数: 1145 | 13 我的公式是：
i from 1 to n
j from i to n
max(i,j) = A[i], when i = j,
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1)), when i != j
max coins get by player 1 = max(1,n)
这公式跟你是一样的吧？(a(i)+sum(i+1,j) = sum(i,j))
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 14 如果硬币个数为偶数的话，就如 lilacc 和 ibread 所说的，只要比较奇数位置硬币之
和，还有偶数硬币之和就可以了。这是因为硬币个数为偶数时，先走的能够确保对手拿
所有奇数（或是偶数）位置的硬币。
打个比方，如果总共有10枚硬币。我先拿位置 1 的硬币，那对手就必须选择位置 2 或
者 10 的硬币。如果我先拿位置 10 的硬币，对手只能选择位置 1 或 9 的硬币。在硬
币个数为偶数时，这样的策略能保证对手拿的硬币位置全是偶数（或奇数），因此先拿
的绝对不会输。
如果硬币个数为奇数的话，那就要多算一步。假设对手也聪明，利用以上的策略，那就
可以准确预测对手下一步会拿那一枚硬币。这样就只需要算多一步。这时候，先拿的未
必会赢。
哦，明白了，dp 公式算的是 maximum possible amount，这里指的是对手拿硬币不一定根据以上的策略。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
i**********e
发帖数: 1145 | 16 There are only 5 different kinds of expressions with different arrangement
of parenthesis for 4 numbers (using an example of 1,2,3,4), shown as below:
1) ((1 + 2) + (3 + 4))
2) (((1 + 2) + 3) + 4)
3) ((1 + (2 + 3)) + 4)
4) (1 + ((2 + 3) + 4))
5) (1 + (2 + (3 + 4)))
An easy way is to brute force using recursive method. Choose all possible
neighboring pairs and merge them using the operators (add, subtract...). For
example, choosing neighboring pairs of (1 and 2):
(1 + 2) + 3 + 4 --> 3 + 3 + 4
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 17 刚想到很精简的 code，不需要用 post-fix stack-based expression，直接储存进一
个 string 数组即可。
效率应该是不错的了，有一些方面可以考虑提高效率，例如用 vector 需要删除元素可
能会慢些，但 vector 里的元素很少，应该影响不大。
还有一点就是每次传递归的时候，都需要把所有的数组重新 copy 一次。这是无可避免
的，因为每次进入下一层递归时必须传 copy，不能在原有数组中更改。
#include
#include
#include
#include
#include
using namespace std;
void generate(vector A, int target, int s, vector expression);
template
void eraseAt(vector &vec, int i) {
typename vector::iterator ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 18 顶.
不知道还有没有其他方法呢？（尤其可以避免每次递归制造额外的 copy）
还有一点就是，以上的方法会列出，但其实在加法没有括号的必要。
((1+2)+3)
(1+(2+3))
要怎么列出绝对 unique 的 arrangements 呢？
感觉会很复杂，很多情况要处理。
大家讨论讨论吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
|
|
i**********e
发帖数: 1145 | 22 My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 23 My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A ... 阅读全帖 |
|
|
|
i**********e
发帖数: 1145 | 26 你的基本思路是对的，但是：
1)问题要得到两个叶子节点，不单单只是 maxsum
2)你的代码 assume 所有节点值都是正数
稍微更改一下就好了。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 27 刚才写的，没有验证过。。。
typedef pair IntNode;
// precondition: binary tree must be complete. (eg, each node must have
either 0 or 2 children)
IntNode maxSumLeafNodes(Node *root, int sumFromRoot, Node *& leaf1, Node *&
leaf2, int &maxSum) {
assert(root);
// base case: leaf node (no children)
if (!root->left && !root->right) return IntNode(root->data, root);
// must have 2 children
assert(root->left && root->right);
IntNode fromLeft = maxSumLeafNodes(root->left, sumFromRoot + roo... 阅读全帖 |
|
i**********e
发帖数: 1145 | 28 第二点我看错了，你的代码是对的，可以返回正确的 maxsum.
关于第一点，我一开始也是跟你一样，base case 判断为 NULL == root。这个如果只
是返回 maxsum 没有问题，但是如果要返回两个叶子节点的话就应该更改下 base case.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 29 还有一点，这题假设 binary tree 是 complete 是有原因的。
complete binary tree 可以保证每个节点必须有０个或者２个孩子。
这样可以保证每个递归都可以有两个 leaf node，也就是一个 solution candidate。
然后再比较两个 leaf node，返回那个路径比较大的给 parent。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
s********e
发帖数: 340 | 31 请教几个面试题，有些好像以前有人问过，我是新手，没找到以前的答案和讨论，还请
赐教，谢谢！
1. Reverse the words of a string
2. Print values of fibonacci pattern. Not the sum, but the number sequence,
starting with 1, 2
3. How to write a maintenance free webservice that has a history of changing
number of inputs taken and number of outputs?
4. Insert value in linked list at given position. How would you test it？
5. System described. Blank page returned. How would you test it
6. Converting two D char array to a int array with space efficient... 阅读全帖 |
|
g*****1
发帖数: 998 | 32 虽然大多数都是面c++的吧，
可是感觉字符串的面试题大家给出答案都是c-style string表达的
是不是面试者在出类似题就期待考察c-style string的细节，
还是什么其他原因？
是不是以后自己复习字符串有关的题目，直接联系c-style string的？ |
|
m**2
发帖数: 2 | 33 谢谢。搭车问，那里有EE方面的面试题同时也带答案的。 |
|
k***k
发帖数: 791 | 34 组里的面试题，都是讨论通过的，每人一个方向。我的方向我都是搞的难题怪题。 目
的只有一个， 尽量让大家都答不出来。
只有在这种情况下， 我才能帮老中。 我一般会做些提示，慢慢地让他们把答案弄出来
， 在纸上写好画好。回头讨论时就说我这个方向只有老中通过，其他都不行。
如果我出个简单的题目， 老中是爽了。 可是烙印也爽了不是？ 我又不能把人家答对
的硬说成错的。面试写的纸按规定都要保留的。就防着这个的。来面试的无论老中烙印
一多半都是有关系内推的。内部人不相信面试结论， 要求来查的还真碰到过。 |
|
I*******x
发帖数: 20 | 35 多谢大家，我不是什么牛人，多几个面试有什么好牛的。只是这些东西能帮助大家提高
水平就很好了。对于各位在上面提出的问题，这里统一回复一下。
1. 如果哪些题目有问题，欢迎跟贴讨论。题目比较多，就不一一分析给提示了。
2. Machine learning也是编程写算法，用什么语言应该都和其他的职位类似。但是确
实python和java有不少ML的package现成的。不过也有大牛一直用c++的。这个没有定数
，看个人喜好。
3. 基础知识怎么准备的问题，不是这个方向的同学，还在学校的可以上上课，在公司
的可以参与到相关的项目里。对于是这个方向的同学来说，那些面试题真的不难。
4. 编程要刷题吗？答案：要。leetcode什么的该做还是要做。真正的machine
learning的职位对编程要求不比software engineer低，而且加了machine learning方
向的问题。应该对人整体要求更高才是。不过不同公司或者不同的组对data scientist
的定义不同，有的不考编程，只是问问sql，但是那些职位我没申请过，不好给建议。 |
|
I*******x
发帖数: 20 | 36 多谢大家，我不是什么牛人，多几个面试有什么好牛的。只是这些东西能帮助大家提高
水平就很好了。对于各位在上面提出的问题，这里统一回复一下。
1. 如果哪些题目有问题，欢迎跟贴讨论。题目比较多，就不一一分析给提示了。
2. Machine learning也是编程写算法，用什么语言应该都和其他的职位类似。但是确
实python和java有不少ML的package现成的。不过也有大牛一直用c++的。这个没有定数
，看个人喜好。
3. 基础知识怎么准备的问题，不是这个方向的同学，还在学校的可以上上课，在公司
的可以参与到相关的项目里。对于是这个方向的同学来说，那些面试题真的不难。
4. 编程要刷题吗？答案：要。leetcode什么的该做还是要做。真正的machine
learning的职位对编程要求不比software engineer低，而且加了machine learning方
向的问题。应该对人整体要求更高才是。不过不同公司或者不同的组对data scientist
的定义不同，有的不考编程，只是问问sql，但是那些职位我没申请过，不好给建议。 |
|
y*****e
发帖数: 712 | 37 L家最爱考的面试题之一就是nested integer了，
还爱考各种iterator的implementation
这题是把两个最爱合在一起了。。。。感觉很有可能出，但网上没找到满意的答案.
题目是这样的
eg: {{1,2},3,{4,{5,6}}}
不断调用iterator的next()返回的序列是 1 2 3 4 5 6
这个data structure的interface是这样的
public interface Data {
// Does this Data hold a collection?
public boolean isCollection();
// Returns the collection contained by this Data, or null if it is a
single element
public Collection> getCollection();
// Returns the single element contained by this Data, or nul... 阅读全帖 |
|
j******8
发帖数: 20 | 38 网上看到pure storage一道面试题：如何用spinlock和queue来实现mutex?
网上也没搜到答案。求高人解答。 |
|
x*****0
发帖数: 452 | 39 下面是一道pure storage常出现的面试题：
我面过，电面就是一个api，每次register的时候需要call一个callback，但是在event
被触发之前call的callback都不能成功被call，在event被
触发之后call的都可以，同时之前delay的call也要成功call，让写具体的function如
何实现，之后还实现单线程多线程来着。
第一轮问的是一个api，每次register的时候需要call一个callback，但是在event被触
发之前call的callback都不能成功被call，在event被触发之后call的都可以，同时之
前delay的call也要成功call，让写具体的function如何work。还问了multithreading
的问题。
网友的简单答案：
是even设成一个全局变量每次没触发就入waitqueue么。。。多线程就给加个锁？
exactly, 我就是这么做的，async的queue，加一个全局flag，多线程就是mutex，lock
unlock，期间多线程的时候有些错，他提示改过来了，我多线程比较弱，后来挂了。... 阅读全帖 |
|
x*****i
发帖数: 1329 | 40 【 以下文字转载自 LeisureTime 讨论区 】
发信人: auo (aeiou), 信区: LeisureTime
标 题: NYT: 鹦鹉学舌的中国式教育 zz
发信站: BBS 未名空间站 (Fri Sep 18 11:22:33 2015, 美东)
鹦鹉学舌的中国式教育
北京——1999年春，我在北京一所小学读五年级。某天放学后，老师给我留了一项作业
。一周前，北约在科索沃战争中轰炸了在贝尔格莱德的中国使馆，导致三名中国记者丧
命。华盛顿将这次袭击称作意外，而中国民众相信这是故意挑衅。我的任务是为第二天
的校会写一篇演讲稿，我的老师告诉我，“来谴责西方列强几世纪以来欺压中国的霸行
”。
那天晚上，我埋头于一摞摞报纸之中，将头版标题中的词句串联起来，拼凑出了演讲稿
。第二天，当老师看了我交给她的草稿后赞许地点了点头时，我感到我的努力有了回报
。演讲稿充斥着诸如“百年国耻”和“反帝斗争”这样的短语。它们的发音令我心跳加
速，但它们的含义我却不甚明了。
上高中时，这些词语再次出现在了我的历史课本里，成了我们需要记住的准则。“中国
建立社会主义，”我对自己重复道，“是现代历史进... 阅读全帖 |
|
x*****c
发帖数: 1005 | 41 【 以下文字转载自 Automobile 讨论区 】
发信人: xhisaac (我想我是海), 信区: Automobile
标 题: 超级难的路考笔试试题，今天刚刚过关的(CT)
发信站: BBS 未名空间站 (Tue Mar 11 16:13:03 2008)
这些全都是我今天早上在康州刚刚做过的笔试（机考题），康州规定16道题，准许错4
道以内，我错了两道，还有两道题我选择skip掉，没有记住，也很难。有4道很easy的
题，我就不写在这里了。
估计很多老司机都答不上来的，大家回答一下吧，
我回头来贴标准答案。
今天好几个老外都fail了，有的人很失落，磨蹭着不想从机考大厅出来，有的人考完灰
溜溜的回家（笔试过关的需要等半个多小时，预约路考时间）
我是做过一些模拟题，所以幸运过关
1，消防水龙头两侧多远距离不能停车?
a 5feet b 10 feet c 15 feet d 25 feet
2,1ounce的whisky相当于多少啤酒
a 0.5 can b 1 can c 1.5 can d 2can
3，通常有多少交通事故与饮酒有关
a 30% b 40% c 50% |
|
a*o
发帖数: 25262 | 42 鹦鹉学舌的中国式教育
北京——1999年春，我在北京一所小学读五年级。某天放学后，老师给我留了一项作业
。一周前，北约在科索沃战争中轰炸了在贝尔格莱德的中国使馆，导致三名中国记者丧
命。华盛顿将这次袭击称作意外，而中国民众相信这是故意挑衅。我的任务是为第二天
的校会写一篇演讲稿，我的老师告诉我，“来谴责西方列强几世纪以来欺压中国的霸行
”。
那天晚上，我埋头于一摞摞报纸之中，将头版标题中的词句串联起来，拼凑出了演讲稿
。第二天，当老师看了我交给她的草稿后赞许地点了点头时，我感到我的努力有了回报
。演讲稿充斥着诸如“百年国耻”和“反帝斗争”这样的短语。它们的发音令我心跳加
速，但它们的含义我却不甚明了。
上高中时，这些词语再次出现在了我的历史课本里，成了我们需要记住的准则。“中国
建立社会主义，”我对自己重复道，“是现代历史进程的必然结果。”
然而到那时，这样的词句已经无法激起我和同学们的兴趣。它们的含义也没有深入人
心。中国历史仿佛是由意识形态的套话勾勒出的一系列条约和运动，既难以琢磨又缺乏
实质。
但课程的简单又是一件幸事。不用学会阐述艰深复杂的论点或调和令人费解的矛盾，我
们只要能... 阅读全帖 |
|
b**********7
发帖数: 814 | 43 【6÷2(1+2)=? 一个有争议的试题】
这一个问题，乍一看，非常的简单，只是一个小学二年级的四则混合运算，其实，这是
一个颇有争议的题目，据说日本、美国还有我国台湾等，对此都有过认真的讨论，好像
还没有共识。
在这题目中，人们认为可以有两个答案，
6÷2(1+2)=1
或6÷2(1+2)=9
这一道题的关键是“省略乘号”的问题。
第一个2后面可不可以省略运算符号？
有人认为，2后面的运算符号不能省略。并列出能够省略运算符的有以下几种情况：
1.数字乘字母。
2.字母乘字母。
3.整数和分数间的乘号也不能省略，带分数是指分数和整数求和。
4.向量之间的乘号。
数学科学坚决取缔双重标准，数学要求严谨。人教版数学教材，关于乘号的省略，明文
规定只有一条，那就是“在不致引起混淆的情况下”。
既然本题有那么多的争议，说明已经是“引起混淆”了。所以，至少说，本题是不规范
的，或索性就应该说本题是错的；
如果把它写规范了，题目应该是：6÷2×(1+2)，那就应该是：6÷2×(1+2)=3×3=9。 |
|
p*e
发帖数: 6785 | 44 【 以下文字转载自 JobHunting 讨论区 】
发信人: moonlake711 (mimiinus), 信区: JobHunting
标 题: 问一道同学遇到的微软面试题：怎么向一个三岁小孩解释Recrusion?
发信站: BBS 未名空间站 (Mon Oct 20 17:16:53 2014, 美东)
这个题我想了很久，网上也找不到答案
遇到这样的题目应该怎么回答好呢 |
|
x****o
发帖数: 21566 | 45 《外国法制史？外星法制史！》华中科技大学外法史神一般期末试题
一． 论述（60分）背景：在某平行宇宙中，银河系外文明程度远高于人类的α星
是一个虫族帝国，帝国舰队将于10年后来到地球，并向地球发出通牒：勒令地球牺牲献
祭童男童女100万名以供奉α星所信奉的普世（universal）大神β，并立β神庙一座。
如果不同意则摧毁地球文明；如果同意则提供α星文明成就给人类，使其得以按照α星
文明社会模式与历史进程改造其文明。
假定你是以下三位角色之一，你将如何应对这一局势：
1. 在平行宇宙A中，当时的地球政体为地球联邦，你是地球联邦的伯理玺
天德（president）。你将如何回应此α星舰队的通牒？同意其要求，还是拒绝？如果
同意，你将如何论证牺牲这100万童男童女的合法性？你将如何在各联邦中分配这些名
额？如果不同意，你将如何说服全球人民承担文明毁弃、种群灭绝的后果？
2. 在平行宇宙B中，当时的地球政体为政教合一，信奉同一普世宗教γ的
地球帝国，你是地球帝国的大祭祀。你将如何回应此α星舰队的通牒？同意其要求，还... 阅读全帖 |
|
p*******0
发帖数: 76 | 46 请版大别删
没在买买提上找到vmware版和active directory版
但我常来database版 :-)
请牛牛们抛点儿玉.给几个vmware和active directory面试题和答案.
帮忙性质,想招有real working experience 的 (senior level). |
|
v***e
发帖数: 2108 | 47 看到这道题好玩，答案是 ab是index scan，cd是table scan
两种SQL plan
再来一道题玩一下，如果Test table巨大无比，一定要用parallel query，
这两种parallel plan会有何不同呢（PX coordinator不算的话）？
不许查书。
发信人: bearkid (bearkid), 信区: Database
标 题: 一道面试题，求助
发信站: BBS 未名空间站 (Wed Dec 28 21:18:35 2011, 美东)
We have the following schema of a table:
create table Test (id number, name varchar2(32), desc varchar2(400));
create index index_test on Test (name);
Which of the following statements will invoke an index scan by oracle
execution plan
a) select * fro... 阅读全帖 |
|
b***d
发帖数: 186 | 48 一道面试题
我抓脑袋想不出来，帮我想想
家里一台电脑A ip 11.22.33.44
公司一台电脑B ip 55.66.77.88 这电脑还有另外一个interface，可以连到公司内部
100台电脑10.1.1.100～10.1.1.199
A可以ssh到B，但是不能直接ssh到公司内部电脑10
问做了什么操作后，可以在A和B直接建立某种连接，使得在家里A电脑上直接访问10.1.
1.100:123 或一百台电脑中任一台的任一端口都可以直接访问。
所有server均运行Linux
已知答案不是在AB间建VPN
也不能用 ssh tunnel with -w option
也不能用 iptables
据说还是特别简单的办法，不需要特别的软件支持。 |
|
z****e
发帖数: 2024 | 49 是我出的面试题。呵呵。
如果好奇想要答案，请去joke回复原帖。 |
|
b********n
发帖数: 609 | 50 【 以下文字转载自 JobHunting 讨论区 】
发信人: forbaby2008 (宝宝), 信区: JobHunting
标 题: Re: 问个cisco的mutex的面试题
发信站: BBS 未名空间站 (Thu Oct 14 13:49:54 2010, 美东)
up一下
后最后问了这一个mutex的题，我实在答不上来，就问他应该怎么做，很简单的回答我
用hashtable，完了上网搜也没搜到答案，来这里问问，希望大牛给指点指点 |
|
