Donald Knuth

Donald Knuth has been described as the Euclid of computer science.

Bill Gates has praised the difficulty of the subject matter in The Art of Computer Programming, stating, “If you think you’re a really good programmer … You should definitely send me a résumé if you can read the whole thing.”

Ken Thompson

To what extent should one trust a statement that a program is free of Trojan horses? Perhaps it is more important to trust the people who wrote the software. (Reflections on Trusting Trust, Ken Thompson)

in his Turing Award lecture, he described how he had incorporated a backdoor security hole in the original UNIX C compiler. To do this, the C compiler recognized when it was recompiling itself and the UNIX login program. When it recompiled itself, it modified the compiler so the compiler backdoor was included. When it recompiled the UNIX login program, the login program would allow Thompson to always be able to log in using a fixed set of credentials.

…the fact that Ken had always wanted to write an operating system of his own was what led fairly directly to Unix (Dennis Ritchie)

Dennis Ritchie

My undergraduate experience convinced me that I was not smart enough to be a physicist, and that computers were quite neat. My graduate school experience convinced me that I was not smart enough to be an expert in the theory of algorithms and also that I liked procedural languages better than functional ones.

Bill Joy

BBN had a big contract to implement TCP/IP, but their stuff didn’t work, and grad student Joy’s stuff worked. So they had this big meeting and this grad student in a T-shirt shows up, and they said, “How did you do this?” And Bill said, “It’s very simple — you read the protocol and write the code.”

Linus Torvalds

John D. Carmack

In the information age, the barriers [to entry into programming] just aren’t there. The barriers are self imposed. If you want to set off and go develop some grand new thing, you don’t need millions of dollars of capitalization. You need enough pizza and Diet Coke to stick in your refrigerator, a cheap PC to work on, and the dedication to go through with it. We slept on floors. We waded across rivers.

Anders Hejlsberg

Anders Hejlsberg’s GitHub profile
https://github.com/ahejlsberg

Problem

160. Intersection of Two Linked Lists

Notes

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• Your code should preferably run in O(n) time and use only O(1) memory.

Java

my solution of O(n) time and O(1) memory

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;
        ListNode nodeA = headA;
        int lenA = 0;
        while (nodeA != null) {
            lenA++;
            nodeA = nodeA.next;
        }
        int lenB = 0;
        ListNode nodeB = headB;
        while (nodeB != null) {
            lenB++;
            nodeB = nodeB.next;
        }
        nodeA = headA;
        nodeB = headB;
        if (lenA < lenB) {
            for (int i = 0; i < lenB - lenA; i++) {
                nodeB = nodeB.next;
            }
        }
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                nodeA = nodeA.next;
            }
        }
        ListNode node = null;
        if (nodeA == nodeB)
            node = nodeA;
        while (nodeA != nodeB) {
            nodeA = nodeA.next;
            nodeB = nodeB.next;
            node = nodeA;
        }
        return node;
    }
}

Submission Detail

• 46 / 46 test cases passed.
• Runtime: 1 ms, faster than 98.53% of Java online submissions for Intersection of Two Linked Lists.
• Memory Usage: 41.7 MB, less than 10.90% of Java online submissions for Intersection of Two Linked Lists.

stack

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
37
38
39
40

import java.util.Deque;
import java.util.LinkedList;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;
        Deque<ListNode> stkA = new LinkedList<ListNode>();
        ListNode node = headA;
        while (node != null) {
            stkA.push(node);
            node = node.next;
        }
        Deque<ListNode> stkB = new LinkedList<ListNode>();
        node = headB;
        while (node != null) {
            stkB.push(node);
            node = node.next;
        }
        while (!stkA.isEmpty() && !stkB.isEmpty()) {
            if (stkA.peek() == stkB.peek()) {
                node = stkA.pop();
                stkB.pop();
            } else
                break;
        }
        return node;
    }
}

Submission Detail

• 46 / 46 test cases passed.
• Runtime: 2 ms, faster than 38.55% of Java online submissions for Intersection of Two Linked Lists.
• Memory Usage: 42.6 MB, less than 11.53% of Java online submissions for Intersection of Two Linked Lists.

by Helen Spalding(1920–1991)

The poem captures elements that have made primes an object of fascination since the time of Euclid. Spalding is herself a mysterious figure whose life is difficult to trace after her last publication in The London Magazine in 1961.

Let us now praise prime numbers
With our fathers who begat us:
The power, the peculiar glory of prime numbers
Is that nothing begat them,
No ancestors, no factors,
Adams among the multiplied generations.

None can foretell their coming.
Among the ordinal numbers
They do not reserve their seats, arrive unexpected.
Along the lines of cardinals
They rise like surprising pontiffs,
Each absolute, inscrutable, self-elected.

