Leetcode 611: Valid Triangle Number

March 9, 2018

Introduction

It is the first time I chose the algorithm in my mock interview as an interviewer. The peer worked on the algorithm in March 9, 2010 10:00 PM. I think that it is the good start for me to master a medium level algorithm called Valid Triangle Number on Leetcode.com. Usually it takes 10 practices to master one hard level algorithm on Leetcode.com. For the medium level, I also like to practice over 6 times. 

This is the third time I worked on the algorithm last 6 months. I did have one mock interview discussion back in Oct. 2017, and then one mock interview in February 2018. 

Code review

The time complexity analysis is so critical in algorithm problem solving. This algorithm can be solved using two pointer techniques and the time complexity can be lowered from brute force solution O(n³) to O(n²). 

Also as an interviewer, I also learn quickly to identify the solution written actually ending using time complexity O(2ⁿ). 

I like to encourage myself and also the interviewee try the best, and heed the lesson of failures in the mock interviews. 

Here is the code I reviewed. The code works, but the time complexity is worse than brute force solution with O(2ⁿ).

Leetcode 611: Valid Triangle Number

Nov. 4, 2017

Introduction

It is the medium level algorithm. The algorithm is very challenging to lower the time complexity from O(n³) to O(n²) using two pointer techniques or binary search. The peer gave me the hint to lower the time complexity, and then I started to think about binary search with time complexity O(n²logn), and then the peer gave me hint to continue to optimize the time complexity.

Plan to write C# code and also read discussions for the algorithm in short future.