Problem

141. Linked List Cycle

Java

Two pointers

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.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean b = false;
        ListNode slowPointer = head;
        ListNode fastPointer = head;
        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
            if (fastPointer != null && fastPointer.next == slowPointer) {
                b = true;
                break;
            }
        }
        return b;
    }
}

Submission Detail

• 17 / 17 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Linked List Cycle.
• Memory Usage: 39.3 MB, less than 12.07% of Java online submissions for Linked List Cycle.

extra space

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

import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean b = false;
        Set<ListNode> coll = new HashSet<ListNode>();
        ListNode node = head;
        while(node!=null) {
            if (!coll.contains(node)) {
                coll.add(node);
            }
            else {
                b = true;
                break;
            }
            node = node.next;
        }
        return b;
    }
}

Submission Detail

• 17 / 17 test cases passed.
• Runtime: 3 ms, faster than 19.93% of Java online submissions for Linked List Cycle.
• Memory Usage: 39.5 MB, less than 11.80% of Java online submissions for Linked List Cycle.

Problem

1290. Convert Binary Number in a Linked List to Integer

Java

Bit Manipulation

© Approach 2: Bit Manipulation

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 int getDecimalValue(ListNode head) {
        if (head == null)
            return 0;
        int d = head.val;
        while (head.next != null) {
            d = (d << 1) | head.next.val;
            head = head.next;
        }
        return d;
    }
}

Submission Detail

• 102 / 102 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Convert Binary Number in a Linked List to Integer.
• Memory Usage: 36.4 MB, less than 11.21% of Java online submissions for Convert Binary Number in a Linked List to Integer.

my solution

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

