Question

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

• For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Question

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Question

Give a binary string s, return the number of non-empty substrings that have the same number of 0‘s and 1‘s, and all the 0‘s and all the 1‘s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Question

An array is said to be analogous to the secret array if all of the following conditions are true:
• The length of the array is equal to the length of the secret array.
• Each integer in the array lies in the interval [lowerBound, upperBound].
• The difference between each pair of consecutive integers of the array must be equal to the difference between the respective pair of consecutive integers in the secret array. In other words, let the secret array be [s[0], s[1],…, s[n-1]] and let the analogous array be [a[0], a[1],…, a[n-1]], then (a[i-1] - a[i]) must be equal to (s[i-1] - s[i]) for each i from 1 to n -1.

Given the value of integers lowerBound and upperBound, inclusive, and the array of differences between each pair of consecutive integers of the secret array, find the number of arrays that are analogous to the secret array. If there is no array analogous to the secret array, return 0.

For example:
consecutiveDifference = [-2, -1, -2, 5]
lowerBound = 3
upperBound = 10

Note that none of the values is out of the bound. All possible analogous arrays are:
[3, 5, 6, 8, 3]
[4, 6, 7, 9, 4]
[5, 7, 8, 10, 5]

Tha answer is 3.

Source: https://leetcode.com/discuss/interview-question/1332322/amazon-online-assessment-july-2021-secret-array

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static int countAnalogousArrays(int[] consecutiveDifference, int lowerBound, int upperBound) {
    // parameter validation
    if (consecutiveDifference == null || consecutiveDifference.length < 1 || lowerBound > upperBound) {
        return 0;
    }
    int delta = 0, maxDelta = 0, minDelta = 0;
    for (int i = 0; i < consecutiveDifference.length; i++) {
        delta += consecutiveDifference[i];
        maxDelta = Math.max(maxDelta, delta);
        minDelta = Math.min(minDelta, delta);
    }
    int maxDiff = maxDelta - minDelta, boundGap = upperBound - lowerBound;
    // max difference exceeds bound gap
    if (maxDiff > boundGap) {
        return 0;
    }
    return boundGap - maxDiff;
}

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later.

Convert char to int

1
2

char c = '9';
int i = Character.getNumericValue(c);

1
2

char c = '9';
int i = c - '0';

Add zeros at the beginning of a number

1
2

int i = 640;
System.out.printf("%05d\n", i);

1

00640

Print an array

1
2

int[] a = {1,2,3,4,5,6};
System.out.println(Arrays.toString(a));

Fill an array

Use Arrays.fill(array, val) to assign values to an array.

1
2
3

int[] a = new int[10];
Arrays.fill(a, 7);
System.out.println(Arrays.toString(a));

1

[7, 7, 7, 7, 7, 7, 7, 7, 7, 7]

Convert between string and char array

1
2
3

char[] arr = {'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd'};
String s = new String(arr);
char[] arr2 = s.toCharArray();

Convert integer to string

1
2
3

String s1 = String.valueOf(i);
String s2 = Integer.toString(i, 10); // radix = 10
String s3 = String.format("%d", i);

Parse integer from string

Do not forget to catch the possible exception thrown by parseInt(). parseInt() ignores leading zeros.

1
2
3
4
5

try {
    Integer.parseInt(s, 10);
} catch (Exception ignored) {

}

1

int i = Integer.parseInt("000015640", 10); // 15640

Default initialization of an array in Java

Everything in a Java program not explicitly set to something by the programmer, is initialized to a zero value.

• For references (anything that holds an object) that is null.
• For int/short/byte/long that is a 0.
• For float/double that is a 0.0
• For booleans that is a false.
• For char that is the null character '\u0000' (whose decimal equivalent is 0).

Initialize the capacity of a List

1

List<Integer> list = new ArrayList<>(10);

In this line of code, we initialize an array list with initial capacity of 10. Note that 10 is its capacity, not its size. So we still need to add elements one by one to this list. Assessing directly without adding any elements, such as directly calling list.get(1), will cause out-of-bound exceptions.

Reverse a List

1

Collections.reverse(list);

Create a List from an array

Take the return of Array.asList() as the parameter of ArrayList constructor.

1
2

int[] array = new int[10];
ArrayList<Integer> arraylIST = new ArrayList<>(Arrays.asList(array));

Sort

• Primitive array: Arrays.sort(arr)
• Object array: Arrays.sort(integerArr, comparator)
• List: Collections.sort(list, comparator)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int[] arr = new int[]{4, 1, 5, 4, 4, 0, 6, 1, 9};
Integer[] integerArr = new Integer[]{4, 1, 5, 4, 4, 0, 6, 1, 9};
List<Integer> list = new ArrayList<Integer>(Arrays.asList(integerArr));
Arrays.sort(arr);
Arrays.sort(integerArr, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
});
Collections.sort(list, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
});

Traverse a map

Use Map.Entry or HashMap.Entry.

1
2
3
4

HashMap<Integer, Integer> hashMap = new HashMap<>();
for (HashMap.Entry<Integer, Integer> e:hashMap.entrySet()) {
    // do something
}

isLetter() and isAlphabetic()

