LeetCode - Algorithms - 207. Course Schedule

my exercises is to find solutions which can help me to understand these puzzle algorithms.

Problem

207. Course Schedule

scheduling problem with precedence constraints.

key

  • DAG: a digraph with no directed cycles.
  • A digraph has a topological order if and only if it is a DAG.
  • Is a given digraph a DAG ?
  • Depth-first search

Java

DFS

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Edge> edges = new ArrayList<Edge>();
for(int i=0; i<prerequisites.length; i++) {
edges.add(new Edge(prerequisites[i][0],prerequisites[i][1]));
}
Graph graph = new Graph(edges, numCourses);
return isDAG(graph, numCourses);
}

private boolean isDAG(Graph graph, int N) {
boolean[] discovered = new boolean[N];

int[] departure = new int[N];

int time = 0;

for (int i = 0; i < N; i++)
if (discovered[i] == false)
time = DFS(graph, i, discovered, departure, time);

for (int u = 0; u < N; u++) {
for (int v : graph.adjList.get(u)) {
if (departure[u] <= departure[v])
return false;
}
}
return true;
}

private int DFS(Graph graph, int v, boolean[] discovered, int[] departure, int time) {
discovered[v] = true;

for (int u : graph.adjList.get(v)) {
if (!discovered[u])
time = DFS(graph, u, discovered, departure, time);
}

departure[v] = time++;

return time;
}
}

class Edge {
int source, dest;

public Edge(int source, int dest) {
this.source = source;
this.dest = dest;
}
}

class Graph {
List<List<Integer>> adjList = null;

Graph(List<Edge> edges, int N) {
adjList = new ArrayList<>(N);

for (int i = 0; i < N; i++) {
adjList.add(i, new ArrayList<>());
}

for (Edge edge : edges) {
adjList.get(edge.source).add(edge.dest);
}
}
}

Submission Detail

  • 42 / 42 test cases passed.
  • Runtime: 5 ms, faster than 69.31% of Java online submissions for Course Schedule.
  • Memory Usage: 44.6 MB, less than 94.62% of Java online submissions for Course Schedule.

ref

LeetCode - Algorithms - 77. Combinations

just run code of others.

Problem

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Java

Iterative Algorithm

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
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combinations = new ArrayList<List<Integer>>();

int[] combination = new int[k];
for (int i = 0; i < k; i++) {
combination[i] = i;
}

while (combination[k - 1] < n) {
List<Integer> comblist = new ArrayList<Integer>();
for(int i=0; i<combination.length; i++) {
comblist.add(combination[i]+1);
}
combinations.add(comblist);
int t = k - 1;
while (t != 0 && combination[t] == n - k + t) {
t--;
}
combination[t]++;
for (int i = t + 1; i < k; i++) {
combination[i] = combination[i - 1] + 1;
}
}

return combinations;
}
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 3 ms, faster than 88.15% of Java online submissions for Combinations.
  • Memory Usage: 39.7 MB, less than 80.43% of Java online submissions for Combinations.

ref

LeetCode - Algorithms - 46. Permutations

just verify code of other peer.

Problem

46. Permutations

Given a collection of distinct integers, return all possible permutations.

Java

BASIC ALGORITHM 1: REMOVE

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
import java.util.ArrayList;
import java.util.List;

class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
permutation_remove(nums,nums.length,list);
return list;
}

private void permutation_remove(int[] a, int n, List<List<Integer>> list) {
if (n == 1) {
List<Integer> x = new ArrayList<Integer>();
for(int i=0;i<a.length;i++)
x.add(new Integer(a[i]));
list.add(x);
return;
}
for (int i = 0; i < n; i++) {
swap(a, i, n - 1);
permutation_remove(a, n - 1, list);
swap(a, i, n - 1);
}
}

private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}

Submission Detail

  • 25 / 25 test cases passed.
  • Runtime: 1 ms, faster than 97.52% of Java online submissions for Permutations.
  • Memory Usage: 38 MB, less than 82.98% of Java online submissions for Permutations.

HEAP’S ALGORITHM

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
import java.util.ArrayList;
import java.util.List;

class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
permutation_heaps(nums,nums.length,list);
return list;
}

private void permutation_heaps(int[] a, int n, List<List<Integer>> list) {
if (n == 1) {
List<Integer> x = new ArrayList<Integer>();
for(int i=0;i<a.length;i++)
x.add(new Integer(a[i]));
list.add(x);
return;
}
for (int i = 0; i < (n - 1); i++) {
permutation_heaps(a, n - 1, list);
if (n % 2 == 0)
swap(a, n - 1, i);
else
swap(a, n - 1, 0);
}
permutation_heaps(a, n - 1, list);
}

private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}

Submission Detail

  • 25 / 25 test cases passed.
  • Runtime: 1 ms, faster than 97.52% of Java online submissions for Permutations.
  • Memory Usage: 36.3 MB, less than 98.58% of Java online submissions for Permutations.

ref

LeetCode - Algorithms - 49. Group Anagrams

Problem

49. Group Anagrams

Given an array of strings, group anagrams together.

JavaScript

solution by Joan Indiana Lyness

Algorithms 101: Group Anagrams in JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
var m = {};
for(var i=0;i<strs.length;i++) {
var s = strs[i];
var c = s.split("").sort();
m[c]?m[c].push(s):m[c]=[s];
}
var r = [];
var keys = Object.keys(m);
for(var k=0; k<keys.length; k++) {
r.push( m[keys[k]] );
}
return r;
};

