‘Super Egg Drop’ is a very classic DP problem. Good articles explaining the O(KN*N) and the O(KN*logN) solutions can be easily found from the internet. Better than that, there is a solution of O(KN). However, there isn’t much about the O(KN) solution and the rare posts about it aren’t very clear. The article you are reading now is an endeavor to fill this gap.

Check Out The Problem

You are given K eggs, and you have access to a building with N floors from 1 to N

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F

Example:

Input: K = 1, N = 2
Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1.
If it didn’t break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.

Analysis

Firstly Let’s define dp(i,j) as the maximum number of floors we can surely find F from with i moves and j eggs. With this definition, the original question can be transformed into finding the minimum m whose dp(m,K) is larger than or equal to N.

Secondly, it can be easily observed that the maximum number of floors we can find F from is equal to the number of moves we can take if there is only 1 egg. In a formula, dp(i,1)=i.

Assuming that to get dp(m,K), the first floor where we drop the egg is dp(m-1, K-1)+1 floor (We will explain why choose this floor later). With this assumption in mind, there will be two different cases to analyse:

• The first egg breaks

  From the breaking of the first egg, we know that the elusive F must be within first dp(m-1,K-1) floors. And with the poor broken first egg lost and the first move taken, we now can move m-1 times with K-1 eggs which is just enough for us to find F from the first dp(m-1,K-1) floors. At this moment, we can confidently say we could always find target F no matter how large the number N is.

• The first egg remains intact

  Since the egg won’t break from dp(m-1,K-1)+1 floor we can conclude that F is not within the first dp(m-1,K-1) floors. With the initial move taken and the egg stay un-broken, we now have m-1 moves to make with K eggs. That is to say, we can check another at mostdp(m-1,K) floors above the first dp(m-1,K-1)+1 floors. At this case, the maximum number of floors we can find from is dp(m-1,K-1)+1+dp(m-1,K).

The proplem states we have to find the answer that we can be 100 percent confident about. In another word, we have to take the worst case into consideration ,i.e. the case of un-broken first egg. After all these analyses, we get the state transforming formula: dp(m,K)=dp(m-1,K-1)+1+dp(m-1,K).

Finally, let’s write the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution(object):
    def superEggDrop(self, K, N):
        m = 1
        dp = [1]*(K+1)
        while dp[K] < N:
            m += 1
            tmp = [m]*(K+1)
            for k in range(2, K+1):
                tmp[k] = dp[k-1]+dp[k]+1
                if tmp[k] >= N:
                    tmp[K] = tmp[k]
                    break
            dp = tmp
        return m

Why Drop The Egg From the dp(m-1,K-1)+1 Floor At The First Place?

To answer this question, we will have two scenarios to analyse:

• Drop the first egg from floor higher than dp(m-1, K-1)+1

  Let’s say the first egg is dropped from dp(m-1,K-1)+2 floor and it breaks. Then we will have to find F from dp(m-1,K-1)+1 floors. Unfortunately, the remaining m-1 moves and K-1 eggs only allow us to find F from dp(m-1, K-1) floors. At the this case, we will fail.

• Drop the first egg from floor lower than dp(m-1,K-1)+1

  Assuming we drop the first egg at floor dp(m-1,K-1) and it doesn’t break. Then the final maximum number of floors we will reach is dp(m-1,K-1)-1+1+dp(m-1,K)=dp(m-1,K-1)+dp(m-1,K) which is smaller than the number dp(m-1,K-1)+1+dp(m-1,K) we can get from the dp(m-1,K-1)+1 floor.

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example:

Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Let’s try to solve this problem by dividing it into smaller quizzes:

For example, to caculate the result for 2954:

• count(2954)=count(2000)+count(954)
• count(954)=count(900)+count(54)
• count(54)=count(50)+count(4)

Now we got the conclusion that count(2954)=count(2000)+count(900)+count(50)+count(4), which is leading us to the question of how to get count(i*10^j)

To calculate count(i*10^j), we separate the ‘1’s we are looking for into two groups:

• 1s appearing in the highest digit, like the first ‘1’ in the number 1111.
  • For numbers starting with 1, this part is the lower part number plus one. Let’s take 1599 as an example. From 1000 to 1599 we got 599+1=600 ‘1’s at the highest digit.
  • For numbers not starting with 1, this part is always 10^math.floor(log10(number)). Like for 2000, from 1000 to 1999 we got 1000 ‘1’ which is equal to 10^3.
