Today, I wanted to take a stab at a social media type question that I was asked once upon a time. How to find the most popular person in a group of people.
In our set up, we assume we are given a 2D array of people who follow one another. (i.e. fi A[i][j] is true, it means that person i follows person j)
I only have 10 minutes, so I’ll try to cut it as short as possible and make a quick overview on a small social media functionality.
Bbelow is the code. I cannot think of an optimization we can do at the moment.
Worst time-complexity seems O(n2) and no way to go around it.
Auxiliary space-complexity is also O(n) in the worst case scenario. Below the code:
How to find the most popular person in a group of people.
|
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 |
* @Author: Ajk Palikuqi * * @Question: How to find the most popular person in a group of people. * * Given a 2D array of people who follow one another, determine who is popular (followed by everyone, follows no one). * Example: If A[i][j] is true, then person i follows person j. */ package iqLib.arrayLib; import java.util.ArrayList; public class FindPopularPerson { public static ArrayList<Integer> FindPopularPeople(int[][] followersMatrix) { ArrayList<Integer> popularPeople = new ArrayList<Integer>(); int numberOfPeople = followersMatrix.length; for (int i = 0; i < numberOfPeople - 1; ++i) { boolean followsSomeone = false; boolean isPopularPerson = true; for (int j = 0; j < numberOfPeople; ++j) { if (followersMatrix[i][j] == 1) { followsSomeone = true; break; } } if (!followsSomeone) { for (int j = 0; j < numberOfPeople; ++j) { if (followersMatrix[j][i] == 0) { isPopularPerson = false; } } } if (isPopularPerson) { popularPeople.add(i); } } return popularPeople; } public static int[][] ComputeMatrixSubSums(int[][] nMatrix) { int nRows = nMatrix.length; int nColumns = nMatrix[0].length; //Shows the computed sums of the rectangle from point 0,0 to here inclusive. int nComputedSums[][] = new int[nRows][nColumns]; //Compute sums for the firt row and first column nComputedSums[0][0] = nMatrix[0][0]; for (int j = 1; j < nColumns; ++j) { nComputedSums[0][j] = nComputedSums[0][j-1] + nMatrix[0][j]; } for (int i = 1; i < nRows; ++i) { nComputedSums[i][0] = nComputedSums[i-1][0] +nMatrix[i][0]; } //Compute sums for the rest for (int i = 1; i < nRows; ++i) { for (int j = 1; j < nColumns; ++j) { nComputedSums[i][j] = nComputedSums[i][j-1] + nComputedSums[i-1][j] - nComputedSums[i-1][j-1] + nMatrix[i][j]; } } return nComputedSums; } public static int FindMatrixSubSumByCache(int[][] nMatrix, Point nTopLeft, Point nBottomRight, int[][] computedSums) { int nSum = 0; for (int i = nTopLeft.x; i < nBottomRight.x; ++i) { for (int j = nTopLeft.y; j < nBottomRight.y; ++j) { nSum += nMatrix[i][j]; } } return nSum; } } |
I do not think there is an easier way, since in the worst case scenario you HAVE TO go through each node (total nodes, n squared), to find out if a person follows / gets followed.
Great now you know a a little piece of implementation of social media following / most popular person abstraction.
Hope you guys enjoyed it… and I’ll see you guys next timd ;D
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017