Submission Detail

  • 101 / 101 test cases passed.
  • Runtime: 144 ms, faster than 32.01% of JavaScript online submissions for Group Anagrams.
  • Memory Usage: 45.6 MB, less than 34.78% of JavaScript online submissions for Group Anagrams.

Java

translation from solution of Joan Indiana Lyness

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
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Arrays;

class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> list = new ArrayList<List<String>>();
Map<String, List<String>> map = new HashMap<String, List<String>>();
String s;
char[] c;
String key;
for (int i = 0; i < strs.length; i++) {
s = strs[i];
c = s.toCharArray();
Arrays.sort(c);
key = new String(c);
if (map.containsKey(key)) {
map.get(key).add(s);
} else {
List<String> glist = new ArrayList<String>();
glist.add(s);
map.put(key, glist);
}
}

list.addAll(map.values());
return list;
}
}

Submission Detail

  • 101 / 101 test cases passed.
  • Runtime: 9 ms, faster than 83.05% of Java online submissions for Group Anagrams.
  • Memory Usage: 40.8 MB, less than 96.49% of Java online submissions for Group Anagrams.

ref

Interesting titles in memory of scientists

Science is the most revolutionary force in the world.
– George Sarton

Canada Waterloo Mathematics Contests

https://www.cemc.uwaterloo.ca/contests/contests.html

Gauss Mathematics Contests

The Gauss Contests are an opportunity for students to have fun and to develop their mathematical problem solving ability.

Audience

All students in Grades 7 and 8 and interested students from lower grades.

Pascal, Cayley and Fermat Mathematics Contests

The Pascal, Cayley and Fermat Contests are an opportunity for students to have fun and to develop their mathematical problem solving ability.

Audience

  • Students in Grade 9 or below are eligible to write the Pascal Contest.
  • Students in Grade 10 or below are eligible to write the Cayley Contest.
  • Students in Grade 11 or below are eligible to write the Fermat Contest.

Fryer, Galois and Hypatia Mathematics Contests

The Fryer, Galois and Hypatia Math Contests are an opportunity for students to write a full-solution contest. They are fun way to develop mathematical problem solving skills through a written mathematical activity.

Audience

  • Students in Grade 9 or below are eligible to write the Fryer Contest.
  • Students in Grade 10 or below are eligible to write the Galois Contest.
  • Students in Grade 11 or below are eligible to write the Hypatia Contest.

Euclid Mathematics Contest

The Euclid Mathematics Contest is an opportunity for students to have fun and to develop their mathematical problem solving ability.

Audience

Students in their final year of secondary school or CÉGEP students and motivated students in lower grades.

FFmpeg Releases

FFmpeg is the leading multimedia framework originally developed by Fabrice Bellard.

https://www.ffmpeg.org/download.html#releases

  • FFmpeg 4.2.1 “Ada”
  • FFmpeg 4.1.4 “al-Khwarizmi”
  • FFmpeg 4.0.4 “Wu”
  • FFmpeg 3.4.6 “Cantor”
  • FFmpeg 3.3.9 “Hilbert”
  • FFmpeg 3.2.14 “Hypatia”
  • FFmpeg 2.8.15 “Feynman”
  • FFmpeg 3.1.11 “Laplace”
  • FFmpeg 3.0.12 “Einstein”
  • FFmpeg 2.7.7 “Nash”
  • FFmpeg 2.6.9 “Grothendieck”
  • FFmpeg 2.5.11 “Bohr”
  • FFmpeg 2.4.14 “Fresnel”
  • FFmpeg 2.3.6 “Mandelbrot”
  • FFmpeg 2.2.16 “Muybridge”
  • FFmpeg 2.1.8 “Fourier”
  • FFmpeg 2.0.7 “Nameless”
  • FFmpeg 1.2.12 “Magic”
  • FFmpeg 1.1.16 “Fire Flower”
  • FFmpeg 1.0.10 “Angel”
  • FFmpeg 0.11.5 “Happiness”
  • FFmpeg 0.10.16 “Freedom”
  • FFmpeg 0.9.4 “Harmony”
  • FFmpeg 0.8.15 “Love”
  • FFmpeg 0.7.17 “Peace”
  • FFmpeg 0.6.7 “Works with HTML5”
  • FFmpeg 0.5.15 “half-way to world domination A.K.A. the belligerent blue bike shed”

LeetCode - Algorithms - 54. Spiral Matrix

Problem

54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Java

solution by myself

Although it is slow, it is pass on Leetcode by myself after attempting six times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length;
int n = m>0?matrix[0].length:0;
List<Integer> list = new ArrayList<Integer>();
for(int delta=0;delta<Math.ceil(Math.min(m, n)/2)+1;delta++) {
for(int i=delta;m>=2*delta+1 && i<n-delta;i++) {
list.add(new Integer(matrix[delta][i]));
}
for(int i=delta+1;n>=2*delta+1 && i<m-delta;i++) {
list.add(new Integer(matrix[i][n-delta-1]));
}
for(int i=n-delta-2;m>=2*delta+2 && i>=delta;i--) {
list.add(new Integer(matrix[m-delta-1][i]));
}
for(int i=m-delta-2;n>=2*delta+2 && i>delta;i--) {
list.add(new Integer(matrix[i][delta]));
}
}
return list;
}
}

