Data Structures | Learn for Master - Part 3
  • Interview Questions: Edit distance

    Edit distance related questions are frequently asked by many large companies such as Google, Facebook, Apple, Microsoft, Uber, Airbnb, Amazon, et al. In this post, we describe three kinds of problems related to edit distance.

    What is edit distance?

    Edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. Edit distances can be applied in natural language processing for automatic spell correction by selecting words from a dictionary that have a low distance to the word in question. 

    [Read More...]
  • LeetCode – Binary Search Tree Iterator (Java)

    Binary Search Tree Iterator

    • Difficulty: Medium

    Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

    Calling next() will return the next smallest number in the BST.

    Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

    Source: https://leetcode.com/problems/binary-search-tree-iterator/

    In this post, we describe a stack based method to solve the Binary Search Tree Iterator problem in Java. This solution similar to the stack based in oder traversal of a binary search tree. 

    [Read More...]
  • Leetcode – Best Time to Buy and Sell Stock (Java)

    Say you have an array for which the ith element is the price of a given stock on day i.

    If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

    Example 1:

    Example 2:

     
    Analysis:
     
    We scan the table, and record the minimum price in the range [0, i – 1], so the potential max profit is prices[i] – min(prices[0, i-1])
    The following is the implementation in Java:
     

     

    [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...]
  • Leetcode – Graph valid tree solution based on Union find set

    Graph Valid Tree
    Given n nodes labeled from 0 to n – 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

    For example:

    Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

    Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

    Hint:

    Given n = 5 and edges = [[0, 1], [1, 2],

    [Read More...]
  • Shortest Path Problems

    Given a weighted graph G Given a weighted graph G (V,E), =(V,E), and a source vertex s, find the minimum weighted path from s to every other vertex in G

    Unweighted graph

    If the graph is unweighted, we can solve this problem using Bread First Search.

    Weighted Graph

    For Weighted Graph, we solve this problem use Dijkstra’s algorithm.

    shortest path between all pairs of vertices

    Given G(V,E), find a shortest path between all pairs of vertices.

    Solutions: (brute -force) Solve Single Source Shortest Path for each vertex as source.  

    [Read More...]
  • Learn Python List by Examples

    Python List is a powerful data structure that you almost need it in every program. Python List can be used to hold a collection of items which can  be any type. In this post, I will use examples to describe how to use python List. 

    Python List Declaration

    It is easy to create a python list object. The following code declare a List L and initialize it with 4 values.

    In [1]:

    L = [1, 2, 'Jim', ('hello, word')]
    print L
    

     

    [1, 2, 'Jim', 'hello, word']
    

     

    Data look up in python List

    We can locate the elements in the List by index.

    [Read More...]
  • Python Dictionary Example

    Python dict structure is similiar to Java’s HashMap or HashTable.
    It aims to store key value pairs.

    Here is an example:
    we build a dict to map a username to his profile information, which is a tuple

    username => (Full_name, gender, age)

    Search in Dict

    Now we can do a look up by username with O(1) time complexity.
    Search the user with username equal to ‘jim’

    Key not exist exception

    you may get key not exist exception when the username is not in the table

    Do key check

    We can get around this issue by an exist check

    Use get with a default value

    A better method is to use the get() method with default value.

    [Read More...]
Page 3 of 3123