• 1s appearing in the lower digits, like the last 3 ‘1’s in the number 1111.
  The formula to calulate this part is: (highest digit) * count(10^math.floor(log10(number)-1)). Like for 3000, the result is 3*count(999)

At this point, the last puzzle we need to solve is to find a way to calculate count(10^n-1). Let’s take a look at some examples:

• For number ranging from 1-99 we got 1 one.
• For number ranging from 1-999 we got 20 ones.
• For number ranging from 1-9999 we got 300 ones.

After some observations, we can see count(10^n-1)=count(10^(n-1)-1)*10+10^(n-1). Combining this with an initial case of count(9)=1, we can extrapolate that count(10^n-1)=n*10^(n-1).

With all these deductions in mind, we can finally solve the original problem with DP.
I implemente this idea with the help of stack to avoid recursion and below is the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

from math import log10

class Solution(object):
    def countDigitOne(self, n):
        if n <= 0:
            return 0
        ord_0, res, t = ord('0'), 0, [
            (i+1)*10**i for i in xrange(0, int(log10(n)))]
        while n:
            te, tem = list(str(n)), int(log10(n))-1
            tmp, te[0] = ord(te[0])-ord_0, '0'
            n = int(''.join(te))
            if tem >= 0:
                res += tmp*t[tem]
                res += n+1 if tmp == 1 else 10**(tem+1)
            else:
                res += 1
        return res

Definitions

• Technical insights

  A technical insight is a new way of applying technology or design that either drives down the cost or increases the functions and usability of the product by a significant factor.

• What is a good product

  The best products are still the ones that are based on technical insights, those unique ideas that apply one or more technologies in a new way to solve big problems.

• A Successful Product Is The One Fails To Fail

• Elevator Pitch

  Elevator pitch” is venture capital–speak for “you have thirty seconds to impress me with your business idea.”

  Elevator pitch should explain what you are working on, the technical insight that’s driving it, how you are measuring your success (particularly customer benefit), and perhaps how it fits into the big picture.

• The 70/20/10 Rule

  70 percent of resources dedicated to the core business, 20 percent on emerging, and 10 percent on new.

• Jobs attractive to the Smart Creatives

  Flying an F-16 at Mach 2 over a boulder-strewn landscape, two meters off the ground. Plus, if you crash it’s just like a video game at the arcade, and we have lots of quarters.”

• Hippo(the Highest-Paid Person’s Opinion)

Suggestions From Google

• Process Is A Friend To Small Companies But An Enemy To Big Ones

  Process is a great thing. It is the art and science of taking something that needs to be done and reducing it to a documented set of steps, often supported by information tools and systems. With process comes scale; you absolutely need process to grow a company profitably.

  At some point, though, process starts to take over. It becomes so entrenched that it can trump common sense and cause executives to, as our head of business operations, Kristen Gil, says, “lose muscle memory.” People stop thinking and instead just depend on the process to make decisions for them.

  The antidote to these issues is to break your own processes. This usually requires “air cover” from a senior leader in the company, someone who says it’s OK not to follow the rules and has the power and authority to fend off the antibodies who will attack the rule-breaker.

• BU(Business Unit) is not a good thing

  We believe in staying functionally organized—with separate departments such as engineering, products, finance, and sales reporting directly to the CEO—as long as possible, because organizing around business divisions or product lines can lead to the formation of silos, which usually stifle the free flow of information and people. Having separate P&Ls seems like a good way to measure performance, but it can have the unfortunate side effect of skewing behavior:
  The leaders of a business unit are motivated to prioritize their unit’s P&L over the company’s.

• Googles’ overall strategy

  Bet on technical insights that help solve a big problem in a novel way, optimize for scale, not for revenue, and let great products grow the market for everyone.

• Hire no incorrect people rather than hiring more correct people

  This is why we would rather our hiring process generate more false negatives (people we should have hired but didn’t) than false positives (we shouldn’t have hired, but did).

• Checklist for Meeting Organizers

  • Every Meeting need a owner
  • Every meeting should have a clear purpose
  • Meeting need a clear time-box
  • Owners’ responsibilities before the metting are to schedue the time and let all attendances know in advance. After the meeting the owner is expected to sumaarize the decisions or conclusions reached at the metting.