Submission Detail

  • 22 / 22 test cases passed.
  • Runtime: 1 ms, faster than 6.37% of Java online submissions for Spiral Matrix.
  • Memory Usage: 34.4 MB, less than 100.00% of Java online submissions for Spiral Matrix.

better 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
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int height = matrix.length, width = height == 0 ? 0 : matrix[0].length;
int size = height * width;

int[] dirX = { 0, 1, 0, -1 };
int[] dirY = { 1, 0, -1, 0 };

int x = 0, y = -1, dir = 0;
for (int step, total = 0; total < size; total += step) {
if (dir == 0 || dir == 2) {
step = width;
height--;
} else {
step = height;
width--;
}
for (int i = step; i > 0; i--) {
x += dirX[dir];
y += dirY[dir];
result.add(matrix[x][y]);
}
dir = ++dir % 4;
}
return result;
}
}

Submission Detail

  • 22 / 22 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Spiral Matrix.
  • Memory Usage: 34.2 MB, less than 100.00% of Java online submissions for Spiral Matrix.

C#

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
public class Solution {
public IList<int> SpiralOrder(int[][] matrix) {
IList<int> list = new List<int>();
int height = matrix.Length;
int width = height == 0 ? 0 : matrix[0].Length;
int size = height * width;

int[] dirX = { 0, 1, 0, -1 };
int[] dirY = { 1, 0, -1, 0 };

int x = 0, y = -1, dir = 0;
for (int step, total = 0; total < size; total += step)
{
if (dir == 0 || dir == 2)
{
step = width;
height--;
}
else
{
step = height;
width--;
}
for (int i = step; i > 0; i--)
{
x += dirX[dir];
y += dirY[dir];
list.Add(matrix[x][y]);
}
dir = ++dir % 4;
}

return list;
}
}

Submission Detail

  • 23 / 23 test cases passed.
  • Runtime: 176 ms, faster than 71.81% of C# online submissions for Spiral Matrix.
  • Memory Usage: 40.5 MB, less than 95.65% of C# online submissions for Spiral Matrix.

Why We Struggle Learning Languages - Gabriel Wyner - TEDxNewBedford - Transcript

So, there’s a myth when it comes to language. And that myth is that children are exceptionally good at learning languages and that we lose that gift when we grow up. We have good reason for believing in this myth.

Many of us have had this experience. We’ve picked a language in high school or college, studied hard for three, four, five years, and then we take a trip to France, and we meet a five-year-old French child, and she speaks way better French then we do. (Laughter) And it’s not fair. I mean, we have struggled so hard, and she has never worked a day in her life, and yet here she is correcting our grammar. And you’re right. It’s not fair. It’s not fair because you are comparing yourself to a child who has had 15,000 hours of French exposure, and you have had 100, maybe 200, maybe 50. It depends upon how much of your classes were actually spent in French instead of in English talking about French. When you make the fair comparison - you take a five-year-old child, transplant them to Spain, give them 500 hours of exposure there; adult gets a job in Spain, 500 hours of exposure - what you’ll find is that the adult beats the child every time. We are better at learning languages than children. We are smarter than them. We’ve learned how to learn. It’s one of the perks of growing up.

That’s not to say there are no advantages to being a kid; there are three. Between the ages of 6 months and 12 months, in that tiny window, children can hear sounds in new languages in a way that we lose. Significant advantage there. Advantage two, children are fearless. They will walk into any conversation, whether they know the words or not, where we will hold ourselves back; we’ll be afraid. Huge advantage. Yet neither of those two advantages outweighs our superior ability to learn. The third advantage of being a child is the advantage of time.

We don’t have 15,000 hours to spend learning French. And so, to succeed at this, we need something that works better than what children use. And to talk about what that might look like, I want to talk about some of my own experiences.

I began my language learning journey with Hebrew, in kindergarten and elementary school. I studied for seven years, and at the end of those seven years of study, I could read the Hebrew … alphabet. (Laughter) So I try it again. In junior high and high school, I was fortunate; I went to a high school that offered Russian with really good teachers, and so I took Russian for five and a half years. I studied hard; I did well on my tests; I did all of my homework; and at the end of those five and a half years, I could read the Russian alphabet. I retained, maybe, 40 words, and I came to the conclusion that this whole language thing was not for me. And then I made a poor decision. I was always a science nerd. I loved science and engineering; I wanted to be a nuclear engineer, focused on plasma physics so I could make fusion reactors. That was my thing as a kid. But I had this hobby, and that hobby was singing. I sang musical theater and opera. And as I was applying to engineering schools for college, I applied to one that had a music conservatory, and I thought, “Wouldn’t it be weird to study opera and mechanical engineering? Wouldn’t that be out there?” And so I did. One of the side effects of that is that I needed to take language courses. For that opera degree, I needed German, French, and Italian. And a French friend of mine came to me and said, “Hey, you know, you can get two semesters of credit in one summer at this school in Vermont.” And I thought, “That sounds great.” So I signed right up for this program. And the way this program works is that you sign a contract on the very first day. It says that if I speak one word that is not German, if I write anything, if I read anything, if I listen to a voicemail that’s not in German, I will get kicked out of the school with no refund. And I thought, “I guess that sounds like fun.” (Laughter) And so I went, and I signed that contract, and I realized that I did not actually speak any German, and so, I stopped talking. (Laughter) And someone came up to me, and he said, “Hallo, ich heiße Joshua. Wie heißt du?” And I said, “Eh?” (Laughter) And he said, “Hallo, ich heiße Joshua. Wie heißt du?” And I said, “Ich heiße Gabriel?” And I learned German that way. Seven weeks later, I could hold a solid conversation in the language, and I became addicted to the feeling of thinking in a completely new way. And so, I went back the following summer to reach fluency in German. In 2007, I moved to Vienna, Austria, to pursue a degree in opera and in song. In 2008, I went to Perugia, Italy, to study Italian. And in 2010, I cheated on a French test. And that’s where all of this comes from. You see, I wanted to go back to that school with the contracts in Vermont because, in a sort of stressful, masochistic way, it was actually kind of fun. And they had a Level 1 for people who weren’t familiar with French, which was appropriate for my level, but they also had Level 1.5 that was a little bit faster. And I thought, this was my third language. Italian is close to French. I can probably manage 1.5. So they sent me a placement test online, and I cheated on it as much as I possibly could. I figured me not knowing French and cheating as much as I could might get me in Level 1.5. And so, I used About.com’s “French grammar” to cheat on the multiple-choice section. I wrote an essay in Google Translate and submitted this thing. (Laughter) I sent it off. I didn’t think about any more of it. And three months later I got an email, and that email said, “Congratulations! You did really well on your placement test! We’re placing you in the intermediate level.” (Laughter) “You have three months. In three months, we’re going to put you in a room with a French speaker. We’ll talk to you for about 15 minutes to make sure you did not do anything stupid, like cheat on your placement test.” (Laughter)