In the beginning where chaos
Ends and zero resolves,
They crowd the foreground prodigal as forest,
But middle distance thins them,
Far distance to infinity
Yields them rare as unreturning comets.

O prime improbable numbers,
Long may formula-hunters
Steam in abstraction, waste to skeleton patience:
Stay non-conformist, nuisance,
Phenomena irreducible
To system, sequence, pattern or explanation.

• Helen Spalding - “Let Us Now Praise Prime Numbers”
• Ode to Prime Numbers - BY SARAH GLAZ - Primes offer poetry both subject matter and structure.

Problem

83. Remove Duplicates from Sorted List

Java

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null)
            return head;
        ListNode node = head;
        while(node!=null) {
            if (node.next!=null && node.next.val==node.val) {
                ListNode obsoleteNode = node.next;
                node.next = node.next.next;
                obsoleteNode = null;
            }
            else
                node = node.next;
        }
        return head;
    }
}

Submission Detail

• 165 / 165 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Duplicates from Sorted List.
• Memory Usage: 38.4 MB, less than 10.24% of Java online submissions for Remove Duplicates from Sorted List.

• Linked list

Problem

876. Middle of the Linked List

Java

1

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while(node!=null) {
            list.add(node);
            node = node.next;
        }
        int n = list.size();
        return list.get(n/2);
    }
}

Submission Detail

• 15 / 15 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
• Memory Usage: 36.3 MB, less than 11.39% of Java online submissions for Middle of the Linked List.

2

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode node = head;
        while(node!=null) {
            n++;
            node = node.next;
        }
        node = head;
        n /= 2;
        while(n>0) {
            node = node.next;
            n--;
        }
        return node;
    }
}

Submission Detail

• 15 / 15 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
• Memory Usage: 36.5 MB, less than 11.39% of Java online submissions for Middle of the Linked List.

Two pointers

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slowPointer = head;
        ListNode fastPointer = head;
        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }
        return slowPointer;
    }
}

Submission Detail

• 15 / 15 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
• Memory Usage: 36 MB, less than 9.03% of Java online submissions for Middle of the Linked List.

Problem

203. Remove Linked List Elements

Java

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null)
            return head;
        ListNode previousNode = head;
        if (head != null) {
            ListNode node = head.next;
            while (node != null) {
                if (node.val == val) {
                    ListNode obsoleteNode = node;
                    previousNode.next = node.next;
                    obsoleteNode = null;
                }
                else
                    previousNode = node;
                node = node.next;
            }
        }
        if (head.val == val) {
            ListNode obsoleteNode = head;
            head = head.next;
            obsoleteNode = null;
        }
        return head;
    }
}

Submission Detail

• 65 / 65 test cases passed.
• Runtime: 1 ms, faster than 82.56% of Java online submissions for Remove Linked List Elements.
• Memory Usage: 40 MB, less than 10.13% of Java online submissions for Remove Linked List Elements.

English idioms, proverbs, and expressions are an important part of everyday English. Learning to use common idioms and expressions will make your English sound more native, so it’s a good idea to master some of these expressions.

The most common English idioms

A blessing in disguise

as part of a sentence

Meaning

a good thing that seemed bad at first

A dime a dozen

as part of a sentence

Meaning

(US) Anything that is common, inexpensive, and easy to get or available anywhere.

Beat around the bush

as part of a sentence

Meaning

• To treat a topic but omit its main points, often intentionally or to delay or avoid talking about something difficult or unpleasant.
• Avoid saying what you mean, usually because it is uncomfortable

Better late than never

by itself

Meaning

Better to arrive late than not to come at all

Bite the bullet

as part of a sentence

Meaning

• To endure a painful or unpleasant situation that is unavoidable.

Break a leg

by itself

Meaning

• A saying from the theatre that means “good luck”.
• a typical English idiom used in theatre to wish a performer “good luck”.

Call it a day

as part of a sentence

Meaning

• To declare the end of a task.
• Stop working on something

Cut somebody some slack

as part of a sentence

Meaning

Don’t be so critical

Cutting corners

as part of a sentence

Meaning

Doing something poorly in order to save time or money

Easy does it

by itself

Meaning

Slow down

Get out of hand

as part of a sentence

Meaning

Get out of control

Get something out of your systems

as part of a sentence

Meaning

Do the thing you’ve been wanting to do so you can move on

Get your act together

by itself

Meaning

Work better or leave

Give someone the benefit of the doubt

as part of a sentence

Meaning

Trust what someone says

Go back to the drawing board

as part of a sentence

Meaning

