15.5 Exercises

Reinforcement

R-15.1 Julia just bought a new computer that uses 64-bit integers to address memory cells. Argue why Julia will never in her life be able to upgrade the main memory of her computer so that it is the maximum-size possible, assuming that you have to have distinct atoms to represent different bits.

R-15.2 Consider an initially empty memory cache consisting of four pages. How many page misses does the LRU algorithm incur on the following page request sequence: (2,3,4,1,2,5,1,3,5,4,1,2,3)?

R-15.3 Consider an initially empty memory cache consisting of four pages. How many page misses does the FIFO algorithm incur on the following page request sequence: (2,3,4,1,2,5,1,3,5,4,1,2,3)?

R-15.4 Consider an initially empty memory cache consisting of four pages. What is the maximum number of page misses that the random algorithm incurs on the following page request sequence: (2,3,4,1,2,5,1,3,5,4,1,2,3)? Show all of the random choices the algorithm made in this case.

R-15.5 Describe, in detail, algorithms for adding an item to, or deleting an item from, an $(a,b)$ tree.

R-15.6 Suppose T is a multiway tree in which each internal node has at least five and at most eight children. For what values of a and b is $T$ a valid $(a,b)$ tree?

R-15.7 For what values of d is the tree $T$ of the previous exercise an order-d B-tree?

R-15.8 Draw the result of inserting, into an initially empty order-7 B-tree, entries with keys (4,40,23,50,11,34,62,78,66,22,90,59,25,72,64,77,39,12), in this order.

Creativity

C-15.9 Describe an efficient external-memory algorithm for removing all the duplicate entries in an array list of size n.

C-15.10 Describe an external-memory data structure to implement the stack ADT so that the total number of disk transfers needed to process a sequence of k push and pop operations is $O(k/B)$.

C-15.11 Describe an external-memory data structure to implement the queue ADT so that the total number of disk transfers needed to process a sequence of k enqueue and dequeue operations is $O(k/B)$.

C-15.12 Describe an external-memory version of the PositionalList ADT (Section 7.3), with block size B, such that an iteration of a list of length n is completed using $O(n/B)$ transfers in the worst case, and all other methods of the ADT require only $O(1)$ transfers.

C-15.13 Change the rules that define red-black trees so that each red-black tree T has a corresponding $(4,8)$ tree, and vice versa.

C-15.14 Describe a modified version of the B-tree insertion algorithm so that each time we create an overflow because of a split of a node w, we redistribute keys among all of w’s siblings, so that each sibling holds roughly the same number of keys (possibly cascading the split up to the parent of w). What is the minimum fraction of each block that will always be filled using this scheme?

C-15.15 Another possible external-memory map implementation is to use a skip list, but to collect consecutive groups of $O(B)$ nodes, in individual blocks, on any level in the skip list. In particular, we define an order-d B-skip list to be such a representation of a skip list structure, where each block contains at least $⌈d/2⌉$ list nodes and at most d list nodes. Let us also choose d in this case to be the maximum number of list nodes from a level of a skip list that can fit into one block. Describe how we should modify the skip-list insertion and removal algorithms for a B-skip list so that the expected height of the structure is $O(logn/logB)$.

C-15.16 Describe how to use a B-tree to implement the Partition ADT (Section 14.7.3) so that the union and find operations each use at most $O(logn/logB)$ disk transfers.

C-15.17 Suppose we are given a sequence S of n elements with integer keys such that some elements in S are colored “blue” and some elements in S are colored “red.” In addition, say that a red element e pairs with a blue element f if they have the same key value. Describe an efficient external-memory algorithm for finding all the red-blue pairs in S. How many disk transfers does your algorithm perform?

C-15.18 Consider the page caching problem where the memory cache can hold m pages, and we are given a sequence P of n requests taken from a pool of $m + 1$ possible pages. Describe the optimal strategy for the offline algorithm and show that it causes at most $m + n/m$ page misses in total, starting from an empty cache.

C-15.19 Describe an efficient external-memory algorithm that determines whether an array of n integers contains a value occurring more than n/2 times.

