问道amazon 面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问道amazon 面试题

问道amazon 面试题# JobHunting - 待字闺中

j*y2012-03-19 07:03

1 楼

话说07年的时候，窗外飞来两只灰色的鸽子夫妇筑巢在爬满爬山虎的窗台上，我很是兴
奋，天天给它们拍照片，看它们怎么孵蛋，孵出来后怎么喂还未长毛的小鸽子，看小鸽
子张着小嘴巴吃父母嘴里度来的食物，觉得很有趣。
谁知道好景不长，小鸽子才刚出世，家里就来了好多虫子，很小很黑的，在墙壁上排队
，咬得身上都是肿块，虽然很痒，但是不过几天就会退掉。一连喷了几瓶杀虫水，天天
洗衣服被子，但还是消灭不掉。那几天过的真是心惊肉跳的。听从以前的邻居建议，把
窗户的缝隙都用玻璃胶给贴住了，再继续喷药水，果然好了。这才明白原来是窗外的鸽
子作怪。邻居跟我一起在网上查，揣测那黑黑小小的虫子莫非就是鸽虱？但想想跟猫身
上的跳蚤又不一样的。但还是往窗外寻求答案，最后发现窗边90°折角处是条缝隙，通
向室内，里面有好多那种小虫子爬进爬出的，鸽子就在其下筑巢，估计就是鸽子身上带
的鸽虱。鱼在那缝隙里喷了半瓶杀虫剂，把鸽子赶走了，把窗户上的爬山虎都拔了，终
于彻底消停了。
也是在那次发现了天然精油配方的杀虫剂。在超市买的一瓶，是跟雷达什么都放在一个
地方，说是生态杀虫剂，比较贵，看看配方主要就是柠檬香茅，这味精油很便宜的，

d*a2012-03-19 07:03

2 楼

“全网零食坚果行业销量第一”“我们，六冠王，三只松鼠连续六年零食行业销量第一
”“全网坚果零食销量TOP1”。由于认为这些宣传语存在夸大与虚构，消费者王先生将
食品类电商三只松鼠以及天猫网络购物平台告上法庭，要求被告撤销不实宣传语，赔偿
购物款等共计500元。日前，该案在北京互联网法院进行开庭审理。
中国商报记者从起诉状中了解到，2018年12月18日，消费者王先生在天猫网络购物平台
上选购商品，当看到三只松鼠打出的“全网零食坚果行业销量第一”等如上文提到的醒
目广告语时，认为三只松鼠是一家有实力、值得信赖的品牌，从而下单购买了三只松鼠
的碧根果与夏威夷果商品，实付款82.64元。
王先生下单后从朋友处得知，三只松鼠发布的“全网零食坚果行业销量第一”等广告内
容是未经验证的统计结果，该结果是夸大的、虚构的，属于虚假广告，该品牌并不值得
信赖。王先生听到朋友这样说，觉得自己上当受骗了。
王先生委托北京世纪律师事务所律师郭杰为其代理人，郭杰代表王先生发表起诉意见称
，商家三只松鼠通过发布夸大的、虚假的、引人误解的广告内容，诱使原告做出了购买
三只松鼠产品的错误意思表示；而天猫作为网络交易平台的提供者，明知或者应当知道
商家利用其平台侵害消费者合法权益，但未采取必要措施，应承担连带责任。
被告方三只松鼠的代理律师辩称，三只松鼠发布的“全网零食坚果行业销量第一”等广
告，是仅限于天猫和淘宝平台，而且有相关依据，并非虚假宣传。天猫的代理律师辩称
，天猫并不是商品的销售者，作为网络平台，不是本案的适格被告。
记者登陆天猫网络平台进入王先生购买商品的三只松鼠旗舰店，发现在网页醒目位置有
“全网零食坚果行业销量NO.1”“爆卖四千万稳居行业第一”等广告宣传语，宣传语
右上方有星号，下方有标注：“数据来源于2018年生意参谋统计，全网指天猫和淘宝”
“数据来源于阿里巴巴生意参谋数字统计，销量第一指天猫超市碧根果品项”等小号字
体注释。
据查询，生意参谋是阿里巴巴商家端统一数据产品平台，为商家提供交易数据、客流来
源、访客分析等数据服务。
对此，郭杰表示，三只松鼠以醒目、引人注意、显著位置的字体宣称“全网零食坚果行
业销量第一”“全网坚果零食销量TOP1”，但以非醒目、非引人注意、非显著位置将全
网范围限定为天猫和淘宝，将数据来源解释为非官方统计机构，被告存在以该方式诱导
消费者购买商品的嫌疑，是违背诚实信用原则的行为。消费者将三只松鼠告上法庭是通
过法律手段正当维权，并非炒作。
由于被告方还需提供更多证据等原因，法官宣布择日继续开庭。

