Entertaining tasks and an excerpt from the book "Career Programmer"

Hi, Habrozhiteli! Earlier we already announced the book “Programmer Career. The 6th edition of "Gayles Luckman McDowell in this post . Now we have the electronic rights to this book, which means we can share the chapter" Java "and suggest to solve the problems:



1. Develop an algorithm for finding the smallest K numbers in an array.

2. Write the function of summing two numbers without using "+" or any other arithmetic operators.

3. For two squares in the plane, find the line that halves the two squares. It is assumed that the upper and lower sides of the square are parallel to the x axis.



Those who offer reasoned decisions - we will gladly send an e-book as a gift.

Java Head

13.1. How will the declaration of private constructor inheritance affect?

')

DECISION



Declaring a class A constructor with the private qualifier ensures that the constructor will be available only to those for whom private methods A. are available. Who else besides A can refer to private methods and constructors A? Internal classes A. In addition, if A contains an internal class Q, then the internal classes Q can also refer to them.

All of this is directly reflected in inheritance, because the subclass invokes the constructor of its parent. Class A can be used for inheritance, but only by internal classes (its own or parent classes).



13.2. Will there be a finally block (in Java code) if the return statement is inside a try block (try-catch-finally construct)?



DECISION



Yes, there will be. The finally block is executed when the try block exits. Even when trying to force an exit from a try block (with a return, continue, break, or some other method), the finally block will still be executed.



The finally block is not executed only in emergency cases, for example:



‰‰ - the virtual machine stopped its operation during the execution of the try / catch block;

‰‰ - the thread that executed the try / catch block was destroyed.



13.3. What is the difference between final, finally and finalize?



DECISION



Despite similar names, final, finally, and finalize have different purposes. final controls the “mutability” of a variable, method, or class. finally is used in the try / catch construct to ensure the execution of a code segment. The finalize () method is called by the garbage collector as soon as the latter decides that the links no longer exist.



These keywords are discussed in more detail below.



final



The purpose of the final command may vary depending on the context:



‰‰ - With variable (primitive): the value of the variable cannot be changed.

‰‰ - With variable (reference): a variable cannot point to any other object on the heap.

‰‰ - With method: method cannot be overridden.

‰‰ - With class: class cannot be subclassed.



finally



An optional finally block can be placed after a try or catch block. Commands that are in the finally block are always executed (an exception is the shutdown of the Java virtual machine in the try block). The finally block is designed to perform final actions, that is, "stripping." It runs after the try and catch blocks, but before returning control to the starting point.



The following example shows how this is done:

1 public static String lem() { 2 System.out.println("lem"); 3 return "return from lem"; 4 } 5 6 public static String foo() { 7 int x = 0; 8 int y = 5; 9 try { 10 System.out.println("start try"); 11 int b = y / x; 12 System.out.println("end try"); 13 return "returned from try"; 14 } catch (Exception ex) { 15 System.out.println("catch"); 16 return lem() + " | returned from catch"; 17 } finally { 18 System.out.println("finally"); 19 } 20 } 21 22 public static void bar() { 23 System.out.println("start bar"); 24 String v = foo(); 25 System.out.println(v); 26 System.out.println("end bar"); 27 } 28 29 public static void main(String[] args) { 30 bar(); 31 } 

The result of executing this code looks like this:

 1 start bar 2 start try 3 catch 4 lem 5 finally 6 return from lem | returned from catch 7 end bar 

Take a closer look at lines 3–5. The catch block executes completely (including the function call in the return command), then the finally block is executed, and only after that the function returns control.



finalize ()



The finalize () method is called by the garbage collector just before the object is destroyed. Thus, a class can override the finalize () method from the Object class to implement non-standard behavior in the garbage collection process.

 1 protected void finalize() throws Throwable { 2 /*   ,    . . */ 3 } 

13.4. Explain the difference between C ++ templates and Java generics.



DECISION



Many programmers believe that the pattern and generalizations are the same: in both cases, constructions of the List type can be used. But how and why each of the languages ​​achieves the desired effect varies significantly.



Java generics come from the idea of ​​"type erasure." This method eliminates type parameterization when converting source code to JVM bytecode.



Suppose you have the following Java code:

 1 Vector<String> vector = new Vector<String>(); 2 vector.add(new String("hello")); 3 String str = vector.get(0); 

At compile time, it will be converted to:

 1 Vector vector = new Vector(); 2 vector.add(new String("hello")); 3 String str = (String) vector.get(0); 

The use of Java generics had virtually no effect on the functionality, but made the code more beautiful. Therefore, Java generics are often called "syntactic decoration."



With C ++ templates, the situation is completely different. Templates in C ++ are essentially a collection of macros that create a new copy of the template code for each type. This convincingly proves the fact that an instance of MyClass will not use a static variable in conjunction with an instance of MyClass. On the other hand, two instances of MyClass will share a static variable.



To illustrate this example, consider the following code:

 1 /*** MyClass.h ***/ 2 template<class T> class MyClass { 3 public: 4 static int val; 5 MyClass(int v) { val = v; } 6 }; 7 8 /*** MyClass.cpp ***/ 9 template<typename T> 10 int MyClass<T>::bar; 11 12 template class MyClass<Foo>; 13 template class MyClass<Bar>; 14 15 /*** main.cpp ***/ 16 MyClass<Foo> * foo1 = new MyClass<Foo>(10); 17 MyClass<Foo> * foo2 = new MyClass<Foo>(15); 18 MyClass<Bar> * bar1 = new MyClass<Bar>(20); 19 MyClass<Bar> * bar2 = new MyClass<Bar>(35); 20 21 int f1 = foo1->val; //   15 22 int f2 = foo2->val; //   15 23 int b1 = bar1->val; //   35 24 int b2 = bar2->val; //   35 

In Java, static variables are shared by MyClass instances regardless of type parameters.



There are other differences to Java generics and C ++ templates:



- C ++ templates can use primitive types (for example, int). For Java generics, this is not possible; they must use Integer.

‰‰ - Java allows you to limit the generalization parameters to a specific type. For example, you can use generalizations to implement CardDeck and specify that the type parameter should extend CardGame.

‰‰ - In C ++, you can create an instance of a type parameter; in Java, this is not possible.

‰‰ - In Java, the type parameter (Foo in MyClass) cannot be used for static methods and variables, as this would lead to their sharing of MyClass and MyClass. In C ++, these are different classes, so the type parameter can be used for static methods and variables.

‰‰ - In Java, all MyClass instances, regardless of their typed parameters, are of the same type. Parameters-types are “erased” at runtime. In C ++, instances with different type parameters refer to different types.



Remember that although Java generics and C ++ templates are similar in appearance, they have many differences.



13.5. Explain the differences between TreeMap, HashMap and LinkedHashMap. Give an example of a situation in which each of these collections works better than others.



DECISION



All of the listed collection classes are designed to store associative key / value pairs and support key brute force tools. The most important difference is the guarantee of temporary complexity and the ordering of keys.

‰‰

- HashMap provides search and insert for O (1) time. When sorting keys, the order of their following is actually unpredictable. The collection is implemented as an array of linked lists.

‰‰ - TreeMap provides search and insert in O (log N) time. The keys are ordered, so if they must be sorted in sorting order, this possibility exists. This means that the keys must implement the isComparable interface. The TreeMap collection is implemented as a red-black tree.

‰‰ - LinkedHashMap provides search and insert for O (1) time. Keys are arranged in order of insertion. The collection is implemented in the form of biconnected blocks.



Imagine that empty instances of TreeMap, HashMap, and LinkedHashMap are passed to the following function:

 1 void insertAndPrint(AbstractMap<Integer, String> map) { 2 int[] array = {1, -1, 0}; 3 for (int x : array) { 4 map.put(x, Integer.toString(x)); 5 } 6 7 for (int k : map.keySet()) { 8 System.out.print(k + ", "); 9 } 10 } 

Results for different collections look like this:







Very important: the results of LinkedListMap and TreeMap should look like the one shown above. For HashMap in my tests, the result was {0, 1, -1}, but the order can be anything. There are no guarantees on this score.



