logo
Redian新闻
>未名空间
>Living
>
家具真是暴利行业啊
avatar
家具真是暴利行业啊# Living
e*6
1 楼
题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
内容都剪切出来了，我现在没有原题，大概描述一下。
1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
抛售日。（coding）
2，给一个字符串，打印出这个字符串所有的permutation。（coding）
我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
不明白，然后问我：你不想改变外面的值吗？
另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
反复解释之后，他突然恍然大悟。。
不知道是不是面试官有意装糊涂然后观察我的表述能力的？
这次题目都很简单。祝大家成功！
avatar
a*e
2 楼
内容纯属转载
We got our daughter's bedroom set for $700 cash...trundle bed, 2 Sealy
mattresses, dresser, mirror, nightstand. It retails on the Land of Nod
website for around $2500 w/o mattresses. Exact same model. Exact same
manufacturer. First run. He's just able to purchase directly from the
manufacturer and sells to friends at cost.
avatar
c*2
3 楼
1. max( max( max(p[i+1]..p[n])-p[i] ))
2. bit mapping to str position
if bit[i]==1, take str[i]
avatar
H*7
4 楼
家具难运输，又占地方，当然零售价高了
avatar
d*a
5 楼
can you give some more detail about problem 1? Could you show the program?
Thanks!

【在 c***2 的大作中提到】
: 1. max( max( max(p[i+1]..p[n])-p[i] ))
: 2. bit mapping to str position
: if bit[i]==1, take str[i]
avatar
K*S
6 楼
who's He?
给我也买一套吧

【在 a******e 的大作中提到】
: 内容纯属转载
: We got our daughter's bedroom set for $700 cash...trundle bed, 2 Sealy
: mattresses, dresser, mirror, nightstand. It retails on the Land of Nod
: website for around $2500 w/o mattresses. Exact same model. Exact same
: manufacturer. First run. He's just able to purchase directly from the
: manufacturer and sells to friends at cost.
avatar
s*n
7 楼
第一题，
find maxand min .
bottom up. pair to pair comparison. winner left, loser right. recusively do
it again.
then by n - 2 comparisons, you get max and min.
buy min and sell max, remember you can short:).

【在 d******a 的大作中提到】
: can you give some more detail about problem 1? Could you show the program?
: Thanks!
avatar
a*e
8 楼
神医们搞家具直销巴。零库存，顺便造福庸医和游户们

【在 K******S 的大作中提到】
: who's He?
: 给我也买一套吧
avatar
e*6
9 楼

my code has been deleted by him right after it's finished, i have no chance
to retain it...
but i can come back to provide my code later.

【在 d******a 的大作中提到】
: can you give some more detail about problem 1? Could you show the program?
: Thanks!
avatar
K*S
10 楼
怎么搞?

【在 a******e 的大作中提到】
: 神医们搞家具直销巴。零库存，顺便造福庸医和游户们
avatar
n*e
11 楼
searching global minimum and maximum prices?
right?
avatar
a*e
12 楼
不是说了嘛，搞直销，怎么联系货源组织运输就是神医的事情了

【在 K******S 的大作中提到】
: 怎么搞?
avatar
E*a
13 楼

.}
关于第二个，可能面试的人不是写c++出身的，在google工作久了，不是很熟悉
referrence的用法，因为我们内部的
coding style是禁止这样用的。

【在 e**********6 的大作中提到】
: 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
: 内容都剪切出来了，我现在没有原题，大概描述一下。
: 1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
: 抛售日。（coding）
: 2，给一个字符串，打印出这个字符串所有的permutation。（coding）
: 我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
: 之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
: 不明白，然后问我：你不想改变外面的值吗？
: 另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
avatar
b*n
14 楼
请问你在哪家店里买的？