Start over

Hang in there

by itself

Meaning

Don’t give up

Hit the sack/sheets/hay

as part of a sentence

Meaning

• To go to bed; to go to sleep.

It’s not rocket science

by itself

Meaning

It’s not complicated

Let someone off the hook

as part of a sentence

Meaning

To not hold someone responsible for something

Make a long story short

as part of a sentence

Meaning

Tell something briefly

Miss the boat

as part of a sentence

Meaning

It’s too late

No pain, no gain

by itself

Meaning

You have to work for what you want

On the ball

as part of a sentence

Meaning

Doing a good job

Pull someone’s leg

as part of a sentence

Meaning

• To tease or joke by telling a lie.
• The phrase, from Scotland, originally meant to make a fool of someone, often by cheating them.
• To joke with someone

Pull yourself together

by itself

Meaning

Calm down

So far so good

by itself

Meaning

Things are going well so far

Speak of the devil

by itself

Meaning

• the short form of the English-language idiom “Speak of the devil and he doth appear” (or its alternative form “speak of the devil and he shall appear”).
• The form “talk of the devil” is also in use in England. It is used when an object of discussion unexpectedly becomes present during the conversation.

That’s the last straw

by itself

Meaning

• My patience has run out
• The last straw is an idiom referring to the Straw that broke the camel’s back.

The best of both worlds

as part of a sentence

Meaning

An ideal situation

Time flies when you’re having fun

by itself

Meaning

You don’t notice how long something lasts when it’s fun

To get bent out of shape

as part of a sentence

Meaning

To get upset

To make matters worse

as part of a sentence

Meaning

Make a problem worse

Under the weather

as part of a sentence

Meaning

• Feeling sick or poorly.
• From under the weather bow (“affected by bad weather; seasick”); weather bow is a nautical term referring to the side of a ship exposed to bad weather.

We’ll cross that bridge when we come to it

by itself

Meaning

Let’s not talk about that problem right now

Wrap your head around something

as part of a sentence

Meaning

Understand something complicated

You can say that again

by itself

Meaning

• That is very true; an expression of wholehearted agreement.
• (idiomatic, in response to another person) That is very true.

Your guess is as good as mine

by itself

Meaning

I have no idea

• English-language idioms
• English idioms

Problem

414. Third Maximum Number

Java

my solution

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

class Solution {
    public int thirdMax(int[] nums) {
        final int N = nums.length;
        int max = nums[0];
        for (int i = 1; i < N; i++) {
            if (nums[i] > max)
                max = nums[i];
        }
        int m2 = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            if (nums[i] < max && nums[i] > m2)
                m2 = nums[i];
        }
        long m3 = Long.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            if (nums[i] < m2 && nums[i] > m3)
                m3 = nums[i];
        }
        return m3 > Long.MIN_VALUE ? new Long(m3).intValue() : max;
    }
}

Submission Detail

• 26 / 26 test cases passed.
• Runtime: 1 ms, faster than 90.82% of Java online submissions for Third Maximum Number.
• Memory Usage: 39.2 MB, less than 7.88% of Java online submissions for Third Maximum Number.

PriorityQueue and HashSet

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

import java.util.*;

class Solution {
    public int thirdMax(int[] nums) {
        Queue<Integer> q = new PriorityQueue<Integer>();
        Set<Integer> set = new HashSet<Integer>();
        for (int i : nums) {
            if (!set.contains(i)) {
                set.add(i);
                q.add(i);
            }
            if (q.size() > 3) {
                set.remove(q.poll());
            }
        }
        if (q.size() < 3) {
            while (q.size() > 1)
                q.poll();
        }
        return q.peek();
    }
}

Submission Detail

• 26 / 26 test cases passed.
• Runtime: 5 ms, faster than 21.06% of Java online submissions for Third Maximum Number.
• Memory Usage: 38.7 MB, less than 10.02% of Java online submissions for Third Maximum Number.

TreeSet

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

import java.util.*;

class Solution {
    public int thirdMax(int[] nums) {
        SortedSet<Integer> treeSet = new TreeSet<Integer>();
        for (int num : nums) {
            treeSet.add(num);
            if (treeSet.size() > 3)
                treeSet.remove(treeSet.first());
        }
        return treeSet.size() < 3 ? treeSet.last() : treeSet.first();
    }
}

Submission Detail

• 26 / 26 test cases passed.
• Runtime: 4 ms, faster than 39.33% of Java online submissions for Third Maximum Number.
• Memory Usage: 38.6 MB, less than 10.02% of Java online submissions for Third Maximum Number.

