It's never too late to learn to be a master
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
Analysis
It’s easy to first sort the array, then pick up the Kth largest element. The time complexity is O(nlogn) if we use quick sort.
Min Heap Based Method
A better method is use a min heap or PriorityQueue with size K.
[Read More...]There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
|
1 2 3 4 5 |
nums1 = [1, 3] nums2 = [2] The median is 2.0 |
Example 2:
|
1 2 3 4 |
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 |
Analysis
It is easy to come up with a O(n) solution. Then it is high likely that the interviewer will ask you to give the algorithm with time complexity O(logn).
For any problem with sorted array, to come up with a O(logN) solution, we should consider the binary search related algorithm.
[Read More...][LeetCode] Evaluate Reverse Polish Notation (RPN)
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
|
1 2 |
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6 |
Analysis
Evaluate RPN is the second step to build a calculator. Once we have converted the infix expression into the RPN, we need to evaluate RPN to get the result.
The basic idea to evaluate reverse polish notation is to use a stack to process the strings.
We scan the array of the RPN expression.
[Read More...]Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space. For example, Given s = "the sky is blue", return "blue is sky the". Could you do it in-place without allocating extra space?
Analysis
This problem is similar to the rotate array to right by k steps problem.
There are two steps:
We use simple examples and diagrams to describe the concept of observer pattern. We also give a simple implementation of the observer pattern in Java.
What is Observer Pattern
The observer pattern defines a one-to-many relationship between two kinds of objects. The one side is called Subject, which maintains a list of Objects (called observers), and automatically notify each of the observers if something interesting happens.
The definition of the Observer pattern provided in the GoF book, Design Patterns: Elements of Reusable Object-Oriented Software, is:
“One or more observers are interested in the state of a subject and register their interest with the subject by attaching themselves.
[Read More...]Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
|
1 2 3 4 5 6 7 |
A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 |
Related to this question Excel Sheet Column Title
This is a normal number system conversion problem. Think about how we convert a binary number to a decimal number?
1101001 = 1* 2 ^6 + 1 * 2^5 ..
We can easily have the following implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class ExcelColumnToNumber { int convert(String str) { char[] chs = str.toCharArray(); int j = 0; int res = 0; while( j < chs.length ) { res = res * 26 + (chs[j] - 'A' + 1); j++; } return res; } public static void main(String[] args) { System.out.println(new ExcelColumnToNumber().convert("AA")); System.out.println(new ExcelColumnToNumber().convert("BA")); System.out.println(new ExcelColumnToNumber().convert("BZ")); } } |
[Read More...]
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given heights = [2,1,5,6,2,3],
return 10.
Analysis
A simple solution is to expand for each bar to its both left and right side until the bar is lower.
[Read More...]
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Analysis
The popular method to implement an LRU cache is to use a bounded Queue.
The key to for implementing an LRU is to put any recently used data at the head of the queue.
[Read More...]This tutorial gives a quick introduction to the Scala language by comparing Scala with Java using examples. It is for people who have learned Java and want to learn Scala.
Scala vs Java: The Hello Word Example
A hello word example for Scala:
|
1 2 3 4 5 |
object HelloWorld { def main(args: Array[String]) { println("Hello, world!") } } |
A hello world example for Java:
|
1 2 3 4 5 6 7 8 |
public class HelloWorld { public static void main(String[] args) { // Prints "Hello, World" to the terminal window. System.out.println("Hello, World"); } } |
object Keyword in Scala
In scala, the object keyword is used to create a singleton object. The declaration above declares both a class called HelloWorld and an instance of that class, also called HelloWorld.
One difference between Scala and Java is that,
[Read More...]Given an array, there is a popular problem to search the minimum value in a range [a, b]. This is called Range Minimum Query. This post describes a method to solve the range minimum query problem using Segment Tree.
The basic idea of a Segment tree is as follows:
Given an array A with size n: the index of the array looks like this [0, 1, 2, …., n-1],
Rss Feeds