【在 a******e 的大作中提到】
: 不是说了嘛，搞直销，怎么联系货源组织运输就是神医的事情了
avatar
j*u
15 楼
1. 我一开始想成根据history的stock price来做predict了，想了半天。。。
其实是这个题的变种
int array A里找两个position i和j，要求A[j]和A[i]的差maximum，同时istatic void BestDay(int[] stockPrices, out int buyDate, out int sellDate)
{
buyDate = sellDate = 0;
int maxDiff = 0, minPrice = stockPrices[0], minPriceDate = 0;
for (int i = 1; i < stockPrices.Length; ++i)
{
int price = stockPrices[i];
int diff = price - minPrice;
if (diff > maxDiff)
{
buyDate = minPriceDate;
sellDate = i;
maxDiff = diff;
}
if (minPrice > price)
{
minPrice = price;
minPriceDate = i;
}
}
}
2. 写递归的话没什么特殊的，如果不in-place的话很简单
static List GetPermutations(string str)
{
if (str.Length == 1)
return new List { str };
string first = str[0].ToString();
str = str.Substring(1);
var perm = new List();
foreach (var p in GetPermutations(str))
{
for (int i = 0; i <= str.Length; i++)
{
perm.Add(p.Insert(i, first));
}
}
return perm;
}
avatar
a*e
16 楼
不是我阿。。。我转贴的

【在 b*****n 的大作中提到】
: 请问你在哪家店里买的？
avatar
j*u
17 楼
不知道reference可能是对C++不熟，也许从C之后直接就java/python了
递归搞不明白就不可饶恕了:P 尤其是问题还是自己问的
不知道是不是面试官有意装糊涂然后观察我的表述能力的？
你觉得Google hire影帝吗 :)

.}

【在 e**********6 的大作中提到】
: 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
: 内容都剪切出来了，我现在没有原题，大概描述一下。
: 1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
: 抛售日。（coding）
: 2，给一个字符串，打印出这个字符串所有的permutation。（coding）
: 我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
: 之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
: 不明白，然后问我：你不想改变外面的值吗？
: 另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
avatar
s*d
18 楼
家具行业暴利个P啊。家具店倒闭的大把大把的，要都是暴力，
大家不用去创业IT公司了，都开家具公司好了。
一个家具店一天卖不了一两件，租那么大地方，雇人，根本很
难赚钱的行业，在你们眼里居然成了暴力。
avatar
i*e
19 楼
Question number one is the same as finding the maximum contiguous sub-array
sum, simple DP problem using Kadane's algorithm.
http://en.wikipedia.org/wiki/Kadane%27s_algorithm
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

.}

【在 e**********6 的大作中提到】
: 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
: 内容都剪切出来了，我现在没有原题，大概描述一下。
: 1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
: 抛售日。（coding）
: 2，给一个字符串，打印出这个字符串所有的permutation。（coding）
: 我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
: 之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
: 不明白，然后问我：你不想改变外面的值吗？
: 另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
avatar
T*U
20 楼
en, 傻子才搞家具直销，运费占成本一半了。0库存，简直就是天方夜谭。

【在 s**********d 的大作中提到】
: 家具行业暴利个P啊。家具店倒闭的大把大把的，要都是暴力，
: 大家不用去创业IT公司了，都开家具公司好了。
: 一个家具店一天卖不了一两件，租那么大地方，雇人，根本很
: 难赚钱的行业，在你们眼里居然成了暴力。
avatar
s*y
21 楼
第一题见过一个类似的。给一只股票一段时间每天的价格，每天可以买也可以卖，求最
大利润。
avatar
S*E
22 楼
大家容易忽略家具的运输仓储损耗一类的费用，光想着出厂成本了

【在 s**********d 的大作中提到】
: 家具行业暴利个P啊。家具店倒闭的大把大把的，要都是暴力，
: 大家不用去创业IT公司了，都开家具公司好了。
: 一个家具店一天卖不了一两件，租那么大地方，雇人，根本很
: 难赚钱的行业，在你们眼里居然成了暴力。
avatar
s*t
23 楼
感觉题意不是这个意思吧！ 都是正数的话，你的那个就是所有加和了。

array

【在 i**********e 的大作中提到】
: Question number one is the same as finding the maximum contiguous sub-array
: sum, simple DP problem using Kadane's algorithm.
: http://en.wikipedia.org/wiki/Kadane%27s_algorithm
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: .}
avatar
a*e
24 楼
我那个帖子里的700还是500是包括了两个matress以及运输的，只是不包括存储损耗而
已，后面一部分难道能超过将近2000刀再外加两个matress？

【在 S*******E 的大作中提到】
: 大家容易忽略家具的运输仓储损耗一类的费用，光想着出厂成本了
avatar
A*H
25 楼
similar concept, keep best profit and lowest buy price so far, update
those two values along the traverse