• How to End an Argument:
  • Say that You are both right
  • Then, after reassuring the argument’s losers and articulating what needs to be done, the decision-maker must ensure that every loser does one of two things: disagree but commit, or escalate publicly.

Mottos

• Never stop learning

  Henry Ford said that “anyone who stops learning is old, whether at twenty or eighty. Anyone who keeps learning stays young. The greatest thing in life is to keep your mind young.”

• Incrementalism Leads To Irrelevance

  It’s also true that many companies get comfortable doing what they have always done, with a few incremental changes. This kind of incrementalism leads to irrelevance over time, especially in technology, because change tends to be revolutionary not evolutionary.

• Googlers also work on the weekend like when doing 20 percent project

The Checklist Manifesto is a book from Atul Gawande. I learned the following three points from this book.

All Tasks Can Be Divided into 3 Groups

• simple ones:

  Simple problems are ones like baking a cake from a mix. There is a recipe. Sometimes there are a few basic techniques to learn. But once these are mastered, following the recipe brings a high likelihood of success.

• complicated ones:

  Ones like launcing a rocket. They can sometimes be broken down into a series of simple problems. Once you learn how to send a rocket to the moon, you can repeat the process with other rockets and perfect it.

• complex problems:

  Like raising a child. Although raising one child may provide experience, it does not guarantee success with the next child. Expertise is valuable but most certainly not sufficient. Indeed, the next child may require an entirely different approach from the previous one.

How to Categorize Checklists

• With a DO-CONFIRM checklist: we perform our jobs from memory and experience, often separately. But then we stop. We pause to run the checklist and confirm that everything that was supposed to be done was done.
• With a READ-DO checklist, on the other hand, we carry out the tasks as we check them off it is more like a recipe.

What Makes a Good Checklists

• Five to nine items at most for a single check list.
• The wording should be simple and exact

Personally I have been using spaced repetition algorithm in my study for many years. There are many different kinds of this algorithm and the one I have used is invented by BlueRaja called SM2+. Based on this algorithm I have written a lib called sm2-plus and I liked it a lot. However, SM2+ has its own problem.

In this post I will show you what problems SM2+ algorithm has and provide a new algorithm named Memory Scheduler that I find quite helpful in my learning.

Problem of SM2+

• It’s a little bit complex.
• It’s not compatible with the forgetting curve theory.

Memory Scheduler Algorithm

To learn with this algorithm, two arguments have to be fed to it:

• intervals([int]): intervals between each study session.
• scroreToProgressChange([int]): how to update the progress based on the score the user gives when reviewing items

For one item we want to learn, store two data:

• dueDate(int): the next day scheduled to review this item.
• progress(int): How many times continuously the user has correctly answered this item.

To reivew an item, the user is asked to chose a score based on how confident he is with the item(the larger, the more confident).

The answer is deemed as correct only when the score is equal to the length of scroreToProgressChange, and in this circumstance the nextDute is intervals[progress] days after today.

Otherwise, the answer is deemed as incorrect and the next review is scheduled at tomorrow.

In both cases, progress should be updated in this way: progress+=scroreToProgressChange[score].

Following is a javascript implementation of this algorithm and I have also published it to npm as memory-scheduler. If you are not satisfied with the this implementation, send me a PR at this repo.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

export default class MS {
  constructor(
    intervals = [1, 2, 3, 8, 17],
    scroreToProgressChange = [-3, -1, 1]
  ) {
    this.intervals = intervals;
    this.scroreToProgressChange = scroreToProgressChange;
  }

  get maxProgress() {
    return this.intervals.length;
  }
  get correctScore() {
    return this.scroreToProgressChange.length - 1;
  }
  calculate(s, { progress }, now) {
    const correct = s === this.scroreToProgressChange.length - 1;
    const newProgress = progress + this.scroreToProgressChange[s];
    let dueDate = now + 1;
    if (correct && progress < this.maxProgress) {
      dueDate = now + this.intervals[progress];
    }
    return {
      dueDate,
      progress: newProgress < 0 ? 0 : newProgress
    };
  }
  getInitialRecord(now) {
    return {
      progress: 0,
      dueDate: now
    };
  }
}