isLetter() and isAlphabetic() are two methods of Character. The difference between them is:

• isAlphabetic() checks UPPERCASE_LETTER && LOWERCASE_LETTER && TITLECASE_LETTER && MODIFIER_LETTER && OTHER_LETTER && LETTER_NUMBER.
• isLetter() checks UPPERCASE_LETTER && LOWERCASE_LETTER && TITLECASE_LETTER && MODIFIER_LETTER && OTHER_LETTER.

The point is that isLetter() will return false given a letter number. For example, roman numeral five (the letter looks like “V”). Certainly, for the English language, the distinction makes no difference.

Use Deque over Stack for LIFO stacks

We should use Deque rather than Stack for LIFO stacks.

1
2

Deque<Integer> dstack = new ArrayDeque<>();
Stack<Integer> sstack = new Stack<>(); // not recommended

There are many reasons to prefer Deque:

• Deque is an interface but Stack is a class. So using Deque brings us more flexibility for future extension.
• Stack is synchronized but Deque is not thread-safe. In the case of no need to ensure thread safety, Deque is more efficient.
• Deque iterates elements from top to bottom. Stack iterates elements from bottom to top.
• Most important: with Stack, we can access/insert/remove arbitrary elements in the LIFO stack by indexes, stack.get(index); stack.add(index, e); stack.remove(index), which breaks the LIFO rule. Although Deque does not absolutely obey the LIFO rule, it can only access/insert/remove the first/last element in the LIFO stack.

Print multi-dimensional arrays

1
2

System.out.println(Arrays.toString(arr)); // print a 1D array
System.out.println(Arrays.deepToString(marr)); // print a multi-dimensional array

Get ceiling/floor value of a number

1
2

double ceilingValue = Math.ceil(3.1); // 4.0
double floorValue = Math.floor(3.1);  // 3.0

Note that these twoMath functions return double. Or if we need to get the ceiling value of a fraction X/Y, we can also do as the following:

1

int res = (X + Y - 1) / Y;

Sort an array/list

• Primitive array int[]: Arrays.sort
• Objective array Integer[]: Arrays.sort and optional comparator
• Objective list List<Integer>: Collections.sort and optional comparator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int[] arr = new int[]{4, 1, 5, 4, 4, 0, 6, 1, 9};
Integer[] integerArr = new Integer[]{4, 1, 5, 4, 4, 0, 6, 1, 9};
List<Integer> list = new ArrayList<Integer>(Arrays.asList(integerArr));
Arrays.sort(arr);
Arrays.sort(integerArr, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
});
Collections.sort(list, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
});

Common time complexity calculation

$$
\sum_{1}^{n}{k^2}=\frac{1}{n}{n(n+1)(2n+1)}=O(n^3)\
\sum_{1}^{n}{k^3}=(\frac{1}{2}{n(n+1)})^2=O(n^4)
$$

String manipulation

1
2
3
4

StringBuilder builder1 = new StringBuilder("abcdefg");
// if we want to delete c and add it back
builder1.deleteCharAt(2); // "abdefg"
builder1.insert(2, 'c');  // "abcdefg"

toCharArray() and getBytes()

toCharArray() is better if we are not dealing with characters outside of the Unicode BMP, which are encoded as two surrogate characters. getBytes() needs to specify encoding, which is prone to mistakes. Also, toCharArray() is faster because for Java 7 and newer, a String object contains a char array internally. toCharArray() just need to complete a copy operation.

Integer object comparison

For two Integer objects, == compares their references while < and > compare their values. To examinate whether they have the same value, we should use equals() or unbox them by intValue().

And, it is safe to use comparison operators (==, <, >) for comparing values between an int and an Integer object.

1
2
3
4
5
6
7

Integer i1 = new Integer(15640);
Integer i2 = new Integer(15640);
Integer i3 = new Integer(15440);
System.out.printf("i1 == i2 : %b\n" +
        "i1.value == i2.value : %b\n" +
        "i1.equals(i2) : %b\n" +
        "i2 > i3 : %b\n", i1 == i2, i1.intValue() == i2.intValue(), i1.equals(i2), i2 > i3);

1
2
3
4

i1 == i2 : false
i1.value == i2.value : true
i1.equals(i2) : true
i2 > i3 : true

substring()

substring(beginIndex, endIndex) returns the substring in [beginIndex, endIndex). And it is safe for beginIndex == endIndex == 0 or length.

1
2
3

String s = "hello";
System.out.println(s.substring(0, 0)); // return ""
System.out.println(s.substring(s.length(), s.length())); // return ""

indexOf()

s.indexOf(pattern, fromIndex) returns the first index of given pattern from fromIndex (inclusive). If such pattern does not exist, it returns -1.

abstract keyword

If a class is declared abstract, it means that this class may be partially implementd. Thus, Java does not allow us to instantiate an abstract class. An abstract class can implement its constructor, functions (abstract or non-abstract) and have its variables.

An abstract function cannot have body. Any classes that declare any abstract functions must also be declared abstract. Any non-abstract classes that inherit abstract functions must implement all of them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

static abstract class Node {
    int id;
    String name;