And so, I panicked. And when I panic, I go to the internet because, clearly, someone there has an answer for everything, and as it turns out, there were some good answers. There are these systems called spaced repetition systems. They’re basically like flashcards. You know those cards with, like, “chat - cat” that you used in school? These are computerized versions of these, but they test you right at the optimal moment, right before you forget any piece of information, so they’re extremely efficient. Now, what people use these space repetitions programs for is they use them with translations. And I knew from my experiences with Hebrew and Russian that that wasn’t going to work for me, and so I did something else. And to explain that, let’s talk about two words. The first word, we learn in a classroom. We’re learning Hungarian. Our teacher comes to the board. She writes fényképezőgép is the Hungarian word for camera. And then she writes 39 other words on the board and says, “This will be your vocabulary for the week. You’ll have a quiz at the end of the week.” The second word, we learn quite differently. You are on an adventure with your best friend. You’re in Scandinavia. You find yourselves in an old bar. There are six grizzled old patrons. You sit at the bar, and the barkeep, he is definitely a Viking. He has a giant red beard, and he is smiling at you in a very disturbing manner as he puts out three shot glasses and pulls out a bottle, and on the bottle you see written M O K T O R, as the barkeep says, “Moktor” and starts pouring something into these shot glasses. And it’s a sort of green liquid, but not a nice, emerald green liquid; it’s a kind of brownish yellowish viscous green liquid. And he puts the bottle away, and he pulls out a white jar. From the white jar, he starts spooning out something into each shot glass. From the scent, you realize this is definitely rotting fish, as he repeats, “Moktor,” and all the patrons now are turning and looking at you and laughing. The barkeep now pulls out a match. He lights it, he lights the three shot glasses on fire, and he repeats, “Moktor,” as all of the patrons now start chanting “Moktor! Moktor! Moktor!” And your friend, your stupid friend, he picks up his shot glass and he shouts “Moktor!” and he blows it out, and he drinks it. And the barkeep, he blows his out, and he shouts “Moktor!” and he drinks it. And now everyone is staring at you, chanting “Moktor! Moktor!” And you pick up your glass - “Moktor!” - and you blow it out - “Moktor!” - and you scream “Moktor!” and you drink it. And it’s the worst thing you’ve ever had in your life. And you will remember the word moktor forever - (Laughter)

where you have already forgotten the Hungarian word for camera. (Laughter) Why? Memories are fascinating things. They’re not stored in any particular location in your brain; they’re actually stored in the connections between regions of your brain. When you saw that glass, you saw the bottle and it said M O K T O R, and the barkeep said, “Moktor,” that sound and that spelling, they interconnected; they formed a memory. Those connections connected to other sounds: the sound of moktor getting poured into those shot glasses, the sound of everyone chanting in the room “Moktor! Moktor!” All of those sounds and that spelling, they interconnected, and they also connected to images. They connected to images of this green bottle. They connected to the shot glasses. They connected to this decaying fish. They connected to the face of that barkeep; that Viking face, that is a part of that word now. And those, in turn, connect to sensory experiences, like that awful taste in your mouth, the smell of burning, decaying fish, the heat of the fire. Those connect to emotional content: to disgust, to anger at your friend, to excitement. They connect to your journey. They connect to what is alcohol, what is Scandinavia, what is friendship, what is adventure. All of these things are now a part of this word, and they make it so that that word is going to stick with you, where the Hungarian word for camera, well, you don’t even remember what it sounds like. This non-memory isn’t associated with iPhone cameras and SLR cameras and the sound of a shutter, and the feelings you get when you look at photos from your past. No, those associations exist; they’re connected to another word, to the word camera. But fényképezőgép has none of that right now. And so, you can’t hold on to it. So what can you do with this?

