The original question can be found here. It’s asking us to find an element that is grater than both left and right neighbors. Since it’s asking for a O(logn) solution, let’s directly jump to the binary search solution. There’re 4…
The original question can be found here. The question is asking us to find a target element in rotated sorted array. Since the question is explictly asking for a O(logn) solution, so let’s jump to the binary search solution. After…
The original question can be found here. The question is asking us to find the minimum element in a rotated sorted array. After analysing, we can observe the following: The array can be divided into 2 parts. The left part…
The original question can be found here. The question is asking us to return a peak element, which means, an element is greater than both 2 adjacent neighbors. Brute Force Scan the array: Time complexity: O(n). Space complexity: O(1). Binary…
The original question can be found here. The question is asking to return the k closet elements to target x. The array is sorted. Heap First solution is using a heap to keep track the current closest elements to x.…
The original question can be found here. The question is asking us to return the index of a target element, however, the size of the array is unknown. The only difference of this question from the traditional binary search question…
The original question can be found here. The question is asking to return a tuple with first and last position of target element in a sorted array. Brute Force Iterate through the whole array and keep track of first and…
The original question can be found here. The question is asking us to perform a binary search on an sorted array, which is a classical algorithm. If you haven’t, please visit my another post which detailed describe this algorithm. Time…
Introduction Java Optional is a container class that encapsulates an optional value, which was introduced by Java 8. However, I still see lots of colleagues not leveraging it in their work. Maybe it’s too hard to use? Or maybe we…
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…
The original question can be found here. The question is asking to return the Nth fibonacci number. F(0) = 0, F(1) = 1 and F(n) = F(n – 1) + F(n – 2). The easist solution is using recursion. If…
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…
The original question can be found here. It’s asking us to provide O(nlogn)solutions. Quick Sort The algorithm can be found here in my another post. Merge Sort The algorithm can be found here in my another post.
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…
This is probably our very first coding preparation question. The original question can found here. This question is asking us to return the indices of 2 elements such that their sum equals to the target number. Brute Force The brute…
The original question can be found here. The question is asking if a string is palindromic if at most 1 character can be removed from string. Let’s look at an example: Let’s say we still use the 2 pointers apporach…
The original question can be found here. The question is asking for a given string, determine if it’s palindromic. Only alphanumeric letters are taking into account and letters’ cases are ignored. Reverse and Compare The first solution we can think…
The original question can be found here. There’re multiple solutions to this question, and we’ll start with the brute force one. Brute Force We enumerate all substrings and check if it’s palindromic. If yes, we update the final result by…
Here are some interview skills and coding styles that on top of my head. Interview Skills Try to avoid “I know a fancy algorithm called xyz…” Try to avoid using uncommon existing algorithms used for very specific cases, such as…
The original question can be found here. The question is asking to return the median number of 2 sorted arrays. Let’s say array nums1‘s length is m and nums2‘s length is n. If the sum of m and n is…
The original question can be found here. The question is aksing for the intersection of two arrays, and element in final result should be unique. There’re multiple solutions for this question. Hash Set Load one array into a hashset, and…
The original question can be found here. It’s asking us to merge array nums2 into array nums1. The most straightforward solution is: for each element inside array nums2, we insert into nums1 to find an appropriate position. Once we find…
The orignal question can be found here. The question is asking the number of subarrays which the sum value equals to K. The brute force solution is very straight forward. We simply enumerate all the possible subarrays to find out…
The original question can be found here. The question is aksing for the largest sum of the subarray. We can enumerate all possible subarrays and return the lagest sum. The time complexity is O(n^2)which is not quite acceptable. To find…
The original question can be found here. The question is asking to find the maximum number inside each sliding window(subarray). Brute Force Go through each subarray and find the maximum value. The time complexity is O(n*k), where n is the…
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].…
The original question can be found here. This question is quite tricky. I will say best of luck to you if this is the first time you see this question during a real interview. I’ll skip the brute force solution…