Introduction
Life is much easy as a programmer once I learn how to write clean code for humans, learn simple things like TED principle, how to break giant expression to write simple code. One thing I have to learn is to make algorithm as simple as possible, go back to my favorite topic - reasoning and analysis, my favorite exercise is to prove something based on axioms.
Today 10:00 pm I had chance to share my proof to the peer how to argue the array is still not descending after the change. The reasoning was very well welcomed by the peer, I got 5 as a reward, top points as an interviewer.
I learned the lesson first time in my life through my real experience. I was told to prove that binary search is most efficient way to solve the search algorithm from 1 to n. I learned the lesson so today I asked the peer the question how to prove his assumption. He could not do it, I showed him in quick 5 minutes talk.
I know that one day I will need some advanced mathematics skills to handle some task. Today it is the first time I showed the proof to a peer. I miss the fun to prove so many mathematics when I was young.
Algorithm practice proof
Supposing that there is an sorted array with distinct integer, denoted as array, how to prove that new array based on array[i] - i is not descending.
My argument is simple, since the array is sorted in ascending order, we have array[i + 1] > array[i] for any i >= 0. Based on the fact that array has distinct integer, it is not possible that array[i + 1] == arr[i]. So my next argument is that the increment is at least 1, in other words, array[i + 1] - array[i] >= 1 for any i >=0. Next step, ascending distinct array {0, 1, 2, ..., n-1} has increment 1. So array[i] - i >= 0.
I was challenged by the peer what kind of interview I prepare for. I just laughed and answered his question. I learned from the real life lesson, I have to give out mathematics proof to show my real interest and talent.
Counter example
Two ascending sorted array, the difference can not be assumed to be non-descending order. The first ascending array is Array[i] = i, second ascending array is secondArray[i] = 2 * i, the new array Array[i] - secondArray[i] = - i, which is descending.
Actionable Item
Write down my proof that binary search O(logn) is most efficient solution.
No comments:
Post a Comment