【在 s*******t 的大作中提到】
: 感觉题意不是这个意思吧！ 都是正数的话，你的那个就是所有加和了。
:
: array
avatar
a*e
26 楼
要是钱不好挣，开个p的家具店啊，这些年倒闭一些不是很正常么，经济不好需求小。
ikea这样的烂店不还在开么

【在 s**********d 的大作中提到】
: 家具行业暴利个P啊。家具店倒闭的大把大把的，要都是暴力，
: 大家不用去创业IT公司了，都开家具公司好了。
: 一个家具店一天卖不了一两件，租那么大地方，雇人，根本很
: 难赚钱的行业，在你们眼里居然成了暴力。
avatar
A*H
27 楼
permutation using swap
void printPermutation(string s, int start, int n) {
if (start>=n) {
cout<return;
}
for (int i=start; iswap(s[start], s[i]);
printPermutation(s, start+1, n);
swap(s[start], s[i]);
}
}
avatar
S*E
28 楼
我们没看到实物，不太好说价格与价值离得有多远，东西跟东西是有差异的，连市场的
西红柿还要分个三六九等呢，别说更复杂的家具了
你说家具是暴利，肯定是不对的，这行业真要是有暴利，这种不复杂的行业，很多投资
商会对这个行业投资的，最后导致行业利润率回归正常，家具行业的进入门槛总比挨踢
容易吧。
ikea可不烂，设计，质量，服务和价格的平衡还是不错的，你觉得不好，可能是ikea的
市场定位满足不了你，你该去看看档次更高点的店
avatar
i*e
29 楼
You are right. I did not see clearly.
Finding the max and min should be the right way.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 s*******t 的大作中提到】
: 感觉题意不是这个意思吧！ 都是正数的话，你的那个就是所有加和了。
:
: array
avatar
s*d
30 楼

家具店倒闭比例比一般店高很多，经济好的05 06年也多处都是。
难道有一家家具店没倒闭就证明家具是暴利了吗？

【在 a******e 的大作中提到】
: 要是钱不好挣，开个p的家具店啊，这些年倒闭一些不是很正常么，经济不好需求小。
: ikea这样的烂店不还在开么
avatar
k*n
31 楼
哎，我说所有人都默认这个字符串里面没有重复字符了是么？

