Hewlett Packard Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
Got issue while pasting the code, See below
// Objective C
@interface SaleReport : NSObject
@property (nonatomic, assign) int buyWeek;
@property (nonatomic, assign) int sellWeek;
@property (nonatomic, assign) int profit;
@end
@implementation SaleReport
@end
@interface StockMarket : NSObject
+ (void)start;
@end
@implementation StockMarket
+ (void)start {
SaleReport *report = [self maxProfitReport:@[@14, @6, @7, @11, @10, @9]];
if(report. profit > 0) {
NSLog(@"Buy on Week : %d", report.buyWeek);
NSLog(@"Sell on Week : %d", report.sellWeek);
NSLog(@"Get Profit : %d", report.profit);
}
else {
NSLog(@"No Profit Making Senerio");
}
}
+ (SaleReport *)maxProfitReport:(NSArray *)weekSales {
//We don’t allow short selling
if ([weekSales count] <= 2) {
return [[SaleReport alloc] init];
}
int highestSellingIndex = [self findHighestSellingFromWeeks:weekSales];
if(highestSellingIndex <= 2) {
return [[SaleReport alloc] init];
}
// To avoid short selling.
int newArrayIndex = (highestSellingIndex - 1);
NSArray *firstHalf = [weekSales subarrayWithRange:NSMakeRange(0, newArrayIndex)];
NSArray *secondHalf = [weekSales subarrayWithRange:NSMakeRange(newArrayIndex, ([weekSales count] - newArrayIndex))];
int lowestSellingIndex = [self findLowestSellingFromWeeks:firstHalf];
SaleReport *secondReport = [self maxProfitReport:secondHalf];
int firstHalfProfit = [weekSales[highestSellingIndex] intValue] - [weekSales[lowestSellingIndex] intValue];
int secondHalfProfit = secondReport.profit;
SaleReport *report = nil;
if (firstHalfProfit > secondHalfProfit) {
report = [[SaleReport alloc] init];
report.buyWeek = lowestSellingIndex;
report.sellWeek = highestSellingIndex;
report.profit = firstHalfProfit;
}
else {
report = secondReport;
}
return report;
}
+ (int)findHighestSellingFromWeeks:(NSArray *)weekSales {
int index = 0;
int value = 0;
for(int i = 2; i < [weekSales count]; i++) {
int newValue = [weekSales[i] intValue];
if(value < newValue) {
value = newValue;
index = i;
}
}
return index;
}
+ (int)findLowestSellingFromWeeks:(NSArray *)weekSales {
int index = 0;
int value = [weekSales.firstObject intValue];
for(int i = 0; i < [weekSales count]; i++) {
int newValue = [weekSales[i] intValue];
if(newValue < value) {
value = newValue;
index = i;
}
}
return index;
}
@end
Dynamic Programming C#
private class BuySell
{
public Int32 buy;
public Int32 sell;
public Int64 profit;
public BuySell()
{
buy = Int32.MaxValue;
sell = Int32.MinValue;
profit = Int64.MinValue;
}
}
public static void Test()
{
int[] a = { 5, 6, 7, 11 };
FindBuySell(a);
}
public static void FindBuySell(int[] weelkyPrice)
{
BuySell bestResult = new BuySell();
bestResult = FindBuySell(weelkyPrice, 0, bestResult);
if (bestResult.profit > 0)
{
Console.WriteLine("Buy on {0} and Sell on {1} to make ${2} profit per share"
, bestResult.buy + 1, bestResult.sell + 1, bestResult.profit);
}
else
{
Console.WriteLine("Can't make profit!");
}
}
private static BuySell FindBuySell(int[] weeklyPrice, int start, BuySell bestResult)
{
if (start == weeklyPrice.Length - 3) // last 3 elements
{
if (weeklyPrice[start] < weeklyPrice[weeklyPrice.Length - 1])
{
bestResult.buy = start;
bestResult.sell = weeklyPrice.Length - 1;
bestResult.profit = weeklyPrice[bestResult.sell] - weeklyPrice[bestResult.buy];
}
}
else
{
bestResult = FindBuySell(weeklyPrice, start + 1, bestResult);
Int32 buyPrice = weeklyPrice[start];
Int32 sellPrice = Int32.MinValue;
Int64 profit = bestResult.profit;
int newSellIndex = Int32.MinValue;
for (int i = start + 2; i < weeklyPrice.Length; i++)
{
sellPrice = weeklyPrice[i];
if (sellPrice - buyPrice > profit)
{
profit = sellPrice - buyPrice;
newSellIndex = i;
}
}
if (profit > bestResult.profit)
{
bestResult.buy = start;
bestResult.sell = newSellIndex;
bestResult.profit = profit;
}
}
return bestResult;
}
Here I prefer to go with divide an conquer approach.
Approach:
From the 52 weeks find the biggest selling value, divide it from there and find the smallest value in front of it.
Also do the same iteration with second cropped part and return the difference of highest and smallest.
The most profit is max value for any of those part.
Now observe the question again.
Point 1 : Short selling is not allowed so while finding the smallest we need to ignore the adjacent one and splitting the array we need to start from that position. Also ignore the first two element while looking for highest value.
- This is the reason I choose divide and conquer we get much more flexibility.
Point 2 : Report if there is no profit making senerio. We after the execution we can check the profit value is greater than 0 to do this. Also check if we had more than 2 weeks otherwise there is no profit making senerio.
- Naveen Shan February 24, 2017