When ordering may be needed in a real situation?



‰‰ - Suppose you create a mapping of names to Person objects. From time to time it is required to display a list of people sorted in alphabetical order by name. TreeMap will allow you to do this.

‰‰ - The TreeMap class also provides the ability to display the following 10 people for a given name, for example, to implement the Next> button in many applications.

- The class LinkedHashMap is convenient in cases where the order of the keys must match the order of insertion. In particular, this feature is useful for organizing caching when you need to delete the oldest item.



In general, it is recommended to use HashMap, unless you have good reasons for a different choice, that is, if you need to get the keys in the order of insertion, use LinkedListMap. If keys should be returned in actual / natural order, use TreeMap. In other cases, the HashMap class is probably best suited: it usually works faster and more efficiently.



13.6. Explain what reflection is about objects in Java and what it is used for.



DECISION



Reflection (or reflection) - a mechanism for obtaining meaningful information about Java classes and objects, as well as performing the following operations:



1. Getting information about the methods and fields of the class at run time.

2. Create a new instance of the class.

3. Direct reading and writing the field values ​​of the object by reference (regardless of the access modifier).



Example of using reflection:

 1 /*  */ 2 Object[] doubleArgs = new Object[] { 4.2, 3.9 }; 3 4 /*   */ 5 Class rectangleDefinition = Class.forName("MyProj.Rectangle"); 6 7 /* : Rectangle rectangle = new Rectangle(4.2, 3.9); */ 8 Class[] doubleArgsClass = new Class[] {double.class, double.class}; 9 Constructor doubleArgsConstructor = 10 rectangleDefinition.getConstructor(doubleArgsClass); 11 Rectangle rectangle = (Rectangle) doubleArgsConstructor.newInstance(doubleArgs); 12 13 /* : Double area = rectangle.area(); */ 14 Method m = rectangleDefinition.getDeclaredMethod("area"); 15 Double area = (Double) m.invoke(rectangle); 

This code is equivalent to the following:

 1 Rectangle rectangle = new Rectangle(4.2, 3.9); 2 Double area = rectangle.area(); 

Why do you need reflection



Of course, in the example above, reflection does not seem necessary, but in some cases it is very useful. Three main reasons for applying reflection:



1. It simplifies monitoring or controlling program behavior at run time.

2. It contributes to debugging or testing programs, since we get direct access to methods, constructors, and fields.

3. It allows you to call methods by name, even if we don’t know that name beforehand. For example, a user can pass a class name, constructor parameters, and a method name, and a program uses this information to create an object and call a method. Performing similar operations without reflection will require the use of a chain of complex if commands (if it is at all possible).



13.7. There is a Country class that contains the getContinent () and getPopulation () methods. Write an int getPopulation (List countries, String continent) function that calculates the population of a given continent from the list of all countries and the name of the continent using lambda expressions.



DECISION



The solution actually consists of two parts. First you need to generate a list of countries (for example, in North America), and then calculate their total population.



Without lambda expressions, this is done quite simply.

 1 int getPopulation(List<Country> countries, String continent) { 2 int sum = 0; 3 for (Country c : countries) { 4 if (c.getContinent().equals(continent)) { 5 sum += c.getPopulation(); 6 } 7 } 8 return sum; 9 } 

To write an implementation with lambda expressions, we divide the problem into several subtasks.

First we use a filter to get a list of countries of a given continent.

 1 Stream<Country> northAmerica = countries.stream().filter( 2 country -> { return country.getContinent().equals(continent);} 3 ); 

The result is then converted into a list with populations of countries:

 1 Stream<Integer> populations = northAmerica.map( 2 c -> c.getPopulation() 3 ); 

Finally, the total population is calculated using the reduce method:

 1 int population = populations.reduce(0, (a, b) -> a + b); 

The following function gathers all the subtasks together:

 1 int getPopulation(List<Country> countries, String continent) { 2 /*   . */ 3 Stream<Country> sublist = countries.stream().filter( 4 country -> { return country.getContinent().equals(continent);} 5 ); 6 7 /*     . */ 8 Stream<Integer> populations = sublist.map( 9 c -> c.getPopulation() 10 ); 11 12 /*  . */ 13 int population = populations.reduce(0, (a, b) -> a + b); 14 return population; 15 } 

