Untitled
unknown
plain_text
a year ago
40 kB
11
Indexable
algorithmandstructure.algorithm.principlesandtechniques
1. CryptographicHashFunctions
1. Cryptographic hash functions (Ham bam mat ma)
Cryptographic hashes are made to work with any input of any length and type by considering it as a sequence of bits: 1
va 0. They also output a sequence of bits but of fixed length. Typically, there are a few hundred bits in the output,
so what we do is consider it as a large number in base 2, convert it to base 16, and write it as a string.
Formally, cryptographic hash functions are a specific subset of hash functions designed for secure cryptographic
applications. They possess all the properties of traditional hash functions and incorporate additional security features.
The distinctive properties of cryptographic hash functions include:
- Pre-image resistance: it is hard to find a message with a given hash value.
- Second pre-image resistance or weak collision resistance: it is difficult to find a message with the same hash value
as a given message.
- Collision resistance or strong collision resistance: it is hard to find two different messages with the same hash value.
2. Pre-image resistance
Imagine a company that stores a table of username-password pairs for a website you use. What they do is save the hash
of your password instead of the password. Now, if the table is leaked, an attacker must find a password that hashes to
the same value as your password to be able to log in as you.
So, the hash function must make it very difficult for an attacker to find such a password. Roughly speaking, even if
someone has the lock (the hash value), it would be extremely difficult or practically impossible for them to figure out
the specific key (the original input) that would open the lock. Such a function is called pre-image resistant: given a
hash value h, it is hard to find a message m with hash(m) = h
3. Second pre-image resistance
One of the ways we can make sure a message was not changed is by sending the hash of the message together with the
message itself. Suppose that an attacker wants to change the message, but cannot change the hash. Then their changed
message should hash to the same value as the original one. Even if the new message might not make sense, it can affect
communication in some ways.
To prevent such situations, we can use a second pre-image-resistant or weak collision-resistant hash function. Imagine
a person holding a unique key and a lock representing the hash function. The person and their key represent the original
input. The lock represents the hash value of that input. Second pre-image resistance means that even if someone examines
the key and the lock, it would be extremely difficult for them to find a different key that fits the lock and produces
the same hash value.
The difference between pre-image and second pre-image resistances is that in the first case we are given a hash value,
while here, we are given a message.
4. Collision resistance
A hash function that makes sure it is hard to find any messages m1, m2 such that hash(m1) = hash(m2) is called
collision-resistant or strong collision-resistant.
In simple words, collision resistance ensures that it is extremely difficult to find two keys that can open the same
safe or produce the same hash value. Unlike the second pre-image resistance, here we are given nothing; we simply want
to make it difficult to find pairs of distinct messages with equal hash values.
5. Examples
First, let's look at MD5. It was created in 1992 as a better alternative to its predecessor, MD4, which turned out to be
non-pre-image resistant due to its linear structure (2008). MD5 takes any input and outputs a 128-bit hash value.
Initially, it was believed to be collision-resistant, but in 2004 it was proved that it wasn't the case. It took 12
years and a lot of research to find this, so it's better to stick with existing hashes than try to create new ones!
Another cryptographic hash function, a more secure one, is SHA256, also known as "SHA-2" or "SHA-256 bit". Its output is
256-bit long and is used in many places, one of them being the Bitcoin proof of work. Let's look at some examples and
see what small changes in the input do to the hash value:
SHA256("Hashes are fun!") = c128f0e84f60397828b11eaa3cbb67262b99f4d11f3ad630139ffa36cc600278
SHA256("Hashes are fun.") = b2cde78b638667158fb91d0c665d1d20cc247925b45d9eccb7d25c08721fea12
SHA256("Hashes are fnu!") = c75bb5fed45a21695e0c607376cc1c925939a02c38fac8e7d5488b8820487bca
######################################
2. HashTable
1. Hash tables
Hash tables are arrays where each entry is a bucket (Thùng). Buckets can hold 0 or more values of a type. They are
identified by their index in the array.
If we want to insert a value in the hash table, we compute its hash value and insert it in the bucket at an index equal
to the hash value (modulo the size of the array). You can do the same to remove an object or search for it.
2. Hash set vs hash map
There are two types of hash tables. The one above is called a hash set. We can use it in scenarios where we only need
to check if a value is present.
Implementations of hash sets are unordered_set in C++ and HashSet in Java.
Another type of hash table is a hash map. They are very similar to hash sets, but they store pairs. The first entry in
the pair is called the key, and the second is the value. Only the hash of the key is used.
Implementations of hash maps are unordered_map in C++ and HashMap in Java.
######################################
3. SimplisticHashFunction
1. Integers
One approach is to use the identity function, in other words h(x) = x or the modulo operation h(x) = x % p.
The first function seems to be flawless: maximum speed, as we don't calculate anything; obviously deterministic and
uniform with no collisions. However, its disadvantage is the wide range of hash values, and this is where the modulo
variation can help. In the case of modulo, the only possible hash values will be 0, 1, 2, ..., p - 1.
2. Integer arrays
Suppose we have the array [v1, v2, ..., vn] and you want to calculate its hash value. The answer is simple: pick a
number p and use the formula hn = v1 * p^(n-1) + v2 * p^(n-2) + ... + vn.
Directly calculating it this way would result in a relatively large time complexity, but we can get around this by
defining h0 = 0 and then using the following operations h(i+1) = hi * p + v(i+1). Once again, to avoid wide sets of hash
values, we can take the values modulo q. That is, we can apply the formula: h(i+1) = (hi * p + v(i+1)) mod q
3. Strings
Is it true that only integers are hashable? The answer is no! In terms of strings or string arrays, everything remains
equivalent, except we first convert the strings to integers.
For example, let's hash the string "Hash" using ASCII code:
- Firstly, we need to convert characters to integers. One way to do it is to assign to every character its corresponding
HEX ASCII code. In our case, H -> 48, a -> 61, s -> 73, h -> 68
- Notice that now we don't have to hash a string anymore, but a sequence of integers, namely [48, 61, 73, 68]
- The rest is clear, we hash this array of integers as explained in the previous section using, for instance p = 5,
q = 103
- We end up with h("Hash") = 27
##############################################
4. StringHashing
1. Building blocks
Usually, a hash for a string is calculated as follows: each symbol of the string is associated with a number, then a
hash value is computed as a sum of these numbers with some coefficients. In this topic, each symbol is associated with
its order number in the alphabet (A - 1, B - 2, ..., Z - 26).
This means that we have established a rule for converting letters to numbers. What is left to do is to choose a rule for
combining these numbers. This rule is exactly the hash function that is going to be applied to the string.
2. Linear hashing
If you think for a moment, the first rule that comes to your mind is simply adding those numbers. Formally speaking,
for a string s = s0s1..s(n-1), a linear hash function hL is defined as a sum of the symbols' associated values ci:
hL(s) = c0 + c1 + ... + c(n-1)
For example, a hash value for s = ABAC is hL(s) = 1 + 2 + 1 + 3 = 7
A disadvantage of the linear hash function is that a hash value does not depend on the order of symbols. This means that
if we reorder the symbols of a string, the hash value for the string won't change.
The smaller the number of such strings, the better the hash function. At this point, linear hashing is not the best
choice, since the limitation described above results in many collisions.
3. Polynomial hashing
Formally speaking, for a string s = s0s1..s(n-1), a polynomial hash function is defined as follows:
hP(s) = (c0 * a^0 + c1 * a^1 + ... + c(n-1) * a^(n-1)) mod m
Here, ci are the codes of each letter si; the number a is a constant, usually a prime number approximately equal to the
total number of different symbols in the alphabet; m s a constant as well, usually a big prime number.
Although the polynomial hash depends on the order of symbols in a string, collisions are still possible. However, the
probability of a collision for the polynomial hash function is estimated to be approximately 1/m. Thus, the polynomial
hash function is a relatively good choice for string hashing, even though its calculation can take considerably more
time than the linear one.
4. String hashing in practice
It is worth noting that programming languages do not use linear and polynomial hashing for their built-in methods. The
hash functions we mentioned above serve for educational purposes, as well as helping tools to build more advanced
approaches and techniques.
Various algorithms are used for string hashing in programming languages. Some of the most popular ones include:
- DJB2: The DJB2 hash function is simple and efficient. It iterates through each character in the input string,
multiplying the current hash value by a prime number and adding the ASCII value of the character. DJB2 is known for
its speed and reasonable distribution properties.
- MurmurHash: MurmurHash is a family of hash functions designed for speed and good distribution. These functions are
widely used in hash tables and other data structures. The MurmurHash algorithm applies a series of bitwise and
arithmetic operations to the input string's bytes, producing a hash code.
- SHA-256: The SHA-256 (Secure Hash Algorithm 256-bit) is a cryptographic hash function. While it's primarily designed
for security, it's also used for hashing strings in non-security contexts due to its excellent distribution properties.
SHA-256 produces a fixed-size (256-bit) hash code, which, combined with its algorithmic properties, contributes to its
high resistance to collisions.
- CityHash: CityHash is a hash function developed by Google. It is designed for performance and is particularly
efficient with short strings. CityHash utilizes a combination of hashing techniques, including multiplicative and
bitwise operations, to produce hash codes.
#########################################
fundamental.devtools.gradle
BuildingApp
1. Initializing an application
After completing the initialization, the project structure will be the following:
.
├── app
│ ├── build.gradle
│ └── src
│ ├── main
│ │ ├── java
│ │ │ └── org
│ │ │ └── hyperskill
│ │ │ └── gradleapp
│ │ │ └── App.java
│ │ └── resources
│ └── test
│ ├── java
│ │ └── org
│ │ └── hyperskill
│ │ └── gradleapp
│ │ └── AppTest.java
│ └── resources
├── gradle
│ └── wrapper
│ ├── gradle-wrapper.jar
│ └── gradle-wrapper.properties
├── gradlew
├── gradlew.bat
└── settings.gradle
2. Running the application
To start the application, you can use the run command of Gradle. To do it, invoke the gradle run command, or you can use
a Gradle wrapper script for your OS. This command will build and run the application. Here is an output example:
> Task :app:run
Hello World!
BUILD SUCCESSFUL in 623ms
2 actionable tasks: 1 executed, 1 up-to-date
If you look at the project structure again, you will see that it has some new files, including files with bytecode
(App.class, AppTest.class). Actually, Gradle built and started the App.class file when we invoked the run command.
3. Building the application
If you would like to generate a bundle of the application with all its dependencies and a script to start the
application, use the gradle build command.
BUILD SUCCESSFUL in 1s
7 actionable tasks: 7 executed
If everything is OK, Gradle will have produced the archive in two formats for you: app/build/distributions/app.tar and
app/build/distributions/app.zip. Now, you can distribute your application!
#################################
data.collections.framework
1. TheComparator
import java.time.LocalDate;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class TheComparator {
static void customDataType() {
class Message {
private final String content;
public Message(String content) {
this.content = content;
}
public String getContent() {
return content;
}
@Override
public String toString() {
return content;
}
}
List<Message> messages = new ArrayList<>();
messages.add(new Message("Hello"));
messages.add(new Message("humans!"));
messages.add(new Message("We"));
messages.add(new Message("came"));
messages.add(new Message("in"));
messages.add(new Message("peace!"));
// If we try to sort the list of these Message objects, we will get a compilation error, because our Message
// class does not support any methods that allow for comparing its instances. To solve this issue, let's create
// a Comparator that will define a sorting order for objects of the Message class.
}
static void theComparator() {
class Message {
private final String content;
public Message(String content) {
this.content = content;
}
public String getContent() {
return content;
}
@Override
public String toString() {
return content;
}
}
class MessageContentComparator implements Comparator<Message> {
@Override
public int compare(Message message1, Message message2) {
int firstLength = message1.getContent().length();
int secondLength = message2.getContent().length();
return Integer.compare(firstLength, secondLength);
}
}
List<Message> messages = new ArrayList<>();
messages.add(new Message("Hello"));
messages.add(new Message("humans!"));
messages.add(new Message("We"));
messages.add(new Message("came"));
messages.add(new Message("in"));
messages.add(new Message("peace!"));
// n the context of Java, the natural order is the order defined by the compareTo method of the Comparable
// interface.
messages.sort(new MessageContentComparator());
messages.forEach(System.out::println);
}
static void multipleFields() {
class Message {
private final String from;
private final String content;
private final LocalDate created;
private int likes;
public Message(String from, String content, int likes, String created) {
this.from = from;
this.content = content;
this.likes = likes;
this.created = LocalDate.parse(created);
}
// getters
public String getFrom() {
return from;
}
public String getContent() {
return content;
}
public LocalDate getCreated() {
return created;
}
public int getLikes() {
return likes;
}
@Override
public String toString() {
return created.toString() + " " + from + " wrote: " +
content + " (" + likes + ")";
}
}
class MessageDateComparator implements Comparator<Message> {
@Override
public int compare(Message message1, Message message2) {
return message1.getCreated().compareTo(message2.getCreated());
}
}
class MessageAuthorComparator implements Comparator<Message> {
@Override
public int compare(Message message1, Message message2) {
return message1.getFrom().compareTo(message2.getFrom());
}
}
List<Message> messages = new ArrayList<>();
messages.add(new Message("Alien", "Hello humans!",
32, "2034-03-25"));
messages.add(new Message("Pirate", "All hands on deck!",
-2, "2034-01-05"));
messages.add(new Message("User765214", "Bump!",
1, "2033-02-17"));
messages.add(new Message("Unregistered", "This message was marked as spam",
-18, "2033-01-14"));
// By date:
messages.sort(new MessageDateComparator());
messages.forEach(System.out::println);
// By author's name:
messages.sort(new MessageAuthorComparator());
messages.forEach(System.out::println);
// with a suitable Comparator, we can apply any sorting logic to any class.
}
static void java8Features() {
class Message {
private final String from;
private final String content;
private final LocalDate created;
private int likes;
public Message(String from, String content, int likes, String created) {
this.from = from;
this.content = content;
this.likes = likes;
this.created = LocalDate.parse(created);
}
// getters
public String getFrom() {
return from;
}
public String getContent() {
return content;
}
public LocalDate getCreated() {
return created;
}
public int getLikes() {
return likes;
}
@Override
public String toString() {
return created.toString() + " " + from + " wrote: " +
content + " (" + likes + ")";
}
}
List<Message> messages = new ArrayList<>();
messages.add(new Message("Alien", "Hello humans!",
32, "2034-03-25"));
messages.add(new Message("Pirate", "All hands on deck!",
-2, "2034-01-05"));
messages.add(new Message("User765214", "Bump!",
1, "2033-02-17"));
messages.add(new Message("Unregistered", "This message was marked as spam",
-18, "2033-01-14"));
// Since Comparator has only a single abstract method (SAM) (Phuong thuc equals duoc ke thua tu Object) and
// therefore is a functional interface, we can use lambda functions to create Comparator instances.
Comparator<Message> dateComparator = (m1, m2) -> m1.getCreated().compareTo(m2.getCreated());
messages.sort(dateComparator);
messages.forEach(System.out::println);
Comparator<Message> authorComparator = Comparator.comparing(Message::getFrom); // message -> message.getFrom()
messages.sort(authorComparator);
}
static void utilityMethods() {
class Message {
private final String from;
private final String content;
private final LocalDate created;
private int likes;
public Message(String from, String content, int likes, String created) {
this.from = from;
this.content = content;
this.likes = likes;
this.created = LocalDate.parse(created);
}
// getters
public String getFrom() {
return from;
}
public String getContent() {
return content;
}
public LocalDate getCreated() {
return created;
}
public int getLikes() {
return likes;
}
@Override
public String toString() {
return created.toString() + " " + from + " wrote: " +
content + " (" + likes + ")";
}
}
List<Message> messages = new ArrayList<>();
messages.add(new Message("Alien", "Hello humans!",
1, "2034-03-25"));
messages.add(new Message("Pirate", "All hands on deck!",
-2, "2034-01-05"));
messages.add(new Message("User765214", "Bump!",
1, "2033-02-17"));
messages.add(new Message("Unregistered", "This message was marked as spam",
-18, "2033-01-14"));
// Comparator also has several non-abstract methods that can be used for combining comparators to create complex
// conditions for comparing objects.
// Comparator.naturalOrder returns a Comparator of the applicable type that compares Comparable objects in the
// natural order. This means that if the class you want to compare using this method does not implement the
// Comparable interface, you will get a compilation error.
// Comparator.reverseOrder similar to the above, but compares Comparable objects using the reverse of the
// natural ordering.
// reversed is called on a Comparator and returns a new Comparator that imposes the reverse ordering of the
// affected Comparator
messages.sort(Comparator.comparing(Message::getCreated).reversed());
// Comparator.comparing accepts a function that extracts a Comparable sort key and returns a Comparator that
// compares objects by that key.
messages.sort(Comparator.comparing(Message::getFrom));
messages.sort(Comparator.comparing(message -> message.getFrom()));
// thenComparing returns a lexicographic-order comparator with a function that extracts a Comparable sort key.
messages.sort(Comparator.comparing(Message::getLikes)
.thenComparing(Message::getContent));
messages.forEach(System.out::println);
}
static void comparableVsComparator() {
// Both these interfaces provide similar functionality: they allow for comparing objects of the same class.
// Which one should you choose? It depends on many factors.
// Comparable defines the natural ordering for objects of a class implementing it. Therefore, it suits perfectly
// in the cases where we compare objects that inherently have a certain natural order, such as numbers or dates.
// In other cases, when your class has multiple properties, for example, name and age or price and userRating,
// you might be unable to define the natural order for such objects. Also, there may be a situation where a
// class whose instances are to be compared does not implement the Comparable interface and you cannot modify
// the source code of that class. In all such cases, the Comparator interface is your choice.
// Also, Comparator serves as an extension and allows for customizing the sorting process. With its help, you
// can easily redefine the natural ordering or add new rules for sorting objects. Further, it makes it possible
// to combine sorting orderings to create complex sorting logic based on different properties of objects.
}
public static void main(String[] args) {
}
}
class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public int compareTo(Person o) {
if (age == o.age) {
return name.compareTo(o.name);
}
return Integer.compare(age, o.age);
}
@Override
public String toString() {
return name + " " + age;
}
public void testCompare() {
List<Person> list = new ArrayList<>(List.of(
new Person("Thieu", 24),
new Person("Hien", 22),
new Person("Tung", 24)
));
list.sort(Person::compareTo); // list.sort((o1, o2) -> o1.compareTo(o2));
list.forEach(System.out::println);
}
}
############################################
2. SetInterface
import java.util.*;
/**
* A set is a collection of unique elements like a mathematical set. A set is significantly different from an array or
* a list since it's impossible to get an element by its index.
*/
public class SetInterface {
static void theSetInterface() {
// The Collections framework provides the Set<E> interface to represent a set as an abstract data type. It
// inherits all the methods from the Collection<E> interface but doesn't add any new ones.
// One method is worth special attention when talking about Set<E> interface, as it is often used with sets:
// retainAll(Collection<E> coll). It retains only those set elements that are contained in the specified
// collection.
// To start using a set, you need to instantiate one of its implementations: HashSet, TreeSet, and LinkedHashSet
// These are mutable sets and they use different rules for ordering elements and have some additional methods.
// There are also immutable sets, whose names are not important for programmers. They also implement the
// Set<E> interface.
// As an addition, there is a high-performance implementation EnumSet for enum types. We will not consider it
// in this topic.
}
static void immutableSet() {
// he simplest way to create a set is to invoke the of method of the Set interface.
Set<String> emptySet = Set.of();
Set<String> people = Set.of("Larry", "Kenny", "Sabrina");
Set<Integer> numbers = Set.of(100, 200, 300, 400);
// The order of elements of immutable sets is not fixed:
System.out.println(emptySet); // []
System.out.println(people); // [Kenny, Larry, Sabrina] or another order
System.out.println(numbers); // [400, 200, 300, 100] or another order
// One of the most widely used set operations is checking whether a set contains an element. Here is an example:
System.out.println(emptySet.contains("hello")); // false
System.out.println(people.contains("Sabrina")); // true
System.out.println(people.contains("John")); // false
System.out.println(numbers.contains(300)); // true
// For immutable sets, it's only possible to invoke contains, size, and isEmpty methods. All others will throw
// UnsupportedOperationException since they try to change the set.
}
static void hashSet() {
// The HashSet class represents a set backed by a hash table. It uses hash codes of elements to effectively
// store them.
// It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the
// order will remain constant over time.
Set<String> countries = new HashSet<>();
countries.add("India");
countries.add("Japan");
countries.add("Switzerland");
countries.add("Japan");
countries.add("Brazil");
System.out.println(countries); // [Japan, Brazil, Switzerland, India]
System.out.println(countries.contains("Switzerland")); // true
// The HashSet class offers constant time O(1) performance for the basic operations (add, remove, and contains),
// assuming the hash function disperses the elements properly among the buckets.
// In practice, sets are often used to check whether some elements belong to them. The HashSet class is
// especially recommended for such cases since its contains operation is highly optimized.
}
static void treeSet() {
// The TreeSet class represents a set that gives us guarantees on the order of the elements. It corresponds to
// the sorting order of the elements determined either by their natural order (if they implement the Comparable
// interface) or by specific Comparator implementation.
// The TreeSet class implements the SortedSet interface which extends the base Set interface. The SortedSet
// interface provides some new methods related to comparisons of elements:
// Comparator<? super E> comparator() returns the comparator used to order elements in the set or null if the
// set uses the natural ordering of its elements;
// SortedSet<E> headSet(E toElement) returns a subset containing elements that are strictly less than toElement
// SortedSet<E> tailSet(E fromElement) returns a subset containing elements that are greater than or equal to
// fromElement;
SortedSet<Integer> sortedSet = new TreeSet<>();
sortedSet.add(10);
sortedSet.add(15);
sortedSet.add(13);
sortedSet.add(21);
sortedSet.add(17);
System.out.println(sortedSet); // [10, 13, 15, 17, 21]
System.out.println(sortedSet.headSet(15)); // [10, 13]
System.out.println(sortedSet.tailSet(15)); // [15, 17, 21]
System.out.println(sortedSet.subSet(13,17)); // [13, 15]
System.out.println(sortedSet.first()); // minimum is 10
System.out.println(sortedSet.last()); // maximum is 21
// Note, while HashSet is much faster than TreeSet: constant-time versus log-time for most operations, it offers
// no ordering guarantees. If you need to use the operations from the SortedSet interface or if the
// value-ordered iteration is required, use TreeSet; otherwise, HashSet would be a better choice.
}
static void linkedHashSet() {
// The LinkedHashSet class represents a set with linked elements. It differs from HashSet by guaranteeing that
// the order of the elements is the same as the order they were inserted to the set. Reinserting an element
// that is already in the LinkedHashSet does not change this order.
// In some sense, LinkedHashSet is something intermediate between HashSet and TreeSet. Implemented as a hash
// table with a linked list running through it, this set provides insertion-ordered iteration and runs nearly
// as fast as HashSet.
Set<Character> characters = new LinkedHashSet<>();
for (char c = 'a'; c <= 'k'; c++) {
characters.add(c);
}
System.out.println(characters); // [a, b, c, d, e, f, g, h, i, j, k]
// The LinkedHashSet implementation spares its clients from the chaotic ordering provided by HashSet without
// incurring the increased time cost of operations associated with TreeSet. But LinkedHashSet requires more
// memory for storing elements.
}
static void setOperations() {
// getting a mutable set from an immutable one
Set<String> countries = new HashSet<>(List.of("India", "Japan", "Switzerland"));
countries.addAll(List.of("India", "Germany", "Algeria"));
System.out.println(countries); // [Japan, Algeria, Switzerland, Germany, India]
countries.retainAll(List.of("Italy", "Japan", "India", "Germany"));
System.out.println(countries); // [Japan, Germany, India]
countries.removeAll(List.of("Japan", "Germany", "USA"));
// List.of("Japan", "Germany", "USA").forEach(countries::remove);
System.out.println(countries); // [India]
// In math and other programming languages, the demonstrated set operations are known as union (addAll),
// intersection (retainAll) and difference (removeAll).
// There is also a method that allows us to check whether a set is a subset of (i.e. contained in) another set.
countries = new HashSet<>(List.of("India", "Japan", "Algeria"));
System.out.println(countries.containsAll(Set.of())); // true
System.out.println(countries.containsAll(Set.of("India", "Japan"))); // true
System.out.println(countries.containsAll(Set.of("India", "Germany"))); // false
System.out.println(countries.containsAll(Set.of("Algeria", "India", "Japan"))); // true
}
static void setEquality() {
// Two sets are equal when they contain the same elements. Equality does not depend on the types of sets
// themselves.
Objects.equals(Set.of(1, 2, 3), Set.of(1, 3)); // false
Objects.equals(Set.of(1, 2, 3), Set.of(1, 2, 3)); // true
Objects.equals(Set.of(1, 2, 3), Set.of(1, 3, 2)); // true
Set<Integer> numbers = new HashSet<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
Objects.equals(numbers, Set.of(1, 2, 3)); // true
}
public static void main(String[] args) {
}
}
############################################
StandardFunctionalInterfaces
import java.util.function.*;
/**
* Groups of functional interfaces
* <p></p>
* All functional interfaces that are presented in the java.util.function package can be divided into five groups:
* functions that accept arguments and produce results;
* operators that produce results of the same type as their arguments (a special case of function);
* predicates that accept arguments and return boolean values (boolean-valued function);
* suppliers that accept nothing and return values;
* consumers that accept arguments and return no result.
* <p></p>
* Functional interfaces from the same group may differ in the number of arguments and be generic as well as non-generic.
*
* <p></p>
* <p></p>
* Naming convention
* <p></p>
* Thanks to the naming conventions of functional interfaces in the java.util.function package, you can easily
* understand an interface characteristic just by looking at its name prefix:
*
* 1. the number of parameters that are accepted by an operation. The prefix Bi indicates that a function, a predicate,
* or a consumer accepts two parameters. Similar to the Bi prefix, Unary and Binary prefixes indicate that an operator
* accepts one or two parameters, respectively.
*
* 2. a type of input parameters. Double, Long, Int, and Obj prefixes indicate the type of input value. For example,
* the IntPredicate interface represents a predicate that accepts the value of an int type.
*
* 3. a type of output parameter. The ToDouble, ToLong, and ToInt prefixes indicate the type of output value. For
* example, the ToIntFunction<T> interface represents a function that returns the value of an int type.
*/
public class StandardFunctionalInterfaces {
static void functionsExample() {
// String to Integer function
Function<String, Integer> converter = Integer::parseInt;
converter.apply("1000"); // the result is 1000 (Integer)
// String to int function
ToIntFunction<String> anotherConverter = Integer::parseInt;
anotherConverter.applyAsInt("2000"); // the result is 2000 (int)
// (Integer, Integer) to Integer function
BiFunction<Integer, Integer, Integer> sumFunction = (a, b) -> a + b;
sumFunction.apply(2, 3); // it returns 5 (Integer)
}
static void operatorsExample() {
// Long to Long multiplier
UnaryOperator<Long> longMultiplier = val -> 100_000 * val;
longMultiplier.apply(2L); // the result is 200_000L (Long)
// int to int operator
IntUnaryOperator intMultiplier = val -> 100 * val;
intMultiplier.applyAsInt(10); // the result is 1000 (int)
// (String, String) to String operator
BinaryOperator<String> appender = (str1, str2) -> str1 + str2;
appender.apply("str1", "str2"); // the result is "str1str2"
System.out.println(BinaryOperator.minBy(String::compareTo));
}
public static void main(String[] args) {
operatorsExample();
}
}
###################################################
import java.math.BigInteger;
import java.util.Scanner;
/**
* Java Class Library provides a class called BigInteger for processing very large numbers (both positive and negative).
* The size of a stored number is only limited by the available memory.
* <p>
* The BigInteger class is immutable which means methods of the class return new instances instead of changing existing
* ones.
*/
public class MyBigInteger {
public static void main(String[] args) {
BigInteger number = new BigInteger("62957291795228763406253098");
number = BigInteger.valueOf(1_000_000_000);
BigInteger zero = BigInteger.ZERO; // 0
BigInteger one = BigInteger.ONE; // 1
BigInteger ten = BigInteger.TEN; // 10
}
public static void methodsOfBigInteger() {
BigInteger zero = BigInteger.ZERO; // 0
BigInteger one = BigInteger.ONE; // 1
BigInteger ten = BigInteger.TEN; // 10
// add
BigInteger eleven = ten.add(one);
System.out.println(eleven); // 11
System.out.println(ten); // 10, it has not changed!
// subtraction, multiplication, integer division
BigInteger nine = ten.subtract(BigInteger.ONE); // 10 - 1 = 9
BigInteger oneHundredTen = ten.multiply(eleven); // 10 * 11 = 110
BigInteger twelve = oneHundredTen.divide(nine); // integer division: 12
// negate
System.out.println(nine.negate());
// divideAndRemainder
BigInteger[] pair = oneHundredTen.divideAndRemainder(nine); // 12 and 2
// abs
BigInteger number = new BigInteger("-8");
System.out.println(number.abs()); // 8
// gcd
BigInteger three = BigInteger.valueOf(3);
BigInteger six = BigInteger.valueOf(6);
System.out.println(three.gcd(six)); // 3
}
}
class BigIntegerExercise {
public static void expressionWithLargeNumbers() {
Scanner scanner = new Scanner(System.in);
var a = scanner.nextBigInteger();
var b = scanner.nextBigInteger();
var c = scanner.nextBigInteger();
var d = scanner.nextBigInteger();
var e = a.negate().multiply(b);
var f = c.subtract(d);
System.out.println(e.add(f));
}
public static BigInteger calcDoubleFactorial(int n) {
// type your java code here
BigInteger result = BigInteger.valueOf(1);
for (int i = n; i >= 1; i -= 2) {
result = result.multiply(BigInteger.valueOf(i));
}
return result;
}
}
Leave a Comment