C # Algorithme amélioré

Votre réponse est O (n ^ 2) car vous devez rechercher la petite liste pour chaque élément de la grande liste. Vous avez peut-être de la chance en utilisant une table de hachage ou une liste triée avec une recherche binaire (dans le cas d'entiers / chaînes) et d'autres manières de réduire les frais généraux de recherche, ce qui vous permettra au moins de vous. N).

À compter de la note, si la taille de la petite liste n'est pas similaire à la taille de la grande liste, votre solution est O (n * m); Vous voudriez d'abord optimiser la liste typiquement plus grande. Si vous pouvez trier la première liste, c'est un bon choix; Si vous n'êtes pas autorisé à le modifier, n'oubliez pas de trier / hachage la deuxième liste.

exemple en utilisant sauf xxx

int[] items1={1,2,3,4}; 
List<int> newList = new List<int>() { 1, 2, 3, 4, 5, 56, 788, 9 };
newList.RemoveAll((int i) => { return items.Contains(i); });

  1) The interviewer replied that the
  algorithm i have employed will
  gradually take time if the item grows
  and asked me to give even better and
  faster one.What would be the efficient
  algorithm ?
Your items1 has a length m, and newlist has a length n. Since you're performing a linear lookup on items1 for each item in newlist, your solution is O(n*m). From my point of view, your implementation is perfectly acceptable, and we probably shouldn't worry about optimizations until we need to.Evidently, however, its not good enough for the interview. Alright, what's "good enough" to the interviewer? Who knows. Now, if you don't mind taking some risks in your interview, you can challenge your interviewer to give more detail on the problem. Inform him that lots of factors and assumptions affect the speed of our code, especially the choice of data structure:
Assuming you require indexed access to newList, then converting items1 to a HashSet (which has O(1) lookup) improves your algorithm to the O(n) time required to rebuild the array.
Assuming newList is a "bag" of elements, meaning we don't care about the order of elements in the collection, then representing newList with a hashset allows us to remove m items in O(m) time.
Assuming we need to preserve the insertion order of elements in the collection, you can represent newList as a LinkedList{T}, while using a Dictionary{T, LinkedListNode} as a lookup table. When you add an item to the collection, you add it to the LinkedList, then add the newly created node to the dictionary. The LinkedList keeps the insertion order, and the Dictionary allows us to remove m items in O(m) time. However, we sacrifice indexed access to the collection.
Assuming newList keeps items in sorted order (doesn't appear to be the case with the sample code provided, but just humor me), most flavors of balanced binary trees will remove m items in O(m log n), they also support O(n) sorted-order traversal. Or if you're in right mood, a skip-list does the same job, only sillier.

  3) He asked me to provide an example
  for Two-Way-Closure? (General I am
  aware of closure, what is meant for
  Two-Way-Closure?, I replied i have
  ever heard that term,but he did not
  satisfy).
I've never heard of it either, and Google doesn't appear to turn up any relevant articles (apart from this thread, none of the results on the first 5 pages are programming or even computer related). The interviewer is an idiot.