【在 A*H 的大作中提到】
: permutation using swap
: void printPermutation(string s, int start, int n) {
: if (start>=n) {
: cout<: return;
: }
: for (int i=start; i: swap(s[start], s[i]);
: printPermutation(s, start+1, n);
: swap(s[start], s[i]);
avatar
s*n
32 楼
我们这家具店很多打着liquidation的旗号，真正倒闭的没几个,都两三年了

【在 s**********d 的大作中提到】
:
: 家具店倒闭比例比一般店高很多，经济好的05 06年也多处都是。
: 难道有一家家具店没倒闭就证明家具是暴利了吗？
avatar
e*6
33 楼
集中回答一下大家的问题。
第一题有一个隐含的限定条件：购买不可以在抛售之后。
第二题，就用简单的递归。pseudo-code如下：
recursive(array, queue, mark){
if queue is full
then print and return
for each char in array not marked
do mark it
push it into queue
recursive(array, queue, mark)
unmark and pop it
}
注意unmark和pop。因为要保持递归每一阶段的唯一性。
avatar
g*9
34 楼
Define 暴利?

【在 a******e 的大作中提到】
: 内容纯属转载
: We got our daughter's bedroom set for $700 cash...trundle bed, 2 Sealy
: mattresses, dresser, mirror, nightstand. It retails on the Land of Nod
: website for around $2500 w/o mattresses. Exact same model. Exact same
: manufacturer. First run. He's just able to purchase directly from the
: manufacturer and sells to friends at cost.
avatar
c*2
35 楼
suppose the closing prices are stored in an array
p[0]...p[i]...p[n-1]
for any position p[i]:
find min from p[0..i-1]
find max from p[i..n-1]
you always buy before you can sell, so global min/max is definitely wrong.

【在 d******a 的大作中提到】
: can you give some more detail about problem 1? Could you show the program?
: Thanks!
avatar
X*n
36 楼
你这第一题有问题吧,　哪里体现出i
【在 j*****u 的大作中提到】
: 1. 我一开始想成根据history的stock price来做predict了，想了半天。。。
: 其实是这个题的变种
: int array A里找两个position i和j，要求A[j]和A[i]的差maximum，同时i: static void BestDay(int[] stockPrices, out int buyDate, out int sellDate)
: {
: buyDate = sellDate = 0;
: int maxDiff = 0, minPrice = stockPrices[0], minPriceDate = 0;
: for (int i = 1; i < stockPrices.Length; ++i)
: {
: int price = stockPrices[i];
avatar
l*c
37 楼
1. one time scan O(n) three variables: max, maxindex, minindex
2. STL library, 递归 is wrong answer

.}

【在 e**********6 的大作中提到】
: 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
: 内容都剪切出来了，我现在没有原题，大概描述一下。
: 1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
: 抛售日。（coding）
: 2，给一个字符串，打印出这个字符串所有的permutation。（coding）
: 我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
: 之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
: 不明白，然后问我：你不想改变外面的值吗？
: 另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
avatar
a*c
38 楼
here is a test case for (1)
day 1 2 3 4 5 6 7 8 9 10 11
closing price 3 6 4 5 3 6 4.5 9 2 9 6
my algorithm says you should buy on either day 3 or 5 and sell on day 11.
avatar
j*u
39 楼
没有问题
minPriceDate总是
【在 X*********n 的大作中提到】
: 你这第一题有问题吧,　哪里体现出i
avatar
g*s
40 楼
第一题没说清楚啊。是否允许反复低吸高抛做波段，还是只能买卖一次？能否做空？
第二题很经典。你的答案是不是有点独特？

.}

【在 e**********6 的大作中提到】
: 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
: 内容都剪切出来了，我现在没有原题，大概描述一下。
: 1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
: 抛售日。（coding）
: 2，给一个字符串，打印出这个字符串所有的permutation。（coding）
: 我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
: 之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
: 不明白，然后问我：你不想改变外面的值吗？
: 另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
avatar
i*e
41 楼
The original question:
Say you have an array for which the ith element is the price of a given
stock on day i.
If you were only permitted to buy one share of the stock and sell one share
of the
stock, design an algorithm to find the best times to buy and sell.
from Hacking a Google interview from MIT.
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_3.pdf
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g*********s 的大作中提到】
: 第一题没说清楚啊。是否允许反复低吸高抛做波段，还是只能买卖一次？能否做空？
: 第二题很经典。你的答案是不是有点独特？
:
: .}
avatar
g*s
42 楼
but can you short-sell then buy-to-cover, aka, selling then buying.

share

【在 i**********e 的大作中提到】
: The original question:
: Say you have an array for which the ith element is the price of a given
: stock on day i.
: If you were only permitted to buy one share of the stock and sell one share
: of the
: stock, design an algorithm to find the best times to buy and sell.
: from Hacking a Google interview from MIT.
: http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_3.pdf
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
avatar
i*e
43 楼
I don't understand what you're asking?
The question mentioned you can only buy one share of the stock and sell one
share of the stock. So I don't see how you can sell then buy? You have to
buy before you sell.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g*********s 的大作中提到】
: but can you short-sell then buy-to-cover, aka, selling then buying.
:
: share
avatar
r*d
44 楼
这个思路非常清楚
不过算起来复杂度是n^2了， 再仔细想想也没有什么加速的方法

【在 c***2 的大作中提到】
: suppose the closing prices are stored in an array
: p[0]...p[i]...p[n-1]
: for any position p[i]:
: find min from p[0..i-1]
: find max from p[i..n-1]
: you always buy before you can sell, so global min/max is definitely wrong.
avatar
g*e
45 楼
o（n），process the array for max[i] and min[i]. classic dp solution

【在 r******d 的大作中提到】
: 这个思路非常清楚
: 不过算起来复杂度是n^2了， 再仔细想想也没有什么加速的方法
avatar
r*d
46 楼
多谢提醒， 刚才想起来算max可以在上一次的基础上接着算， 所以复杂度是o(n), 那
就不用琢磨加速了， 已经够快的了， 呵呵 dp那章还没有看的说。。。。

【在 g*****e 的大作中提到】
: o（n），process the array for max[i] and min[i]. classic dp solution
avatar
e*6
47 楼

这道题无论你用什么容器，都是一个递归的过程。因为实质是一个树的遍历。

【在 l******c 的大作中提到】
: 1. one time scan O(n) three variables: max, maxindex, minindex
: 2. STL library, 递归 is wrong answer
:
: .}
avatar
e*6
48 楼

