e**********6
发帖数: 78 | 1 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
内容都剪切出来了，我现在没有原题，大概描述一下。
1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
抛售日。（coding）
2，给一个字符串，打印出这个字符串所有的permutation。（coding）
我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
不明白，然后问我：你不想改变外面的值吗？
另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
反复解释之后，他突然恍然大悟。。
不知道是不是面试官有意装糊涂然后观察我的表述能力的？
这次题目都很简单。祝大家成功！ |
c***2
发帖数: 838 | 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] |
d******a
发帖数: 238 | 3 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]
|
s*****n
发帖数: 5488 | 4 第一题，
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!
|
e**********6
发帖数: 78 | 5
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!
|
n********e
发帖数: 518 | 6 searching global minimum and maximum prices?
right? |
E********a
发帖数: 124 | 7
.}
关于第二个，可能面试的人不是写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的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
|
j*****u
发帖数: 1133 | 8 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];
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;
} |
j*****u
发帖数: 1133 | 9 不知道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的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
|
i**********e
发帖数: 1145 | 10 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的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
|
|
|
s********y
发帖数: 161 | 11 第一题见过一个类似的。给一只股票一段时间每天的价格，每天可以买也可以卖，求最
大利润。 |
s*******t
发帖数: 248 | 12 感觉题意不是这个意思吧！ 都是正数的话，你的那个就是所有加和了。
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
:
: .}
|
A*H
发帖数: 127 | 13 similar concept, keep best profit and lowest buy price so far, update
those two values along the traverse
【在 s*******t 的大作中提到】
: 感觉题意不是这个意思吧！ 都是正数的话，你的那个就是所有加和了。
:
: array
|
A*H
发帖数: 127 | 14 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]);
}
} |
i**********e
发帖数: 1145 | 15 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
|
k*n
发帖数: 150 | 16 哎，我说所有人都默认这个字符串里面没有重复字符了是么？
【在 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]);
|
e**********6
发帖数: 78 | 17 集中回答一下大家的问题。
第一题有一个隐含的限定条件：购买不可以在抛售之后。
第二题，就用简单的递归。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。因为要保持递归每一阶段的唯一性。 |
c***2
发帖数: 838 | 18 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!
|
X*********n
发帖数: 570 | 19 你这第一题有问题吧, 哪里体现出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];
|
l******c
发帖数: 2555 | 20 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的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
|
|
|
a***c
发帖数: 2443 | 21 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. |
j*****u
发帖数: 1133 | 22 没有问题
minPriceDate总是
【在 X*********n 的大作中提到】
: 你这第一题有问题吧, 哪里体现出i
|
g*********s
发帖数: 1782 | 23 第一题没说清楚啊。是否允许反复低吸高抛做波段，还是只能买卖一次？能否做空？
第二题很经典。你的答案是不是有点独特？
.}
【在 e**********6 的大作中提到】
: 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
: 内容都剪切出来了，我现在没有原题，大概描述一下。
: 1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
: 抛售日。（coding）
: 2，给一个字符串，打印出这个字符串所有的permutation。（coding）
: 我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
: 之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
: 不明白，然后问我：你不想改变外面的值吗？
: 另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
|
i**********e
发帖数: 1145 | 24 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 的大作中提到】
: 第一题没说清楚啊。是否允许反复低吸高抛做波段，还是只能买卖一次？能否做空？
: 第二题很经典。你的答案是不是有点独特？
:
: .}
|
g*********s
发帖数: 1782 | 25 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
|
i**********e
发帖数: 1145 | 26 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
|
r******d
发帖数: 308 | 27 这个思路非常清楚
不过算起来复杂度是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.
|
g*****e
发帖数: 282 | 28 o（n），process the array for max[i] and min[i]. classic dp solution
【在 r******d 的大作中提到】
: 这个思路非常清楚
: 不过算起来复杂度是n^2了， 再仔细想想也没有什么加速的方法
|
r******d
发帖数: 308 | 29 多谢提醒， 刚才想起来算max可以在上一次的基础上接着算， 所以复杂度是o(n), 那
就不用琢磨加速了， 已经够快的了， 呵呵 dp那章还没有看的说。。。。
【在 g*****e 的大作中提到】
: o（n），process the array for max[i] and min[i]. classic dp solution
|
e**********6
发帖数: 78 | 30
这道题无论你用什么容器，都是一个递归的过程。因为实质是一个树的遍历。
【在 l******c 的大作中提到】
: 1. one time scan O(n) three variables: max, maxindex, minindex
: 2. STL library, 递归 is wrong answer
:
: .}
|
|
|
e**********6
发帖数: 78 | 31
顺带一提，这道题我事后测试过了，我的打印结果是完全正确地。。
【在 l******c 的大作中提到】
: 1. one time scan O(n) three variables: max, maxindex, minindex
: 2. STL library, 递归 is wrong answer
:
: .}
|
e**********6
发帖数: 78 | 32
我的答案就是最经典的方法
【在 g*********s 的大作中提到】
: 第一题没说清楚啊。是否允许反复低吸高抛做波段，还是只能买卖一次？能否做空？
: 第二题很经典。你的答案是不是有点独特？
:
: .}
|
g*********s
发帖数: 1782 | 33 那面试人再不济，手里也该有份标准答案啊。
【在 e**********6 的大作中提到】
:
: 我的答案就是最经典的方法
|
e**********6
发帖数: 78 | 34
我哪儿知道啊。。所以才问：他是不是故意装糊涂来考察我的表述力？
【在 g*********s 的大作中提到】
: 那面试人再不济，手里也该有份标准答案啊。
|
g*********s
发帖数: 1782 | 35 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
|
a****y
发帖数: 2548 | 36 这个就是个简单的数学问题，跟真实的股票交易无关。股票交易都是实时的，不可能知
道未来没发生的价格，怎么做到低买高卖？
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?
|
g*********s
发帖数: 1782 | 37 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,
|
A*H
发帖数: 127 | 38
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]);
printPermutation(s, start+1, n);
swap(s[start], s[i]);
}
}
【在 k*n 的大作中提到】
: 哎，我说所有人都默认这个字符串里面没有重复字符了是么？
|
o********1
发帖数: 4 | 39 第二题可不可以这样：
void permutations(string set){
permutations("",set);
}
void permutations(string fixedprefix, string rest){
for(i=0;i
permutations(fixedprefix+rest[i],rest.substr(0,i)+rest.substr(i+1));
}
if (rest.empty()){
cout<
}
} |
c*****l
发帖数: 30 | 40 第一题: 开两个数组; min[], max[]; 正序遍历数组, 然后填入0..i的最小值进入min[
i]; 然后倒叙遍历数组, 然后填入i..n的最大值进入max[i];然后再遍历得出max[i] -
min[i]的最小值
第二题: next_permutation. 先sort下字符串; 然后next_permutation输出全部可能
permutation; 如果有重复的字母, 也会被take care |
|
|
c*****l
发帖数: 30 | 41 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];
} |
a****y
发帖数: 2548 | 42 这样会忽略所有的重复，不完全对。
【在 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]);
|
e********s
发帖数: 248 | 43 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 的大作中提到】
: 这样会忽略所有的重复，不完全对。
|
l****i
发帖数: 396 | |
l******c
发帖数: 2555 | 45 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 的大作中提到】
:
: 我哪儿知道啊。。所以才问：他是不是故意装糊涂来考察我的表述力？
|
g*********s
发帖数: 1782 | 46 我今晚试了一下，觉得楼主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的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
|
V*****i
发帖数: 92 | 47 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; j
if (!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
|
e**********6
发帖数: 78 | 48
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
|
x****k
发帖数: 2932 | 49 第二题也是老题，有时会加问如果有重复的character怎么办。
career cup上给的结果的是用DP，只能针对非duplicate的情况。已有n个character的
permutation，将第n+1个character插入到已有的序列的每个可能位置中。
有duplicate的情况要麻烦一些，elfenliedsp6的方法是正确的。基本概念是先sort所
有的character。然后在每次入queue时只push连续相同character中的第一个，忽略后
续相同的。 |
l******c
发帖数: 2555 | 50 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。。但是你说得对
: ，这是一
|
|
|
c**s
发帖数: 43 | 51 其实是一样的吧，把整个数组跑一遍，算出每个数和前面那个的差，
就变成wikipedia里面的那个题目了吧？
【在 s*******t 的大作中提到】
: 感觉题意不是这个意思吧！ 都是正数的话，你的那个就是所有加和了。
:
: array
|
l**********3
发帖数: 161 | 52 第一题可不可以这么做，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; i
if (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;
} |
i*****r
发帖数: 265 | 53 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总是
|
Q****r
发帖数: 7340 | 54 有些时候觉得cs是最难的了
面的问题都很变态
.}
【在 e**********6 的大作中提到】
: 题目不难，两道题都是coding，是个印度人打来的。由于面试之后他就立即把文档里的
: 内容都剪切出来了，我现在没有原题，大概描述一下。
: 1，假设告诉你某只股票连续一段时间每天的收盘价格，写一个程序返回最佳的购买和
: 抛售日。（coding）
: 2，给一个字符串，打印出这个字符串所有的permutation。（coding）
: 我很shock的是，这个人不知道C++的pass by reference。我写了func(int &i){i=...}
: 之后他居然要求我改为*i=...。然后我提示他我用的是pass by reference，好像他也
: 不明白，然后问我：你不想改变外面的值吗？
: 另外，我第二题用了一个很obvious的递归，但是他却绕进去想不明白。。要求我把递
: 归的所有步骤都写出来给他看，然后我就写了，他还是纠结于一个问题不明白。。在我
|
