6

I have having trouble figure out how to write this code.

I have a list of items, the items all have an ID. There is also another value that we will call otherID. If otherID is zero or null, we will ignore it. However, if otherID contains the ID of another item in the list, I want to remove that item from the list.

Example:

item1.ID = 5, item1.otherID = null
item2.ID = 6, item2.otherID = 5
item3.ID = 7, item3.otherID = null

so item1 should be removed from the list because it's ID is present in the otherID field of item2

Any one know how I would write this?

Improve this question

2 Answers 2

Reset to default
11

One way to do this would be a 2-stage process:

  1. Build up a set of Ids that must be removed.
  2. Remove items from the list whose Id's are present in the blacklist.

This will require two passes of the list. Since adding to a HashSet / testing if it contains an item should be a constant-time operation, the entire operation should run in linear time. 

var idsToBeRemoved = new HashSet<int?>(list1.Select(item => item.otherID)
                                            .Where(otherId => otherId.HasValue));

list1.RemoveAll(item => idsToBeRemoved.Contains(item.ID));

EDIT: Updated Id's type to int? after clarification from the OP.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I'm sure he is using psuedo code. ID is probably type object, guid, or int?
Yes, Id's type was not mentioned in the question. Will edit int? into my answer.
Why not new HashSet<int>(list1.Where(item => item.otherID.HasValue).Select(item => item.otherID.Value))?
@Greg: That is also possible, but remember that Id is probably also of type int?. So you would then need change the second lambda to item => item.ID.HasValue && idsToBeRemoved.Contains(item.ID.Value). On balance, I thought my original approach was less verbose.
8

Like this:

list.RemoveAll(r => list.Any(o => o != r && r.ID == o.otherID));
Improve this answer

4 Comments

you should edid last assightment to ==
Ani's solution is O(n), while yours is O(n^2)
Shogun: for every item in the list, this solution will potentially have to look at every item in the list; Ani's solution will only have to look at each item twice: once to build the set of idsToBeRemoved and once to remove them.
@Gabe Good point here Gabe. If I could +1 you here for commenting on "scalable code" I would. Great add!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.