5
\$\begingroup\$

Given the following JSON data containing 4 articles by 4 different authors:

const data = {
  "DataSet": {
    "Article": [
      {
        "Title": 'A',
        "AuthorList": {
          "Author": [{
            "FirstName": "Al",
            "LastName": "Ab",
            "Initials": "A"
          }, {
            "FirstName": "Bi",
            "LastName": "By",
            "Initials": "B"
          }] // Author
        } // AuthorList
      }, // Article
      {
        "Title": 'B',
        "AuthorList": {
          "Author": [{
            "FirstName": "Bi",
            "LastName": "By",
            "Initials": "B"
          }, {
            "FirstName": "Ch",
            "LastName": "Ch",
            "Initials": "C"
          }] // Author
        } // AuthorList
      }, // Article
      {
        "Title": 'C',
        "AuthorList": {
          "Author": [{
            "FirstName": "Ch",
            "LastName": "Ch",
            "Initials": "C"
          }, {
            "FirstName": "Al",
            "LastName": "Ab",
            "Initials": "A"
          }] // Author
        } // AuthorList
      }, // Article
      {
        "Title": 'D',
        "AuthorList": {
          "Author": [{
            "FirstName": "Da",
            "LastName": "Do",
            "Initials": "D"
          }, {
            "FirstName": "Bi",
            "LastName": "By",
            "Initials": "B"
          }] // Author
        } // AuthorList
      } // Article
    ] // Articles
  } // DataSet
};

I need to answer the following query:

Generate a matrix such that each cell (i, j) contains say N the number of articles authored by the author in column and co-authored by author in row. A paper may have more than 2 authors. It may be assumed that JSON is present as a file.

For above example the output would simply look like:

[2, 1, 1, 0]
[1, 3, 1, 1]
[1, 1, 2, 0]
[0, 1, 0, 1]

I have devised the solution below without thinking too much about design and performance:

const fullName = (author) => author["FirstName"] + ' ' + author["LastName"];

const authorMap = {};

const getArticles = (data) =>
  data["DataSet"]["Article"];

const getAuthors = (data) =>
  data["DataSet"]["Article"]
    .reduce((accum, article) => {     
      return [...accum, ...article["AuthorList"]["Author"].map((author) => {
        return fullName(author);
      })];
    }, []);

const matrix = [];

const initializeMatrix = () => {
  const N = Object.keys(authorMap).length;
  for (let i = 0; i < N; i++) {
    matrix[i] = Array(N).fill(0);
  }
};

console.clear();
let authors = getAuthors(data);
authors = Array.from(new Set(authors));
const articles = getArticles(data);
authors.forEach((author, idx) => {
  authorMap[author] = idx;
});

initializeMatrix();

articles.forEach((a) => {
  const authors = a["AuthorList"]["Author"];
  const authorIds = [];
  authors.forEach((author) => {
    authorIds.push(authorMap[fullName(author)]);
  });
  for (let i of authorIds) {
    for (let j of authorIds) {
      matrix[i][j] = matrix[i][j] + 1;
    }
  }
});

const printMatrix = (matrix) => {
  console.log('///////////////');
  for (let i = 0; i < matrix[0].length; i++) {
    console.log(matrix[i]);
  }
};

printMatrix(matrix);

Note:

There can be more than two authors per article.

Questions:

  1. How to test the code?
  2. What are the edge cases?
  3. What if there are millions of articles? how to optimize the code?

Update 1:

The author name is FirstName + LastName

Update 2:

Adding unit tests.

'use strict';
/* eslint-env mocha */
const assert = require('assert');
const m = require('./');

it('should check for invalid data format', () => {
  assert.throws(() => m('fixtures/invalid.json'), /Invalid data/);
});

it('should return matrix of size 1 for single author', () => {
  const expected = {
    'A A': {
      'A A': 1,
    }
  };
  assert.deepEqual(m('fixtures/single-author.json'), expected);
});

