Algorithm and friendship in 2018

January 9, 2018

Introduction

It is most challenging time for a lot of people, specially for those young graduate students who studies in United States. I have met over three Chinese master graduate students last few months on mock interview platform, and I really like to work with them. It is hard for young people to find time to work on practice since they have so many courses to study full time, but somehow they can write very beautiful code also good analysis of the algorithm.

One of my most favorite is to write solution in five minutes as long as I give him the hint. I could not be more happy if I work with him as full time job. And then I will be a lazy lady and have a lot of time to learn fancy technology and framework.

Code practice

One algorithm can make friendship better because we all like to work on algorithm and data structure. So I have to write one algorithm for friendship since the peer asked me to write through wechat.

Here is my code practice today, it takes me over 20 minutes. I still made a few mistakes in first writing, and I kept telling myself "Do not use debug. Use whiteboard testing." I did and found a few bugs. And the code passed three test cases first time.

Extended algorithm

What if the elements in the array are any value?

My first idea is to sort the array, and then find the value in the sorted array using binary search, or using hashmap to record the value and its index value. But time complexity is at least O(nlogn).

The peer told me that it should be linear algorithm. So I think about it carefully, in theory we do not need to sort the array, all we care about is the first chunk max value is smaller than next chunk's smallest value.

The idea is to use extra array and then preprocess the array from right to left, and get the minimum value for each index covering the range of [index, length - 1].