h*g2012-03-19 07:03

3 楼

Check if identical BSTs from given number streams
Question: You are given 2 number streams. You need to find whether they will
create the same BST or not.
Example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
Result: True
Array1:10 5 20 15 30
Array2:10 15 30 20 5
Result: False

P*U2012-03-19 07:03

4 楼

对每一个stream（以数组形式），切分为第一个元素（root),比root小的元素数组（
left)以及比root大的元素数组(right),并统计stream的元素总数。
如果元素总数不同或者root不同，直接返回false。
否则，递归的用这个过程比较两个stream的left数组和right数组，如果都相同，返回
true，否则，返回false

P*o2012-03-19 07:03

5 楼

第一个能解释一下为什么是true么？
array2的5在10的右边为什么是bst?
谢谢

will

【在 h*****g 的大作中提到】

: Check if identical BSTs from given number streams
: Question: You are given 2 number streams. You need to find whether they will
: create the same BST or not.
: Example:
: Array1:10 5 20 15 30
: Array2:10 20 15 30 5
: Result: True
: Array1:10 5 20 15 30
: Array2:10 15 30 20 5
: Result: False

w*o2012-03-19 07:03

6 楼

能不能解释一下这个题给定的条件和要解决的问题？好像很模糊的。
number steam是按照BST的什么order遍历的结果，还是随意的？
为什么第一个例子返回的结果是true? 而第二个例子的结果是false? 我看不出有什么
不同。
还有number steam里面可以有重复的数字吗？
我记得BST的左子树的数字 <= 当前的节点 < 右子树，对吧？

will

【在 h*****g 的大作中提到】

P*U2012-03-19 07:03

7 楼

lz的意思是按给定的stream的顺序插入一个空的BST

p*22012-03-19 07:03

8 楼

这个应该可以。我也是这个思路。

【在 P*******U 的大作中提到】

: 对每一个stream（以数组形式），切分为第一个元素（root),比root小的元素数组（
: left)以及比root大的元素数组(right),并统计stream的元素总数。
: 如果元素总数不同或者root不同，直接返回false。
: 否则，递归的用这个过程比较两个stream的left数组和right数组，如果都相同，返回
: true，否则，返回false

h*g2012-03-19 07:03

9 楼

按给定的stream的顺序插入一个空的BST

【在 w****o 的大作中提到】

: 能不能解释一下这个题给定的条件和要解决的问题？好像很模糊的。
: number steam是按照BST的什么order遍历的结果，还是随意的？
: 为什么第一个例子返回的结果是true? 而第二个例子的结果是false? 我看不出有什么
: 不同。
: 还有number steam里面可以有重复的数字吗？
: 我记得BST的左子树的数字 <= 当前的节点 < 右子树，对吧？
:
: will

h*g2012-03-19 07:03

10 楼

按给定的stream的顺序插入一个空的BST

【在 P***o 的大作中提到】

: 第一个能解释一下为什么是true么？
: array2的5在10的右边为什么是bst?
: 谢谢
:
: will

b*i2012-03-19 07:03