C-15.20 Consider the page caching strategy based on the least frequently used (LFU) rule, where the page in the cache that has been accessed the least often is the one that is evicted when a new page is requested. If there are ties, LFU evicts the least frequently used page that has been in the cache the longest. Show that there is a sequence P of n requests that causes LFU to miss $Ω(n)$ times for a cache of m pages, whereas the optimal algorithm will miss only $O(m)$ times.

C-15.21 Suppose that instead of having the node-search function $f (d) = 1$ in an order-d B-tree T , we have $f (d) = logd$. What does the asymptotic running time of performing a search in T now become?

Projects

P-15.22 Write a Java class that simulates the best-fit, worst-fit, first-fit, and next-fit algorithms for memory management. Determine experimentally which method is the best under various sequences of memory requests.

P-15.23 Write a Java class that implements all the methods of the sorted map ADT by means of an $(a,b)$ tree, where a and b are integer constants passed as parameters to a constructor.

P-15.24 Implement the B-tree data structure, assuming a block size of 1024 and integer keys. Test the number of “disk transfers” needed to process a sequence of map operations.

1.10 Exercises

Reinforcement

R-1.1 Write a short Java method, inputAllBaseTypes, that inputs a different value of each base type from the standard input device and prints it back to the standard output device.

R-1.2 Suppose that we create an array A of GameEntry objects, which has an integer scores field, and we clone A and store the result in an array B. If we then immediately set A[4].scores equal to 550, what is the score value of the GameEntry object referenced by B[4]?

R-1.3 Write a short Java method, isMultiple, that takes two long values, n and m, and returns true if and only if n is a multiple of m, that is, $n = mi$ for some integer i.

R-1.4 Write a short Java method, isEven, that takes an int i and returns true if and only if i is even. Your method cannot use the multiplication, modulus, or division operators, however.

R-1.5 Write a short Java method that takes an integer n and returns the sum of all positive integers less than or equal to n.

R-1.6 Write a short Java method that takes an integer n and returns the sum of all the odd positive integers less than or equal to n.
R-1.7 Write a short Java method that takes an integer n and returns the sum of the squares of all positive integers less than or equal to n.

R-1.8 Write a short Java method that counts the number of vowel in a given character string.

R-1.9 Write a short Java method that uses a StringBuilder instance to remove all the punctuation from a string s storing a sentence, for example, transforming the string “Let’s try, Mike!” to “Lets try Mike”.

R-1.10 Write a Java class, Flower, that has three instance variables of type String, int, and float, which respectively represent the name of the flower, its number of petals, and price. Your class must include a constructor method that initializes each variable to an appropriate value, and your class should include methods for setting the value of each type, and getting the value of each type.

R-1.11 Modify the CreditCard class from Code Fragment 1.5 to include a method that updates the credit limit.

R-1.12 Modify the CreditCard class from Code Fragment 1.5 so that it ignores any request to process a negative payment amount.

R-1.13 Modify the declaration of the first for loop in the main method in Code Fragment 1.6 so that its charges will cause exactly one of the three credit cards to attempt to go over its credit limit. Which credit card is it?

Creativity

C-1.14 Write a pseudocode description of a method that reverses an array of n integers, so that the numbers are listed in the opposite order than they were before, and compare this method to an equivalent Java method for doing the same thing.

C-1.15 Write a pseudocode description of a method for finding the smallest and largest numbers in an array of integers and compare that to a Java method that would do the same thing.

C-1.16 Write a short program that takes as input three integers, a, b, and c, from the Java console and determines if they can be used in a correct arithmetic formula (in the given order), like “a+b = c,” “a = b - c,” or “a ∗ b = c.”

C-1.17 Write a short Java method that takes an array of int values and determines if there is a pair of distinct elements of the array whose product is even.

C-1.18 The p-norm of a vector v = (v1,v2,…,vn) in n-dimensional space is defined as kvk = qp v1p +v2p +···+vnp. For the special case of p = 2, this results in the traditional Euclidean norm, which represents the length of the vector. For example, the Euclidean norm of a two-dimensional vector with coordinates (4,3) has a Euclidean norm of √42 +32 = √16+9 = √25 = 5. Give an implementation of a method named norm such that norm(v, p) returns the p-norm value of v and norm(v) returns the Euclidean norm of v, where v is represented as an array of coordinates.

