2018年6月21日 星期四

[ProjectEuler] Problem 621: Expressing an integer as the sum of triangular numbers

Statement:
  • Gauss famously proved that every positive integer can be expressed as the sum of three triangular numbers (including 0 as the lowest triangular number). In fact most numbers can be expressed as a sum of three triangular numbers in several ways.
  • Let G(n) be the number of ways of expressing n as the sum of three triangular numbers, regarding different arrangements of the terms of the sum as distinct.
  • For example, G(9)=7, as 9 can be expressed as: 3+3+3, 0+3+6, 0+6+3, 3+0+6, 3+6+0, 6+0+3, 6+3+0.
  • You are given G(1000)=78 and G(10^6)=2106.
  • Find G(17526 × 10^9).


Proof of Integer is Sum of Three Triangular Numbers:

2018年6月15日 星期五

Google Phone Interview


Before:
  • Fail on Amazon Phone Interview.
    • Lesson learn: should practice leetcode.
  • Recruiter prescreen passed.
  • Recruiter said you might practice leetcode.

Data structure & algorithm (rusty):

System design:
After:
  • Reject.
  • Feedback:
    • Good at problem understanding 
    • Good at algorithm
    • Bad at coding
    • Wait for next 6 months
  • Lesson learn:
    • More practice on coding
    • No system design problem in the phone interview. Only algorithm and actual coding in google doc.

    2018年6月9日 星期六

    [Data Structure] Sliding Window

    Problems:


    239. Sliding Window Maximum:
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || k == 0) {
                return new int[0];
            }
            int[] maxSlidingWindow = new int[nums.length - k + 1];
            int maxSlidingWindowPos = 0;
            Deque<Integer> potential = new ArrayDeque<>();
            for (int i = 0; i < nums.length; i++) {
                while (!potential.isEmpty() && potential.peekFirst() < i - k + 1) {
                    potential.pollFirst();
                }
                
                while (!potential.isEmpty() && nums[potential.peekLast()] < nums[i]) {
                    potential.pollLast();
                }
                
                potential.offer(i);
                
                if (i - k + 1 >= 0) {
                    maxSlidingWindow[maxSlidingWindowPos++] = nums[potential.peekFirst()];
                }
            }
            return maxSlidingWindow;
        }
    }
    

    [Algorithm][Graph] Topological sort

    Topological-Sort(G)
    1. call DFS(G) to compute finishing times v.f for each vertex v
    2. as each vertex is finished, insert in onto the front of a linked list
    3. return the linked list of vertices

    Problem:

    2018年6月8日 星期五

    [Data Structure] LRU Cache

    Video: https://www.youtube.com/watch?v=q1Njd3NWvlY

    Java: HashMap + doubly linked list (custom).

    [Algorithm][Geometry] Sweep line algorithm

    Problems:



    Articles: https://leetcode.com/articles/rectangle-area-ii/
    • Moving the sweep line
    • Sweeping algorithms typically manage two sets of data:
      • The sweep-line status gives the relationships among the objects intersected by the sweep line.
      • The event-point schedule is a sequence of x-coordinates, ordered from left to right, that defines the halting positions of the sweep line. We call each such halting position an event point. Changes to the sweep-line status occur only at event points.
    • The sweep-line status is a total preorder T:
      • INSERT(T, s): insert segment s into T.
      • DELETE(T, s): delete segment s from T.
      • ABOVE(T, s): return the segment immediately above segment s in T.
      • BELOW(T, s): return the segment immediately below segment s in T.
    Any-segments-intersect algorithm:
    ANY-SEGMENTS-INTERSECT(S)
    1. T -> {}
    2. sort the endpoints of the segments in S from left to right, breaking ties by putting points with lower y-coordinates first 
    3. for each point p in the sorted list of endpoints
    4.     if p is the left endpoint of a segment s
    5.     then INSERT(T, s)
    6.     if (ABOVE(T, s) exists and intersects s) or (BELOW(T, s) exists and intersects s)
    7.         then return TRUE
    8.     if p is the right endpoint of a segment s
    9.         if both ABOVE(T, s) and BELOW(T, s) exist and ABOVE(T, s) intersects BELOW(T, s)
    10.             return TRUE
    11.         DELETE(T, s)
    12. return FALSE



    Java: