![Level 26. Answers to interview questions on the topic of the level. Part 1. Questions 1-5, 10. - 1]()
The summary turned out to be quite cumbersome, so I divided it into two parts. The second part contains answers to questions regarding cancarency and multithreading. The rest in the first part. The writing was pretty hard. I still don’t understand much, therefore, as always, comments, remarks, additions are welcome)
1. How to use the Comparable interface?
ComparableOnly one method is declared in the interface
compareTo(Object obj), designed to implement the ordering of class objects. It is useful when sorting ordered lists or arrays of objects. This method compares the called object with
obj. Unlike the method
equals, which returns
true or
false ,
compareToreturns:
- 0 if the values are equal;
- A negative value if the callee is less than the parameter;
- A positive value if the called object is greater than the parameter.
First of all, it is useful for sorting ordered lists (
java.util.List) and arrays of objects. If the list/array contains elements that implement this interface, then they can be sorted automatically by the
java.util.Collections.sort(List)/Arrays.sort(Object[]). The concept of natural ordering is associated with an interface
Comparable, because it establishes the natural order of instances of any class that implements this interface. In other words, the order (x, y) corresponds to the condition
x.compareTo(y) <= 0. The rules for implementing
Comparable, or rather, its method
compareTo(Object)are as follows (x and y are instances of the class that implements
Comparable):
x.compareTo(y)returns -1 or 1 if x should be before or after y, respectively. If the method returns 0, then the orders (x, y) and (y, x) are equivalent.- If
sign(a)is a function that returns -1,0,1 for a, respectively, less than 0, equal to 0 and greater than 0, then the equality must hold sign(x.compareTo(y))==-sign(y.compareTo(x)). Which is logical: if x comes before y, then y must go after x, and vice versa.
- If
x.compareTo(y) > 0and y.compareTo(z) > 0, then x.compareTo(z) > 0is the relation of transitivity of inequalities.
- If
x.compareTo(y) == 0, then sign(x.compare(z)) == sign(y.compareTo(z)), for any z.
- The call
x.compareTo(null)must throw an exception NullPointerException. There is a discrepancy with the implementation logic in this equals(remember, x.equals(null)it returns false ).
- If y cannot be type-comparable to x, then the call
x.compareTo(y)must throw an exception ClassCastException.
(x.compareTo(y) == 0) == x.equals(y), i.e. the call x.compareTo(y)must return 0 if and only if x.equals(y)it returns true . This is the rule of consistency, and it is very important to consider it.
Sources:
2. How to use the Comparator interface?
The interface
Comparatordeclares two methods
compare(Object obj1, Object obj2)and
equals(Object obj). When using the interface
Comparator, the logic for comparing a pair of objects is not hidden inside the class / object, but is implemented in a separate class. The method
compare(x,y)is exactly the same as calling
x.compareTo(y). In the same way, all rules must be followed, as are the rules for implementing an
compareTo(Object)interface method
Comparable.
Comparatorcan be used anywhere where sorting is needed. In this case, firstly, the necessary flexibility appears - the possibility of implementing several sorting rules. And secondly, the objects being sorted may not implement the
Comparable. If they do implement it,
Comparatorit has priority. An interface
Comparatoralso defines a method.
equals(Object), however paradoxical it may seem. This method compares the interface instances themselves
Comparatorand should only return
true if the objects being compared provide the same sort order. However, it is always safe to leave the original implementation
Object.equals(Object)untouched
. Source:
3. What methods does the Collections class have?
public static <T> boolean addAll(Collection<? super T> c, T... elements) The method adds array elements
elementsto the collection
Collection<? super T> c. Elements can be specified individually or as an array. When the elements are specified individually, this method provides the ability to conveniently add all the elements to the existing collection:
Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) Both methods search the list passed in the parameter for the object passed in the parameter using the binary search algorithm. The index of the element is returned if there is such an element in the list, otherwise the index of the first element of the list greater than
key, if all elements are less than
key, returns
list.size(). Lists must be sorted before using these methods. In the first case, sorted in ascending order in the "natural" order of the elements of the list (same as when using
Collections.sort(list)). In the second case, the list must be sorted in ascending order, which provides the passed comparator (the same order as when using
Collections.sort(list, c)[here "c" is the comparator from the parameters of the described method])
public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type)
Preamble: the generics mechanism in the language provides type checking at compile time . Usually this is enough, but there are times when it is still not. For example, we pass our collection to the library code, somewhere on the side unknown to us, and we really want the code of this "third-party library" not to insert an element of the wrong type into our collection. This is possible problem number 1. Possible problem number 2 is next. Suppose our program gives us
ClassCastException
, which notifies us that an element of the wrong type was inserted into the collection. Unfortunately, this exception can be thrown at any time after an invalid element has been inserted, and usually gives us little or no information about the source of the problem. By using method method
checkedCollectionwe can save ourselves the trouble of one and two, because this method creates a run-time verifiable collection. The solution to problem number two, using this method: For example, we have this, and we have
ClassCastException.
Collection<String> c = new HashSet<String>();
The code above can be temporarily replaced with:
Collection<String> c = Collections.checkedCollection(
new HashSet<String>(), String.class);
When we run the program again, we localize the line of code that inserts an element of the wrong type into our collection. Related methods in my opinion:
public static <E> List<E> checkedList(List<E> list,Class<E> type)
public static <K,V> Map<K,V> checkedMap(Map<K,V> m, Class<K> keyType,Class<V> valueType)
public static <E> Set<E> checkedSet(Set<E> s,Class<E> type)
public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K,V> m,Class<K> keyType,Class<V> valueType)
public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,Class<E> type)
public static <T> void copy(List<? super T> dest,List<? extends T> src) The method copies the elements of src to dest. the indexes of the copied elements will match.
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
public static <T> T min(Collection<? extends T> coll,Comparator<? super T> comp)
public static <T> T max(Collection<? extends T> coll,Comparator<? super T> comp) methods return the minimum\maximum element in the collection in terms of "natural order" (Comparable interface) or the order of the passed comparator.
public static boolean disjoint(Collection<?> c1,Collection<?> c2) Returns
true if the collections do not have identical elements.
<T> List <T> emptyList(), <K,V> Map <K,V> emptyMap(),
<T> Set <T> emptySet()– return an empty list, display map and set, respectively;
<T> void fill(List<? super T> list, T obj)– fills the list with the given element ;
int frequency(Collection<?> c, Object o)– returns the number of occurrences of the given element in the collection;
<T> List <T> nCopies(int n, T o)- returns a list of
ngiven elements;
<T> boolean replaceAll(List<T> list, T oldVal, T newVal)– replaces all given elements with new ones;
void reverse(List<?> list)– “reverses” the list;
void rotate(List<?> list, int distance)- shifts the list cyclically by a given number of elements;
void shuffle(List<?> list)- shuffles the elements of the list;
<T> Set <T> singleton(T o), singletonList(T o), singletonMap(K key, V value)– create a set, a list and a display map, consisting of a single element;
<T extends Comparable<? super T>> void sort(List<T> list),
<T> void sort(List<T> list, Comparator<? super T> c)- sorting the list, in natural order and using
Comparatoraccordingly;
void swap(List<?> list, int i, int j)– swaps the elements of the list at the given positions.
Sources:
4. What methods does the Arrays class have?
The full list of methods of the Arrays class can be seen in
the documentation . In this summary, I will list just a few of them. [translated methods from the documentation, and unfortunately lost most of my translation. It's a shame, and I don't want to waste time on the same thing, so I'll insert the google]
public static <T> List<T> asList(T... a) generates a list based on an array. The array is used for the internal representation of the list. This maintains the link between the list and the original array: changes to the array will be reflected in the list:
String[] a = { "foo", "bar", "baz"};
List<String> list = Arrays.asList(a);
System.out.println(list);
a[0] = "aaa";
System.out.println(list);
changes to the list will be reflected in the array:
String[] a = { "foo", "bar", "baz"};
List<String> list = Arrays.asList(a);
System.out.println(list);
list.set(0, "bbb");
System.out.println(Arrays.toString(a));
If the array contains objects, obviously both the array and the list will refer to the same instances:
Object[] a = { new Object(), new Object(), new Object()};
List<Object> list = Arrays.asList(a);
System.out.println(a[0] == list.get(0));
int binarySearch(параметры)– an overloaded method for organizing a binary search for a value in arrays of primitive and object types. Returns the position of the first match;
void fill(параметры)– overloaded method for filling arrays with values of various types and primitives;
void sort(parameters) - an overloaded method for sorting an array or its part using the Comparator interface and without it;
static <T> T[] copyOf(T[] original, int newLength)- fills an array of a certain length, discarding elements or filling null if necessary;
static <T> T[] copyOfRange(T[] original, int from, int to)– copies the specified area of the array to a new array;
<T> List<T> asList(T… a)is a method that copies the elements of an array into an object of type List<T>.
Source:
5. What is the name of the sort that is used when calling Collections.sort()?
From the docs : The implementation is a Python adaptation of Tim Peters' (TimSort) list sort. This implementation dumps the list into an array, sorts the array, then iterates through the list and reloads each list element from the corresponding array element. This avoids the n*n log(n) complexity that would result from trying to sort the linked list directly.
From the wiki: Timsort is a hybrid sorting algorithm that combines insertion sort and merge sort, published in 2002 by Tim Peters. Timsort is currently the default sorting algorithm in Python, OpenJDK 7, and implemented in Android JDK 1.5. The main idea of the algorithm is that in the real world sorted data arrays often contain ordered subarrays. On such data, Timsort is significantly faster than many sorting algorithms.
10. What is an iterator?
Introduced in the JDK 1.2 release of the Java language, the interface
java.util.Iteratorprovides iteration of container classes. Each Iterator implements
next()and
hasNext()and optionally supports a
remove(). Iterators are created by the corresponding container classes, usually by the
iterator(). The method
next()advances the iterator to the next value and returns the specified value to the iterator. When initially created, an iterator points to a special value before the first element, so the first element can only be retrieved after the first call to
next(). The test method is used to determine when all the elements in the container have been iterated
hasNext(). The following example demonstrates the simple use of iterators:
Iterator iter = list.iterator();
while (iter.hasNext())
System.out.println(iter.next());
For a collection of types that supports this, the iterator method
remove()removes the last 'visited' element from the container. Almost all other types of container modification during iteration are unsafe. It also
java.util.Listhas
java.util.ListIteratora similar API, but allows forward and backward iteration, providing a determination of the current index in the list and moving to an element by its position.
Source:
Part 2
The summary turned out to be quite cumbersome, so I divided it into two parts. The second part contains answers to questions regarding cancarency and multithreading. The rest in the first part. The writing was pretty hard. I still don’t understand much, therefore, as always, comments, remarks, additions are welcome)
GO TO FULL VERSION