That’s all I want to say about Memory Scheduler algorithm. As you can see, it’s pretty simple to use. I believe with this algorithm, we can learn better in a faster pace.

Every body knows that writing unit test is very important during programming.
However, it is not an easy job, especially when it comes to asynchronous code.

Initially, callback has to be used to test asynchronous code:

1
2
3
4
5
6
7
8
9
10
11

describe('User Profile', function(){
  it('can get user profile', function(done){
    getProfile('bulkan', function(err, result){
      if(err) {
        done(err)
      }
      assert.equal(result.userName, 'bulkan');
      done();
    });
  });
});

This kind of test could easily turned out to be a [callback hell][ch] when the logic become complex.
Thank god, with the advent of promise, testing asynchronous code is not that much depressing now.

1
2
3
4
5
6
7
8
9
10
11
12

describe('User Profile', function(){
  it('can get user profile', function(done){
    getProfile('bulkan')
    .then(function(result){
      assert.equal(result.userName, 'bulkan');
      done();
    })
    .catch(function(err){
      done(err);
    });
  });
});

Actually manually calling done is not necessary any more in newer version of mocha, as mocha takes care of promise itself pretty well.
So the above code can be written as:

1
2
3
4
5
6
7
8

describe('User Profile', function(){
  it('can get user profile', function(){
    return getProfile('bulkan')
    .then(function(result){
      assert.equal(result.userName, 'bulkan');
    })
  });
});

Now this looks good.
However, we won’t be satisfied with this, will we?
Take a look at how this code could be further improved with async/await.

1
2
3
4
5
6

describe('User Profile', function(){
  it('can get user profile', async function(){
    const result = await getProfile('bulkan');
    assert.equal(result.userName, 'bulkan');
  });
});

In the above snippet, we are taking advantage of of one lovely feature of Async functions:

Async functions always return a promise, no matter whether or not await is invoked.
The promise, returned by async function, would resolve with whatever the async function returns, or rejects with whatever the async function throws.
With the async/await, testing asynchronous code is nearly identical to testing synchronous code.
Cheer!!!

Caveat

Every thing comes at a price.
Although it is very trendy now, we still need a transpiler like bable to use async/await.
What a pity.
[ch]:http://callbackhell.com/

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

1. The order of returned grid coordinates does not matter.
2. Both m and n are less than 150.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

If you try to do a DFS or BFS on each grid to see if it can reach both Pacific and Atlantic ocean, you will get a time out error.

Luckily, we can solve this problem if we think in a contrary way.
We can deduce which grids can reach Atlantic ocean and which can reach Pacific ocean, then the intersection of the two set is the answer.

In this way, the number of iterations can be greatly reduced to the sum of of the 4 edges’ grids, thus averting the time out error.

It’s straightforward to use two vectors to separately store the connectivities of Atlantic ocean and Pacific ocean, but there is an optimization with which you only need one vector to store the same data.That is bit mask( All credits belong to zyoppy008).
Since the data we are trying to maintain are basically two boolean states, two bits in one int are totally enough.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <vector>
#include <stack>
#include <iostream>
#include <climits>

using namespace std;

class Solution
{

public:

  vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix)
  {
    vector<pair<int, int> > ret;
    stack <pair<int, int> > s1;
    stack <pair<int, int> > s2;
    vector <vector<int> > intermidiate;
    int hSize, vSize;
    vSize = matrix.size();
    if (vSize)
    {
      hSize = matrix[0].size();
      if (hSize)
      {
        intermidiate.resize(vSize, vector<int>(hSize, 0));
        for (int index = 0; index < vSize; index++)
        {
          s1.push(pair<int, int>(index, 0));
          s2.push(pair<int, int>(1, INT_MIN));
          s1.push(pair<int, int>(index, hSize - 1));
          s2.push(pair<int, int>(2, INT_MIN));
        }
        for (int index = 0; index < hSize; index++)
        {
          s1.push(pair<int, int>(0, index));
          s2.push(pair<int, int>(1, INT_MIN));
          s1.push(pair<int, int>(vSize - 1, index));
          s2.push(pair<int, int>(2, INT_MIN));
        }
        while (!s1.empty())
        {
          pair<int, int> pos = s1.top(), meta = s2.top();
          int vPos = pos.first, hPos = pos.second, previousValue = meta.second, flag = meta.first;
          s1.pop();
          s2.pop();
          if (vPos >= 0 && vPos < vSize && hPos >= 0 && hPos < hSize && matrix[vPos][hPos] >= previousValue &&
              (intermidiate[vPos][hPos]&flag) == 0)
          {
            intermidiate[vPos][hPos] = intermidiate[vPos][hPos] | flag;
            if (intermidiate[vPos][hPos] == 3)
            {
              cout << vPos << ' ' << hPos << endl;
              ret.push_back(pos);
            }
            s1.push(pair<int, int>(vPos - 1, hPos));
            s2.push(pair<int, int>(flag, matrix[vPos][hPos]));
            s1.push(pair<int, int>(vPos + 1, hPos));
            s2.push(pair<int, int>(flag, matrix[vPos][hPos]));
            s1.push(pair<int, int>(vPos, hPos - 1));
            s2.push(pair<int, int>(flag, matrix[vPos][hPos]));
            s1.push(pair<int, int>(vPos, hPos + 1));
            s2.push(pair<int, int>(flag, matrix[vPos][hPos]));
          }
        }
      }
    }
    return ret;
  }

};
int main()
{
  vector <vector<int> > testData = {{1, 2, 2, 3, 5}, {3, 2, 3, 4, 4}, {2, 4, 5, 3, 1}, {6, 7, 1, 4, 5}, {5, 1, 1, 2, 4}};
  Solution s;
  s.pacificAtlantic(testData);
  return 0;
}

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.

You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

This is a typical greedy problem.

The partial best solution is to find the smallest cookie that could be given to the least greedy child.

Find partial best solutions in repetition until there is no cooky that could be given to the least greedy child or all children receive a cooky.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class Solution
{

public:

  int findContentChildren(vector<int>& g, vector<int>& s)
  {
    sort(g.begin(),g.end());
    sort(s.begin(),s.end());
    int result = 0;
    vector<int>::iterator child = g.begin();
    vector<int>::iterator cooky = s.begin();
    while (child != g.end() && cooky != s.end())
    {
      if (*cooky >= *child)
      {
        result += 1;
        child ++;
      }
      cooky ++;
    }
    return result;
  }

};

int main()
{
  Solution s = Solution();
  vector<int> children({1, 2, 3});
  vector<int> cookies({1, 1});
  cout<<s.findContentChildren(children, cookies)<<endl;
  cout<<"*******"<<endl;
  vector<int> children1({1, 2});
  vector<int> cookies1({1, 2,3});
  cout<<s.findContentChildren(children1, cookies1)<<endl;
}

We all know that we should avert the use of iframe, but sometimes, we have no choice but to use it.
This article is about how to use postmessage to communicate with an iframe using React.
Assumptions were made that you know what is postmessage and how to use it, so if you are not familiar with it, read this this introduction to postmessage before moving on.
At first I want you to know as we need to run js on websites within and outside the child iframe so this method can only be used when you have administration privilege on both sides.

Let’s see what we can do with this method.

As you can see, informations about the scrollTop and height of the child iframe is transfered to the parent component so we can tell whether or not the child iframe is scrolled to top or bottom.

To achieve this, we had to run the following javascript inside the website which is shown inside the iframe.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

(function () {
  var scrollTop;
  var domain;
  var url;
  var body;
  var target;
  function sendHeight() {
    target.postMessage({ url: url, value: body.scrollHeight, type: 'height' }, domain);
  }

  function sendScrollTop() {
    scrollTop = body.scrollTop;
    target.postMessage({ url: url, value: scrollTop, type: 'scrollTop' }, domain);
  }

  body = document.getElementsByTagName('body')[0];
  function receiveMessage(event) {
    switch (event.data.type) {
      case 'setScroll':
        body.scrollTop = event.data.value;
        scrollTop = event.data.value;
        url = event.data.url;
        target = event.source;
        domain = event.origin;
        sendHeight();
        sendScrollTop();
        break;
    }
  }

  window.addEventListener('message', receiveMessage);
  window.addEventListener('scroll', function (e) {
    if (e.target.activeElement === body && scrollTop !== body.scrollTop) {
      sendScrollTop();
    }
  });
})();

