面试问题由财务软件公司的程序员岗位

Q1）假设你有一个数组，第i个元素是给定股票的价格       那天我。

如果你只允许买股票的一个份额和卖一的份额       股票，设计一个算法，发现买入和卖出的最佳时间。

我的解决方案：     我的解决办法是让对ARRAYSIZE-1天一天，我和天我+ 1之间的区别在股票价格的数组，然后使用Kadane算法返回最大连续子array.I的总和然后将买进的开始最大连续阵列和卖出的最大结束 连续阵列。

我想知道如果我的解决办法是正确的，是有没有更好的解决方案在那里???

回答后有人问我一个跟进的问题，我正好回答了同样的

Q2）既然你知道X公司的未来的收盘价为未来10天，       设计一个算法，以确定是否应该买入，卖出或持有的每       单日（你被允许只能每天做决定1）与目的       利润最大化的

例如：第1天收盘价：2.24          第2天收盘价：2.11           ...           10日收盘价：3.00

我的解决方法：同上

我想知道如果theres没有更好的算法，在那里以利润最大化定 我可以做决定的每一天

Q1如果你只允许购买一股股票和卖出股票的一个份额，设计一个算法来找到最佳时间购买和出售。

在通过阵列单传，确定指数我用最低的价格和指数Ĵ与最高价。你买的我，卖在Ĵ（出售，然后再购买，借用的股票，是在一般金融获准，所以它是好的，如果 J＆LT;我）。如果所有的价格都是一样的，你没有做任何事情。

Q2既然你知道未来关闭X公司的价格在接下来的10天，设计一个算法，以确定是否应该买入，卖出或持有的每一天（你被允许只能使1号决定每一天）与利润最大化的目的

有只有10天，因此，只有 3 ^ 10 = 59049 不同的可能性。因此，它是完全有可能用蛮力。也就是说，尝试各种可能性，只需选择其中一个给人最大的利润。 （即使一个更有效的算法被发现，这将保持测试更有效的算法的有效方式。）

部分的强力方法所产生的解决方案可能是无效的，例如：它可能无法将自己（或欠）以上的份额一次。此外，你需要最终拥有0股，在10天的末尾，或者任何职位，在10天结束时自动平仓？另外，我想澄清的是，我在第一季度取得，即它可以在购买之前采取股票价格优势跌倒的出售假设。最后，有可能是交易费用考虑在内，包括付款，如果你借股票，才能在购买之前就卖掉它作出。

在这些假设澄清它很可能是可能采取设计出更有效的算法。例如，在最简单的情况下，如果你只能拥有一股，你必须买你卖过，那么你将有系列中的买入的第一最小，卖出上一次最大，并购买和销售在任何最小值和最大值其间。

我越去想它，我越觉得这些面试问题都是一样关于看候选人如何以及是否澄清一个问题，因为他们对解决问题的方法。

Interview Question by a financial software company for a Programmer position

Q1) 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.

My Solution : My solution was to make an array of the differences in stock prices between day i and day i+1 for arraysize-1 days and then use Kadane Algorithm to return the sum of the largest continuous sub array.I would then buy at the start of the largest continuous array and sell at the end of the largest continous array.

I am wondering if my solution is correct and are there any better solutions out there???

Upon answering i was asked a follow up question, which i answered exactly the same

Q2) Given that you know the future closing price of Company x for the next 10 days , Design a algorithm to to determine if you should BUY,SELL or HOLD for every single day ( You are allowed to only make 1 decision every day ) with the aim of of maximizing profit

Eg: Day 1 closing price :2.24 Day 2 closing price :2.11 ... Day 10 closing price : 3.00

My Solution: Same as above

I would like to know what if theres any better algorithm out there to maximise profit given that i can make a decision every single day

Q1 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.

In a single pass through the array, determine the index i with the lowest price and the index j with the highest price. You buy at i and sell at j (selling before you buy, by borrowing stock, is in general allowed in finance, so it is okay if j < i). If all prices are the same you don't do anything.

Q2 Given that you know the future closing price of Company x for the next 10 days , Design a algorithm to to determine if you should BUY,SELL or HOLD for every single day ( You are allowed to only make 1 decision every day ) with the aim of of maximizing profit

There are only 10 days, and hence there are only 3^10 = 59049 different possibilities. Hence it is perfectly possible to use brute force. I.e., try every possibility and simply select the one which gives the greatest profit. (Even if a more efficient algorithm were found, this would remain a useful way to test the more efficient algorithm.)

Some of the solutions produced by the brute force approach may be invalid, e.g. it might not be possible to own (or owe) more than one share at once. Moreover, do you need to end up owning 0 stocks at the end of the 10 days, or are any positions automatically liquidated at the end of the 10 days? Also, I would want to clarify the assumption that I made in Q1, namely that it is possible to sell before buying to take advantage of falls in stock prices. Finally, there may be trading fees to be taken into consideration, including payments to be made if you borrow a stock in order to sell it before you buy it.

Once these assumptions are clarified it could well be possible to take design a more efficient algorithm. E.g., in the simplest case if you can only own one share and you have to buy before you sell, then you would have a "buy" at the first minimum in the series, a "sell" at the last maximum, and buys and sells at any minima and maxima inbetween.

The more I think about it, the more I think these interview questions are as much about seeing how and whether a candidate clarifies a problem as they are about the solution to the problem.