Java | Learn for Master - Part 3
  • LeetCode – Find the kth largest element in an unsorted array (Java)

    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...]
  • LeetCode – Median of Two Sorted Arrays Java Solution

    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:

    Example 2:

    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 (Java)

    [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:

    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...]
  • Leetcode – Reverse Words in a String II (Java)

    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:

    1. use the space ‘ ‘ to determine the boundary of words.
    [Read More...]
  • Design Pattern: Observer Pattern in Java

    observer pattern

    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...]
  • Leetcode – Excel Sheet Column Number (Java)

    Given a column title as appear in an Excel sheet, return its corresponding column number.

    For example:

    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:

     

    [Read More...]
  • Leetcode – Largest Rectangle in Histogram Java

    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...]
  • Leetcode – LRU cache solution in Java

    LRU cache figure

    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...]
  • Scala vs Java examples

    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:

    A hello world example for Java:

    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...]
  • Range Minimum Query – Segment Tree (Java)

    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], 

    1. The root of the Tree contains the minimum value of the whole array, or the minimum value in the range [0, n – 1]. 
    [Read More...]
Page 3 of 41234