Also, due to the nature of this particular task, you can do without a filter. The reduce operation may contain logic that binds the population of countries in other continents to zero. Thus, the total contribution of other continents will not be taken into account.

 1 int getPopulation(List<Country> countries, String continent) { 2 Stream<Integer> populations = countries.stream().map( 3 c -> c.getContinent().equals(continent) ? c.getPopulation() : 0); 4 return populations.reduce(0, (a, b) -> a + b); 5 } 

Lambda functions appeared in Java 8, and if you don’t know about them, you won’t be surprised. But you have a good reason to study them.



13.8. Write a List function getRandomSubset (List list) that returns a random subset of arbitrary size. All subsets (including empty) should be selected with the same probability. When writing a function, you should use lambda expressions.



DECISION



At first glance, you can go a simple way: choose the size of the subset from 0 to N, and then generate a random set of that size.



However, this approach causes two problems:



1. Probabilities will have to assign weights. If N> 1, then the number of subsets with size N / 2 is greater than the number of subsets with size N (which, of course, is always equal to 1).

2. It is more difficult to generate a subset of a limited size (for example, 10) than to generate a subset of an arbitrary size.



Instead of generating a subset based on size, consider the task of generating based on elements. (The fact that the problem suggests using lambda expressions also suggests that you need to look for some form of busting with handling elements.)



Imagine that we iterate over the set {1, 2, 3} to create a subset. Should element 1 enter a subset?



There are two possible answers: "yes" and "no." The probabilities of choice should be assigned weights based on the proportion of subsets that include 1. So, what part of the subset contains 1?



For each individual element, the number of subsets that include it is equal to the number of subsets in which this element is not included. Consider the following example:

 {} {1} {2} {1, 2} {3} {1, 3} {2, 3} {1, 2, 3} 

Note that the subsets in the left and right columns differ only in the occurrence of 1. The number of subsets in the left and right column is the same, because one subset is converted to another by simply adding an element.



This means that to build a random subset, it is enough to go through the list and “throw a coin” (that is, to make a decision with a 50/50 probability) to decide whether each element should fall into this set.



Without lambda expressions, the implementation looks like this:

 1 List<Integer> getRandomSubset(List<Integer> list) { 2 List<Integer> subset = new ArrayList<Integer>(); 3 Random random = new Random(); 4 for (int item : list) { 5 /* / */ 6 if (random.nextBoolean()) { 7 subset.add(item); 8 } 9 } 10 return subset; 11 } 

Implementation with lambda expressions:

 1 List<Integer> getRandomSubset(List<Integer> list) { 2 Random random = new Random(); 3 List<Integer> subset = list.stream().filter( 4 k -> { return random.nextBoolean(); /* / */ 5 }).collect(Collectors.toList()); 6 return subset; 7 } 

You can also use a predicate (defined in a class or function):

 1 Random random = new Random(); 2 Predicate<Object> flipCoin = o -> { 3 return random.nextBoolean(); 4 }; 5 6 List<Integer> getRandomSubset(List<Integer> list) { 7 List<Integer> subset = list.stream().filter(flipCoin). 8 collect(Collectors.toList()); 9 return subset; 10 } 

One of the advantages of this implementation is the possibility of using the flipCoin predicate in other places.

Tasks

Task 1. Develop an algorithm for finding the smallest K numbers in an array.



DECISION



The solution to this problem can be approached in several different ways. We will consider three options: sorting, max-heap and the algorithm of ranked selection. Some of these algorithms require array modification. Discuss this point with the interviewer. However, even if the modification of the original array is unacceptable, nothing prevents you from creating a copy and modifying it - this will not affect the total complexity of the algorithm.



Solution 1. Sort