Well, let’s return to where I was with French. My situation was as follows: I was taking two master’s degrees, one in song, one in opera, and so I had six days of class a week. My only free time was an hour a day on the subway, Sundays, and Austrian national holidays, of which, thankfully, there were many. And during that time, I did one thing: I built and reviewed flashcards in one of these computerized spaced repetition systems. But instead of using translations on those flashcards, I began with pictures. If I wanted to learn the French word for dog, chien, then I would search on Google Images for chien, and I would find that French bloggers didn’t choose the dogs I would expect. Their dogs were smaller and cuter and, somehow, more French. (Laughter) And so, I used these dogs to learn chien and built a vocabulary out of these pictures from French bloggers. And as I built that vocabulary, I graduated over to sentences. And I started learning abstract words and grammar that way, using fill-in-the-blank sentences. If I wanted to learn a word, like, went is the past tense of to go, I would use a story. Yesterday, I blank to school - with a picture of a schoolhouse. And so, I learned my abstract grammar in that way. And then, three months later, I had that interview. And I found myself in this room with this French person, who began our conversation with “Bonjour.” And then, the first thing that came to my mind was, “Bonjour.” And she started speaking to me in French, and I realized I understood what she was saying, and what’s more, I knew what to say back. And it wasn’t fluent; it was a bit stunted, but this was the first time I had spoken French in my life, and I was speaking in French, and I was thinking in French, and we had a 15-minute conversation, and at the end of this conversation, the teacher tells me, “You know, there something wrong with your placement test. It says you should be in the intermediate level, but we’re placing you in the advanced level.” And so, over the next seven weeks, I read 10 books, I wrote 70 pages of essays, and by the end of that summer, I was fully fluent in French. And I realized that I had found something important. And so I started writing about it and creating computerized tools around it and tinkering.

In 2012, I learned Russian. I had my revenge on that language. In 2013 through 2015, I learned Hungarian. In 2015, I started Japanese, then stopped, learned Spanish, came back, and started Japanese again because Japanese is endless. In each of these experiences, I learned a lot. I learned ways of tweaking the system to find efficiency boosts here and there, but the overall concept has always remained exactly the same. If you want to learn a language efficiently, then you need to give that language life. Every word needs to connect to sounds and images and scents and tastes and emotions. Every bit of grammar can’t be some kind of abstract grammatical code; it needs to be something that can help you tell your story. And if you do this, you will find that the words begin to stick in your mind, and the grammar, it begins to stick too. And you start to realize that you don’t need some kind of language gene, some gift from God to accomplish this. This is something that everyone has both the time and the ability to do. Thank you.

What Bruce Lee can teach us about living fully - Shannon Lee - TED Salon - Transcript

Bruce Lee is my father, and he is best well-known as a martial artist and an action film star, as I’m sure most of you know. He died when I was four years old, but I have a really deep memory of him. I don’t have those long-form, storied memories that you do when you’re older, but the memory that I do have is of the feeling of him. I remember his energy, his presence, his love – the safety of it, the power of it, the radiance of it. And to me that memory is very deep and personal. And it is the memory of the quality of his essential nature.

What a lot of people don’t know about my father is that he was also a philosopher. He had a very ever-evolving philosophy that he lived, and it is that distinction – that he lived his philosophy and didn’t just espouse his philosophy – that made him the force of nature that he was, and still engages us today. His wisdom has salvaged me many times in my life: when my brother died, when my heart’s been broken, whenever I have faced a challenge to my mind, my body or my spirit, the way that he expressed himself has lifted me up. And so I come to you today not as a researcher or an educator or a guru or even a life coach, but as a student of Bruce Lee – as his daughter, and also as a student of my own life.

So … my big burning question that I want you all to consider today is … how are you? Let me elaborate. Whenever anyone would ask my mom what my father was like, she would say, “How he was in front of the camera, how you saw him in his films, how you saw him in his interviews was, in fact, exactly how he was.” There were not multiple Bruce Lees. There was not public Bruce Lee and private Bruce Lee, or teacher Bruce Lee and actor Bruce Lee and family man Bruce Lee. There was just one unified, total Bruce Lee. And that Bruce Lee had a very deep, philosophical life practice called self-actualization. You’ve probably heard that term before. It’s also known as how to be yourself in the best way possible. And that Bruce Lee said this: “When I look around, I always learn something and that is to be always yourself, and to express yourself and have faith in yourself. Don’t go out and find a successful personality and duplicate it, but rather start from the very root of your being, which is ‘How can I be me?’

Many of us have done some soul-searching or at least some incessant thinking and worrying about things like our purpose, our passion, our impact, our values and our “reason for being.” And that is sometimes considered our why. Why am I here? Why this life? What am I meant to be doing? If we can grab a little piece of that information, it can help to ground us and root us, and it can also point us in a direction, and typically what it points us to is our what. What we manifest in the world, what we have. So our job, our home, our hobbies and the like. But there’s this little space in between the why and the what that often doesn’t get our full attention, and that is our … how. How we get there and the quality of that doing. And I want to offer that this is actually the most important part of the equation when it comes to our personal growth, our sense of wholeness and even the long-term impact that we make.

How is the action that bridges the gap from the internal to the external. And bridging the gap is a very important concept for martial artists like my father. It’s how you get from point A to point B. It’s how you get from here to your target under the most vital of circumstances. And so it makes all the difference. Do you get there as an amateur? Are you sloppy? Are you wild, chaotic, sometimes you get lucky, sometimes you’re not lucky? Or are you a warrior? Are you confident? Are you focused? Are you skilled? Are you intuitive? Are you expressive, creative, aware? So I want to talk to you today about your how in your life.

