Data Structures | Learn for Master - Part 2
  • Count word frequency

    Count word frequency is a popular task for text analysis. In this post, I describe how to count word frequency using Java HashMap, python dictionary, and Spark. 

    Use Java HashMap to Count Word frequency

    {a=5, b=2, c=6, d=3}

    Use Python Dict to count word frequency

    The output:

    {‘a’: 5, ‘c’: 6, ‘b’: 2, ‘d’: 3}

    Use Spark to count word Frequency

    The above method works well for small dataset. However, if you have a huge dataset, the hashTable based method will not work. You will need to develop a distributed program to accomplish this task.

    [Read More...]
  • Remove Element from an Array (Java)

    LeetCode – Remove Element

    Given an array and a value, remove all instances of that value in place and return the new length.

    Do not allocate extra space for another array, you must do this in place with constant memory.

    The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

    Example:
    Given input array nums = [3,2,2,3], val = 3

    Your function should return length = 2, with the first two elements of nums being 2.

    Analysis

    This problem is similar to another leetcode problem: Remove Duplicates from Sorted Array

    [Read More...]
  • Remove Duplicates from Sorted Array (Java)

    Leetcode: Remove Duplicates from Sorted Array

    Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

    Do not allocate extra space for another array, you must do this in place with constant memory.

    For example,
    Given input array nums = [1,1,2],

    Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

     Analysis
     

    We defined two indexes: pre and cur.

    [Read More...]
  • Leetcode – Remove Nth Node From End of List (Java)

    Remove Nth Node From End of List

    Given a linked list, remove the nth node from the end of list and return its head.

    For example,

       Given linked list: 1->2->3->4->5, and n = 2.
    
       After removing the second node from the end, the linked list becomes 1->2->3->5.
    

    Note:
    Given n will always be valid.
    Try to do this in one pass.

    Analysis:

    The key to solve this problem is to use two pointers: pre and cur. The pre pointer moves N steps in the first place,

    [Read More...]
  • System design interview- consistent hash

    consistent hash virtual node

    Consistent hashing is a simple yet powerful solution to a popular problem: how to locate a server in a distributed environment to store or get a value identified by a key, while handle server failures and network change?

    A simple method is number the servers from 0 to N – 1. To store or retrieve a value V, we can use Hash(V) % N to get the id of the server. 

    However, this method does not work well when 1) some servers failed in the network (e.g, N changes) or 2)  new machines are added to the server.

    [Read More...]
  • 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...]
  • Convert infix notation to reverse polish notation (Java)

    How to implement a calculator is a popular interview question. To answer this question well, you need to maser Stack data structures, convert an infix notation to RPN and evaluate reverse polish notation. 

    Since the input is usually in infix notation, e.g. “3 + 6 * 2”, it is difficult develop a program to evaluate it directly.

    In practice, we can implement a calculator algorithm into two steps:

    1. the first step is to convert your mathematical expressions, which is called infix notation, into Reverse Polish Notation (RPN),
    [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...]
  • Leetcode- Rotate Array to right by K steps (java)

    Rotate an array of n elements to the right by k steps.

    For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

    How many different ways do you know to solve this problem?

    Analysis

    It is easy to use an intermediate array to solve this problem. Suppose the original array is A, the new array is B, we will copy 

    A[0:n-k -1] to B[k:n-1], and A[n – k:n-1] to B[0:k – 1], then we copy all the elements in B back to Array A using System.arrayCopy.

    [Read More...]
Page 2 of 3123