C-1.19 Write a Java program that can take a positive integer greater than 2 as input and write out the number of times one must repeatedly divide this number by 2 before getting a value less than 2.

C-1.20 Write a Java method that takes an array of float values and determines if all the numbers are different from each other (that is, they are distinct).

C-1.21 Write a Java method that takes an array containing the set of all integers in the range 1 to 52 and shuffles it into random order. Your method should output each possible order with equal probability.

C-1.22 Write a short Java program that outputs all possible strings formed by using the characters ‘c’, ‘a’, ‘t’, ‘d’, ‘o’, and ‘g’ exactly once.

C-1.23 Write a short Java program that takes two arrays a and b of length n storing int values, and returns the dot product of a and b. That is, it returns an array c of length n such that c[i] = a[i]· b[i], for i = 0,…,n - 1.

C-1.24 Modify the CreditCard class from Code Fragment 1.5 so that printSummary becomes a nonstatic method, and modify the main method from Code Fragment 1.6 accordingly.

C-1.25 Modify the CreditCard class to add a toString() method that returns a String representation of the card (rather than printing it to the console, as done by printSummary). Modify the main method from Code Fragment 1.6 accordingly to use the standard println command.

Projects

P-1.26 Write a short Java program that takes all the lines input to standard input and writes them to standard output in reverse order. That is, each line is output in the correct order, but the ordering of the lines is reversed.

P-1.27 Write a Java program that can simulate a simple calculator, using the Java console as the exclusive input and output device. That is, each input to the calculator, be it a number, like 12.34 or 1034, or an operator, like + or =, can be done on a separate line. After each such input, you should output to the Java console what would be displayed on your calculator.

P-1.28 A common punishment for school children is to write out a sentence multiple times. Write a Java stand-alone program that will write out the following sentence one hundred times: “I will never spam my friends again.” Your program should number each of the sentences and it should make eight different random looking typos.

P-1.29 The birthday paradox says that the probability that two people in a room will have the same birthday is more than half, provided n, the number of people in the room, is more than 23. This property is not really a paradox, but many people find it surprising. Design a Java program that can test this paradox by a series of experiments on randomly generated birthdays, which test this paradox for n = 5,10,15,20,…,100.

P-1.30 (For those who know Java graphical user interface methods:) Define a GraphicalTest class that tests the functionality of the CreditCard class from Code Fragment 1.5 using text fields and buttons.

I started with OCA Java SE 8 Programmer I exam last year, it took me 12 days to prepare the OCA exam. It was relatively easy to pass the OCA exam, but it was much harder to pass the OCP 11 exam. It took me roughly 3 months to get fully prepared for the ultimate 1Z0-816, namely Java SE 11 Programmer II exam, for which response to the Oracle Certified Professional: Java SE 11 Developer certification. This is by far the most difficult Java certification exam from Oracle/Sun, not just because it covers topics such as modules, functional programming, concurrent programming, IO. But also it includes some new objectives, like Java Secure Coding Guideline. For those who plan on taking the Oracle Java Certification exam, I strongly recommend you take a look at the official exam objectives before you start your study plan. Buy a good book, I think Selikoff’s book is great, I use that book for my exam preparation. Study the book chapter by chapter, or by topic, or whatever you want. Be sure to do the exercises, it will help you to consolidate your knowledge. It is also helpful to use flashcards to aid the memorization process, for example, some core APIs or some syntax rules. Don’t go directly into the quiz without studying the materials thoroughly, that will just a waste of time and energy. Because that’s very frustrating to see lots of errors. Take your time, start slowly, and gradually level up the difficulty. Below are some useful references.

真题1 某知名互联网下载服务提供商软件工程师笔试题

一、选择题
1. 访问修饰符作用范围由大到小是（ ）。

A.private-protected-default-public
B.public-protected-default-private
C.private-default-protected-public
D.public-default-protected-private

