Ill teach you the rightway of thinkingfor breaking down tricky algorithmic coding interview questions youve never seen before.
Thebest answer so faris, of course, the max profit that we can get based on the prices weve seen so far.
So if the stock cost $500 at 10:30am, that meansstock_prices[60] = 500.
We call this a breakdown step. Its how we teach youthe right way to think about the problem.
This ones a good example of thegreedyapproach in action. Greedy approaches are great because theyrefast(usually just one pass through the input). But they dont work for every problem.
more accurately answer the challenge
I wish I had known about this website back when I was in algorithms class in college.This made me finally understand a number of concepts that had eluded me for years.
are the time (in minutes) past trade opening time, which was 9:30am local time.
Andthatsthe problem with this method of studying.
time andspace.We only loop through thelistonce.
No!max_profitis still always 0.Whats happening?
Youre standing in front of the whiteboard, working on one of those tricky interview questions.
to decide if its worth making a purchase.
if len(stock_prices) 2: raise ValueError(Getting a profit requires at least 2 prices) min_price = stock_prices[0] max_profit = stock_prices[1] – stock_prices[0]
Whaaat?? How do you evencome upwith something like that?
Your site was really indispensable for the Google/Amazon interview process.Ive recommended your site to everyone I know that wants to become both a better programmer and a better interviewer. Great work.
If were going to do better than, were probably going to do it in eitheror.comes up in sorting and searching algorithms where were recursively cutting thelistin half. Its not obvious that we can save time by cutting thelistin half here. Lets first see how well we can do by looping through thelistonlyonce.
Thebrute forceapproach would be to tryevery pair of times(treating the earlier time as the buy time and the later time as the sell time) and see which one is higher.
On Interview Cake, when you get stuck, you dont have to give up and look at the answer.
You cant just take the difference between the highest price and the lowest price, because the highest price might comebeforethe lowest price. And you have to buy before you can sell.
Well, were doing a lot of extra work. Were looking at every pairtwice. We know we have to buy before we sell, so in ourinner for loopwe could just look at every priceafterthe price in ourouter for loop.
In this case, its probably best to go with option (1). The advantages of returning a negative profit are:
So I grabbed Apples stock prices from yesterday and put them ina listcalledstock_prices, where:
You understandwhat the answer is, but you have no ideahow you could have gotten there yourself.
Suppose wecouldcome up with the answer in one pass through the input, by simply updating the best answer so far as we went. Whatadditional valueswould we need to keep updated as we looked at each item in our input, in order to be able to update thebest answer so farin constant time?
So for every price, well need to:
Then, the whiteboard marker crawls to a halt. It hangs there, hovering above the board. Frozen.
No prior computer science training necessaryIll get you up to speed quickly, skipping all the overly academic stuff.
Youre in! Loading your free trial question…
Programming interview questions by company:
Well, what are our options? Leaving ourfunctionas it is and just returning zero isnota reasonable optionwe wouldnt know if our best profit was negative oractuallyzero, so wed be losing information. Two reasonable options could be:
Honestly, this feels like cheating.Very efficient way to spend your study time and definitely pays for itself!
I used a number of resources to help prep for the coding interviews butInterview Cake stood out as by far and away the most useful.I owe you a massive debt of thanks
Instead,well give you thenext logical step you should be makingfor breaking down the question.
Subscribe to our weekly question email list
We have plenty more practice programming interview questions. Some easy, some hard. If youre ready toget really freaking good at programming interviews,get started now
But if the valuegoes down all day, were in trouble. Ourfunctionwould return 0, but theres no way we could break even if the price always goes down.
Theadditional valueis the minimum price weve seen so far. If we keep that updated, we can use it to calculate the new max profit so far in constant time. The max profit is the larger of:
How do you know if a problem will lend itself to a greedy approach? Best bet is to try it out and see if it works. Trying out a greedy approach should be one of the first ways you try to break down a new question.
Your site was an invaluable resource andreally helped me develop the iterative algorithmic problem solving skills big tech companies & startups are looking for.Great case of quality over quantity.
Youll see what we mean when you try it out:
Enter your email below to get a link to a free trial question.
When were calculating themax_profit, we need to make sure we never have a case where we tryboth buying and selling stocks at thecurrent_price.
But that will taketime,since we have two nested loopsforeverytime, were going throughevery othertime. Also,its not correct: we wont ever report a negative profit! Can we do better?
To start, try writing an example value forstock_pricesand finding the maximum profit by hand. Whats your process for figuring out the maximum profit?
Well, we started ourmin_priceat the first price, so lets start ourmax_profitat thefirst profit we could getif we buy at the first time and sell at the second time.
Since were trying to loop through thelistonce, lets use agreedyapproach, where we keep a runningmax_profituntil we reach the end. Well start ourmax_profitat $0. As were iterating, how do we know if weve found a newmax_profit?
How do we know when we have case (2)?
Thanks to your site, I have offers from Apple, Facebook and Google. Thats a hell of an ROI!I didnt go to school for computer science, and now I have multiple senior engineering offers from the worlds best tech companies.
Programming interview practice and tips for software engineers looking for jobs.
Were finding the max profit with one pass and constant space!
Explaining what to do next. Step by step.
Well also need to pay special attention to time 0. Make sure we dont try to buyandsell at time 0.
Are we done?Lets think about some edge cases. What if the pricestays the same? What if the pricegoes down all day?
Wedowant toraise an exceptionin that case, sinceprofitrequires buyingandselling, which we cant do with less than 2 prices. So, lets explicitly check for this case and handle it:
To try it on a new problem, start by asking yourself:
def get_max_profit(stock_prices): max_profit = 0 Go through every price (with its index as the time) for earlier_time, earlier_price in enumerate(stock_prices): And go through all the LATER prices for later_time in xrange(earlier_time + 1, len(stock_prices)): later_price = stock_prices[later_time] See what our profit would be if we bought at the earlier price and sold at the later price potential_profit = later_price – earlier_price Update max_profit if we can do better max_profit = max(max_profit, potential_profit) return max_profit
Youll see what we mean about learninghow to get the answer, not just what the answer is.
Youll learn the rightway of thinkingto quickly break down problems youve never seen before.
Well never post on your wall or message your friends.
Wellgreedilywalk through thelistto track the max profit and lowest price so far.
Its kinda like were sitting there with you, guiding you along as you go.
The way to fix whiteboard freeze is to run practice problems…right?
Well, our outer for loop goes throughallthe times and prices, but our inner for loop goes throughone fewer price each time. So our total number of steps is the sumn + (n – 1) + (n – 2) … + 2 + 1, which isstilltime.
to quickly solve problems youve never seen before.
. If profit is revenue minus expenses, were returning the
s users. It would be easy to wrap our
Check outfor more advice, guides, and practice questions.
If the price doesnt change, the max possible profit is 0. Ourfunctionwill correctly return that. So were good.
def get_max_profit(stock_prices): max_profit = 0 Go through every time for outer_time in xrange(len(stock_prices)): For every time, go through every other time for inner_time in xrange(len(stock_prices)): For each pair, find the earlier and later times earlier_time = min(outer_time, inner_time) later_time = max(outer_time, inner_time) And use those to find the earlier and later prices earlier_price = stock_prices[earlier_time] later_price = stock_prices[later_time] See what our profit would be if we bought at the earlier price and sold at the later price potential_profit = later_price – earlier_price Update max_profit if we can do better max_profit = max(max_profit, potential_profit) return max_profit
def get_max_profit(stock_prices): min_price = stock_prices[0] max_profit = 0 for current_price in stock_prices: Ensure min_price is the lowest price weve seen so far min_price = min(min_price, current_price) See what our profit would be if we bought at the min price and sold at the current price potential_profit = current_price – min_price Update max_profit if we can do better max_profit = max(max_profit, potential_profit) return max_profit
def get_max_profit(stock_prices): if len(stock_prices) 2: raise ValueError(Getting a profit requires at least 2 prices) Well greedily update min_price and max_profit, so we initialize them to the first price and the first possible profit min_price = stock_prices[0] max_profit = stock_prices[1] – stock_prices[0] Start at the second (index 1) time We cant sell at the first time, since we must buy first, and we cant buy and sell at the same time! If we started at index 0, wed try to buy *and* sell at time 0. This would give a profit of 0, which is a problem if our max_profit is supposed to be *negative*–wed return 0. for current_time in xrange(1, len(stock_prices)): current_price = stock_prices[current_time] See what our profit would be if we bought at the min price and sold at the current price potential_profit = current_price – min_price Update max_profit if we can do better max_profit = max(max_profit, potential_profit) Update min_price so its always the lowest price weve seen so far min_price = min(min_price, current_price) return max_profit
id:8502150,username:2018-06-07_09:13:06_g54o41,email:null,date_joined:2018-06-07T09:13:06.408161+00:00,first_name:,last_name:,full_name:,short_name:friend,is_anonymous:true,is_on_last_question:false,percent_done:0,num_questions_done:0,num_questions_remaining:46,recruiting_is_interested_in_intros:null,is_full_access:false,first_payment_date:null,last_payment_date:null,num_free_questions_left:3,terms_has_agreed_to_latest:false,preferred_content_language:,preferred_editor_language:,is_staff:false,auth_providers_human_readable_list:,num_auth_providers:0,auth_email:,profile_public_id:null
how much we would have lost. If were trying to get rich, well probably care about those numbers.
Heres one possible solution:
Learningwhat the answer isdoesnt help you. You need to learnhow to come up withthe answer.
if we would have lost money, and it
Having tried several resources for interview prep, I can honestly say thatInterview Cake provides the most structured and confidence-inducing approach.
Youre drawing a complete blank. Nothing.
Programming interview questions by language:
Youre off to a reasonable start. Jotting down some notes on the board while thinking out loud.
I got offers from 7/8 of the companies at which I interviewed.After not going through a formal interview process in nearly a decade, your site really helped build my confidence. Youre a hero, Parker 😉
You pull up a practice problem, work on it, get as far as you can…
Writing programming interview questions hasnt made me rich yet … so I might give up and start trading Apple stocks all day instead.
What if the pricegoes down all day? In that case, the best profit will benegative.
But we have the potential foran index out of bounds errorhere, ifstock_priceshas fewer than 2 prices.
The max profit we can get by selling at thecurrent_priceis simply the difference between thecurrent_priceand themin_pricefrom earlier in the day. If this difference is greater than the currentmax_profit, we have a newmax_profit.
At each iteration, ourmax_profitis either:
Youre in! Head over to your email inbox right now to read day one!
Until you get stuck. You give up and look at the answer.
No spam. Easy unsubscribe if you hate it.
You make eye contact with your interviewer (or mock interviewer), whos watching you expectantly.
Learningwhat the answer isdoesnt help you. You need to learnhow to come up withthe answer.
No shortingyou need to buy before you can sell. Also, you cant buyandsell in the same time stepat least 1 minute has to pass.
are the price (in US dollars) of one share of Apple stock at that time.
We decided to return anegativeprofit if the price decreases all day and we cant make any money. We could haveraised an exceptioninstead, but returning the negative profit is cleaner, makes ourfunctionless opinionated, and ensures we dont lose information.
Your website was so helpful thatI didnt just receive an offer from Google, I also received a competing offer from Amazon.
Interview Cake mimics an actual interview experience – the hints are gradual enough to nudge you in the correct direction so you can learn the thought process needed to succeed.
If the price always goes down,min_priceis always set to thecurrent_price. Socurrent_price – min_pricecomes out to 0, which of course will always be greater than a negative profit.
Write an efficientfunctionthat takesstock_pricesand returnsthe best profit I could have made from one purchase and one sale of one share of Apple stock yesterday.
Right now I have an offer from Microsoft and Im still in the interview process with Google and LinkedIn.Life is pretty good, and I owe so much of that to Interview Cake.
How can we adjust ourfunctionto return a negative profit if we can only lose money?Initializingmax_profitto 0 wont work…
To make sure were always buying at anearlierprice, never thecurrent_price, lets switch the order around so we calculatemax_profitbeforewe updatemin_price.
Try applying this greedy methodology to future questions.
First, I wanna know how much money Icould havemade yesterday if Id been trading Apple stocks all day.
No spam, ever. Unsubscribe whenever.
The problem is, the way most people practice simply doesnt work.