javascript

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    var max=nums[0],min=nums[0];
    for(var i=1;i<nums.length;i++) {
        if (nums[i]>max)
            max = nums[i];
        if (nums[i]<min)
            min = nums[i];
    }
    var lowguard = min-1;
    var m2 = lowguard;
    for(var i=0;i<nums.length;i++) {
        if (nums[i]<max && nums[i]>m2)
            m2 = nums[i];
    }
    var m3 = lowguard;
    for(var i=0;i<nums.length;i++) {
        if (nums[i]<m2 && nums[i]>m3)
            m3 = nums[i];
    }
    return m3!=lowguard?m3:max;
};

Submission Detail

• 26 / 26 test cases passed.
• Runtime: 80 ms, faster than 72.32% of JavaScript online submissions for Third Maximum Number.
• Memory Usage: 38.9 MB, less than 5.00% of JavaScript online submissions for Third Maximum Number.

• LeetCode 414 - Third Maximum Number

Shor’s algorithm

Shor’s algorithm is a polynomial-time quantum computer algorithm for integer factorization. It was invented in 1994 by the American mathematician Peter Shor.

Shor’s algorithms runs much (almost exponentially) faster than the best-known classical algorithm for factoring, the general number field sieve.

Shor’s algorithm was the first non-trivial quantum algorithm showing a potential of ‘exponential’ speed-up over classical algorithms, It captured the imagination of many researchers who took notice of quantum computing because of its promise of truly remarkable algorithmic acceleration. Therefore, to implement Shor’s algorithm is comparable to the ‘Hello, World’ of classical computing. (Mark Ritter, senior manager of physical sciences at IBM)

Peter Shor

Shor: I’ve been writing poetry occasionally since high school, but I never considered making a career of it.

If computers that you build are quantum,
Then spies of all factions will want ‘em.
Our codes will all fail,
And they’ll read our email,
Till we’ve crypto that’s quantum, and daunt ‘em.
(by Jennifer and Peter Shor)

You can see why I chose a career as a scientist rather than as a poet.(Shor’s joke)

There are several aspects of quantum mechanics that make quantum computers more powerful than digital computers. One of these is the superposition principle, which says that a quantum system can be in more than one state at the same time. Another one of these is interference; a third is the exponentially large size of the state space of a quantum mechanical system.

There are some problems that quantum computers seem to be exponentially faster than classical computers at, like factoring. There are other problems that quantum computers don’t speed up at all, like sorting. So asking “which is better, a classical computer or a quantum computer” is like asking “which is a better transportation device, a boat or a car.” It really depends on what you want to do with it.

Grover’s algorithm

Grover’s algorithm is a quantum algorithm for searching an unstructured database or an unordered list. It was devised by Lov Grover in 1996.

Grover’s algorithm runs quadratically faster than the best possible classical algorithm for the same task, a linear search.

Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover’s algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when N is large.

Grover’s algorithm demonstrate the power of quantum parallelism, in specific, making queries in parallel.

• Quantum algorithm
• Quantum Computing for English Majors - The poet who discovered Shor’s algorithm answers questions about quantum computers and other mysteries
• The beginning of the end for encryption schemes? - New quantum computer, based on five atoms, factors numbers in a scalable way.
• QC — Grover’s algorithm

Problem

896. Monotonic Array

Java

One Pass

© Approach 3: One Pass (Simple Variant)

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean isMonotonic(int[] A) {
        boolean increasing = true;
        boolean decreasing = true;
        for (int i = 0; i < A.length - 1; i++) {
            if (A[i] > A[i + 1]) decreasing = false;
            if (A[i] < A[i + 1]) increasing = false;
        }
        return increasing || decreasing;
    }
}

Submission Detail

• 366 / 366 test cases passed.
• Runtime: 1 ms, faster than 100.00% of Java online submissions for Monotonic Array.
• Memory Usage: 47.8 MB, less than 18.59% of Java online submissions for Monotonic Array.

my solution

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

class Solution {
    public boolean isMonotonic(int[] A) {
        final int N = A.length;
        if (N<=2)
            return true;
        int[] d = new int[N-1];
        for(int i=1, j=0; i<N; i++,j++) {
            d[j] = A[i]-A[i-1];
        }
        int min=d[0],max=d[0];
        for(int i=1; i<N-1; i++) {
            if (d[i]<min) min = d[i];
            if (d[i]>max) max = d[i];
        }
        return (min<=0 && max<=0) || (min>=0 && max>=0);
    }
}

Submission Detail

• 366 / 366 test cases passed.
• Runtime: 2 ms, faster than 31.40% of Java online submissions for Monotonic Array.
• Memory Usage: 46.9 MB, less than 18.59% of Java online submissions for Monotonic Array.