这题没什么好说，当然是选择 B 啦，初学的时候可能有点难记住，不过习惯了就记住了。后来越了解就更容易记住，根本不需要死记硬背。 default 关键字，表示访问权限的时候，其实新的规范（8以上？）改称为 ‘package private’ 可以理解为包内私有访问权限，所以限制程度就是仅次于私有。接着protected和public容易，因为public肯定是范围最宽（大）的。
关于类的访问修饰符的作用范围，Java语言规范的 8.1.1 节有：
The access modifier public pertains only to top level classes and member classes, not to local classes or anonymous classes.
The access modifier protected and private pertain only to member classes within a directly enclosing class declaration.

1. Given

class Booby {
}
class Dooby extends Booby {
}
class Tooby extends Dooby {
}

public class TestClass {
  Booby b = new Booby();
  Tooby t = new Tooby();
  public void do1(List<? super Dooby> dataList) {
    //1 INSERT CODE HERE
  }
  public void do2(List<? extends Dooby> dataList) {
    //2 INSERT CODE HERE
  }
}

and the following four statements:

1. b = dataList.get(0);
2. t = dataList.get(0);
3. dataList.add(b);
4. dataList.add(t);

What can be inserted in the above code?

• Statements 1 and 3 can inserted at //1 and Statements 2 and 4 can be inserted at //2.
• Statement 4 can inserted at //1 and Statement 1 can be inserted at //2.
• Statements 3 and 4 can inserted at //1 and Statements 1 and 2 can be inserted at //2.
• Statements 1 and 2 can inserted at //1 and Statements 3 and 4 can be inserted at //2.
• Statement 1 can inserted at //1 and Statement 4 can be inserted at //2.

Explanation

1. addData1(List<? super Dooby> dataList)
   This means that dataList is a List whose elements are of a class that is either Dooby or a super class of Dooby. We don’t know which super class of Dooby. Thus, if you try to add any object to dataList, it has to be a assignable to Dooby.
   Thus, dataList.add(b); will be invalid because b is not assignable to Dooby.
   Further, if you try to take some object out of dataList, that object will be of a class that is either Dooby or a Superclass of Dooby. Only way you can declare a variable that can be assigned the object retrieved from dataList is Object obj. Thus, t = dataList.get(0); and b = dataList.get(0); are both invalid.

2. addData2(List<? extends Dooby> dataList)
   This means that dataList is a List whose elements are of a class that is either Dooby or a subclass of Dooby. Since we don’t know which subclass of Dooby is the list composed of, there is no way you can add any object to this list.
   If you try to take some object out of dataList, that object will be of a class that is either Dooby or a subclass of Dooby and thus it can be assigned to a variable of class Dooby or its superclass.. Thus, t = dataList.get(0); is invalid.

泛型规则（JLS）
A type argument $T_1$ is said to contain another type argument $T_2$, written $T_2 <= T_1$, is the set of types denoted by $T_2$ is provably a subset of the set of types denoted by $T_1$ under the reflexive and transitive closure of the following rules(where $<:$ denotes subtyping($\S4.10$)):

• $?\space extends\space T<=\space ?\space extends \space S$ if $T <: S$
• $?\space extends \space T<=\space ?$
• $?\space super \space T<=\space ?\space super \space S$ if $T <: S$
• $?\space super \space T<=\space ?$
• $?\space super \space T<=\space ? \space extends \space Object$
• $ T<=\space T$
• $T <= \space ? \space extends \space T$
• $T <= \space ? \space super \space T$

1. Which of the following is an advantage of the Java Platform Module System? B

A. A central repository of all modules
B. Encapsulating packages
C. Encapsulating objects
D. No defined types
E. Platform independence

2. Which statement is true of the following module? D

zoo.staff
|---zoo
|-- staff
|-- Vet.java

A. The directory structure shown is a valid module.
B. The directory structure would be a valid module if module.java were added directly underneath zoo.staff.
C. The directory structure would be a valid module if module.java were added directly underneath zoo.
D. The directory structure would be a valid module if module-info.java were added directly underneath zoo.staff.
E. The directory structure would be a valid module if module-info.java were added directly underneath zoo.
F. None of these changes would make this directory structure a valid module.

