Buy and Sell stock twice

Buy and Sell stock twice 

Problem Statement 

Given an array of stock prices on each day. Write a program that gives the maximum profit one can achieve by buying and selling a stock at most twice. 

Problem Solving

• Immediately I started to think like I solved the previous one stock problem and thought of instead of registering one max_profit I can register two maxprofits. 
• However this could make the complexity n*m where m is the number of times we can sell. 
• For eg. We would iterate the array looking for local minima and keep updating the max_profit array[2]. However we need to make sure that we evict the smallest of the profits. For 2 this could simple be a std::pair with wrapper. However for n elements we need to make a priority queue (earlier I thought of linklist which can cause quadratic runtime) which can make the eviction and insertion log n. That would make the total complexity be O(nlogm) 
• However as I saw in the book there is an linear order time complexity solution to this problem. 
• So I cheated and looked at the answer. I took me some time to understand and that's because If I would have spent some time thinking about how to optimize this solution to O(n) probably I would have fired my neurons which already know this technique because I remember I used this technique to solve the Google Interview question. That means somewhere in my brain this chain of thought is present it's only to reach that thought with reasoning. 
• So after writing about how guilty I feel, let move to the answer. 
• What we can do here is to understand that we need to make utmost 2 buy sell and strictly one after an other. 
• This one after an other also is a good hint for this technique. 
• So what we can do is that we iterate and store results from left to right and from right to left registering max_profit one could make only considering 0...i values and in the reverse array we would have max_profit from i+1 ... n. 
• Finally to get the answer we iterate both the arrays and get max of sum of both arrays and that  would be our answer. 
• One optimization that they have done here it that instead of doing the operation of calculating reverse and then adding they have clubbed the last two steps in the same array to save space and time. Smart ! 
• Find code here.

Learnings

• Do not jump to answers please. 
• This would not register in the brain properly if I haven't reasoned about it well and just looked at the answer. 
• The technique is good and easily understandable. 
• My original solution however is scalable. We can make it to calculate n sell and buy opportunities.  
• One good thing that happened was that once the algo was in my head I coded and it worked in first time without having to redo any algo changes. So that is a good sign. 

Buy and Sell Stock Once

Buy and Sell Stock Once

Problem Statement

Write a program that takes an array of stock prices and return maximum profit that can be made by buying and selling one stock. 

Problem Solving

• This question I have seen a hundred times, lets kill this once and for all. 
• So a list of array with number and we are interested in the max profit. 
• Max profit would be obtained by buying at a local minima followed by a local maxima. 
• The brute force way would be for each day consider buying and then calculate how much profit we get by selling on remaining following days.
• This would surely give correct ans with quadratic time complexity.  
• A linear approach would be to iterate through the array in ascending time and keep registering max_profit.
• At every element we check whether the element is a local minima if so the is it less than the current local minima, if yes then we update out buying option.
• Otherwise we continue iterating and registering max_profit. 
• Stop when we reach the last element.  
• Find code here.  

Learning

• Like the previous problem problem solving really is emotionally challenging despite being able to solve the problem in decent time. The emotional strength to face it is enormous. 
• Thinking the brute force way was obviously morale boosting that at least there is a way. 
• Further optimizing it was easy and confidence boosting. 
• I think I should now face problems with more confidence and these are really not that difficult. 
• One more thing, today this problem was solved without any compiler errors and in one go. 

Delete Duplicates From Sorted Array

Delete Duplicates From Sorted Array 

Problem Statement

Write a program that takes input as a sorted array and updates it so that all duplicates have been removed and the remaining elements have been shifted left to fill the empty indices.

Problem Solving

• We need to update the array in place.
• Something gives me intuition about iterating from left. 
• Now if I were to iterate from right then on encountering a duplicate I need to move it somewhere on the left but that would mess up the order. 
• I need to keep growing up a subarray of duplicate dump in the left. 
• Can we do something like the partition problem where we swap elements into respective groups. 
• One solution is to keep two iterators one tells which position to write as new elements other iterates through the array on each elements we check in a unordered set whether this elements if found or not if found then we move on else we update the write iterator with value on array_itr and then move on.
• This would require us to build a unordered hash set which can store all unique elements in the array and would cost space theta of n as we store exactly n elements in the set. 
• This idea will actually work with unsorted array too. that means this idea does not use the fact that the array is sorted. 
• Hence a better approach could be to iterate with two iterators like in the previous element but instead of checking each element in the set we iterate till we find a number that is not the last element found and update the write pointer.
• This seems to use the fact that we are bound to find duplicates in order and not random.
• Find Core here.

Learning

• Intuitions can be wrong, infact they can be exactly opposite.
• In case of ordering problems a quick way to find out that your solution is optimal is to check whether your solution works on if the elements we unordered. If so then you are not using the sorted information. Like in this case we achieved a better solution by detecting that our solution is agnostic to whether the given array is sorted.

Advancing through an Array

Advancing through an Array

Problem Statement

Write a program that takes an array of n integers, where A[i] denotes maximum we can advance from index i and return whether it is possible to reach the last index when started from the beginning  of the array. 

Problem Solving

