0

Given a list of 100 elements, if I take out 1 element from list, How will you find out what is the element removed?

I have been asked this question in one of my interview.

Shr
  • 11
  • 1
  • 2
    Are you given the original list as well as the list with the element deleted? – Louis Wasserman Apr 07 '16 at 21:59
  • Duplicate? https://stackoverflow.com/questions/919387/how-can-i-calculate-the-difference-between-two-arraylists – Benedict Lewis Apr 07 '16 at 23:45
  • `List` is ordered per the API spec... So if one `List`, `after`, is really just another `List`, `before` with a single element removed via `List::remove`, you can just iterate through and return the first where `before.get(i) != after.get(i)`. – BeUndead Apr 08 '16 at 00:13

3 Answers3

0

Assuming that you are given different references to the contents of the collection before and after the deletion of the element, the command

before.removeAll(after);

will leave before with just one element, i.e. the deleted one, if the remaining elements are not equal to the deleted one.

Otherwise, depending on how the deletion is done, you get the removed element either as a parameter to remove(element) or as the return value of remove(elementIndex), for collections that support indexed deletion (e.g., subclasses of List).

PNS
  • 19,295
  • 32
  • 96
  • 143
  • That works for `Set` but not for `List`. For example if `before` is `[1, 1]` and `after` is `[1]`, then `removeAll` would give `[]`. – Paul Boddington Apr 07 '16 at 22:05
  • To solve that, parallel iteration, printing and skipping values in `before` that don't match next value in `after`. – Andreas Apr 07 '16 at 22:37
  • @PaulBoddington Good point, I have updated the answer. Thanks. – PNS Apr 08 '16 at 00:12
0

If you are given the new collection and the old collection then the simplest mechanism is to remove each item in the new from the old. What is left is the difference between the two.

For example, in Java 8:

newCollection.stream().forEach(oldCollection::remove);

This works because the stream and remove methods are both in the Collection interface so it should work for all collections that support remove. Because remove is called once for each item in newCollection only a single instance of each will be removed which helps with duplicate items.

If remove is not supported by the collection then a simple solution is to create a new copy before using this method (e.g. new ArrayList<>(oldCollection)):

If you are specifically looking for one item in an indexed collection then you can just look for the first one that doesn't match which is much cheaper:

IntStream.range(0, oldCollection.size())
    .filter(n -> n >= newCollection.size() 
       || !oldCollection.get(n).equals(newCollection.get(n)))
    .findFirst();

This returns an Optional to allow for the situation in which no items have been removed.

sprinter
  • 27,148
  • 6
  • 47
  • 78
0

Assuming they give you 100 int elements and remove 1 int from the collection. what you can do is to do a sum() for 100 elements and another sum() for the 99 elements. Then you do a subtraction between the two sum and you will get the element that was removed from the collection.

T_Y
  • 57
  • 1
  • 5
  • This only gives you an answer if the collections are numerical (I may have read the question wrong, but I don't think numerical values were specified) – Benedict Lewis Apr 08 '16 at 00:05
  • @BenedictLewis the question itself is not clear. thats why I was using the word "Assuming". – T_Y Apr 08 '16 at 00:54