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 | |
z*****u 发帖数: 51 | |
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 | |
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 的大作中提到】 : 不对的,应该是
|
|
|
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 |
|
|
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;
|
|
|
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()])
|