/**
 * 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 int getDecimalValue(ListNode head) {
        int n = 0;
        ListNode node = head;
        while (node != null) {
            n++;
            node = node.next;
        }
        node = head;
        int x = 0;
        for (int i = n - 1; i > 0; i--) {
            x += node.val * (2 << (i - 1));
            node = node.next;
        }
        x += node.val;
        return x;
    }
}

Submission Detail

• 102 / 102 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Convert Binary Number in a Linked List to Integer.
• Memory Usage: 36.4 MB, less than 10.97% of Java online submissions for Convert Binary Number in a Linked List to Integer.

On the 30th of May, 1832, a gunshot was heard ringing out across the 13th arrondissement in Paris. A peasant, who was walking to market that morning, ran towards where the gunshot had come from, and found a young man writhing in agony on the floor, clearly shot by a dueling wound. The young man’s name was Evariste Galois. He was a well-known revolutionary in Paris at the time. Galois was taken to the local hospital where he died the next day in the arms of his brother. And the last words he said to his brother were, “Don’t cry for me, Alfred. I need all the courage I can muster to die at the age of 20.”

It wasn’t, in fact, revolutionary politics for which Galois was famous. But a few years earlier, while still at school, he’d actually cracked one of the big mathematical problems at the time. And he wrote to the academicians in Paris, trying to explain his theory. But the academicians couldn’t understand anything that he wrote. This is how he wrote most of his mathematics.

So, the night before that duel, he realized this possibly is his last chance to try and explain his great breakthrough. So he stayed up the whole night, writing away, trying to explain his ideas. And as the dawn came up and he went to meet his destiny, he left this pile of papers on the table for the next generation. Maybe the fact that he stayed up all night doing mathematics was the fact that he was such a bad shot that morning and got killed.

But contained inside those documents was a new language, a language to understand one of the most fundamental concepts of science – namely symmetry. Now, symmetry is almost nature’s language. It helps us to understand so many different bits of the scientific world. For example, molecular structure. What crystals are possible, we can understand through the mathematics of symmetry.

In microbiology you really don’t want to get a symmetrical object, because they are generally rather nasty. The swine flu virus, at the moment, is a symmetrical object. And it uses the efficiency of symmetry to be able to propagate itself so well. But on a larger scale of biology, actually symmetry is very important, because it actually communicates genetic information.

I’ve taken two pictures here and I’ve made them artificially symmetrical. And if I ask you which of these you find more beautiful, you’re probably drawn to the lower two. Because it is hard to make symmetry. And if you can make yourself symmetrical, you’re sending out a sign that you’ve got good genes, you’ve got a good upbringing and therefore you’ll make a good mate. So symmetry is a language which can help to communicate genetic information.

Symmetry can also help us to explain what’s happening in the Large Hadron Collider in CERN. Or what’s not happening in the Large Hadron Collider in CERN. To be able to make predictions about the fundamental particles we might see there, it seems that they are all facets of some strange symmetrical shape in a higher dimensional space.

And I think Galileo summed up, very nicely, the power of mathematics to understand the scientific world around us. He wrote, “The universe cannot be read until we have learnt the language and become familiar with the characters in which it is written. It is written in mathematical language, and the letters are triangles, circles and other geometric figures, without which means it is humanly impossible to comprehend a single word.“

But it’s not just scientists who are interested in symmetry. Artists too love to play around with symmetry. They also have a slightly more ambiguous relationship with it. Here is Thomas Mann talking about symmetry in “The Magic Mountain.” He has a character describing the snowflake, and he says he “shuddered at its perfect precision, found it deathly, the very marrow of death.”

But what artists like to do is to set up expectations of symmetry and then break them. And a beautiful example of this I found, actually, when I visited a colleague of mine in Japan, Professor Kurokawa. And he took me up to the temples in Nikko. And just after this photo was taken we walked up the stairs. And the gateway you see behind has eight columns, with beautiful symmetrical designs on them. Seven of them are exactly the same, and the eighth one is turned upside down.

And I said to Professor Kurokawa, “Wow, the architects must have really been kicking themselves when they realized that they’d made a mistake and put this one upside down.” And he said, “No, no, no. It was a very deliberate act.” And he referred me to this lovely quote from the Japanese “Essays in Idleness” from the 14th century, in which the essayist wrote, “In everything, uniformity is undesirable. Leaving something incomplete makes it interesting, and gives one the feeling that there is room for growth.” Even when building the Imperial Palace, they always leave one place unfinished.

But if I had to choose one building in the world to be cast out on a desert island, to live the rest of my life, being an addict of symmetry, I would probably choose the Alhambra in Granada. This is a palace celebrating symmetry. Recently I took my family – we do these rather kind of nerdy mathematical trips, which my family love. This is my son Tamer. You can see he’s really enjoying our mathematical trip to the Alhambra. But I wanted to try and enrich him. I think one of the problems about school mathematics is it doesn’t look at how mathematics is embedded in the world we live in. So, I wanted to open his eyes up to how much symmetry is running through the Alhambra.

You see it already. Immediately you go in, the reflective symmetry in the water. But it’s on the walls where all the exciting things are happening. The Moorish artists were denied the possibility to draw things with souls. So they explored a more geometric art. And so what is symmetry? The Alhambra somehow asks all of these questions. What is symmetry? When [there] are two of these walls, do they have the same symmetries? Can we say whether they discovered all of the symmetries in the Alhambra?

And it was Galois who produced a language to be able to answer some of these questions. For Galois, symmetry – unlike for Thomas Mann, which was something still and deathly – for Galois, symmetry was all about motion. What can you do to a symmetrical object, move it in some way, so it looks the same as before you moved it? I like to describe it as the magic trick moves. What can you do to something? You close your eyes. I do something, put it back down again. It looks like it did before it started.

So, for example, the walls in the Alhambra – I can take all of these tiles, and fix them at the yellow place, rotate them by 90 degrees, put them all back down again and they fit perfectly down there. And if you open your eyes again, you wouldn’t know that they’d moved. But it’s the motion that really characterizes the symmetry inside the Alhambra. But it’s also about producing a language to describe this. And the power of mathematics is often to change one thing into another, to change geometry into language.

So I’m going to take you through, perhaps push you a little bit mathematically – so brace yourselves – push you a little bit to understand how this language works, which enables us to capture what is symmetry. So, let’s take these two symmetrical objects here. Let’s take the twisted six-pointed starfish. What can I do to the starfish which makes it look the same? Well, there I rotated it by a sixth of a turn, and still it looks like it did before I started. I could rotate it by a third of a turn, or a half a turn, or put it back down on its image, or two thirds of a turn. And a fifth symmetry, I can rotate it by five sixths of a turn. And those are things that I can do to the symmetrical object that make it look like it did before I started.

Now, for Galois, there was actually a sixth symmetry. Can anybody think what else I could do to this which would leave it like I did before I started? I can’t flip it because I’ve put a little twist on it, haven’t I? It’s got no reflective symmetry. But what I could do is just leave it where it is, pick it up, and put it down again. And for Galois this was like the zeroth symmetry. Actually, the invention of the number zero was a very modern concept, seventh century A.D., by the Indians. It seems mad to talk about nothing. And this is the same idea. This is a symmetrical – so everything has symmetry, where you just leave it where it is.

So, this object has six symmetries. And what about the triangle? Well, I can rotate by a third of a turn clockwise or a third of a turn anticlockwise. But now this has some reflectional symmetry. I can reflect it in the line through X, or the line through Y, or the line through Z. Five symmetries and then of course the zeroth symmetry where I just pick it up and leave it where it is. So both of these objects have six symmetries. Now, I’m a great believer that mathematics is not a spectator sport, and you have to do some mathematics in order to really understand it.

So here is a little question for you. And I’m going to give a prize at the end of my talk for the person who gets closest to the answer. The Rubik’s Cube. How many symmetries does a Rubik’s Cube have? How many things can I do to this object and put it down so it still looks like a cube? Okay? So I want you to think about that problem as we go on, and count how many symmetries there are. And there will be a prize for the person who gets closest at the end.

But let’s go back down to symmetries that I got for these two objects. What Galois realized: it isn’t just the individual symmetries, but how they interact with each other which really characterizes the symmetry of an object. If I do one magic trick move followed by another, the combination is a third magic trick move. And here we see Galois starting to develop a language to see the substance of the things unseen, the sort of abstract idea of the symmetry underlying this physical object. For example, what if I turn the starfish by a sixth of a turn, and then a third of a turn?

So I’ve given names. The capital letters, A, B, C, D, E, F, are the names for the rotations. B, for example, rotates the little yellow dot to the B on the starfish. And so on. So what if I do B, which is a sixth of a turn, followed by C, which is a third of a turn? Well let’s do that. A sixth of a turn, followed by a third of a turn, the combined effect is as if I had just rotated it by half a turn in one go. So the little table here records how the algebra of these symmetries work. I do one followed by another, the answer is it’s rotation D, half a turn. What I if I did it in the other order? Would it make any difference? Let’s see. Let’s do the third of the turn first, and then the sixth of a turn. Of course, it doesn’t make any difference. It still ends up at half a turn.

And there is some symmetry here in the way the symmetries interact with each other. But this is completely different to the symmetries of the triangle. Let’s see what happens if we do two symmetries with the triangle, one after the other. Let’s do a rotation by a third of a turn anticlockwise, and reflect in the line through X. Well, the combined effect is as if I had just done the reflection in the line through Z to start with. Now, let’s do it in a different order. Let’s do the reflection in X first, followed by the rotation by a third of a turn anticlockwise. The combined effect, the triangle ends up somewhere completely different. It’s as if it was reflected in the line through Y.

Now it matters what order you do the operations in. And this enables us to distinguish why the symmetries of these objects – they both have six symmetries. So why shouldn’t we say they have the same symmetries? But the way the symmetries interact enable us – we’ve now got a language to distinguish why these symmetries are fundamentally different. And you can try this when you go down to the pub, later on. Take a beer mat and rotate it by a quarter of a turn, then flip it. And then do it in the other order, and the picture will be facing in the opposite direction.

Now, Galois produced some laws for how these tables – how symmetries interact. It’s almost like little Sudoku tables. You don’t see any symmetry twice in any row or column. And, using those rules, he was able to say that there are in fact only two objects with six symmetries. And they’ll be the same as the symmetries of the triangle, or the symmetries of the six-pointed starfish. I think this is an amazing development. It’s almost like the concept of number being developed for symmetry. In the front here, I’ve got one, two, three people sitting on one, two, three chairs. The people and the chairs are very different, but the number, the abstract idea of the number, is the same.

And we can see this now: we go back to the walls in the Alhambra. Here are two very different walls, very different geometric pictures. But, using the language of Galois, we can understand that the underlying abstract symmetries of these things are actually the same. For example, let’s take this beautiful wall with the triangles with a little twist on them. You can rotate them by a sixth of a turn if you ignore the colors. We’re not matching up the colors. But the shapes match up if I rotate by a sixth of a turn around the point where all the triangles meet. What about the center of a triangle? I can rotate by a third of a turn around the center of the triangle, and everything matches up. And then there is an interesting place halfway along an edge, where I can rotate by 180 degrees. And all the tiles match up again. So rotate along halfway along the edge, and they all match up.

Now, let’s move to the very different-looking wall in the Alhambra. And we find the same symmetries here, and the same interaction. So, there was a sixth of a turn. A third of a turn where the Z pieces meet. And the half a turn is halfway between the six pointed stars. And although these walls look very different, Galois has produced a language to say that in fact the symmetries underlying these are exactly the same. And it’s a symmetry we call 6-3-2.

Here is another example in the Alhambra. This is a wall, a ceiling, and a floor. They all look very different. But this language allows us to say that they are representations of the same symmetrical abstract object, which we call 4-4-2. Nothing to do with football, but because of the fact that there are two places where you can rotate by a quarter of a turn, and one by half a turn.

Now, this power of the language is even more, because Galois can say, “Did the Moorish artists discover all of the possible symmetries on the walls in the Alhambra?” And it turns out they almost did. You can prove, using Galois’ language, there are actually only 17 different symmetries that you can do in the walls in the Alhambra. And they, if you try to produce a different wall with this 18th one, it will have to have the same symmetries as one of these 17.

But these are things that we can see. And the power of Galois’ mathematical language is it also allows us to create symmetrical objects in the unseen world, beyond the two-dimensional, three-dimensional, all the way through to the four- or five- or infinite-dimensional space. And that’s where I work. I create mathematical objects, symmetrical objects, using Galois’ language, in very high dimensional spaces. So I think it’s a great example of things unseen, which the power of mathematical language allows you to create.

So, like Galois, I stayed up all last night creating a new mathematical symmetrical object for you, and I’ve got a picture of it here. Well, unfortunately it isn’t really a picture. If I could have my board at the side here, great, excellent. Here we are. Unfortunately, I can’t show you a picture of this symmetrical object. But here is the language which describes how the symmetries interact.

Now, this new symmetrical object does not have a name yet. Now, people like getting their names on things, on craters on the moon or new species of animals. So I’m going to give you the chance to get your name on a new symmetrical object which hasn’t been named before. And this thing – species die away, and moons kind of get hit by meteors and explode – but this mathematical object will live forever. It will make you immortal. In order to win this symmetrical object, what you have to do is to answer the question I asked you at the beginning. How many symmetries does a Rubik’s Cube have?

Okay, I’m going to sort you out. Rather than you all shouting out, I want you to count how many digits there are in that number. Okay? If you’ve got it as a factorial, you’ve got to expand the factorials. Okay, now if you want to play, I want you to stand up, okay? If you think you’ve got an estimate for how many digits, right – we’ve already got one competitor here. If you all stay down he wins it automatically. Okay. Excellent. So we’ve got four here, five, six. Great. Excellent. That should get us going. All right.

Anybody with five or less digits, you’ve got to sit down, because you’ve underestimated. Five or less digits. So, if you’re in the tens of thousands you’ve got to sit down. 60 digits or more, you’ve got to sit down. You’ve overestimated. 20 digits or less, sit down. How many digits are there in your number? Two? So you should have sat down earlier. (Laughter) Let’s have the other ones, who sat down during the 20, up again. Okay? If I told you 20 or less, stand up. Because this one. I think there were a few here. The people who just last sat down.

Okay, how many digits do you have in your number? (Laughs) 21. Okay good. How many do you have in yours? 18. So it goes to this lady here. 21 is the closest. It actually has – the number of symmetries in the Rubik’s cube has 25 digits. So now I need to name this object. So, what is your name? I need your surname. Symmetrical objects generally – spell it for me. G-H-E-Z No, SO2 has already been used, actually, in the mathematical language. So you can’t have that one. So Ghez, there we go. That’s your new symmetrical object. You are now immortal. (Applause)

And if you’d like your own symmetrical object, I have a project raising money for a charity in Guatemala, where I will stay up all night and devise an object for you, for a donation to this charity to help kids get into education in Guatemala. And I think what drives me, as a mathematician, are those things which are not seen, the things that we haven’t discovered. It’s all the unanswered questions which make mathematics a living subject. And I will always come back to this quote from the Japanese “Essays in Idleness”: “In everything, uniformity is undesirable. Leaving something incomplete makes it interesting, and gives one the feeling that there is room for growth.” Thank you. (Applause)

Go to the roots of these calculations! Group the operations. Classify them according to their complexities rather than their appearances! This, I believe, is the mission of future mathematicians. This is the road on which I am embarking in this work.

Ne pleure pas, Alfred ! J’ai besoin de tout mon courage pour mourir à vingt ans ! (Don’t cry, Alfred! I need all my courage to die at twenty!) - Évariste Galois(1811 – 1832)

No episode in the history of thought is more moving than the life of Evariste Galois — the young Frenchman who passed like a meteor about 1828, devoted a few feverish years to the most intense meditation, and died in 1832 from a wound received in a duel, at the age of twenty. He was still a mere boy, yet within these short years he had accomplished enough to prove indubitably that he was one of the greatest mathematicians of all time. When one sees how terribly fast this ardent soul, this wretched
and tormented heart, were consumed, one can but think of the beautiful meteoric showers of a summer night. But this comparison is misleading, for the soul of Galois will burn on throughout the ages and be a perpetual flame of inspiration. His fame is incorruptible; indeed the apotheosis will become more and more splendid with the gradual increase of human knowledge. (George Sarton)

The Paris circles with their intensive mathematical enterprise, produced around 1830 with Evariste Galois a genius of the highest quality, who, like a comet, vanished just as fast as he had appeared. (Dirk Jan Struik)

In many ways, Galois is to be regarded as the father of modern algebra.

Several hundred years passed without anyone finding a radical formula for the roots of a general quintic polynomial. There was a good reason for this. There is no such formula. Nor is there a formula for polynomials of degree greater than 5. This fact was first established in the early nineteenth century by Abel(who died aged twenty-six), after which Galois(who died aged twenty-one) built an entirely new theory of equations that not only explained the nonexistence of formulas but laid the foundations for a whole edifice of algebra and number theory known as Galois theory, a major area of modern-day research. (The Princeton Companion to Mathematics - Part V Theorems and Problems, V.21 The Insolubility of the Quintic, by Martin W. Liebeck)

The great Austrian mathematician Emil Artin wrote about Galois, “Since my mathematical youth, I have been under the spell of the classical theory of Galois. This charm has forced me to return to it again and again.”

Galois’s invention of groups was a stroke of genius. After all, the great mathematician Abel, who worked on the problem of solvability by radicals at the same time, did not come up with group theory. Indeed, only Cauchy, on his return to France in the 1840s, seemed to appreciate Galois’s achievement, and Cauchy’s intense group theoretical studies led to the use of group theory in other fields of mathematics. (Joseph Rotman, the University of Illinois)

Galois wrote three letters the night before he was entangled in the game of Russian roulette that led to his death. One of these had further details of the brilliant mathematical theory he had developed. Mathematician Hermann Weyl said of this testament, “This letter, if judged by the novelty and profundity of ideas it contains, is perhaps the most substantial piece of writing in the whole literature of mankind.” After his tragic death, his brother passed his papers to a leading French mathematician, Joseph Liouville, who edited Galois’s collected works for publication in 1846. Only then did his extraordinary brilliance become apparent to the mathematical world.

The main object of Évariste Galois’s investigations is the conditions of solvability of equations by radicals. The author constructs the fundamentals of a general theory which he applies in detail to any equation whose power is a prime number. ・・・ my diligence was rewarded and I felt extraordinary content at the moment when, having made some minor corrections, was convinced in the validity of the method Galois used to prove this beautiful theorem. (Joseph Liouville)

But Liouville’s article was still too far-fetched for other mathematicians to enjoy and understand. It took another 24 years to find a French mathematician outstanding enough to better understand Galois and make his ideas limpid. This outstanding mathematician is Camille Jordan. In fact, Jordan’s 1870 book on Galois theory was so well-written that German mathematician Felix Klein found it as readable as a German book!

It would take another 82 years for the great Austrian mathematician Emil Artin to finally give the Galois theory its modern form.

Instead of using infinite groups, Galois began with a particular equation and constructed his group from a handful of solutions to the equation. It was groups from the solutions to quintic equations which allowed Galois to derive his results about these equations. A century and a half later, Wiles would use Galois’s work as the foundation for his proof of the Taniyama—Shimura conjecture. (Fermat’s Last Theorem, Simon Singh)

There is a general principle, which is very fruitful in mathematics that if you want to learn something about a mathematical object, investigate its automorphism group (Symmetry, Hermann Weyl)

Galois theory paved the way for modern algebraic thinking.

Galois theory is a very difficult topic usually only introduced in the final year of an undergraduate mathematics degree.

Felix Klein: There is a contradiction here that should be deplored by both students and teachers. On the one hand, instructors are eager to teach Galois theory because of the brilliance of its discovery and the far-reaching nature of its results; on the other hand, this subject presents immense difficulties to the average beginner’s understanding. In most cases the sad result is that the instructors’ inspired and enthusiastic efforts make no impression on most of the audience, awaken no understanding. The particular difficulty of the task which Galois theory presents to the expositor must bear its share of the blame for this result.

Galois theory is a very big subject, and until you are quite immersed in mathematical study in a way which is unusual unless studying for a degree in maths, it can seem quite pointless.

To understand Galois theory, you have to be comfortable with vector spaces and finite group theory. If you are not comfortable with those concepts, you should learn those first. Do not attempt to study Galois theory or any mathematical subject before you’ve mastered the prerequisites. It’s pointless, frustrating, and damaging.

Before embarking on the study of Galois theory, you will need to have mastered basic linear algebra really well, up to and including linear algebra over arbitrary fields, the idea of dimension, linear transformations, kernels, images, subspaces, bases and linear independence.

A better preparation includes knowing about groups, homomorphisms, the isomorphism theorems, permutations and parity, cyclic groups, abelian groups and ideally solvable groups. A good first course in group theory will make it a lot easier for you.

• Trying to understand the Galois correspondence
• The Revolutionary Galois Theory
• What is Galois Theory Anyway?
• An Introduction to Galois Theory
• Galois Theory
• What is the best way to learn Galois theory?
• The tragic, brief life of Évariste Galois
• Galois Groups and the Symmetries of Polynomials
• For the Love of Mathematics
• ‘Groups’ Underpin Modern Math. Here’s How They Work.
• Galois’ Enduring Legacy

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.