11 楼

弱弱问一下，这个你在切分的时候，是不是按照quicksort里面的partition那样？
如果是的话，岂不是会打乱原来的顺序（因为partition是不稳定的）？

【在 P*******U 的大作中提到】

A*u2012-03-19 07:03

12 楼

#include
using namespace std;
bool is_same_bst(int* A, int m, int* B, int n)
{
if ( m == 0 & n == 0 )
return true;
if ( m != n)
return false;
else
{
if ( A[0] != B[0] ) // root
return false;
else
{
//看看，root,左右儿子数目是否一致
int smaller1 = 0;
int larger1 = 0;
for(int i = 1; i < m; ++i)
{
if ( A[i] < A[0] ) ++smaller1;
if ( A[i] > A[0] ) ++larger1;
}
int smaller2 = 0;
int larger2 = 0;
for(int i = 1; i < n; ++i)
{
if ( B[i] < B[0] ) ++smaller2;
if ( B[i] > B[0] ) ++larger2;
}
//递归
if (smaller1 != smaller2 || larger1 != larger2 )
return false;
else
{
int* A_left=0;
if (smaller1 > 0) A_left = new int[smaller1];
int* B_left=0;
if (smaller2 > 0) B_left = new int[smaller2];
int* A_right=0;
if (larger1 > 0 ) A_right = new int[larger1];
int* B_right=0;
if (larger1 > 0 ) B_right = new int[larger1];
int i = -1;
int j = -1; //创建左右子序列
for(int k = 1; k < m; ++k)
{
if (A[k] < A[0])
{
++i;
A_left[i] = A[k];
}
if ( A[k] > A[0])
{
++j;
A_right[j] = A[k];
}
}
i = -1;
j = -1; //数组B
for(int k = 1; k < n; ++k)
{
if (B[k] < B[0])
{
++i;
B_left[i] = B[k];
}
if ( B[k] > B[0])
{
++j;
B_right[j] = B[k];
}
}
bool result = is_same_bst(A_left,smaller1,B_left,smaller2) &&
is_same_bst(A_right,larger1,B_right,larger2);
if (larger1 > 0) delete []A_right;
if (larger2 > 0) delete []B_right;
if (smaller1 > 0) delete []A_left;
if (smaller2 > 0) delete []B_left;
return result;
}
}
}
}
int main(){
int A[5] = {10,5,20,15,30};
int B[5] = {10,20,15,30,5};
int C[5] = {10,15,30,20,5};
cout << is_same_bst(A,5,B,5) << endl;
cout << is_same_bst(A,5,C,5) << endl;
return 0;
}
参考算法 http://tech-queries.blogspot.com/2011/06/check-if-identical-bsts-from-given.html

F*u2012-03-19 07:03

13 楼

bool is_same_BST(int *A, int m, int a_min, int a_max, int *B, int n, int b_
min, int b_max)
{
if( A == NULL || B == NULL )
return false;
if( m == 0 && n == 0 )
return true;
if( m == 0 || n == 0 )
return false;
if( A[0] != B[0] )
return false;
int i, j, a, b;
// A tree -> left subtree root
for( i = 1; i < m; i++ )
{
if( A[i] > a_min && A[i] < A[0] )
break;
}
// B tree -> left subtree root
for( j = 1; j < n; j++ )
{
if( B[j] < B[0] && B[j] > b_min )
break;
}
// A tree -> right subtree root
for( a = 1; a < m; a++ )
{
if( A[a] > A[0] && A[a] < a_max )
break;
}
// B tree -> right subtree root
for( b = 1; b < n; b++ )
{
if( B[b] > B[0] && B[b] < b_max )
break;
}
return is_same_BST( &A[i], m-i, a_min, A[0], &B[j], n-j, b_min, B[0] )
&& is_same_BST( &A[a], m-a, A[0], a_max, &B[b], n-b, B[0], b_max
) ;
}
int main()
{
int A[5] = {10,5,20,15,30};
int B[5] = {10,20,15,30,5};
int C[5] = {10,15,30,20,5};
cout << is_same_BST(A,5,INT_MIN, INT_MAX,B,5,INT_MIN, INT_MAX) << endl;
cout << is_same_BST(A,5,INT_MIN, INT_MAX,C,5,INT_MIN, INT_MAX) << endl;
}

s*r2012-03-19 07:03

14 楼

/**
* Took FightingXu's algorithm and implemented in JAVA:
*/
public static boolean isSameBST(int[] arrA, int aOffset, int aMin, int aMax,
int[] arrB, int bOffset, int bMin, int bMax)
{
if (arrA == null || arrB == null)
return false;
if (aOffset > -1 && aOffset == 0 && bOffset > -1 && bOffset == 0)
return true;
if (arrA.length == aOffset || arrB.length == bOffset)
return false;
if (aOffset > -1 && bOffset > -1 && arrA[aOffset] != arrB[bOffset])
return false;
int i, aLeftOffset = 0, bLeftOffset = 0, aRightOffset = 0, bRightOffset = 0;
aOffset = aOffset < 0 ? 0 : aOffset;
bOffset = bOffset < 0 ? 0 : bOffset;
// A tree -> left subtree root
for (i = aOffset + 1; i < arrA.length; i++)
{
if (arrA[i] > aMin && arrA[i] < arrA[aOffset])
{
aLeftOffset = i;
break;
}
}
// B tree -> left subtree root
for (i = bOffset + 1; i < arrB.length; i++)
{
if (arrB[i] > bMin && arrB[i] < arrB[bOffset])
{
bLeftOffset = i;
break;
}
}
// A tree -> right subtree root
for (i = aOffset + 1; i < arrA.length; i++)
{
if (arrA[i] > arrA[aOffset] && arrA[i] < aMax)
{
aRightOffset = i;
break;
}
}
// B tree -> right subtree root
for (i = bOffset + 1; i < arrB.length; i++)
{
if (arrB[i] > arrB[bOffset] && arrB[i] < bMax)
{
bRightOffset = i;
break;
}
}
return isSameBST(arrA, aLeftOffset, aMin, arrA[aLeftOffset], arrB, bLeftOffset, bMin, arrB[bLeftOffset])
&& isSameBST(arrA, aRightOffset, arrA[aRightOffset], aMax, arrB, bRightOffset, arrB[bRightOffset], bMax);
}
public static void main(String[] args) {
int[] arrA = {10,5,20,15,30};
int[] arrB = {10,20,15,30,5};
int[] arrC = {10,15,30,20,5};
boolean sameBST = BinaryTree.isSameBST(arrA, -1, Integer.MIN_VALUE, Integer.MAX_VALUE,
arrB, -1, Integer.MIN_VALUE, Integer.MAX_VALUE);
System.out.println(sameBST);
sameBST = BinaryTree.isSameBST(arrA, -1, Integer.MIN_VALUE, Integer.MAX_VALUE,
arrC, -1, Integer.MIN_VALUE, Integer.MAX_VALUE);
System.out.println(sameBST);
}

s*f2012-03-19 07:03

15 楼

python:
def SameBST(a, b):
if len(a) < 1:
return len(b) < 1;
if len(a) != len(b) or a[0] != b[0]:
return False
aleft = [x for x in a if x < a[0]]
aright = [x for x in a if x > a[0]]
bleft = [x for x in b if x < b[0]]
bright = [x for x in b if x > b[0]]
return SameBST(aleft, bleft) and SameBST(aright, bright)
if __name__ == "__main__":
a = [10, 5, 20, 15, 30]
b = [10, 20, 15, 30, 5]
b1 = SameBST(a, b)
c = [10, 5, 20, 15, 30]
d = [10, 15, 20, 30, 5]
b2 = SameBST(c, d)
pass

will

【在 h*****g 的大作中提到】