it('should return matrix of size 2 for two authors', () => {
  const expected = {
    'A A': {
      'A A': 1,
      'B B': 1,
    },
    'B B': {
      'A A': 1,
      'B B': 1,
    }
  };
  assert.deepEqual(m('fixtures/two-authors.json'), expected);
});
\$\endgroup\$
  • 2
    \$\begingroup\$ Are your current results correct according to the challenge? Because I would think that the diagonal of the matrix (assuming both rows and columns use the same ordering of authors) would be zero – you can't co-author a paper with yourself, can you? \$\endgroup\$ – Flambino Apr 13 '17 at 12:15
  • \$\begingroup\$ Also, does author/co-author mean different things? If they don't - they're both just names listed on the article, regardless of order - then you only have to work out half of the matrix, since it'll be symmetrical (e.g. if A & B wrote one article, then B & A wrote is also one). But in academia the author is sometimes thought of as only the first person listed, and co-authors are those listed after (e.g. A authored one article with B as co-author, but B didn't author any articles with A as co-author) \$\endgroup\$ – Flambino Apr 13 '17 at 12:47
  • 1
    \$\begingroup\$ From the example I assumed that a author is co-author of itself. The example output was part of the problem \$\endgroup\$ – CodeYogi Apr 13 '17 at 13:17
  • 2
    \$\begingroup\$ Did the problem tell you what the authoritative author identifier is? Is it the initials field? Is it first name + last name as you seem to be using? \$\endgroup\$ – Mike Brant Apr 13 '17 at 16:08
  • \$\begingroup\$ @Flambino is there any way to optimise code performance and have better design? \$\endgroup\$ – CodeYogi Apr 13 '17 at 16:55
4
+100
\$\begingroup\$

You seem to be taking a very non-optimal approach from a performance standpoint, as you iterate over the data set unnecessarily trying to extra only derive certain pieces from it at a single time. I would think your goal would be to map the data into your data structure with a single iteration over the data.dataSet.article array, resulting in \$O(n)\$ operational complexity to read the data in).

Right now you do:

  • Build an array of authors - \$O(n)\$, where n is number of articles
  • Cast authors in to a Set - \$O(n)\$, where n is number of authors from previous step
  • Get articles into array - \$O(n)\$, where n is # of articles. Note you gain nothing from mapping articles in place into there own array, but double memory usage and add this \$O(n)\$ performance hit. At a minimum you should kill this step.
  • You map authors into an object with index position as value - \$O(n)\$ where n i # of authors. Another unnecessary step it seems, as you could iterate the authors set just as you have done here later if needed.
  • You initialize the matrix to hold empty 0's - \$O(n)\$ where n is number of authors. This could have been done at any other point where you already iterated author set.
  • You iterate the articles array - \$O(n)\$ where n is # of articles.

As you can see that is a lot of unnecessary complexity (and memory consumption).

You should be able to build your matrix in a single pass.

  • Initialize your matrix as an empty object which will later be filled in .

The target data structure may look like this:

{
    'ch ch': {
        'ch ch':  *,
        'other author': *,
        ...
    },
    'other author': { ... },
    ...
}
  • iterate through data.dataSet.article. On each element populate counters on properties in proposed data structure above.
  • populate all authors into a set for use in rendering display.

This all could be as simple as:

const matrix = {};
const authors = new Set();
const articleLen = data.dataSet.article.length;
for (let artIdx = 0; artIdx < articleLen; artIdx++) {
    const len = element[artIdx].authorList.length;
    for (let i = 0; i < len; i++) {
        let author = fullname(element[artIdx].authorList[i]);
        authors.add(author);
        for (let j = 0; j < len; j++) {
            let coauthor = fullname(element[artIdx].authorList[j]);
            matrix[coauthor][author] = (matrix[coauthor][author]++ || 0) + 1;
        }
    }
}

Note: I used for loops for performance optimization rather than array methods. You really could use either. If writing code for real-world system where I did not expect millions of rows and the performance micro-optimization was not necessary I would probably use array methods for cleaner code.

  • Fill 0's in matrix on display (or as secondary process if you really need the data structure). You do this by iterating the author set in nested loop.

  • This would result in complexity that is \$O(n)\$ (n = articles)for article iteration + \$O(m^2)\$ (m = authors) for matrix display. So, if # of articles are assumed to be >> # of authors, this would likely be a good approach.

