由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 新鲜C3 energy面经
相关主题
问道面试题a question
被Facebook的面试的一道题目难倒了unsorted int array怎么找到第一个大于0,并且不在此array的数
老问题了,网上竟然找不到答案两道题目
找2个sorted array中的第K小的元素,有O(lgn)方法吗?也问两个算法题
两个Sorted Array,找K smallest elementGoogle onsite问题
问一下deep copy和shallow copy的问题(C#)继续贴几个题目
Find the intersection of two sorted arrays【扩展】请教一道面试题
请教一下external sorting的问题做道有序数组元素求最大和题?
相关话题的讨论汇总
话题: treenode话题: int话题: null话题: array话题: max
进入JobHunting版参与讨论
1 (共1页)
z*****u
发帖数: 51
1
面试的是infrastructure的software engineer的职位,面试的全是印度人,不知道是
不是c3 energy已经被印度人霸占了
第一轮电面,印度人
1. Binary tree,判断两个node是不是cousins
按层traverse然后判断
2. 给定两个array,要求按照第二个array的顺序排列第一个array,如果第一个array
里面有不包含第二个array的元素,则按照顺序排列
hashmap的应用
第二轮电面,两轮skype。因为我不在加州,所以用Skype。如果在加州,就直接去他们
公司。本来要面三轮。面的不好,直接给挂了
<1> 给一个amount和一堆denomination,然后把所有的可能组成amount的denomination
的组合输出出来
这道题不难,我用的是dfs search。然后又有几个follow up: 能不能用cache加快;如
果amount非常大,list of denomination size很大该怎么办;如果给你很多机器,怎
么进行分布式计算。这一轮就这么一道题。聊的感觉还不错,各种hadoop mapreduce的
乱扯了一通,三哥说make sense。然后问了几个问题就结束了
<2> 给一个time series,要求计算这个值是最大的连续的天数,很难描述…给个例子:
input: 3.2, 5, 6, 4
output: 1, 2, 3, 1
我给的方法是记录left max的index,然后每次计算。如果当前值比leftmax小,则用另
外一个数组记录rightmax value,然后count。这样可以保证o(n)。三哥说如果是
streaming,不能从右向左scan怎么办…我就给了个worset case 是o(n^2)的solution
。三哥说不行,太复杂。我说有没有什么hint,没有response,就说可以更简单一些。
扯到差不多省了10分钟的时候,写了个solution。就结束了,然后10分钟后,就收到拒
信了~~~ 求大牛指点O(n)或者O(n log(n))的算法~~
d****y
发帖数: 58
2
坐等第二题答案
z*****u
发帖数: 51
3
自己顶一下~
R****E
发帖数: 391
4
第二题怎么入手

array

【在 z*****u 的大作中提到】
: 面试的是infrastructure的software engineer的职位,面试的全是印度人,不知道是
: 不是c3 energy已经被印度人霸占了
: 第一轮电面,印度人
: 1. Binary tree,判断两个node是不是cousins
: 按层traverse然后判断
: 2. 给定两个array,要求按照第二个array的顺序排列第一个array,如果第一个array
: 里面有不包含第二个array的元素,则按照顺序排列
: hashmap的应用
: 第二轮电面,两轮skype。因为我不在加州,所以用Skype。如果在加州,就直接去他们
: 公司。本来要面三轮。面的不好,直接给挂了

s********l
发帖数: 998
5
第二轮第二题 没看明白什么意思
input: 3.2, 5, 6, 4 还有个3.2? 还是 2啊?
output: 1, 2, 3, 1
这个输入是对的吗?
你是想说 连续的几个数里 第几大?

array

【在 z*****u 的大作中提到】
: 面试的是infrastructure的software engineer的职位,面试的全是印度人,不知道是
: 不是c3 energy已经被印度人霸占了
: 第一轮电面,印度人
: 1. Binary tree,判断两个node是不是cousins
: 按层traverse然后判断
: 2. 给定两个array,要求按照第二个array的顺序排列第一个array,如果第一个array
: 里面有不包含第二个array的元素,则按照顺序排列
: hashmap的应用
: 第二轮电面,两轮skype。因为我不在加州,所以用Skype。如果在加州,就直接去他们
: 公司。本来要面三轮。面的不好,直接给挂了

z*****u
发帖数: 51
6
是3.2
就是开始时只有3.2最大,所以长度是1
然后输入5,5比3.2大,所以长度是2
以此类推,可以知道输入6,长度是3;输入4长度是1 因为4比6小
一定要求是连续的

【在 s********l 的大作中提到】
: 第二轮第二题 没看明白什么意思
: input: 3.2, 5, 6, 4 还有个3.2? 还是 2啊?
: output: 1, 2, 3, 1
: 这个输入是对的吗?
: 你是想说 连续的几个数里 第几大?
:
: array

z*****u
发帖数: 51
7
我的想法是,用hashmap保存array 1里面的数字,按照array 2里面的顺序,这样需要
先遍历array 2一遍,然后遍历array 1一遍


【在 R****E 的大作中提到】
: 第二题怎么入手
:
: array

x********k
发帖数: 256
8
先不纠结double,假设都是int的话,下面这个用例对么?
3 5 6 4 5 6 1 1 1 9 8 7
1 2 3 1 2 3 1 2 3 4 1 1
z*****u
发帖数: 51
9
不对的,应该是
x********k
发帖数: 256
10
哦,明白点了,看来是否是这个规律?
max = a[0];
for (i = 1; i < n; i ++) {
if (a[i - 1] <= a[i]) { // 如果数字变大,根据是否是历史最大值看是否直接取当
前下标,还是前一个下标+1
if (a[i] >= max) {
b[i] = i;
} else {
b[i] = b[i - 1] + 1;
}
} else { // 如果数字变小, 重置成1
b[i] = 1;
}
max = max(max, a[i]);
}

【在 z*****u 的大作中提到】
: 不对的,应该是
相关主题
问一下deep copy和shallow copy的问题(C#)a question
Find the intersection of two sorted arrays【扩展】unsorted int array怎么找到第一个大于0,并且不在此array的数
请教一下external sorting的问题两道题目
进入JobHunting版参与讨论
a****o
发帖数: 21
11
应该是这样的。

【在 x********k 的大作中提到】
: 哦,明白点了,看来是否是这个规律?
: max = a[0];
: for (i = 1; i < n; i ++) {
: if (a[i - 1] <= a[i]) { // 如果数字变大,根据是否是历史最大值看是否直接取当
: 前下标,还是前一个下标+1
: if (a[i] >= max) {
: b[i] = i;
: } else {
: b[i] = b[i - 1] + 1;
: }

l*********8
发帖数: 4642
12
C3 energy我连online test都没过啊。。。
第二轮<2>,用一个辅助数组保存local max value和下标。
例子:
input 对应的local_max array
{} {}
{3} {<3,0>}
{3,4} {<4,1>}
{3,4,2} {<4,1>, <2,2>}
{3,4,2,1} {<4,1>, <2,2>, <1,3>}
{3,4,2,1,3.5} {<4,1>, <3.5,4>}
更新local_max array的时候,将当前alue和下标插入到local_max array, 从local_
max末尾向前搜索,遇到比当前元素小的,就删除。 这样,local_max数组就是按value
逆序排列的,而前面更新local_max可以用二分搜索。 每次更新log n time, n次更
新nlog(n)

array

【在 z*****u 的大作中提到】
: 面试的是infrastructure的software engineer的职位,面试的全是印度人,不知道是
: 不是c3 energy已经被印度人霸占了
: 第一轮电面,印度人
: 1. Binary tree,判断两个node是不是cousins
: 按层traverse然后判断
: 2. 给定两个array,要求按照第二个array的顺序排列第一个array,如果第一个array
: 里面有不包含第二个array的元素,则按照顺序排列
: hashmap的应用
: 第二轮电面,两轮skype。因为我不在加州,所以用Skype。如果在加州,就直接去他们
: 公司。本来要面三轮。面的不好,直接给挂了

z*****u
发帖数: 51
13
我尝试了下面这个例子:
input: 6, 1, 2, 1, 4
correct output: 1, 1, 2, 1, 4
你的算法的output:1, 1, 2, 1, 2
因为4并不比max大但是比前面的值都大
比max大的情况比较简单
比max小的时候我当时的想法是从右边向左边扫描,记录最大值,然后count
output of scan from right to left: 6, 4, 4, 4, 4
然后count最大值的个数,这样也可以保证o(n),但是三哥说不能从右边向左边scan,
可能是streaming

【在 x********k 的大作中提到】
: 哦,明白点了,看来是否是这个规律?
: max = a[0];
: for (i = 1; i < n; i ++) {
: if (a[i - 1] <= a[i]) { // 如果数字变大,根据是否是历史最大值看是否直接取当
: 前下标,还是前一个下标+1
: if (a[i] >= max) {
: b[i] = i;
: } else {
: b[i] = b[i - 1] + 1;
: }

z*****u
发帖数: 51
14
嗯,这样可以保证每个元素被访问的次数不会超过log(n)次,总体复杂度可以是o(n
log(n))

【在 l*********8 的大作中提到】
: C3 energy我连online test都没过啊。。。
: 第二轮<2>,用一个辅助数组保存local max value和下标。
: 例子:
: input 对应的local_max array
: {} {}
: {3} {<3,0>}
: {3,4} {<4,1>}
: {3,4,2} {<4,1>, <2,2>}
: {3,4,2,1} {<4,1>, <2,2>, <1,3>}
: {3,4,2,1,3.5} {<4,1>, <3.5,4>}

k******4
发帖数: 94
15
试着写了下time serises那道题,
void printConsectiveLength(vector A)
{
if (A.size() == 0)
return;
stack st;

for(int i=0; i {
while(st.size() > 0 && A[i] > A[st.top()])
st.pop();
if (st.size() > 0)
cout< else
cout< st.push(i);
}
cout< return;
}
每个index进出stack最多一次,时间O(n),空间O(n).
k******4
发帖数: 94
16
while(st.size() > 0 && A[i] > A[st.top()])
这行或需要改成
while(st.size() > 0 && A[i] >= A[st.top()])
取决于和面试官的讨论
z*****u
发帖数: 51
17
嗯,牛逼啊!目前看到最好的solution了!

【在 k******4 的大作中提到】
: while(st.size() > 0 && A[i] > A[st.top()])
: 这行或需要改成
: while(st.size() > 0 && A[i] >= A[st.top()])
: 取决于和面试官的讨论

z***b
发帖数: 127
18
楼主coin change 这道题如果list of denomination size很大又不能用递归该怎么办
呢?
用dp可以知道有多少种组合,但是要打印出每种组合好像挺难啊
s********l
发帖数: 998
19
我想问一下
如果array 2 是 5 2 6 8 -1 3
array 1 是 0 6 3 8 4 5 2
arry1按照arry2拍好后 , 0 和 4放哪里啊?
0 放-1后面还是2前面?
4方3后面还是5前面?

【在 z*****u 的大作中提到】
: 我的想法是,用hashmap保存array 1里面的数字,按照array 2里面的顺序,这样需要
: 先遍历array 2一遍,然后遍历array 1一遍
:

h***e
发帖数: 123
20
电面1 binary tree 判断cousin 如何code, 哪个大神给个sample
相关主题
也问两个算法题请教一道面试题
Google onsite问题做道有序数组元素求最大和题?
继续贴几个题目Amazon 面试题
进入JobHunting版参与讨论
k******4
发帖数: 94
21
找到LCA,如果不等于两个node中的任意一个且LCA到两个节点的距离为2,返回true,
否则false。找LCA的过程中应该还可以剪枝优化一下。

【在 h***e 的大作中提到】
: 电面1 binary tree 判断cousin 如何code, 哪个大神给个sample
h***e
发帖数: 123
22
同问, 两array 大小是否相同.
比如 arr 1 3 5 6 9 0
arr 2 9 5 3 -1
应该输出什么

【在 s********l 的大作中提到】
: 我想问一下
: 如果array 2 是 5 2 6 8 -1 3
: array 1 是 0 6 3 8 4 5 2
: arry1按照arry2拍好后 , 0 和 4放哪里啊?
: 0 放-1后面还是2前面?
: 4方3后面还是5前面?

s********l
发帖数: 998
23
这题根本不需要lca

【在 k******4 的大作中提到】
: 找到LCA,如果不等于两个node中的任意一个且LCA到两个节点的距离为2,返回true,
: 否则false。找LCA的过程中应该还可以剪枝优化一下。

z*****u
发帖数: 51
24
这道题用dp的确不行,memory的思路是如果有些denominator可以用其他denominator表
示,这样就不用再算了,举个例子
target: 12
denominator: {1, 2, 4}
第一步:{4, 4, 4}
第二步就可以用{1,2}去分4,然后把结果整合

【在 z***b 的大作中提到】
: 楼主coin change 这道题如果list of denomination size很大又不能用递归该怎么办
: 呢?
: 用dp可以知道有多少种组合,但是要打印出每种组合好像挺难啊

z*****u
发帖数: 51
25
我可能题目没有表述清楚:
这道题是说先根据array2的出现顺序排序,再把array1里面的剩余元素排序
output: 5, 2, 6, 8, 3, 0, 4
前面5个是array2里面出现的元素,所以先排,后面0, 4是按照正常顺序排列

【在 s********l 的大作中提到】
: 我想问一下
: 如果array 2 是 5 2 6 8 -1 3
: array 1 是 0 6 3 8 4 5 2
: arry1按照arry2拍好后 , 0 和 4放哪里啊?
: 0 放-1后面还是2前面?
: 4方3后面还是5前面?

z*****u
发帖数: 51
26
我当时用的是layer by layer的遍历,如果发现他们是兄弟,直接返回false. 如果发
现不是兄弟而且在同一个layer,则count++,如果count==2,则返回true. 否则返回
false

【在 h***e 的大作中提到】
: 电面1 binary tree 判断cousin 如何code, 哪个大神给个sample
s********l
发帖数: 998
27
我一直默认 cousin 是指在一行里的。。。
你这cousin怎么定义? 是说他们的parent必须是兄弟?

【在 z*****u 的大作中提到】
: 我当时用的是layer by layer的遍历,如果发现他们是兄弟,直接返回false. 如果发
: 现不是兄弟而且在同一个layer,则count++,如果count==2,则返回true. 否则返回
: false

l***p
发帖数: 160
28
time series 的题和leetcode 的 Largest Rectangle in Histogram 很像
我的解法(把int 改成double) 是一样的。
class Solution {
public:
vector maxDays(vector nums) {
int size = nums.size();
vector result(size, 0);
nums.push_back(INT_MAX);
stack s;
int idx = 0;
while (idx <= size) {
if (s.empty() || nums[idx] < nums[s.top()]) {
s.push(idx++);
}
else {
int cur = s.top();
s.pop();
int maxdays = s.empty() ? idx : (idx - s.top() - 1);
result[cur] = maxdays;
}
}
return result;
}
};
z*****u
发帖数: 51
29
只要在同一个layer就可以了,parent不一定是兄弟。你一个一个layer的遍历,就可以
发现在这一行里的所有nodes了:
boolean findIfCousins(TreeNode root, TreeNode a, TreeNode b) {
if(root == null || (root.val == a.val|| root.val == b.val) || a.val
== b.val)
return false;

ArrayList preLayer = null, curLayer = new ArrayList<
TreeNode>();
curLayer.add(root);

int count = 0;
while(!curLayer.isEmpty()){
preLayer = curLayer;
curLayer = new ArrayList();
count = 0;
for(TreeNode n : preLayer){
if(n != null){
if(n.left != null && n.right != null &&
((n.left.val == a.val && n.right.val == b.val) ||
(n.left.val == b.val && n.right.val == a.val)))
return false;
if(n.left != null && (n.left.val == a.val || n.left.val
== b.val))
count++;
if(n.right != null && (n.right.val == a.val || n.right.
val == b.val))
count++;

if(n.left != null)
curLayer.add(n.left);
if(n.right != null)
curLayer.add(n.right);
}
}
if(count == 2)
return true;
} // while: curlayer is not empty

return false;
}

【在 s********l 的大作中提到】
: 我一直默认 cousin 是指在一行里的。。。
: 你这cousin怎么定义? 是说他们的parent必须是兄弟?

z*****u
发帖数: 51
30
嗯,正解~

【在 l***p 的大作中提到】
: time series 的题和leetcode 的 Largest Rectangle in Histogram 很像
: 我的解法(把int 改成double) 是一样的。
: class Solution {
: public:
: vector maxDays(vector nums) {
: int size = nums.size();
: vector result(size, 0);
: nums.push_back(INT_MAX);
: stack s;
: int idx = 0;

相关主题
问一个问题(4)被Facebook的面试的一道题目难倒了
两个数组找duplicated有什么好办法老问题了,网上竟然找不到答案
问道面试题找2个sorted array中的第K小的元素,有O(lgn)方法吗?
进入JobHunting版参与讨论
m*****k
发帖数: 731
31
try[2,2],
should be
while(st.size() > 0 && A[i] >= A[st.top()]) 吧?

【在 k******4 的大作中提到】
: 试着写了下time serises那道题,
: void printConsectiveLength(vector A)
: {
: if (A.size() == 0)
: return;
: stack st;
:
: for(int i=0; i: {
: while(st.size() > 0 && A[i] > A[st.top()])

1 (共1页)
进入JobHunting版参与讨论
相关主题
做道有序数组元素求最大和题?两个Sorted Array,找K smallest element
Amazon 面试题问一下deep copy和shallow copy的问题(C#)
问一个问题(4)Find the intersection of two sorted arrays【扩展】
两个数组找duplicated有什么好办法请教一下external sorting的问题
问道面试题a question
被Facebook的面试的一道题目难倒了unsorted int array怎么找到第一个大于0,并且不在此array的数
老问题了,网上竟然找不到答案两道题目
找2个sorted array中的第K小的元素,有O(lgn)方法吗?也问两个算法题
相关话题的讨论汇总
话题: treenode话题: int话题: null话题: array话题: max