Apply Permutation

Apply Permutation

Problem Statement

Write a program that takes a permutation array and a input array and reorder the input array as per the given permutation.

Problem Solving 

• I can see that this seems to be a linear time problem. 
• We need to apply permutation inc cycle.
• Start at 0 replace current position at 0 with previous input, swap previous input at current position. continue till end. 
• However there are multiple missing things in this solution. 
• As there can be multiple cycle in the same array. Therefore we need mechanism to break from cycle and then run on the next cycle. 
• To break the cycle we need to keep an bool index whether the position is processed or not. 
• and to go to next cycle we can always scan the processed array for non processed items and then start the process there. 
• This seems okay. 
• Find code here.  

Learning

• This question might seem simple but to implement it correctly is difficult. 
• Since I coded through the problem solving my code also looked tangled and complex. 
• After multiple debugging sessions and fixing problems. The code looked in a very bad shape. 
• However it passed all test cases. 
• Then I looked at the answer to find it to my surprise, that the code written is so much more elegant than what I had written. 
• However there is space optimization in the book's answer but ignoring that also the code was  much more simple. 
• Later I refactored my code into that shape. Felt both good and bad. 
• Writing good code is really really difficult. I understand it now. Everyone can code but to make proper sentences in the language is the art. To write pieces that are elegant and clear and concise. 
• Now that I have refactored it. It look good.
• Also one key insight is that whenever you feel like using an iterator that runs through all the elements in linear fashion use a for loop. and when needed to skip use continue or empty loop cycle. No need to write make complex iterator advances. 
• Small question lots of learning. 

Enumerate All Primes to N

Enumerate All Primes to N

Problem Statement

Write a program that takes an integer argument and returns all primes between 1 and that integer. 

Problem Solving

• There is not much of any solving here as I already know an ancient and well known algorithm for this. It's called the Sieve of Eratosthenes. 
• The idea is to create a list of all numbers to n. 
• Then iterate all number from two and at each number keep marking the multiples of those numbers as false or -1. 
• The iterate to the next non -1 number and do the same. 
• Find Code here. 

Learning

• Must always check for bounds. 
• The time complexity is n2 and space in O(n). 
• There is a way to save some space as the even numbers can be removed. 
• std::iota in the numeric header is a library function that can fill array with increasing numbers.
• There is also a Segmented Sieve which is used for large ranges and by segmenting them into smaller chunks
•  Since I could not understand all aspect of optimizations to this problem I am currently leaving behind this problem and moving on to next one.

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.