Introduction Sometimes we need to infer algorithms by time complexity. After we bring out the brute force solution, the interviewer may ask: Can you solve by time complexity of O(xxx)? We don’t always know what’s the optimal solution, but we…
Introduction Binary search is a very popular algorithm for finding a target element in a sorted array. Algorithm Here’s a standard way for implementing this algorithm: Time complexity: O(logn). Space complexity: O(1). However, this implementation will be problematic if we…
Introduction Recursion is a common topic during coding interview. This post talks about how to succesfully write a correct recursion solution for a coding exercise. Method signature Method signature we care in a recursion method is defined by all the…
Introduction Quick select is an algorithm used to quickly locate the Kth largest/smallest element in an array. Technically speaking, it’s part of quick sort algorithm. Algorithm Let’s say we want to find the Kth largest element in an array. Every…
Introduction Both merge sort and quick sort are popular sorting algorithms. They both use recursion and leverage devide and conquer principles. But what are their differences? Time Complexity Merge sort has time complexity as O(nlogn), where n is the size…
Introduction Merge sort is another popular algorithm, with time complexity as O(nlogn). It’s leveraging the principle of divide and conquer, and this is definitely the algorithm we should master. Algorithm We recursively split the array into 2 parts, sort them…
Introduction Quick sort is one of the most popular algorithms for sorting. It’s not uncommon to see this algorithm or other algorithms(e.g. partition) leveraging the principle of quick sort during interview. Algorithm The idea behind quick sort is divide and…
Prefix sum is a very useful technique which can be used for some subarray questions. Let’s look at how it works. PrefixSum[i] stands for the sum of first i elements, which means the sum from array[0] to array[i – 1].…