Menu
Yesterday I have attended for an interview. He gave me few programming questions to solve. When I solved them, the interviewer said it can be done in better Time complexity. I was so much depressed that I cannot do the program in the best time complexity. Finally I am not able to get through the interview process. But what I want to know is how can we do in best time for any problem? What should be my approach to reach that state? I know the perfect answer is practice. But still I want to know how and what ways to do a program such that it runs in less time and use best memory. What books I have to read? What problems I have to practice?
P.S: I know this is not a technical question. But please let me know how can I do that.
526
To reduce time complexity you need to optimize your algorithm. It will most often come as a result of using proper data structure or algorithm. So you will need to learn data structures and algorithms for being able to perform well.
While writing any industry level algorithm/code or even in competitive programming one must keep in mind the complexity of it. In order to make anything scalable we must need to optimize our code for large data as much as possible. Scalability & optimization are directly related.
If you've observed, the time complexity of Quicksort is O(n logn) in the best and average case scenarios and O(n^2) in the worst case. But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
Time complexity is profoundly related to the input size. As the size of the input increases, the run time (which is — time taken by the algorithm to run) also increases.
One of the best books about algorithms, data structures, time and space complexity is Introduction to Algorithms. I can also recommend you to read following books for good preparation for an interview:
101
Solving this sort of problem involves practice, plus "seeing the trick". For this specific example you might notice that B[i] = P/A[i], where P is the product of all the A[i] elements multiplied together. So in this case the O(n) performance comes from first calculating P once (n-1 multiplications), followed by calculating each B[i] (another n divisions).
Sometimes, the best way of 'seeing thew trick' is to look for repeated patterns in the algorithm you use. For your example, note that in your description you actually typed the string "A[2] * A[3] ... A[n-1]" twice, so this is the sort of place to think "can I do this thing only once in the algorithm".
20
Read lots of algorithms and practice them.
Solving problems from online judges is also helpful for increasing efficiency and accuracy of problem solving skill.
List of some judges are given below:
45
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
