I was asked this during a coding interview and cannot figure it out for the life of me.

Input 0 -> 1

1 -> 0,2,3,4,5

2 -> 1, 3,4,5

3 -> 1,2,4,5

4 -> 0

5 -> 1,2,3,4

N = 2

Output

1 -> 2,3,5

2 -> 1,3,5

3 -> 1,2,5

5 -> 1,2,3

Essentially each list is of people the primary value knows (0 knows 1), if they don't know N people they are removed from the guest list, and from the list of the other members. Log the state of the party after removing those who don't know enough people

My current modeling:

public class Guest
    {
        public int Id { get; set; }
        public IList<int> Friends { get; set; }
    }


public static void Main(string[] args)
    {
        var guest0 = new Guest
        {
            Id = 0,
            Friends = new List<int> {1}
        };
        
        var guest1 = new Guest
        {
            Id = 1,
            Friends = new List<int> {0,2,3,4,5}
        };
        
        var guest2 = new Guest
        {
            Id = 2,
            Friends = new List<int> {1, 3, 4,5}
        };
        
        var guest3 = new Guest
        {
            Id = 3,
            Friends = new List<int> {1,2,4,5}
        };
        
        var guest4 = new Guest
        {
            Id = 4,
            Friends = new List<int> {0}
        };
        
        var guest5 = new Guest
        {
            Id = 5,
            Friends = new List<int> {1,2,3,4}
        };
        
        var guestList = new List<Guest>{guest0, guest1, guest2, guest3, guest4, guest5};
        
        UpdateGuestList(guestList, 2);
    }

    public static void UpdateGuestList(List<Guest> guests, int needToKnow)
    {
        
    }

CodePudding user response：

I suggest a bit different data structure: Dictionary<int, HashSet<int>> where Key is a guest an Value contains known people. Here we should remove and items and we can do it more efficient by hashes:

var data = new Dictionary<int, HashSet<int>>() {
  { 0, new HashSet<int>() { 1 } },
  { 1, new HashSet<int>() { 0, 2, 3, 4, 5 } },
  { 2, new HashSet<int>() { 1, 3, 4, 5 } },
  { 3, new HashSet<int>() { 1, 2, 4, 5 } },
  { 4, new HashSet<int>() { 0 } },
  { 5, new HashSet<int>() { 1, 2, 3, 4 } }, 
};

int N = 2;

Please note, that we should remove guests in a loop: if we remove guest #0, some other potential guests who know #) now can know less people then N:

while (true) {
  var remove = data
    .Where(pair => pair.Value.Count < N)
    .Select(pair => pair.Key)
    .ToList();
 
  if (remove.Count <= 0)
    break;

  foreach (int key in remove) {
    data.Remove(key);

    foreach (var value in data.Values)
      value.Remove(key);
  }
}

Time to provide some report:

var report = string.Join(Environment.NewLine, data
  .OrderBy(pair => pair.Key)
  .Select(pair => $"{pair.Key} -> {string.Join(", ", pair.Value.OrderBy(item => item))}")
);

Console.Write(report);

Output:

1 -> 2, 3, 5
2 -> 1, 3, 5
3 -> 1, 2, 5
5 -> 1, 2, 3

Please, fiddle yourself

CodePudding user response：

I think you should first save a list of people who don't have enough friends in the first place and then go through them using an iterative loop. For example because 0 doesn't have enough friends, you look who they are friends with. You see they are friends with 1 so you go to 1's list and remove 0. Then you check if 1 has enough friends. If they didn't, you would see who 1 is friends with and delete 1 from their lists and so on. Then you do the same to 4.

You don't need to delete the nodes, the key is that they tell you which lists you should be deleting a mention of them from. Then you just let the loop follow the path. After that you just iterate though the whole guest list again and see who has enough friends still.