•  A simple solution to this problem would be to calculate a max_reach at any given position and while iterating to reach the max_reach we keep updating it. If in the end we reach the end of an array then a solution is possible otherwise not.
• One optimization we can add it to stop iterating as soon as the max_reach becomes greater than size of the array. 
• Find Code here.

 Learning

• Lately I have realized that Problem Solving is as much a emotional task as it is a mental task. When we pick up a new problem all those imposter syndrome feelings and fear of unknown starts dwelling in. I worry more about the blow to confidence I would get if I could not solve this problem more than I think about how to solve the problem.

Multiply two arbitrary precision integers

Increment Arbitrary  precision number

Problem Statement

Write a program that takes two array B1 and B2 and return a new array with value B1 * B2 . 

Problem Solving

• Straight forward I think this is again a duplicate of high school method simulation. 
• We need to break down this into manageable chunks or functions.
• First we will take a two vector of integers and need a function to carry out multiplication of array with an int so we need a function for that.
• Once we are done with creating individual multiplication chunks. We need to add them with offsets as in school days. 
• So we need to separate the indexing with offset logic with the function that carries out actual addition. 
• In all these we need to maintain that all functions return correct values for individual inputs. This helps intensively in debugging. And that all functions return values in correct order, since we are using vectors here. we need to insert new elements at back which causes most computation to return values in reverse order so we need to reverse the final outputs for each function. 
• Find Code here. 

Learning

• The most difficult part was the offset addition. This added with complexity of reverse notion of number really hurt my brain. 
• However whatever doesn't kill you makes you stronger. 
• Also there were numerous compile time issues, this indicates I need to understand "const" in depth this causes me a lot of pain. 
• Also C++ compiler errors are extremely verbose or may be the right word is cryptic. May be some time will make me comfortable. 
• This was a difficult problem no doubt not in terms of problem solving but actual coding. 

 

Increment arbitrary precision number

Increment Arbitrary  precision number

 

Problem Statement

Write a program that takes an array of digits encoding a decimal number D and updates the array to represent the number D+1. 

Problem Solving

• Straight forward I can think of doing arithmetic as taught in school. 
• Add 1 to the last digit if the digit becomes more than 9 then carry repeat the process on the next digit. 
• Since we always increment the digit by 1 therefore we only need to check for digit 9.
• So we iterate the array in reverse order if the digit is non -9 then increment it by one and return else set it to 0 and keep iterating till end.
• If we reach the end that means that all digits were 9 hence we need to insert a 1 in the beginning. 
• Find Code here

 Learning 

• Due to one stupid mistake I learnt quite a few things here.   
• First since the google C++ style guide mentions that always take pointer as arguments if we wish to modify it. That makes the caller confident about what objects will be modified. 
• However to work with it we try not to use pointer in the callee function instead we cast it to a normal object. However if we try to write something like A a = *b. then a is a copy of value b. which is not what we want instead always do A &a = *b then a is a reference to the pointer value.
• This also gave me a better understanding about references and their uses in c++. 
• References are not variables that is they do not have any memory of there own they are just compiler syntactic sugar. 
• Overall the problem was naive. 
• Time complexity is linear while space is constant. 

Dutch National Flag Partitioning

Dutch National Flag Partitioning

Problem Statement

Partitioning is a common process used in other algorithms such a quicksort. In this problem, we are given an Array A and an index i. We have to rearrange A such that , all elements less than A[i] appears first followed by all elements equal to A[i] followed by all elements greater than A[i]. 

Problem Solving

• Not lying but since I have done such a problem sometime in past, this has quickly led me to think of using iterators that spans 3 ranges of less than, equal to and greater than values. 
• However the first question is to where to position each initially. 
• First I thought of positioning them at begin and end -1 position, but just initializing them there because we do not have other option is breaking the invariant that at any time those iterator should point to correct values. 
• Also there can be a case where all values are same then there would be no point in doing anything. 
• This also means that we should skip the part that is correct and hence post skipping we could arrive at the correct iterator location. 
• So first iterate from both ends and get to a location for both iterators where they are in accordance with the arrangement that left iterator has values less than A[i] and the right one has values greater than A[i] 
• when this process ends we would reach the exact range we need to actually rearrange and bonus point if there is no range left to process. 
• Once we reach this range. We need to create another iterator that starts at begin + 1, to iterate till right iterator. 
• at every point we check if the iterator is less than A[i] then we swap it with left itr and increment left itr and similarly if it is greater than A[i] then we swap it with right itr.
• And yes that should do it. 
• It should also be able to handle cases where all values fall into one range, since that we would skip at the beginning only.
• I wrote it, it failed and corrected it and ran correctly then. 
• Find Code here.

Learning  

• Never doubt yourself In the first attempt the answer came out wrong and I immediately jumped to the conclusion that the comparison mechanism is incorrect since I have recalled it from past memory. 
• However it turns out that all that was missing was one more iteration that I did not perform. 
• This also makes me aware of the fact whenever we talk about iteration we need to be accurate about what are iteration limits. 
• The complexity for this solution straight forward is constant since we are only swapping elements by traversing the array once and no extra memory is required. 
• Also I learned the best way to swap elements of iterators are iter_swap a built in function in algorithms library. 
• Hmm.. simple one but panic caused a lot of time waste.