We can sort the elements in ascending order, and then take the first k elements.

 1 int[] smallestK(int[] array, int k) { 2 if (k <= 0 || k > array.length) { 3 throw new IllegalArgumentException(); 4 } 5 6 /*  . */ 7 Arrays.sort(array); 8 9 /*   k . */ 10 int[] smallest = new int[k]; 11 for (int i = 0; i < k; i++) { 12 smallest[i] = array[i]; 13 } 14 return smallest; 15 } 

The time complexity is O (n log (n)).



Solution 2: Max Heap



Also, to solve the problem, you can use the max-heap. First a max-heap is created (with the largest element at the top) for the first million numbers. Then begins the search list. Each element, if it is smaller than the root, is inserted into the heap, after which the largest element (which will be the root) is deleted. At the end of the traversal, a heap containing the million smallest numbers will be obtained. This algorithm runs in O (n log (m)) time, where m is the number of required values.

 1 int[] smallestK(int[] array, int k) { 2 if (k <= 0 || k > array.length) { 3 throw new IllegalArgumentException(); 4 } 5 6 PriorityQueue<Integer> heap = getKMaxHeap(array, k); 7 return heapToIntArray(heap); 8 } 9 10 /*    k  . */ 11 PriorityQueue<Integer> getKMaxHeap(int[] array, int k) { 12 PriorityQueue<Integer> heap = 13 new PriorityQueue<Integer>(k, new MaxHeapComparator()); 14 for (int a : array) { 15 if (heap.size() < k) { //    16 heap.add(a); 17 } else if (a < heap.peek()) { //  ,   18 heap.poll(); //   19 heap.add(a); //    20 } 21 } 22 return heap; 23 } 24 25 /*     . */ 26 int[] heapToIntArray(PriorityQueue<Integer> heap) { 27 int[] array = new int[heap.size()]; 28 while (!heap.isEmpty()) { 29 array[heap.size() - 1] = heap.poll(); 30 } 31 return array; 32 } 33 34 class MaxHeapComparator implements Comparator<Integer> { 35 public int compare(Integer x, Integer y) { 36 return y - x; 37 } 38 } 

To implement heap functionality in Java, the PriorityQueue class is used. By default, it works as a min-heap, in which at the top is the smallest element. In order to have the largest element on top, it is enough to pass another comparator.



Do you know more solutions?



Task 2. Write the function of summing two numbers without using “+” or any other arithmetic operators.



DECISION



The first thing that comes to mind in such tasks is the bitwise operations. Why? If the “+” operator cannot be used, what else is left? We will summarize the numbers as computers do!



Now we need to understand more deeply how summation works. Let us examine an additional example and try to find something interesting - to identify a pattern that could be reproduced in the code.



So, consider an additional task. For convenience, we will use the decimal number system. To sum up 759 + 674, we usually add digit [0] from each number, transfer the unit, then go to digit [1], transfer, etc. In the same way, you can work with bits: sum up all digits and, if necessary, carry units.

Is it possible to simplify the algorithm? Yes! Suppose I want to separate "summation" and "transfer".



I have to do the following.



1. Perform operation 759 + 674, “forgetting” about the transfer. The result is 323.

2. Perform operation 759 + 674, but make only transfers (without summation of digits). The result is 1110.

3. Now we need to add the results of the first two operations (using the same mechanism described in steps 1 and 2): 1110 + 323 = 1433.



Now back to the binary system.



1. If we sum a pair of binary numbers, without taking into account the transfer of the sign, then the i-th bit of the sum can be zero only if the i-th bits of the numbers a and b coincided (both had the value 0 or 1). This is a classic XOR operation.

2. If we add a pair of numbers, performing only the transfer, then the i-th bit of the sum will be equal to 1 only if the i-1st bits of both numbers (a and b) had the value 1. This is an AND operation with a shift.

3. To repeat, while there are transfers.



The following code implements this algorithm.

 1 int add(int a, int b) { 2 if (b == 0) return a; 3 int sum = a ^ b; //    4 int carry = (a & b) << 1; //    5 return add(sum, carry); //   sum + carry 6 }    . 1 int add(int a, int b) { 2 while (b != 0) { 3 int sum = a ^ b; //    4 int carry = (a & b) << 1; //    5 a = sum; 6 b = carry; 7 } 8 return a; 9 } 

Tasks related to the implementation of basic operations (addition, subtraction) are relatively common. To solve such a problem, you need to thoroughly understand how such an operation is usually performed, and then implement it anew, taking into account the set limitations.



Do you know more solutions?



Task 3. For two squares on the plane, find the line that halves the two squares. It is assumed that the upper and lower sides of the square are parallel to the x axis.



DECISION



Before we begin, we need to think about what is meant by "line." How will the line be set - the angle of inclination and the intersection point with the y axis? Two points on the line? Or does a line actually mean a segment, the beginning and end of which lie on the sides of the squares?



To make the task more interesting, we will choose the third option - the segment, the beginning and end of which lie on the sides of the squares. While at the interview, you can discuss this point with the interviewer.



The straight line, which divides two squares in half, must pass through their middle. The slope of the line is described by the formula: slope = (y1 - y2) / (x1 - x2). The same principle can be used to calculate the starting and ending points of the segment.



The following code assumes that the origin (0, 0) is in the upper left corner.

 1 public class Square { 2 ... 3 public Point middle() { 4 return new Point((this.left + this.right) / 2.0, 5 (this.top + this.bottom) / 2.0); 6 } 7 8 /*  ,   ,  mid1  mid2, 9 *    1.       mid2 10 *  mid1      . */ 11 public Point extend(Point mid1, Point mid2, double size) { 12 /*  ,     mid2 -> mid1. */ 13 double xdir = mid1.x < mid2.x ? -1 : 1; 14 double ydir = mid1.y < mid2.y ? -1 : 1; 15 16 /*   mid1  mid2  x ,    17 *    0.    . */ 18 if (mid1.x == mid2.x) { 19 return new Point(mid1.x, mid1.y + ydir * size / 2.0); 20 } 21 22 double slope = (mid1.y - mid2.y) / (mid1.x - mid2.x); 23 double x1 = 0; 24 double y1 = 0; 25 26 /*     (y1 - y2) / (x1 - x2). 27 * :  ""  (>1)   28 *    .  "" 29 *  (<1)     30 *  . */ 31 if (Math.abs(slope) == 1) { 32 x1 = mid1.x + xdir * size / 2.0; 33 y1 = mid1.y + ydir * size / 2.0; 34 } else if (Math.abs(slope) < 1) { //   35 x1 = mid1.x + xdir * size / 2.0; 36 y1 = slope * (x1 - mid1.x) + mid1.y; 37 } else { // steep slope 38 y1 = mid1.y + ydir * size / 2.0; 39 x1 = (y1 - mid1.y) / slope + mid1.x; 40 } 41 return new Point(x1, y1); 42 } 43 44 public Line cut(Square other) { 45 /*    ,  , 46 *   . */ 47 Point p1 = extend(this.middle(), other.middle(), this.size); 48 Point p2 = extend(this.middle(), other.middle(), -1 * this.size); 49 Point p3 = extend(other.middle(), this.middle(), other.size); 50 Point p4 = extend(other.middle(), this.middle(), -1 * other.size); 51 52 /*     .    53 *   (   ),   -  54 *  (   ). */ 55 Point start = p1; 56 Point end = p1; 57 Point[] points = {p2, p3, p4}; 58 for (int i = 0; i < points.length; i++) { 59 if (points[i].x < start.x || 60 (points[i].x == start.x && points[i].y < start.y)) { 61 start = points[i]; 62 } else if (points[i].x > end.x || 63 (points[i].x == end.x && points[i].y > end.y)) { 64 end = points[i]; 65 } 66 } 67 68 return new Line(start, end); 69 } 

The main goal of this task is to see how attentive you are to code writing. It is very easy to forget about special cases (when the midpoints of the squares coincide along any of the axes). You should think about the behavior of the program in special situations before you start writing code. This question requires thorough testing.



Do you know more solutions?



Publish your methods of solving problems in the comments to those who offer a constructive approach - an e-book as a gift.



»More information about the book can be found on the publisher's website.

» Table of Contents

» Excerpt



For Habrozhiteley a 25% discount on the coupon - McDowell