\$\endgroup\$
  • \$\begingroup\$ Nice answer. I found it however to be a little bit harder to follow than it could be, so I rewritten it. Since performance is crucial in this case, I also think while loops could come in handy (benchmark). \$\endgroup\$ – Przemek Apr 13 '17 at 21:29
  • \$\begingroup\$ I see that overall complexity is same as mine, apart from the fact that I used some extra memory os, performance wise its same. The main bottleneck is iterating over all the pairs of authors. \$\endgroup\$ – CodeYogi Apr 14 '17 at 13:19
  • \$\begingroup\$ @CodeYogi You are right in the fact that both solutions face the \$O(n^2)\$ problem when building matrix for display, but you iterate articles 3 times vs. once, I would not consider this to be same complexity even though they are both linear. If you had degenerate use case of one author per articles, this would be the primary determinant of overall performance. \$\endgroup\$ – Mike Brant Apr 14 '17 at 13:43
  • \$\begingroup\$ I was wondering if that can be improved hope others to chime in too, apart from that could this code can be made more moduler /flexible ? say if this code would be used as an open source library? \$\endgroup\$ – CodeYogi Apr 14 '17 at 13:47
  • \$\begingroup\$ @CodeYogi I don't see an improvement on matrix display as long as the data structure itself would require looping each row and column to fill out the zeroes as far as I can tell. I don't think there is much opportunity for generalization here as this code is heavily coupled to the data structure. The is really no special logic to be encapsulated here other than for working with this specific data structure. \$\endgroup\$ – Mike Brant Apr 14 '17 at 14:04
1
\$\begingroup\$

I don't see the reasoning for building all the intermediate arrays of articles and authors and stuff. I'm also not sure whether to use a full matrix for the result matrix is the best option. Most likely this matrix would be a very sparse matrix, so to avoid large memory usage you could opt for data structures allowing for sparse matrixes (or possibly use a hashed array where the key is the (i, j) coordinates.

Here is a pseudo-code version for looping through the article set once, the author set once with a double for-loop based on author id's afterwards.

  • For each article, article, do the following:

    • Reset currentAuthors list
    • Loop through the author's of the article, and for each author do:
      • Check if author is part of the authorList array.
      • If found keep the authorIndex, and if not found add and keep the new authorIndex
      • Push authorIndex to a sorted list, currentAuthors
    • for i = 0 to currentAuthors.size() - 1
      • for j = i + 1 to currentAuthors.size()
        • A: Only upper right matrix: Increase matrix(currentAuthors[i], currentAuthors[j]) with 1
        • B: To create full matrix: Increase matrix(currentAuthors[j], currentAuthors[i]) with 1
  • Print out the final matrix...

This will using only A create the upper right part of the matrix, and if also including B it'll create the full matrix.

To avoid creating a full sparse matrix, you could opt for using a hash array, where the key is like currentAuthors[i]_currentAuthors[j]. When printing you could sort the keys, and print 0 for all non-existent keys, and the actual values for existing entries. The dimension of the full matrix are given by the number of authors in authorList.

The time complexity of this method should be \$O(n*m*log(m))\$, with n as number of articles, and m as a local number of authors for a given article. The space complexity should also be optimal, as you don't store the articles or any extra information besides the global list of authors, and intermediate list of author ids for the current article. I don't think you can do a lot better than this. (The space complexity is somewhat dependent on the storage of the potential sparse matrix)

Your questions

Testing your code

If you make this into a function, and have proper reset functions, it should be rather easy to make a function allowing for multiple input sets, and then match the output towards your expected result.

Depending on test methodology you could opt for making tests which tests that the author matrix is as expected, or just the result matrix. In other words, whether you also want to test the inner parts of your code or not.

The various test set should test for various aspects, like many articles with few authors, or few articles with many authors, or many articles with many authors, or many articles with few authors.

Edge cases

Typical edge cases are a few articles with a lot of authors, or many articles each with a unique author. The latter case would trigger the worst space consumption if not some technique for the sparse matrix issue.

A million articles

As this solution doesn't store the articles, the number of articles is somewhat irrelevant. The author list will increase, but that can't be helped.

If implementing a good handling related to the sparse matrix (and possibly only storing the upper right part), like the hash-keying, you can't reduce the space complexity either.

For exceptionally large cases of multiple authors, you could opt for using databases for the author id list and/or result matrix, but that seems like overkill in most cases.

\$\endgroup\$
  • \$\begingroup\$ I think what you are saying is done by above answer, right? \$\endgroup\$ – CodeYogi Apr 20 '17 at 15:08
  • \$\begingroup\$ I think this is a slightly alternate approach to the answer given by Mike Brant. This solution doesn't do a full \$O(m^2)\$ for the author vs coauthor. But they are similar. It also suggests not to use full matrixes, which could be very memory efficient given a large article/author lists. \$\endgroup\$ – holroy Apr 20 '17 at 15:11
  • \$\begingroup\$ Also, I see that in other answer too an object is used as matrix which is kind of sparse matrix. My main concern was to check if I can reduce O(n* m^2) complexity because this is part of some important job interview and the solution feels too easy to me :) \$\endgroup\$ – CodeYogi Apr 20 '17 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.