顺带一提，这道题我事后测试过了，我的打印结果是完全正确地。。

【在 l******c 的大作中提到】
: 1. one time scan O(n) three variables: max, maxindex, minindex
: 2. STL library, 递归 is wrong answer
:
: .}
avatar
e*6
49 楼

我的答案就是最经典的方法

【在 g*********s 的大作中提到】
: 第一题没说清楚啊。是否允许反复低吸高抛做波段，还是只能买卖一次？能否做空？
: 第二题很经典。你的答案是不是有点独特？
:
: .}
avatar
g*s
50 楼
那面试人再不济，手里也该有份标准答案啊。

【在 e**********6 的大作中提到】
:
: 我的答案就是最经典的方法
avatar
e*6
51 楼

我哪儿知道啊。。所以才问：他是不是故意装糊涂来考察我的表述力？

【在 g*********s 的大作中提到】
: 那面试人再不济，手里也该有份标准答案啊。
avatar
g*s
52 楼
the problem just say you can only buy one share and sell one share. it doesn
't say you can only sell after buy.
"short" in stock trading means u can sell a share you don't have but borrow
from the broker, then buy it back to return. when stock price is going down,
traders make money from shorting the stock.
i think this problem actually could have a couple of variations. what you
said is the most common one.
even for that one, there are still details to be determined. what if the
stock is always going down from day 1? is the trader allowed to do nothing
with earning 0, or does he have to trade?

one

【在 i**********e 的大作中提到】
: I don't understand what you're asking?
: The question mentioned you can only buy one share of the stock and sell one
: share of the stock. So I don't see how you can sell then buy? You have to
: buy before you sell.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
avatar
a*y
53 楼
这个就是个简单的数学问题，跟真实的股票交易无关。股票交易都是实时的，不可能知
道未来没发生的价格，怎么做到低买高卖？

doesn
borrow
down,

【在 g*********s 的大作中提到】
: the problem just say you can only buy one share and sell one share. it doesn
: 't say you can only sell after buy.
: "short" in stock trading means u can sell a share you don't have but borrow
: from the broker, then buy it back to return. when stock price is going down,
: traders make money from shorting the stock.
: i think this problem actually could have a couple of variations. what you
: said is the most common one.
: even for that one, there are still details to be determined. what if the
: stock is always going down from day 1? is the trader allowed to do nothing
: with earning 0, or does he have to trade?
avatar
g*s
54 楼
1. with real stock properties there could be interesting variations. the
interviewer doesn't necessarily use the original one. why not get better
prepared?
2. even for real stock trading, this problem is making a lot of sense. it
can serve as an optimal benchmark to measure the performance of the fund
manager or the trading robot, just like Belady's cache algorithm.

【在 a****y 的大作中提到】
: 这个就是个简单的数学问题，跟真实的股票交易无关。股票交易都是实时的，不可能知
: 道未来没发生的价格，怎么做到低买高卖？
:
: doesn
: borrow
: down,
avatar
A*H
55 楼

just need another line of check
void printPermutation(string s, int start, int n) {
if (start>=n) {
cout<return;
}
for (int i=start; iif (s[i]==s[start] && (i!=start)) continue; // skip duplicate case
swap(s[start], s[i]);
printPermutation(s, start+1, n);
swap(s[start], s[i]);
}
}