    public Node(int _id, String _name) {
        id = _id;
        name = _name;
    }

    public void printHello() {
        System.out.println("hello");
    }

    // an abstract function cannot have body
    public abstract void printWorld();
}

static class ANode extends Node {
    public ANode(int _id, String _name) {
        super(_id, _name);
    }

    // the non-abstract subclass of an abstract class must implement all inherited abstract functions
    @Override
    public void printWorld() {
        System.out.println("world");
    }
}

public static void main(String[] args) {
    // cannot instantiate an abstract class
    // Node n = new Node();
    Node n = new ANode(1, "node1");
    n.printHello();
    n.printWorld();
}

Immutable objects

String and all primitive wrapper classes (Integer, Double, Long, Character, etc.) are immutable.

Inner class and nested class

An instance of inner class can exist only within an instance of its outerClass. The instance of the inner class has direct access to the methods and fields of its outer instance. A nested class can access all static resources of its outer class.

The difference between inner class and nested class is straightforward. Inner class has non-static features. Nested class has static features.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class TestInnerNested {

    class InnerClass {
        final String name = "inner";

        public void print() {
            printHello();
        }
    }

    static class NestedClass {
        NestedClass next;

        public void print() {
            System.out.println(id);
        }
    }

    static final String id = "15640";

    private void printHello() {
        System.out.println("hello");
    }

    public static void main(String[] args) {
        // an instance of InnerClass can exist only within an instance of OuterClass
        // the instance of the inner class has direct access to the methods and fields of its outer instance
        TestInnerNested test = new TestInnerNested();
        TestInnerNested.InnerClass inner = test.new InnerClass();
        inner.print();

        // a nest class can access all static resources of its outer class
        TestInnerNested.NestedClass nested = new TestInnerNested.NestedClass();
        nested.print();
    }
}

Round a float number to n decimal places

Use DecimalFormat.

1
2
3

DecimalFormat df = new DecimalFormat("#.####");
df.setRoundingMode(RoundingMode.CEILING);
System.out.println(df.format(15640.123456)); // 15640.1235

Traverse key-value pairs in a map

Use nested class Map.Entry<>.

1
2
3
4
5

Map<Integer, String> map = new HashMap<>();
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    int key = entry.getKey();
    String value = entry.getValue();
}

assert keyword

Do Not use assert in test. They can be activated at run-time by way of the -ea option on the java command, but are not turned on by default.

Split a string into at most 2 pieces

1

String[] arr = str.split(" ", 2);

Difference between Exception and RuntimeException

Any exception that derives from Exception is a checked exception. If a function throws an Exception in its body, it should also declare this behavior in this function declaration. Whereas a class that derives from RuntimeException is un-checked. RuntimeExceptions do not need to be explicitly handled by the calling code.

Generally RuntimeExceptions are exceptions that can be prevented programmatically.

floorEntry() and lowerEntry() of TreeMap

floorEntry(key) gets the entry corresponding to the specified key; if no such entry exists, returns the entry for the greatest key less than the specified key; if no such entry exists, returns null.

lowerEntry(key) returns the entry for the greatest key less than the specified key; if no such entry exists (i.e., the least key in the Tree is greater than the specified key), returns null.

Using a custom class as a key

To use a custom class as a key in Java Map, the custom class must define its equals and hashCode methods. Though Java provides an implicit implementation of these two methods for every class, the default implementation may lead to unexpected behaviors of Map (such as failing to find an existing key when inquiring with a new object with the same fields).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

@Override
public boolean equals(Object obj) {
    if (obj == null) {
        return false;
    }
    if (obj.getClass() != this.getClass()) {
        return false;
    }
    // return ...
}

@Override
public int hashCode() {
    return Objects.hash(...);
}

Shift

Signed shift: <<, >>

Unsigned shift: <<<, >>>

Add 0x prefix when printing hex numbers

Use %#x placeholder.

1
2
3
4
5

func TestPrintHex()  {
	var i int = 0x123456
	fmt.Printf("%x\n", i)
	fmt.Printf("%#x\n", i)
}

1
2

123456
0x123456

Print the type of a variable

1
2
3

fmt.Printf("%T\n", i)
fmt.Println(reflect.Typeof(i))
fmt.Prinft("%s\n", reflect.Typeof(i).String())

Chapter-1 A Tutorial Introduction

Notes of The C programming Language

Integer Division of C

In C, integer division will truncate the result to zero, regardless of whether the result is positive or negative.

printf Conversion Specification %f

For example, %6.4f means printf should print the value as floating point, at least 6 characters wide (it means the total width) and 4 after the decimal point.

1
2
3
4
5
6
7
8
9

#include <stdio.h>

int main() {
    float printFloatWidth1 = 1111.222;
    float printFloatWidth2 = 0.2;
    printf("printFloatWidth1: %6.4f\n", printFloatWidth1);
    printf("printFloatWidth2: %6.2f\n", printFloatWidth2);
    return 0;
}

1
2

printFloatWidth1: 1111.2220
printFloatWidth2:   0.20

If the valid digits of the value cannot fill the least width, printf will fill it with spaces, as illustrated in printFloatWidth2.