Basically, the above code does 3 thing.

1. Set up a handler listening to the incoming message sent from the parent container through postmessage.
2. Set up a handler listening to the scrolling event and send scrollTop to the parent container at appropriate time.
3. Send height to the parent container;

Now let’s move to the parent side.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

import React, { Component, PropTypes } from 'react';
import { connect } from 'react-redux';
import { setScrollTop, setHeight } from './action';

class container extends Component {

  constructor(props) {
    super(props);
    this.msgHandler = this.msgHandler.bind(this);
    this.send = this.send.bind(this);
    this.componentDidMount = this.componentDidMount.bind(this);
    this.maxScrollTop = 10;
  }

  send() {
    if (this.container && this.container.contentWindow) {
      this.container.contentWindow.postMessage(this.data, '*');
      this.container.scrollTop = 20;
    }

    if (!this.received) {
      setTimeout(this.send, 100);
    }
  }

  componentDidMount() {
    this.previous = false;
    this.next = false;
    this.data = {
      url: this.props.content,
      type: 'setScroll',
      value: this.props.scrollTop,
    };
    this.send();
    this.reveived = false;
    window.addEventListener('message', this.msgHandler);
  }

  msgHandler(e) {
    if (e.data.url !== this.props.content) {
      // console.info(e.data.url);
      return;
    }

    switch (e.data.type) {
      case 'height':
        this.maxScrollTop = e.data.value - this.container.offsetHeight;
        this.received = true;
        break;
      case 'scrollTop':
        this.props.saveScroll(e.data.value);

        break;
    }
  }

  render() {
    return (
      <div
        className = 'group'
      >
        <h4 >
          {`Scroll Top:${this.props.scrollTop}`}
        </h4>
        <button
          onClick = {() => alert('wanna go to previous page?')}
          disabled={this.props.scrollTop !== 0}
        >
          Previous
        </button>
        <iframe
          ref = {e => {
            this.container = e;
          }}

          src = {this.props.content}
        />
        <button
          disabled={this.props.scrollTop < this.maxScrollTop}
            onClick = {() => alert('wanna go to next page?')}
        >
          Next
        </button>
      </div>
);
  }
}

container.propTypes = {
  scrollTop: PropTypes.number.isRequired,
  saveScroll: PropTypes.func.isRequired,
  content: PropTypes.string.isRequired,
};

container.mapStateToProps = state => ({
  scrollTop: state.scrollTop,
  height: state.height,
  content: 'http://localhost:8080/one.html',
});

container.mapDispatchToProps = dispatch => ({
  saveScroll: num => {
    dispatch(setScrollTop(Math.round(num)));
  },

  saveHeight: num => {
    dispatch(setHeight(num));
  },
});

export default connect(container.mapStateToProps,
                       container.mapDispatchToProps,
                       container.mapMergeProps)(container);

Firstly, send() is continuously invoked to establish connection with the child iframe in componentDidMount until a reply is recieved.
Then monitor the scrollTop and height attribute of the child iframe inside the msgHandler.
Having known the scrollTop and height, we can tell if the user scrolls to the top or bottom by comparing those two attributes.

What is Missing in This Article?

For safety reasons, we should always check the origin of messages in both the parent and child sides, but to keep the article short, I ignored this part.(Never do this in your production environment)

If you want to know more about security measures which we should implement when using postmessage, check out this document.

Full source code were disclosed at this repo, play with it if you are interested.

If you come here for a solution to the problem, you are in a wrong place.
Because my code for this quiz wasn’t accepted yet and the purpose of this post is to make a summary about what I have learnt about BFS from doing this exercise.
I will share my code at the end of this post and any ideas on where my code is wrong would be greatly appreciated.

When Should We Use BFS

When the target is to find the shortest path,BFS is a good choice.
If you do not have to find all the shortest paths, then you can stop whenever the first path is found.
Otherwise you would have to wait until all the nodes from current layer are processed.

How to Implement BFS

Use a queue to store the tree, and take advantage of the FIFO characteristic of queue to implement BFS.

Optimizations You May Want To Use With BFS

1. Use adjacency matrix to store the relationships between nodes so you only has to do this calculation once.
2. Save the length of the first path you found, whenever the depth of another path is larger than it, you can safely ignore that path.
3. Save all the nodes of current layer and remove them when depth increasing to improve efficiency of further searches.