【在 k*n 的大作中提到】
: 哎，我说所有人都默认这个字符串里面没有重复字符了是么？
avatar
o*1
56 楼
第二题可不可以这样：
void permutations(string set){
permutations("",set);
}
void permutations(string fixedprefix, string rest){
for(i=0;ipermutations(fixedprefix+rest[i],rest.substr(0,i)+rest.substr(i+1));
}
if (rest.empty()){
cout<}
}
avatar
c*l
57 楼
第一题: 开两个数组; min[], max[]; 正序遍历数组, 然后填入0..i的最小值进入min[
i]; 然后倒叙遍历数组, 然后填入i..n的最大值进入max[i];然后再遍历得出max[i] -
min[i]的最小值
第二题: next_permutation. 先sort下字符串; 然后next_permutation输出全部可能
permutation; 如果有重复的字母, 也会被take care
avatar
c*l
58 楼
hmmm... 第一题我这样做就3次遍历了
遍历一编应该就可以了:
lowest = price[0];
bestdeal = 0;
for(int i=1; i{
if(price[i] - lowest > bestdeal)
bestdeal = price[i] - lowest;

if(lowest > price[i])
lowest = price[i];
}
avatar
a*y
59 楼
这样会忽略所有的重复，不完全对。

【在 A*H 的大作中提到】
:
: just need another line of check
: void printPermutation(string s, int start, int n) {
: if (start>=n) {
: cout<: return;
: }
: for (int i=start; i: if (s[i]==s[start] && (i!=start)) continue; // skip duplicate case
: swap(s[start], s[i]);
avatar
e*s
60 楼
No, still has duplicates.
Use "accd" as an example, I got:
1 accd
2 acdc
3 adcc
4 cacd
5 cadc
6 ccad
7 ccda
8 cdca
9 cdac
10 ccad
11 ccda
12 cacd
13 cadc
14 cdac
15 cdca
16 dcca
17 dcac
18 dacc

【在 a****y 的大作中提到】
: 这样会忽略所有的重复，不完全对。
avatar
l*i
61 楼
第二题，用set就可以避免重复把？
avatar
l*c
62 楼
I don't think so.
Please read stl source code.
input : aaaaaaaa
output: aaaaaaaa
inout: aaab
output: aaab,aaba, abaa, baaa
so, basically, during the interview, if they have question about your answer
, you need ask them if the string has duplicate char or not.
递归 is right if there no duplicate char, but not good solution

【在 e**********6 的大作中提到】
:
: 我哪儿知道啊。。所以才问：他是不是故意装糊涂来考察我的表述力？
avatar
g*s
63 楼
我今晚试了一下，觉得楼主coding很牛。
第一个，如果事先没见过，想清楚算法后再写出O(N)的程序，45分钟之内完全搞定挺难
。还没算面试官读code的时间。
即使是O(N^2)的算法，要一遍bug free，加上检查的时间，也得二十分钟。
第二个算法简单，但要一遍下来bug free，也得是熟手，平时常练这种permutation才
行。
这俩题，一个半小时会比较从容。

.}

【在 e**********6 的大作中提到】
: 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
: 内容都剪切出来了，我现在没有原题，大概描述一下。
: 1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
: 抛售日。（coding）
: 2，给一个字符串，打印出这个字符串所有的permutation。（coding）
: 我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
: 之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
: 不明白，然后问我：你不想改变外面的值吗？
: 另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
avatar
V*i
64 楼
One should use a lookup table to check duplicates
My code is like this:
void find_permutations(string s, int i, int n) {
if (i >= n) {
cout << s << endl;
} else {
bool ch[256];
for (int j=0; j<256; j++) ch[j] = false;
for (int j=i; jif (!ch[s[j]]) {
ch[s[j]] = true;
swap(s[i], s[j]);
find_permutations(s, i+1, n);
swap(s[i], s[j]);
}
}
}
}
Use "accd" as an example, I got
accd
acdc
adcc
cacd
cadc
ccad
ccda
cdca
cdac
dcca
dcac
dacc

【在 e********s 的大作中提到】
: No, still has duplicates.
: Use "accd" as an example, I got:
: 1 accd
: 2 acdc
: 3 adcc
: 4 cacd
: 5 cadc
: 6 ccad
: 7 ccda
: 8 cdca
avatar
e*6
65 楼

answer
即便用stl容器，他也要靠一个递推的过程（我是指递归的过程，不一定需要递归函数
来实现）来实现，
不然用什么呢？
对于stl里面的permutation，它给出的定义说：A permutation is each one of the N
!
possible arrangements the elements can take (where N is the number of
elements in the range). 我感觉他会assume已经给出的是一个set。。但是你说得对
，这是一
个陷阱，应该提前问好是否会有重复的字符出现。。唉又被阿三给阴了。。

【在 l******c 的大作中提到】
: I don't think so.
: Please read stl source code.
: input : aaaaaaaa
: output: aaaaaaaa
: inout: aaab
: output: aaab,aaba, abaa, baaa
: so, basically, during the interview, if they have question about your answer
: , you need ask them if the string has duplicate char or not.
: 递归 is right if there no duplicate char, but not good solution
avatar
x*k
66 楼
第二题也是老题，有时会加问如果有重复的character怎么办。
career cup上给的结果的是用DP，只能针对非duplicate的情况。已有n个character的
permutation，将第n+1个character插入到已有的序列的每个可能位置中。
有duplicate的情况要麻烦一些，elfenliedsp6的方法是正确的。基本概念是先sort所
有的character。然后在每次入queue时只push连续相同character中的第一个，忽略后
续相同的。
avatar
l*c
67 楼
you are not allowed to use stl. My suggestion is to read stl code.
here, I list an example, if you are interested, you can write code
input:
axbb
first step:
sort the sting:
abbx smallest
xbba biggest
for( value = abbx; value < xbba; value ++)
{
print value
}
note: about value++
abbx + 1 = abxb
abxb + 1 = axbb
...........
xbab + 1 = xbba
the above is the correct answer.
list all permutations then delete is unaccetable.

N

【在 e**********6 的大作中提到】
:
: answer
: 即便用stl容器，他也要靠一个递推的过程（我是指递归的过程，不一定需要递归函数
: 来实现）来实现，
: 不然用什么呢？
: 对于stl里面的permutation，它给出的定义说：A permutation is each one of the N
: !
: possible arrangements the elements can take (where N is the number of
: elements in the range). 我感觉他会assume已经给出的是一个set。。但是你说得对
: ，这是一
avatar
c*s
68 楼
其实是一样的吧，把整个数组跑一遍，算出每个数和前面那个的差，
就变成wikipedia里面的那个题目了吧？

【在 s*******t 的大作中提到】
: 感觉题意不是这个意思吧！ 都是正数的话，你的那个就是所有加和了。
:
: array
avatar
l*3
69 楼
第一题可不可以这么做，O(N)的方法，请大虾指教。
#include
using namespace std;
typedef struct best_days {
int buy;
int sell;
} best_days_t;
best_days_t get_best_days(double* prices, int days){
best_days_t best;
best.buy = best.sell = -1;

int minday = 0;
double dmax = 0.0f;
double minprice = prices[0];

for (int i=1; iif (prices[i] - minprice > dmax){
dmax = prices[i] - minprice;
best.sell = i;
best.buy = minday;
}
if (prices[i] < minprice){
minprice = prices[i];
minday = i;
}
}

return best;
}
int main (int argc, char* argv[])
{
double prices[] = {3, 6, 4, 5, 3, 6, 4.5, 9, 2, 9, 6};
best_days_t best = get_best_days(prices, sizeof(prices)/sizeof(double));
cout << best.buy << "->" << best.sell << endl;

return 0;
}
avatar
i*r
70 楼
dude, this is a confusing way of using recursion. It is not
straightforward if it is correct or not. Remember, for a big company, if
others don't understand you code quickly, it is your fault. It doesn't
you are smarter than others, it means your code is not good enough and
is wasting other people's time.

【在 j*****u 的大作中提到】
: 没有问题
: minPriceDate总是
avatar
Q*r
71 楼
有些时候觉得cs是最难的了
面的问题都很变态

.}

【在 e**********6 的大作中提到】
: 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
: 内容都剪切出来了，我现在没有原题，大概描述一下。
: 1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
: 抛售日。（coding）
: 2，给一个字符串，打印出这个字符串所有的permutation。（coding）
: 我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
: 之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
: 不明白，然后问我：你不想改变外面的值吗？
: 另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
相关阅读
大家跟邻居经常串门么？急问：refinance：required services you can shop for空调滤网被吸进管道里了？从中国寄钱请问Steam Cleaner好用不？pay bi-weekly/weekly 还是 MONTHLY 好呢？5 yr ARMAgent给我说交易的时候不需要Lawyer谁能推荐下信誉好价格合适的房屋保险公司？想省钱，买lowes的prefinished cabinet，自己油漆， 可行吗？车库遥控器坏了怎么修？室外炒菜炉子问题。请推荐NJ的中国师傅装厨房！refinance rate装实木地板6.5/sqft价格算公道么？7/1 ARM 3.25% no cost, no fee.有经验的人说说postdoc期间买房的利弊吧买车贷款会影响房贷申请吗竹子地板好吗？请推荐上网+电话+中文电视的组合
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。