So we do a little bit of – we spend a little time in existential crisis over “Why am I here? What am I meant to be doing?” and we put a ton of effort into our what – our job, our career, our partner that we have and the hobbies we pursue. But I want us to consider that our how is the expression of our why in every what, whether we’re aware of it or not. And so let’s take an example. Let’s say that I have a value of kindness. I’m all about kindness, I feel really natural being kind, I want to see more kindness in the world. Is that kindness – is that value in the result or is it in the doing? Are you trying to be kind when it’s hard to be kind? Can you do something you don’t want to do kindly, like fire someone? Can you leave a relationship with kindness? If kindness is the value, then are you trying to express it in the whole spectrum of your doing – and trying to do that? Or are you just doing it when it’s easy? So I want us to think about that for a moment and consider, you know, if we come home and we’re kind and generous and loving with our kids, but then we go to work and we are dismissive and rude to our assistant and we treat them like a subhuman, then there is a fragmentation in the beingness of our value. And so I want us to consider that how we are in our lives is in fact how we are. Meaning, if I am the kind of person that walks down the street and smiles at people and says “hi” as I walk past them on the sidewalk, then that is how I am. But if I’m also the kind of person who makes fun of my brother every chance that I get behind his back, that is also the kind of person that I am. And ultimately how we are makes up the totality of the picture of who we are. And so I want to talk about how do we unite these pieces if we have any fragmentation. I want to understand how we embody ourselves as our one and only self.

How do we actualize the whole self? My father said, “All goals apart from the means are an illusion. There will never be means to ends – only means. And I am means. I am what I started with and when it is all over, I will be all that is left.“ So you can employ a systematic approach to training and practicing, but you can’t employ a systematic approach to actually living because life is a process not a goal. It is a means and not an end. So “to obtain enlightenment” – and I’m going to say self-actualize, to be self-actualized or to obtain wholeness – “emphasis should fall NOT on the cultivation of the particular department” – all of our whats – “which then merges into the totality of who we are as a total human being, but rather, on the total human being that then enters into and unites those particular departments.” You are your how.

You – if you have some consciousness and you want to bring some practice, if you want to step into that warrior space around your how – how you express in every aspect of your life – then you get to be the artist of that expression. You get to step into that and claim it and exercise it and bring that beingness through your doingness into your havingness. And there you will find the most profound of your growth, you will find a sense of wholeness and ultimately, you will leave a lasting impact on your environment.

My father was his how. He applied the execution of who he was to every aspect of his life. He was way more than that kung fu guy from the ‘70s. He was someone who worked very hard at actualizing his inner self and expressing it out into the world. And that laid the foundation for what continues to inspire us, engage us, excite us and attract us to him. He was the embodied example of living fully. He said, “I am means.“ And there are only means.

So I’m going to ask you one more time. Thank you for listening, and please consider, for you, across the spectrum of your doing, how are you?

Thank you.


Walking Along the Bank of Lake Washington

by Bruce Lee

The breeze on the bank
Already blows cool and mild;
The distant merging of lake and sky
Is but a red trace of sunset.

The deep silence of the lake,
Cuts of all tumult from me.
Along the lonely bank
I move with slow footsteps:

Alone the disturbed frogs scurry off.
Here and there are houses,
Cool beads of light spring out from them.

A dazzling moon
Snines down from the lonely depths of the sky.
In the moonlight slowly I move to a gung fu form.
Body and soul are fused into one.

Conceptual Blockbusting - A Guide To Better Ideas

the programmer’s main problem was not so much technical as psychological: he couldn’t make progress because he was trying to solve the wrong problem. We finally solved his problem by breaking through his conceptual block and solving an easier problem. Conceptual Blockbusting by James L. Adams studies this kind of leap and is generally a pleasant prod towards more creative thinking. Although it was not written with programmers in mind, many of its lessons are particularly appropriate for programming problems. Adams defines conceptual blocks as “metal walls that block the problem-solver from correctly perceiving a problem or conceiving its solution”. - Programming Pearls, by Jon Bentley


texts below are from © Conceptual Blockbusting 4th Edition, by James L. Adams

Chapter One Introduction

We spend little time monitoring our own thinking and comparing it with a more sophisticated ideal.

Thinking form

Conceptual blocks still control us. Much of thinking is quite automatic.

The following puzzle, which originates with Carl Duncker, is taken from The Arc of Creation by Arthur Koestler.

Puzzle: One morning, exactly at sunrise, a Buddhist monk began to climb a tall mountain. A narrow path, no more than a foot or two wide, spiraled around the mountain to a glittering temple at the summit. The monk ascended at varying rates of speed, stopping many times along the way to rest and eat dried fruit he carried with him. He reached the temple shortly before sunset. After several days of fasting and meditation he began his journey back along the same path, starting at sunrise and again walking at variable speeds with many pauses along the way His average speed descending was, of course, greater than his average climbing speed. Prove that there is a spot along the path that the monk will occupy on both trips at precisely the same time of day.

Solutions to Problems That Don’t Exist

Conceptual Blocks

mental walls that blocks the problem-solver from correctly perceiving a problem or conceiving its solutions.

Once again, please do the exercises and problems. The only way you will identify your own conceptual blocks is to try activities that are impeded by their existence.

Chapter Two Perceptual Blocks