解释： Modules are required to have a module-info.java file at the root directory of the module. Option D matches this requirement.

3. B

4. D -> G The -m or –module option is used to specify the module and class name. The -p or -module-path option is used to specify the location of the modules. Option D would be correct if the rest of the command were correct. However, running a program requires specifying the package name with periods (.) instead of slashes. Since the command is incorrect, option G is correct.

5. AF -> AFG Options C and D are incorrect because there is no use keyword. Options A and F are correct because opens is for reflection and uses declares an API that consumes a service. Option G is also correct as the file can be completely empty. This is just something you have to memorize.

6. BDF -> BC Packages inside a module are not exported by default, making option B correct and option A incorrect. Exporting is necessary for other code to use the packages; it is not necessary to call the main() method at the command line, making option C correct and option D incorrect. The module-info.java file has the correct name and compiles, making options E and F incorrect.

7. EF -> DG Options A, B, E, and F are incorrect because they refer to keywords that don’t exist. The requires transitive keyword is used when specifying a module to be used by the requesting module and any other modules that use the requesting module. Therefore, dog needs to specify the transitive relationship, and option G is correct. The module puppy just needs to require dog, and it gets the transitive dependencies, making option D correct.

创建工程

• greetings-service

  在 start.spring.io 选择 2.3.0 M2 版本 Spring Boot，依赖项如下

  Lombok

  RSocket

  Spring Security

• greetings-client

  客户端的依赖项也是

  Lombok

  RSocket

  Spring Security

服务端应用

GreetingsServiceApplication.java

课程计划

• 入门

• HttpClient

• Jsoup

• 案例

  dependencies {
      implementation('org.jsoup:jsoup:1.12.2')
      implementation('org.apache.httpcomponents:httpclient:4.5.2')
    
      testImplementation('org.slf4j:slf4j-log4j12:1.7.25')
      testImplementation('org.junit.jupiter:junit-jupiter:5.6.0')
  }
  

爬虫功能

从功能上来讲，爬虫一般分为数据采集，处理，存储三个部分。爬虫从一个或若干个初始页面的URL开始，获得初始页面上的URL，在抓取页面的过程中，不断从当前页面抽取新的URL放入队列，直到满足系统的一定停止条件。

• 数据采集
• 处理
• 存储

从初始页面开始，爬取这个页面里面的详细页面连接，接着是下一页，等等。

4. Given:

Path p1 = Paths.get("c:\\temp\\test1.txt");
Path p2 = Paths.get("c:\\temp\\test2.txt");

Which of the following code fragments moves the file test1.txt to test2.txt, even if test2.txt exists?

• Files.move(p1, p2);

  This will throw a java.nio.file.FileAlreadyExistsException if the file already exists.

• Files.move(p1, p2, StandardCopyOption.REPLACE_EXISTING);
• try(Files.move(p1, p2)) { }

  Files.move returns a Path object (of the destination file), which is not a resource that can be closed because it does not implement AutoCloseable interface. So this will not compile.

• try(Files.copy(p1, p2, StandardCopyOption.REPLACE_EXISTING)) { Files.delete(p1); }
• Files.copy(p1, p2, StandardCopyOption.REPLACE_EXISTING); Files.delete(p1);

Explanation
Files.copy method will copy the test1.txt into test2.txt. If test2.txt doesn’t exist, it will be created. However, Files.isSameFile method doesn’t check the contents of the file. It is meant to check if the two path objects resolve to the same file or not. In this case, they are not, and so, it will return false.
The following is brief JavaDoc description for both the methods:
public static Path copy(Path source, Path target, CopyOption... option) throws IOException

1. Unmodifiable collections using of/copyOf and Collections.unmodifiableXXX methods

java.util.List and java.util.Set have of and copyOf static factory methods that provide a convenient way to create unmodifiable lists/sets.

The of methods accept either an array or multiple individual parameters. If you pass it a collection, it will be treated as a regular object i.e. it will return a list/set containing the same collection object instead of returning a list/set containing the objects that the passed collection contains.

The copyOf, on the other hand, accepts only a Collection. It iterates through the passed Collection and adds all the elements of that Collection in the returned list/set.