A Mistake You May Make When Using BFS

Possibility exists that you may include paths that are longer than the shortest ones in your result set so do a filter to get rid of them.
Luckily, you only need to take care of this when you are required to find all the shortest paths.

Lessons I Have Learnt about Javascript

1. The Right Way to Check the Existence of an Element Within an Array
   I used !array.findIndex(element !== target) to check if target is not in array , but this was wrong when target is the first element of array.
   The right way is to use array.findIndex(element !== target)===undefined.

2. A Fast Way to Get the Last Element of an Array
   array.slice(-1)[0].

Here comes the code, I have no idea which part is wrong…lol.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

function Queue(first) {
  this.queue = [{
    path: [0],
    word: first,
  }];
}

Queue.prototype.enque = function (elements) {
  this.queue = this.queue.concat(elements);
};

Queue.prototype.dequeue = function () {
  return this.queue.pop();
};

const getDifferenceNum = (source, target) => {
  const ret = source.filter((s, i) => s !== target[i]).length;
  return ret;
};

function Test(begin, end, list) {
  this.results = [];
  this.list = [begin, ...list];
  this.list = this.list.map(s => s.split(''));
  this.end = end.split('');
  this.queue = new Queue(begin.split(''));
  this.deep = Number.MAX_SAFE_INTEGER;
  this.removeRepitition();
  this.makeAdjacencyMatrix();
  this.currentLevel = 0;
  this.currentLevelElements = [];
  this.usedElements = [];
}

Test.prototype.makeAdjacencyMatrix = function () {
  const length = this.list.length;
  this.adjacency = [];
  let index = 0;
  while (index < length) {
    this.adjacency[index] = [];
    index += 1;
  }

  index = 0;
  while (index < length) {
    let innerIndex = index + 1;
    while (innerIndex < length) {
      if (getDifferenceNum(this.list[index], this.list[innerIndex]) === 1) {
        // making use of the symmetry of the adjacency matrix
        this.adjacency[index].push(innerIndex);
        this.adjacency[innerIndex].push(index);
      }

      innerIndex += 1;
    }

    index += 1;
  }
};

Test.prototype.removeRepitition = function () {
  const hash = {};
  const newList = [];
  this.list.forEach(l => {
    if (!hash[l]) {
      hash[l] = true;
      newList.push(l);
    }
  });
  this.list = newList;
};

Test.prototype.findChildren = function (parent) {
  const currentIndex = parent.path.slice(-1)[0];
  if (parent.path.length > this.currentLevel) {
    this.usedElements = this.usedElements.concat(this.currentLevelElements);
    this.currentLevelElements = [currentIndex];
    this.currentLevel = parent.path.length;
  } else {
    this.currentLevelElements.push(currentIndex);
  }

  const ret = this.adjacency[currentIndex].filter(l =>
    {
      return parent.path.find(p => p === l) === undefined
        && this.usedElements.find(p => p === l) === undefined;
    });

  return ret.map(r => (
    {
      word: this.list[r],
      path: [...parent.path, r],
    }
    ));
};

Test.prototype.findResults = function () {
  let current = this.queue.dequeue();
  while (current) {
    if (current) {
      if (getDifferenceNum(current.word, this.end) === 1
          && current.path.length <= this.deep) {
        this.deep = current.path.length;
        this.results.push(current.path);
      } else if (current.path.length < this.deep) {
        const children = this.findChildren(current);
        this.queue.enque(children);
      }
    }

    current = this.queue.dequeue();
  }
};

Test.prototype.filterResults = function () {
  let minLength = Number.MAX_SAFE_INTEGER;
  this.results.forEach(r => {
    if (r.length < minLength) {
      minLength = r.length;
    }
  });
  this.results = this.results.filter(r => r.length <= minLength);
};

Test.prototype.convertResults = function () {
  this.results = this.results.map(r => r.map(l => this.list[l]));
  this.results.forEach(r => r.push(this.end.join('')));
};

var findLadders = function (beginWord, endWord, wordList) {
  const tem = new Test(beginWord, endWord, wordList);
  tem.findResults();
  tem.filterResults();
  tem.list = tem.list.map(t => t.join(''));
  tem.convertResults();
  return tem.results;
};