Outstanding developers pay a lot of attention to time and space consumption and have the passion
needed to continue improving performance of their own code. When there are multiple solutions for a
problem, interviewers always expect the best one. If interviewers point out that there are better
solutions, candidates should try their best to find approaches to improving time and space performance,
demonstrating his or her enthusiasm to pursue excellence, which is an essential spirit to have as an
outstanding developer.
www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community
The first thing candidates should understand is how to analyze time and space efficiencies. Various
implementations of the same algorithm may result in dramatic performance distinctions, so it is
important to analyze performance of an algorithm and its implementation. Take the calculation of the
Fibonacci Sequence as an example. The classical solution is based on the recursive equation f(n) = f(n-1)
+ f(n-2). It is not difficult to find out the time complexity increases exponentially since there are lots of
duplicated calculations. However, the complexity will reduce to O(n) if it is calculated iteratively. First of
all, f(1) and f(2) are calculated, and then f(3) is based on f(1) and f(2); f(4) is get based on f(2) and f(3). The
sequence continues until f(n) is calculated in a loop. Please refer to the section Fibonacci Sequence for
more details.
Candidates have to master pros and cons of each data structure and be able to choose the most suitable one to improve performance. For example, it seems that multiple types of data structures are available to get the median of a stream, including arrays, lists, balanced binary trees, and heaps. After analyzing the characteristics of each data type, we find that the best choice is to utilize two heaps—a maximal heap and a minimal heap (section Median in Stream).
Candidates should also be proficient in common algorithms. The most popular algorithms in interviews are about search and sort. It costs O(n) time to scan an array sequentially. However, it is reduced to O(logn) with the binary search algorithm if an array is sorted. The problem “Maximal Number in a Unimodal Array” and “Times of Occurrences in a Sorted Array”are both solved based on the binary search algorithm. The quicksort algorithm is widely used for other problems besides sorting. The Partition function in quicksort can be used to get the kth maximal number out of n numbers and solve the problem “Majority in an Array”and “Minimal k Numbers”.
Candidates have to master pros and cons of each data structure and be able to choose the most suitable one to improve performance. For example, it seems that multiple types of data structures are available to get the median of a stream, including arrays, lists, balanced binary trees, and heaps. After analyzing the characteristics of each data type, we find that the best choice is to utilize two heaps—a maximal heap and a minimal heap (section Median in Stream).
Candidates should also be proficient in common algorithms. The most popular algorithms in interviews are about search and sort. It costs O(n) time to scan an array sequentially. However, it is reduced to O(logn) with the binary search algorithm if an array is sorted. The problem “Maximal Number in a Unimodal Array” and “Times of Occurrences in a Sorted Array”are both solved based on the binary search algorithm. The quicksort algorithm is widely used for other problems besides sorting. The Partition function in quicksort can be used to get the kth maximal number out of n numbers and solve the problem “Majority in an Array”and “Minimal k Numbers”.
No comments:
Post a Comment