Perceptual Blocks are obstacles that prevent the problem-solver from clearly perceiving either the problem itself or the information needed to solve the problem.

One: Detecting What You Expect - Stereotyping

Context is a key element in many memory techniques.

Two: Difficulty in isolating the Problem

Three: Tendency to Delimit the Problem Area Poorly

Puzzle: Draw no more than four straight lines(without lifting the pencil from the paper) which cross through all nine dots.

the widespread nature of this block is what makes this puzzle classic.

Four: Inability to See the Problem from Various Viewpoints

Five: Saturation

Six: Failure to Utilize all Sensory Inputs

Chapter Three Emotional blocks

The Mystery of Emotion

Freud

The Humanistic Psychologists

Fear of Taking a Risk

No Appetite for Chaos

Judging Rather than Generating ideas

inability Or Unwillingness to Incubate

Lack of challenge versus Excessive Zeal

Reality and Fantasy

of Flow and Angst

Chapter Four Cultural and Environmental blocks

Taboos

Humor in Problem-Solving

Reason and Intuition

Left-Handed and Right-Handed thinking

Primary and Secondary Creativity

Everybody Should Be Just Like Me

Cyber Is Better

Adria Anuzis looked at three aspects of communication, which she called
personal(same location, personal interaction),
cultural(commonalties of interest, background, and values),
cyber(interacting electronically).
she found that the most successful professional interaction made use of all three.

the best creative work comes from people who are not only electronically interconnected, but also share cultural values and interact personally in the same physical space.

Tradition and Change

Thinking Through Blocks

Environmental Blocks

Supportive Environments

Accepting and Incorporating Criticism

Autocratic Bosses

Non-Support

Chapter Five Intellectual and Expressive Blocks

Choosing Your Problem-Solving Language

Flexibility in Your Use of Strategies

Build upDisplaySimulate
EliminateOrganizeTest
Work ForwardListPlay
Work BackwardCheckManipulate
AssociateDiagramCopy
ClassifyChartInterpret
GeneralizeVerbalizeTransform
ExemplifyVisualizeTranslate
CompareMemorizeExpand
RelateRecallReduce
CommitRecordExaggerate
DeferRetrieveUnderstate
Leap InSearchAdapt
Hold backselectsubstitute
FocusPlancombine
releasepredictseparate
forceassumeChange
relaxquestionvary
dreamhypothesiscycle
imagineguessrepeat
purgedefinesystemize
incubatesymbolizerandomize

The Computer

Importance of Correct Information

Expressive Blocks

Chapter Six Alternate Thinking Languages

Visual Thinking

Other Sensory Languages

Cognitive Diversity

The Problems of Specialization

Analysis-Synthesis

Convergence-Divergence

Deduction-Induction

Jung and the Myers-Briggs Test

Chapter Seven Kinds of Blockbusters

A Questioning Attitude

Working on the Right Problem

Time and Effort Focusers

Set Breakers

Using other People’s ideas

Crossing Disciplines

Crossing Cultures and Changing Environments

Unconscious Blockbusting

Maslow

Barron

Other Paths for Freeing the Unconscious

Chapter Eight Groups

The Process

Synectics

Affiliation / Ego Needs

Leadership

Group Membership

Proper Support

Chapter Nine Organizations

Control vs. Creativity

The Pattern of Growth

Tradition and Past Success

Reward System and Support

Psychological Rewards

Support

Culture

LeetCode - Concurrency - 1114. Print in Order

An example of multiple solutions selected from discuss.

Java

volatile

Using volatile variables reduces the risk of memory consistency errors, because any write to a volatile variable establishes a happens-before relationship with subsequent reads of that same variable. This means that changes to a volatile variable are always visible to other threads. What’s more, it also means that when a thread reads a volatile variable, it sees not just the latest change to the volatile, but also the side effects of the code that led up the change.

volatile has semantics for memory visibility. Basically, the value of a volatile field becomes visible to all readers (other threads in particular) after a write operation completes on it. Without volatile, readers could see some non-updated value.

In programming, an atomic action is one that effectively happens all at once. An atomic action cannot stop in the middle: it either happens completely, or it doesn’t happen at all. No side effects of an atomic action are visible until the action is complete.

  • Reads and writes are atomic for reference variables and for most primitive variables (all types except long and double).
  • Reads and writes are atomic for all variables declared volatile (including long and double variables).

&#91;Java&#93; Simple, yet effective. Using volatile without lock

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
class Foo {
private volatile int flag;

public Foo() {
flag = 1;
}

public void first(Runnable printFirst) throws InterruptedException {
for(;;) {
if (flag==1) {
printFirst.run();
flag = 2;
break;
}
}
}

public void second(Runnable printSecond) throws InterruptedException {
for(;;) {
if (flag==2) {
printSecond.run();
flag=3;
break;
}
}
}

public void third(Runnable printThird) throws InterruptedException {
for(;;) {
if (flag==3) {
printThird.run();
flag = 1;
break;
}
}
}
}

36 / 36 test cases passed.
Runtime: 9 ms, faster than 88.93% of Java online submissions for Print in Order.
Memory Usage: 35.9 MB, less than 100.00% of Java online submissions for Print in Order.

Semaphore

Conceptually, a semaphore maintains a set of permits. Each acquire() blocks if necessary until a permit is available, and then takes it. Each release() adds a permit, potentially releasing a blocking acquirer. However, no actual permit objects are used; the Semaphore just keeps a count of the number available and acts accordingly.

Semaphores are often used to restrict the number of threads that can access some (physical or logical) resource.

[Java/Go] Implements

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
import java.util.concurrent.Semaphore;

class Foo {
Semaphore semaphore1 = new Semaphore(0);
Semaphore semaphore2 = new Semaphore(0);

public Foo() {

}

public void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
semaphore1.release();

}

public void second(Runnable printSecond) throws InterruptedException {
semaphore1.acquire();
printSecond.run();
semaphore2.release();

}

public void third(Runnable printThird) throws InterruptedException {
semaphore2.acquire();
printThird.run();
}
}

36 / 36 test cases passed.
Runtime: 9 ms, faster than 89.05% of Java online submissions for Print in Order.
Memory Usage: 35.7 MB, less than 100.00% of Java online submissions for Print in Order.

synchronized

The Java programming language provides two basic synchronization idioms: synchronized methods and synchronized statements.

Unlike synchronized methods, synchronized statements must specify the object that provides the intrinsic lock.

Synchronized statements are also useful for improving concurrency with fine-grained synchronization.

[Java] Basic version with just a synchronized block & a counter

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
class Foo {
private String mutex = new String("");
private int counter = 1;

public Foo() {
}

public void first(Runnable printFirst) throws InterruptedException {
boolean loop = true;
while (loop) {
synchronized(mutex) {
if (counter == 1) {
printFirst.run();
++counter;
loop = false;
}
}
}
}

public void second(Runnable printSecond) throws InterruptedException {
boolean loop = true;
while (loop) {
synchronized(mutex) {
if (counter == 2) {
printSecond.run();
++counter;
loop = false;
}
}
}
}

public void third(Runnable printThird) throws InterruptedException {
boolean loop = true;
while (loop) {
synchronized(mutex) {
if (counter == 3) {
printThird.run();
++counter;
loop = false;
}
}
}
}
}

36 / 36 test cases passed.
Runtime: 9 ms, faster than 89.16% of Java online submissions for Print in Order.
Memory Usage: 36 MB, less than 100.00% of Java online submissions for Print in Order.

CountDownLatch

A synchronization aid that allows one or more threads to wait until a set of operations being performed in other threads completes.

A CountDownLatch is initialized with a given count. The await methods block until the current count reaches zero due to invocations of the countDown() method, after which all waiting threads are released and any subsequent invocations of await return immediately. This is a one-shot phenomenon – the count cannot be reset.

A CountDownLatch is a versatile synchronization tool and can be used for a number of purposes. A CountDownLatch initialized with a count of one serves as a simple on/off latch, or gate: all threads invoking await wait at the gate until it is opened by a thread invoking countDown(). A CountDownLatch initialized to N can be used to make one thread wait until N threads have completed some action, or some action has been completed N times.

A useful property of a CountDownLatch is that it doesn’t require that threads calling countDown wait for the count to reach zero before proceeding, it simply prevents any thread from proceeding past an await until all threads could pass.

Another typical usage would be to divide a problem into N parts, describe each part with a Runnable that executes that portion and counts down on the latch, and queue all the Runnables to an Executor. When all sub-parts are complete, the coordinating thread will be able to pass through await.

[Java] 7ms CountDownLatch

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
import java.util.concurrent.CountDownLatch;

class Foo {
private final CountDownLatch L1 = new CountDownLatch(1);
private final CountDownLatch L2 = new CountDownLatch(1);

public Foo() {
}

public void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
L1.countDown();
}

public void second(Runnable printSecond) throws InterruptedException {
L1.await();
printSecond.run();
L2.countDown();

}

public void third(Runnable printThird) throws InterruptedException {
L2.await();
printThird.run();
}
}

36 / 36 test cases passed.
Runtime: 9 ms, faster than 89.16% of Java online submissions for Print in Order.
Memory Usage: 35.4 MB, less than 100.00% of Java online submissions for Print in Order.

Phaser

A reusable synchronization barrier, similar in functionality to CyclicBarrier and CountDownLatch but supporting more flexible usage.

Methods arrive() and arriveAndDeregister() record arrival. These methods do not block, but return an associated arrival phase number; that is, the phase number of the phaser to which the arrival applied.

Method awaitAdvance(int) requires an argument indicating an arrival phase number, and returns when the phaser advances to (or is already at) a different phase.

Java Phaser solution, very fast

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
import java.util.concurrent.Phaser;

class Foo {
private Phaser phaser;

public Foo() {
phaser = new Phaser(3);
}

public void first(Runnable printFirst) throws InterruptedException {
phaser.arrive();
phaser.awaitAdvance(0);
printFirst.run();
phaser.arrive();
phaser.arrive();

}

public void second(Runnable printSecond) throws InterruptedException {
phaser.arrive();
phaser.awaitAdvance(0);
phaser.arrive();
phaser.awaitAdvance(1);
printSecond.run();
phaser.arrive();

}

public void third(Runnable printThird) throws InterruptedException {
phaser.arrive();
phaser.awaitAdvance(0);
phaser.arrive();
phaser.awaitAdvance(1);
phaser.arrive();
phaser.awaitAdvance(2);
printThird.run();
}
}

36 / 36 test cases passed.
Runtime: 10 ms, faster than 55.92% of Java online submissions for Print in Order.
Memory Usage: 36 MB, less than 100.00% of Java online submissions for Print in Order.