English Conversation for Beginners

texts below are from © English Conversation for Beginners: 45+ Phrases for the English Speaking Adventure of a Lifetime

Starting an English Conversation

If you need a push to start having conversations in English, watch the clip below for motivation.

Then, any polite conversation starts with a greeting (saying hello). There are many ways to greet someone, and your choice will depend on who you are talking to.

It may be an informal conversation with a friend or an acquaintance (someone you know, but not very well). Or you may use a more formal dialogue when having an English conversation with a colleague, a teacher, a stranger or a government employee.

Informal greetings

Let’s start with informal greetings. Here is how you can say hello:

  • Hello!
    (A universal greeting that works for every conversation.)
  • Hi!
    (A neutral and friendly greeting.)
  • Hey!
    (An informal and relaxed greeting.)
  • Greetings!
    (This is quite formal and rare these days, but could be used humorously among friends.)

Formal greetings

For a more formal way to greet someone, use the model “good + [time of day]”:

  • Good morning!
    (Reserved for any time before noon.)
  • Good afternoon!
    (Typically used between noon and 5-6 p.m.)
  • Good evening!
    (Any time after 6 p.m.)

Remember that “good night” normally means that you are saying goodbye. It is also commonly used right before going to bed.

Introductions

What if you have never met the person you are talking to before? Then, after greeting them, it would be polite to introduce yourself and ask for their name. Here’s how:

  • My name is _____. What’s your name?
    (This is simple, neutral and always works well!)

If you met somebody once before, but you do not remember their name, you can say this:

  • I’m sorry, I don’t remember your name. You are…?
    (This is a bit more informal.)

If you want to introduce a person to someone else, you can simply say:

  • Please meet + [name]
    Please meet my friend Tom!
    (Formal introduction)

  • This is + [name]
    This is Tom!
    (Common introduction)

Now that you have introduced yourself, use one of the phrases below to respond to someone’s introduction.

  • Nice to meet you!
    (The most common)

  • Pleased to meet you!
    (Simple and polite)

  • It’s a pleasure!
    (Informal, but nice)

Making Small Talk in English

names and greeted each other, you may go on to make some “small talk.”

Small talk is common in many English-speaking countries, especially in the U.S., Canada and England. It is considered polite to add small talk to the beginning of the conversation before talking about the subject of the conversation, whether it is personal or professional.

The most widespread (common) question is “How are you?” In fact, it is so common, that it becomes automatic for people to say, even when they hardly know the person! “How are you” is often even considered part of the greeting (i.e. “Hi, how are you?”). That is how necessary it has become!

There are several ways to ask someone how they are doing:

  • How are you? / How are you doing?
    (Neutral)
  • How’s it going?
    (More informal)
  • How are things?
    (Informal)
  • What’s up?
    (Very informal)

An interesting thing about asking these questions is that an answer is not really required. Unless you are very close friends with someone, they are not expecting you to tell them an honest answer about your day

Instead, a simple answer and a “how are you” in return is enough for a typical conversation in English:

  • I’m well. How are you?
  • It’s going well, thank you. How are you doing?
  • Fine, thanks. And yourself?

Note that you might often hear people say “I’m good” when they mean that they are well and doing well. “I’m good” is grammatically incorrect in this context, but it is very common in spoken English

Small talk can also be the primary goal of a conversation, especially when you are talking to people you don’t know and are unlikely to meet again. There are many ways to use small talk successfully, even when you’re still getting comfortable with English conversation for beginners.

Asking and Answering Questions

A conversation is an exchange of ideas, questions and thoughts. The best way to keep a conversation going is to ask questions!

There are two types of questions you may ask: closed-ended and open-ended questions.

Closed-ended questions are also called “yes/no” questions, because their goal is to confirm or deny certain information. For example:

  • Are you having a good day?
  • Did you just get to the office?
  • Have you seen my email?

Compare the examples above to the open-ended questions below. They will ask a person to elaborate—that is, to give more information instead of simply saying “yes” or “no.”

  • How is your day going?
    (A perfect example of small talk!)
  • When did you arrive at the office?
  • What do you think about that email I sent?

Open-ended questions typically begin with “who,” “what,” “where,” “when” and “why.” They are important to make your English conversation informative and productive.

When the person you are talking to is asking you a question, listen for the keywords and pay attention to the verb being used. This will help you construct your answer using proper grammar.

Don’t worry about using difficult words—it is fine to keep things simple! And if you don’t understand a certain question or word, don’t be afraid to ask.

As a beginner, you may have trouble understanding everything being said in English. This is okay! You are still learning.

Asking for Clarification

You are getting good at conversations in English, but suddenly you realize that you are lost. Maybe the other person is speaking too fast. Maybe she has an unfamiliar accent. Maybe you didn’t hear the last thing she said.

It is perfectly normal to ask for clarification or to repeat something. Just remember to be polite!

If you don’t understand something, let’s say a word or even some idea relating to your conversation, you could say:

  • I’m sorry, I don’t understand. Could you please repeat that?
  • I’m sorry, I don’t understand. Could you please explain that?

or even…

  • Care to elaborate?
    (This very informal question is the short version of “Do you care to elaborate on this?”)

If you simply didn’t hear something, just say it like this:

  • I’m sorry, I didn’t hear that. Could you please repeat?
  • I’m sorry, I didn’t catch that. Could you please repeat?

or even…

  • Could you say that again, please?

Don’t be shy to ask for help. People are generally very happy to explain or repeat something! Please don’t forget to thank them after they do.

Bringing an English Conversation to a Close

Say you have got all the information you need from the person. It is time for you to go. Maybe you are running late and want to keep the conversation brief. No matter the reason, it is always nice to let the person know you cannot continue talking to them for much longer.

There are many ways to do it depending on the situation. For example, if you are late, say:

  • I have to get going. / It’s time for me to go.
    (This is polite and neutral.)
  • I have to run—can we continue later?
    (This is more informal, but also polite.)

And if you have all the information you’d wanted:

  • Thank you so much for your help!
    (A very common and useful expression)
  • Got it, thanks!
    (Very informal and friendly)
  • I think I have everything I need, thank you!
    (This is formal and may come across as rude if you don’t thank the person after, so use it with caution.)

Using Small Talk to End a Conversation

Hey, guess what? Small talk can be used at the end of an English conversation too! Before saying goodbye, it is polite to say something like…

  • Have a good day!
    (This works in any situation.)
  • Enjoy your day!
    (This one is a bit more formal.)
  • Good luck!
    (If the person needs it; it will depend on the situation.)
  • Talk to you soon!
    (This is neutral and does not necessarily mean that you will really talk to the person soon.)
  • Great seeing you / Great talking to you!
    (This is informal yet common.)
  • Catch you later!
    (This is very informal and fun.)

And after that, the only thing left to do is…

Saying Goodbye in English

This one is easy. You really cannot go wrong with just a simple “goodbye” or “bye” in spoken English. You can also use any small talk expression to complement your goodbye. For example:

  • Bye! Have a good day!
  • Catch you later! Bye-bye!

And, as mentioned at the very beginning of this guide…

  • Good night!

Useful English Phrases

texts below are from © Basic English: 30+ Golden Phrases That Are Incredibly Useful

Phrases for Anywhere

Thanks so much.

This is a simple sentence you can use to thank someone.

  • Thanks so much for the birthday money.

  • Thanks so much for driving me home.

I really appreciate…

You can also use this phrase to thank someone.

  • I really appreciate your help.
  • Thanks so much for cooking dinner. I really appreciate it.
  • Thanks so much. I really appreciate you cooking dinner.

Excuse me.

When you need to get through but there’s someone blocking your way, say “Excuse me.”

You can also say this phrase to politely get someone’s attention. For example:

  • Excuse me sir, you dropped your wallet.
  • Excuse me, do you know what time it is?

I’m sorry.

Use this phrase to apologize, whether for something big or small. Use “for” to give more detail. For example:

  • I’m sorry for being so late.
  • I’m sorry for the mess. I wasn’t expecting anyone today.

You can use “really” to show you’re very sorry for something:

  • I’m really sorry I didn’t invite you to the party.

What do you think?

When you want to hear someone’s opinion on a topic, use this question.

  • I’m not sure if we should paint the room yellow or blue. What do you think?

How does that sound?

If you suggest an idea or plan, use this phrase to find out what others think.

  • We could have dinner at 6, and then go to a movie. How does that sound?
  • Let’s hire a band to play music, and Brent can photograph the event. How does that sound?

That sounds great.

If you like an idea, you can respond to How does that sound? with this phrase. “Great” can be replaced with any synonym, such as “awesome,” “perfect,” “excellent” or “fantastic.”

A: My mom is baking cookies this afternoon. We could go to my house and eat some. How does that sound?
B: That sounds fantastic!

(Oh) never mind.

Let’s say someone doesn’t understand an idea you’re trying to explain. If you’ve explained it over and over and want to stop, just say “oh, never mind.” You can now talk about something else!

You can also use “never mind” to mean “it doesn’t matter” or “just forget it.” In these situations, say it with a smile and positive tone, though. Otherwise, when you say this phrase slowly with a falling low tone, it can mean you’re bothered or upset.

A: Are you going to the grocery store today?
B: No, I’m not. But why—do you need something?
A: Oh, never mind. It’s okay, I’ll go tomorrow.

Phrases for Learning English

As an English learner, you’ll need to tell others that English is not your first language. You’ll also need to ask native speakers to repeat phrases and words or to speak slower. The following phrases will be useful for this.

I’m learning English.

This simple phrase tells people that English is not your native language. If you’re a total beginner, add “just started” after I: “I just started learning English.”

  • My name is Sophie and I’m learning English.

I don’t understand.

Use this phrase when you don’t understand what someone means.

  • Sorry, I don’t understand. The U.S. Electoral College seems very confusing!

Could you repeat that please?

If you’d like someone to say a word, question or phrase again, use this question. Since “to repeat” means “to say again,” you can also ask, “Could you say that again please?”

We can say “please” either at the end of the question or right after “you,” like this:

  • Could you please repeat that?
  • Could you repeat that please?

Could you please talk slower?

Native speakers can talk very fast. Fast English is hard to understand! This is an easy way to ask someone to speak more slowly.

Note: This phrase is not grammatically correct. However, it’s used often in everyday (casual) speech. The grammatically correct question would be, “Could you please talk more slowly?”

That’s because “slowly” is an adverb, so it describes verbs (like “talk”). “Slower” is a comparative adjective, which means it should be used to describe nouns (people, places or thing), not verbs. (For example: My car is slower than yours.)

A: You can give us a call any weekday from 8:00 a.m. to 5:00 p.m. at five five five, two five zero eight, extension three three—
B: I’m sorry, could you please talk slower?

Thank you. That helps a lot.

After someone starts speaking more slowly for you, thank them with this phrase.

You can use it in many other situations, too.

A: Ben, could you please make the font bigger? It’s hard for me to read the words.
B: Sure! I’ll change it from size 10 to 16. How’s this?
A: Thank you. That helps a lot

What does _____ mean?

When you hear or see a new word, use this phrase to ask what it means.

A: What does “font” mean?
B: It’s the style of letters, numbers and punctuation marks when you type. A common font in the USA is Times New Roman.

How do you spell that?

English spelling can be tricky, so make sure to learn this question. You could also ask someone, “Could you spell that for me?”

A: My name is Robbertah Handkerchief.
B: How do you spell that?

What do you mean?

When you understand the words one by one, but not what they mean together, use this question. You can ask it whenever you’re confused about what someone is telling you.

A: The Smiths do have a really nice house, but the grass is always greener on the other side.
B: What do you mean?
A: I mean that if we had the Smith’s house, we probably wouldn’t be happier. We always think other people have better lives than us, but other people have problems too.

Phrases for Introducing Yourself and Making Friends

Here are some phrases for introducing yourself when you meet new people, and questions to learn more about them.

Hi! I’m [Name]. (And you?)

Here’s an informal greeting you can use when you meet new friends. If the person doesn’t tell you their name, you can ask “And you?” or “And what’s your name?”

Hi! I’m Rebecca. And you?

Nice to meet you.

After you learn each other’s names, it’s polite to say this phrase.

A: Hi Rebecca, I’m Chad.
B: Nice to meet you, Chad.
A: Nice to meet you too.

Where are you from?

Ask this question to find out which country someone is from. You answer this question with “I’m from ~.”

Can you answer this question in English? Say both the question and answer aloud right now. (Four times, remember?)

A: Nice to meet you, Sergio. So, where are you from?
B: I’m from Spain.

What do you do?

Most adults ask each other this question when they meet. It means what do you do for a living (what is your job).

I think this question is boring, so I ask other questions. But many people will probably ask you this, so it’s important to know what it means.

A: What do you do, Cathleen?
B: I work at the university as a financial specialist.

What do you like to do (in your free time)?

Instead of asking for someone’s job title, I prefer to ask what they enjoy doing. The responses (answers) are usually much more interesting!

A: So Cathleen, what do you like to do in your free time?
B: I love to read and to garden. I picked two buckets of tomatoes last week!

What’s your phone number?

If you want to keep in contact with someone you just met, ask this question to find out their phone number. You can replace “phone number” with “email address” if you want to know their email address.

You might also hear people use the more casual “Can I get your ~?,” as in, “Can I get your phone number?”

It would be great to meet up again sometime. What’s your phone number?

Do you have Facebook?

Many people keep in touch (contact) through Facebook. Use this question to find out if someone has a Facebook account. You might also ask, “Are you on Facebook?”

Let’s keep in touch! Do you have Facebook?

Phrases for Work

Finally, here are seven basic phrases you might use at a job.

How can I help you?

If you work in customer service, you’ll use this phrase a lot. It’s also a common phrase when answering the phone.

[On the phone]: Hello, this is Rebecca speaking. How can I help you?

I’ll be with you in a moment.

When someone wants to see you, use this phrase if you need a minute to finish something first. If a client is waiting at a store, you can also use this phrase to show that their turn is next.

You can replace “moment” with “minute”: “I’ll be with you in (just) a minute.”

Another common phrase for this situation is “I’ll be right with you.”

Good morning! I’ll be with you in a moment.

What time is our meeting?

You can use this question’s structure to ask the time of any event: “What time is [event]?”

If you want to ask about a meeting on a certain day, add “on [day].” For example, “What time is our meeting on Thursday?”

What time is our meeting on Wednesday?

Please call me (back) at…

When you want someone to call you or to call you back (to return your call), use this phrase to give your phone number.

Hi, this is Cathleen from the financial office.
I’m wondering if you found those missing receipts.
Please call me back at 555-5555. Thanks!

(Oh really?) Actually, I thought…

When you disagree with someone, “Actually, I thought…” will make you sound kinder and more polite than saying “No” or “You’re wrong.” This phrase is useful when you have a different idea than someone else.

A: So Sam’s coming in tonight at 8, right?
B: Actually, I thought he wasn’t working at all this week.
A: Oh, ok. I’ll have to look at the schedule again.

Actually, I [verb]…

Just like in #28, you can use “actually, I…” with many different verbs: “heard,” “learned,” “am,” “can,” “can’t,” etc. You should use it for the same situation as above: when you have a different idea than someone else.

A: Did you finish the reports?
B: Actually, I am running a bit behind, but they’ll be done by noon!

C: When you type, always put two spaces between sentences.
D: Actually, I learned to put a single space between sentences.

I’m (just) about to [verb]…

When you’re going to start something very soon, you’re “just about to” do something.

I’m just about to send those faxes.

I’m about to go and pick up some coffee. Do you want anything?

LeetCode - Algorithms - 1037. Valid Boomerang

It’s easy indeed once you think about the slope of a line.

Zoomerang a Boomerang

by Ruth I. Dowell

Zoomerang a boomerang
Around a maple tree!
Zoomrang a boomerang
But don’t hit me!

from Poems to make your belly laugh

Problem

1037. Valid Boomerang

A boomerang is a set of 3 points that are all distinct and not in a straight line.

Java

cross product

1
2
3
4
5
class Solution {
public boolean isBoomerang(int[][] points) {
return (points[2][1]-points[0][1])*(points[1][0]-points[0][0]) == (points[1][1]-points[0][1])*(points[2][0]-points[0][0])?false:true;
}
}

Submission Detail

  • 190 / 190 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Valid Boomerang.
  • Memory Usage: 37.2 MB, less than 100.00% of Java online submissions for Valid Boomerang.

Heron’s formula

1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean isBoomerang(int[][] points) {
double a = Math.sqrt(Math.pow(points[1][0] - points[0][0], 2) + Math.pow(points[1][1] - points[0][1], 2));
double b = Math.sqrt(Math.pow(points[2][0] - points[1][0], 2) + Math.pow(points[2][1] - points[1][1], 2));
double c = Math.sqrt(Math.pow(points[2][0] - points[0][0], 2) + Math.pow(points[2][1] - points[0][1], 2));
double s = (a + b + c) / 2;
double A = Math.sqrt(s * (s - a) * (s - b) * (s - c));
return A != 0;
}
}

Submission Detail

  • 190 / 190 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Valid Boomerang.
  • Memory Usage: 36.9 MB, less than 83.23% of Java online submissions for Valid Boomerang.

Gauss’s area formula

Shoelace formula

let \( \mathbf {A} \) be the area of the triangle whose vertices are given by the coordinates \( (x_{1},y_{1}) \), \( (x_{2},y_{2}) \), and \( (x_{3},y_{3}) \).

\( \mathbf {A} \) can be written as a determinant

\( {\displaystyle \mathbf
{A} ={\frac {1}{2}}
{
\begin{vmatrix}1&1&1 \\
x_{1}&x_{2}&x_{3} \\
y_{1}&y_{2}&y_{3}
\end{vmatrix}
}
}
\)

If the coordinates are written in a clockwise order, the value of the determinant will be \( {\displaystyle -\mathbf {A} } \)

Rearranging another way

\( {\displaystyle \mathbf {A} ={\frac {1}{2}}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{1}y_{3}|} \)

which is the form of the shoelace formula. This formula can be extended to find the area of any polygon since a simple polygon can be divided into triangles.

1
2
3
4
5
6
7
class Solution {
public boolean isBoomerang(int[][] points) {
int A = points[0][0] * points[1][1] + points[1][0] * points[2][1] + points[2][0] * points[0][1]
- points[1][0] * points[0][1] - points[2][0] * points[1][1] - points[0][0] * points[2][1];
return A != 0;
}
}

Submission Detail

  • 190 / 190 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Valid Boomerang.
  • Memory Usage: 37.7 MB, less than 15.65% of Java online submissions for Valid Boomerang.

LeetCode - Algorithms - 35. Search Insert Position

Problem

35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int searchInsert(int[] nums, int target) {
int left=0, right=nums.length-1;
int mid=0;
while(left<=right) {
mid = (left+right)/2;
if (nums[mid]>target) {
right = mid-1;
}
else if (nums[mid]<target){
left = mid+1;
}
else
return mid;
}
if (target>nums[mid])
return mid+1;
else
return mid;
}
}

Submission Detail

  • 62 / 62 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Search Insert Position.
  • Memory Usage: 38.9 MB, less than 100.00% of Java online submissions for Search Insert Position.

JPA and Hibernate

  • Hibernate, as an ORM solution, effectively “sits between” the Java application data access layer and the Relational Database.
  • As a JPA provider, Hibernate implements the Java Persistence API specifications.

JPA annotations

@Entity

The @Entity annotation is used to specify that the currently annotate class represents an entity type. Unlike basic and embeddable types, entity types have an identity and their state is managed by the underlying Persistence Context.

@Table

The @Table annotation is used to specify the primary table of the currently annotated entity.

@Column

The @Column annotation is used to specify the mapping between a basic entity attribute and the database table column.

@Id

The @Id annotation specifies the entity identifier. An entity must always have an identifier attribute which is used when loading the entity in a given Persistence Context.

@GeneratedValue

The @GeneratedValue annotation specifies that the entity identifier value is automatically generated using an identity column, a database sequence, or a table generator. Hibernate supports the @GeneratedValue mapping even for UUID identifiers.

@Temporal

The @Temporal annotation is used to specify the TemporalType of the currently annotated java.util.Date or java.util.Calendar entity attribute.

@Enumerated

The @Enumerated annotation is used to specify that an entity attribute represents an enumerated type.

@ManyToOne

The @ManyToOne annotation is used to specify a many-to-one database relationship.

@JoinColumn

The @JoinColumn annotation is used to specify the FOREIGN KEY column used when joining an entity association or an embeddable collection.

@OneToMany

If the @OneToMany doesn’t have a mirroring @ManyToOne association on the child side, the @OneToMany association is unidirectional. If there is a @ManyToOne association on the child side, the @OneToMany association is bidirectional and the application developer can navigate this relationship from both ends.

Every bidirectional association must have one owning side only (the child side), the other one being referred to as the inverse (or the mappedBy) side.

@OneToOne

The @OneToOne annotation is used to specify a one-to-one database relationship.

Hibernate annotations

@Where

The @Where annotation is used to specify a custom SQL WHERE clause used when fetching an entity or a collection.

ref

24. Mapping annotations
https://docs.jboss.org/hibernate/orm/5.3/userguide/html_single/Hibernate_User_Guide.html#annotations

All JPA Annotations: Mapping Annotations
Let’s take a look at ALL the JPA mapping annotations.
https://dzone.com/articles/all-jpa-annotations-mapping-annotations

javax.persistence
Annotation Type OneToMany
https://docs.oracle.com/javaee/7/api/javax/persistence/OneToMany.html

The best way to map a @OneToMany relationship with JPA and Hibernate
https://vladmihalcea.com/the-best-way-to-map-a-onetomany-association-with-jpa-and-hibernate/

LeetCode - Algorithms - 50. Pow(x, n)

Problem

50. Pow(x, n)

Java

Accepted

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix.

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 double myPow(double x, int n) {
if (x==0.0d && n==0)
return Double.POSITIVE_INFINITY;
if (n>=0) {
return myPow_recur(x, n);
}
else {
double reciprocal = myPow_recur(x, -n);
return 1.0/reciprocal;
}
}

private double myPow_recur(double x, int n) {
if (n==0) return 1;
double square = myPow_recur(x,n/2);
if ( (n & 1) == 1 ) {
return x*square*square;
}
return square*square;
}
}

Submission Detail

  • 304 / 304 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Pow(x, n).
  • Memory Usage: 36.6 MB, less than 5.88% of Java online submissions for Pow(x, n).

Time Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public double myPow(double x, int n) {
if (x==0.0d && n==0)
return Double.POSITIVE_INFINITY;
double y = 1;
if (n==0)
y=1;
if (n>0) {
for(int i=n;i>0;i--)
y*=x;
}
if (n<0) {
double reciprocal = 1;
for(int i=-n;i>0;i--)
reciprocal*=x;
y = 1.0/reciprocal;
}
return y;
}
}

Submission Detail

  • 299 / 304 test cases passed.
  • Status: Time Limit Exceeded

ref

The Green Grass Under The Snow

By Annie A. Preston

The Work of the sun is slow,
But as sure as heaven, we know;
So we’ll not forget,
When the skies are wet,
There’s green grass under the snow.

When the winds of winter blow,
Wailing like voices of woe,
There are April showers,
And buds and flowers,
And green grass under the snow.

We find that it’s ever so
In this life’s uneven flow;
We’ve only to wait,
In the face of fate,
For the green grass under the snow.

LeetCode - Algorithms - 704. Binary Search

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky … — Donald Knuth

in the history in Section 6.2.1 of his Sorting and Searching, Knuth points out that while the first binary search was published in 1946, the first published binary search without bugs did not appear untial 1962. – Programming Pearls, Jon Bentley

Problem

704. Binary Search

Java

1

Copyright © 2000–2019 Robert Sedgewick and Kevin Wayne. All rights reserved.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int search(int[] nums, int target) {
int lo = 0;
int hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (target < nums[mid])
hi = mid - 1;
else if (target > nums[mid])
lo = mid + 1;
else
return mid;
}
return -1;
}
}

Submission Detail

  • 46 / 46 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Search.
  • Memory Usage: 40.6 MB, less than 29.73% of Java online submissions for Binary Search.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int search(int[] nums, int target) {
final int len = nums.length;
int left=0, right=len-1;
while(left<=right) {
int mid = (left+right)/2;
if (nums[mid]>target) {
right = mid-1;
}
else if (nums[mid]<target){
left = mid+1;
}
else {
return mid;
}
}
return -1;
}
}

Submission Detail

  • 46 / 46 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Search.
  • Memory Usage: 42.8 MB, less than 5.41% of Java online submissions for Binary Search.

ref

Do we see reality as it is? - Donald Hoffman - TED2015 - Transcript

Cognitive scientist Donald Hoffman is trying to answer a big question: Do we experience the world as it really is … or as we need it to be? In this ever so slightly mind-blowing talk, he ponders how our minds construct reality for us.

I love a great mystery, and I’m fascinated by the greatest unsolved mystery in science, perhaps because it’s personal. It’s about who we are, and I can’t help but be curious.

The mystery is this: What is the relationship between your brain and your conscious experiences, such as your experience of the taste of chocolate or the feeling of velvet?

Now, this mystery is not new. In 1868, Thomas Huxley wrote, “How it is that anything so remarkable as a state of consciousness comes about as the result of irritating nervous tissue is just as unaccountable as the appearance of the genie when Aladdin rubbed his lamp.” Now, Huxley knew that brain activity and conscious experiences are correlated, but he didn’t know why. To the science of his day, it was a mystery. In the years since Huxley, science has learned a lot about brain activity, but the relationship between brain activity and conscious experiences is still a mystery. Why? Why have we made so little progress? Well, some experts think that we can’t solve this problem because we lack the necessary concepts and intelligence. We don’t expect monkeys to solve problems in quantum mechanics, and as it happens, we can’t expect our species to solve this problem either. Well, I disagree. I’m more optimistic. I think we’ve simply made a false assumption. Once we fix it, we just might solve this problem. Today, I’d like tell you what that assumption is, why it’s false, and how to fix it.

Let’s begin with a question: Do we see reality as it is? I open my eyes and I have an experience that I describe as a red tomato a meter away. As a result, I come to believe that in reality, there’s a red tomato a meter away. I then close my eyes, and my experience changes to a gray field, but is it still the case that in reality, there’s a red tomato a meter away? I think so, but could I be wrong? Could I be misinterpreting the nature of my perceptions?

We have misinterpreted our perceptions before. We used to think the Earth is flat, because it looks that way. Pythagorus discovered that we were wrong. Then we thought that the Earth is the unmoving center of the Universe, again because it looks that way. Copernicus and Galileo discovered, again, that we were wrong.

Galileo then wondered if we might be misinterpreting our experiences in other ways. He wrote: “I think that tastes, odors, colors, and so on reside in consciousness. Hence if the living creature were removed, all these qualities would be annihilated.”

Now, that’s a stunning claim. Could Galileo be right? Could we really be misinterpreting our experiences that badly? What does modern science have to say about this?

Well, neuroscientists tell us that about a third of the brain’s cortex is engaged in vision. When you simply open your eyes and look about this room, billions of neurons and trillions of synapses are engaged.

Now, this is a bit surprising, because to the extent that we think about vision at all, we think of it as like a camera. It just takes a picture of objective reality as it is. Now, there is a part of vision that’s like a camera: the eye has a lens that focuses an image on the back of the eye where there are 130 million photoreceptors, so the eye is like a 130-megapixel camera. But that doesn’t explain the billions of neurons and trillions of synapses that are engaged in vision. What are these neurons up to?

Well, neuroscientists tell us that they are creating, in real time, all the shapes, objects, colors, and motions that we see. It feels like we’re just taking a snapshot of this room the way it is, but in fact, we’re constructing everything that we see. We don’t construct the whole world at once. We construct what we need in the moment.

Now, there are many demonstrations that are quite compelling that we construct what we see. I’ll just show you two. In this example, you see some red discs with bits cut out of them, but if I just rotate the disks a little bit, suddenly, you see a 3D cube pop out of the screen. Now, the screen of course is flat, so the three-dimensional cube that you’re experiencing must be your construction.

In this next example, you see glowing blue bars with pretty sharp edges moving across a field of dots. In fact, no dots move. All I’m doing from frame to frame is changing the colors of dots from blue to black or black to blue. But when I do this quickly, your visual system creates the glowing blue bars with the sharp edges and the motion. There are many more examples, but these are just two that you construct what you see.

But neuroscientists go further. They say that we reconstruct reality. So, when I have an experience that I describe as a red tomato, that experience is actually an accurate reconstruction of the properties of a real red tomato that would exist even if I weren’t looking.

Now, why would neuroscientists say that we don’t just construct, we reconstruct? Well, the standard argument given is usually an evolutionary one. Those of our ancestors who saw more accurately had a competitive advantage compared to those who saw less accurately, and therefore they were more likely to pass on their genes. We are the offspring of those who saw more accurately, and so we can be confident that, in the normal case, our perceptions are accurate. You see this in the standard textbooks. One textbook says, for example, “Evolutionarily speaking, vision is useful precisely because it is so accurate.” So the idea is that accurate perceptions are fitter perceptions. They give you a survival advantage.

Now, is this correct? Is this the right interpretation of evolutionary theory? Well, let’s first look at a couple of examples in nature.

The Australian jewel beetle is dimpled, glossy and brown. The female is flightless. The male flies, looking, of course, for a hot female. When he finds one, he alights and mates. There’s another species in the outback, Homo sapiens. The male of this species has a massive brain that he uses to hunt for cold beer. (Laughter) And when he finds one, he drains it, and sometimes throws the bottle into the outback. Now, as it happens, these bottles are dimpled, glossy, and just the right shade of brown to tickle the fancy of these beetles. The males swarm all over the bottles trying to mate. They lose all interest in the real females. Classic case of the male leaving the female for the bottle. (Laughter) (Applause) The species almost went extinct. Australia had to change its bottles to save its beetles. (Laughter) Now, the males had successfully found females for thousands, perhaps millions of years. It looked like they saw reality as it is, but apparently not. Evolution had given them a hack. A female is anything dimpled, glossy and brown, the bigger the better. (Laughter) Even when crawling all over the bottle, the male couldn’t discover his mistake.

Now, you might say, beetles, sure, they’re very simple creatures, but surely not mammals. Mammals don’t rely on tricks. Well, I won’t dwell on this, but you get the idea. (Laughter)

So this raises an important technical question: Does natural selection really favor seeing reality as it is? Fortunately, we don’t have to wave our hands and guess; evolution is a mathematically precise theory. We can use the equations of evolution to check this out. We can have various organisms in artificial worlds compete and see which survive and which thrive, which sensory systems are more fit.

A key notion in those equations is fitness. Consider this steak: What does this steak do for the fitness of an animal? Well, for a hungry lion looking to eat, it enhances fitness. For a well-fed lion looking to mate, it doesn’t enhance fitness. And for a rabbit in any state, it doesn’t enhance fitness, so fitness does depend on reality as it is, yes, but also on the organism, its state and its action. Fitness is not the same thing as reality as it is, and it’s fitness, and not reality as it is, that figures centrally in the equations of evolution.

So, in my lab, we have run hundreds of thousands of evolutionary game simulations with lots of different randomly chosen worlds and organisms that compete for resources in those worlds. Some of the organisms see all of the reality, others see just part of the reality, and some see none of the reality, only fitness. Who wins?

Well, I hate to break it to you, but perception of reality goes extinct. In almost every simulation, organisms that see none of reality but are just tuned to fitness drive to extinction all the organisms that perceive reality as it is. So the bottom line is, evolution does not favor veridical, or accurate perceptions. Those perceptions of reality go extinct.

Now, this is a bit stunning. How can it be that not seeing the world accurately gives us a survival advantage? That is a bit counterintuitive. But remember the jewel beetle. The jewel beetle survived for thousands, perhaps millions of years, using simple tricks and hacks. What the equations of evolution are telling us is that all organisms, including us, are in the same boat as the jewel beetle. We do not see reality as it is. We’re shaped with tricks and hacks that keep us alive.

Still, we need some help with our intuitions. How can not perceiving reality as it is be useful? Well, fortunately, we have a very helpful metaphor: the desktop interface on your computer. Consider that blue icon for a TED Talk that you’re writing. Now, the icon is blue and rectangular and in the lower right corner of the desktop. Does that mean that the text file itself in the computer is blue, rectangular, and in the lower right-hand corner of the computer? Of course not. Anyone who thought that misinterprets the purpose of the interface. It’s not there to show you the reality of the computer. In fact, it’s there to hide that reality. You don’t want to know about the diodes and resistors and all the megabytes of software. If you had to deal with that, you could never write your text file or edit your photo. So the idea is that evolution has given us an interface that hides reality and guides adaptive behavior. Space and time, as you perceive them right now, are your desktop. Physical objects are simply icons in that desktop.

There’s an obvious objection. Hoffman, if you think that train coming down the track at 200 MPH is just an icon of your desktop, why don’t you step in front of it? And after you’re gone, and your theory with you, we’ll know that there’s more to that train than just an icon. Well, I wouldn’t step in front of that train for the same reason that I wouldn’t carelessly drag that icon to the trash can: not because I take the icon literally – the file is not literally blue or rectangular – but I do take it seriously. I could lose weeks of work. Similarly, evolution has shaped us with perceptual symbols that are designed to keep us alive. We’d better take them seriously. If you see a snake, don’t pick it up. If you see a cliff, don’t jump off. They’re designed to keep us safe, and we should take them seriously. That does not mean that we should take them literally. That’s a logical error.

Another objection: There’s nothing really new here. Physicists have told us for a long time that the metal of that train looks solid but really it’s mostly empty space with microscopic particles zipping around. There’s nothing new here. Well, not exactly. It’s like saying, I know that that blue icon on the desktop is not the reality of the computer, but if I pull out my trusty magnifying glass and look really closely, I see little pixels, and that’s the reality of the computer. Well, not really – you’re still on the desktop, and that’s the point. Those microscopic particles are still in space and time: they’re still in the user interface. So I’m saying something far more radical than those physicists.

Finally, you might object, look, we all see the train, therefore none of us constructs the train. But remember this example. In this example, we all see a cube, but the screen is flat, so the cube that you see is the cube that you construct. We all see a cube because we all, each one of us, constructs the cube that we see. The same is true of the train. We all see a train because we each see the train that we construct, and the same is true of all physical objects.

We’re inclined to think that perception is like a window on reality as it is. The theory of evolution is telling us that this is an incorrect interpretation of our perceptions. Instead, reality is more like a 3D desktop that’s designed to hide the complexity of the real world and guide adaptive behavior. Space as you perceive it is your desktop. Physical objects are just the icons in that desktop.

We used to think that the Earth is flat because it looks that way. Then we thought that the Earth is the unmoving center of reality because it looks that way. We were wrong. We had misinterpreted our perceptions. Now we believe that spacetime and objects are the nature of reality as it is. The theory of evolution is telling us that once again, we’re wrong. We’re misinterpreting the content of our perceptual experiences. There’s something that exists when you don’t look, but it’s not spacetime and physical objects. It’s as hard for us to let go of spacetime and objects as it is for the jewel beetle to let go of its bottle. Why? Because we’re blind to our own blindnesses. But we have an advantage over the jewel beetle: our science and technology. By peering through the lens of a telescope we discovered that the Earth is not the unmoving center of reality, and by peering through the lens of the theory of evolution we discovered that spacetime and objects are not the nature of reality. When I have a perceptual experience that I describe as a red tomato, I am interacting with reality, but that reality is not a red tomato and is nothing like a red tomato. Similarly, when I have an experience that I describe as a lion or a steak, I’m interacting with reality, but that reality is not a lion or a steak. And here’s the kicker: When I have a perceptual experience that I describe as a brain, or neurons, I am interacting with reality, but that reality is not a brain or neurons and is nothing like a brain or neurons. And that reality, whatever it is, is the real source of cause and effect in the world – not brains, not neurons. Brains and neurons have no causal powers. They cause none of our perceptual experiences, and none of our behavior. Brains and neurons are a species-specific set of symbols, a hack.

What does this mean for the mystery of consciousness? Well, it opens up new possibilities. For instance, perhaps reality is some vast machine that causes our conscious experiences. I doubt this, but it’s worth exploring. Perhaps reality is some vast, interacting network of conscious agents, simple and complex, that cause each other’s conscious experiences. Actually, this isn’t as crazy an idea as it seems, and I’m currently exploring it.

But here’s the point: Once we let go of our massively intuitive but massively false assumption about the nature of reality, it opens up new ways to think about life’s greatest mystery. I bet that reality will end up turning out to be more fascinating and unexpected than we’ve ever imagined.

The theory of evolution presents us with the ultimate dare: Dare to recognize that perception is not about seeing truth, it’s about having kids. And by the way, even this TED is just in your head.

Thank you very much.

(Applause)

Chris Anderson: If that’s really you there, thank you. So there’s so much from this. I mean, first of all, some people may just be profoundly depressed at the thought that, if evolution does not favor reality, I mean, doesn’t that to some extent undermine all our endeavors here, all our ability to think that we can think the truth, possibly even including your own theory, if you go there?

Donald Hoffman: Well, this does not stop us from a successful science. What we have is one theory that turned out to be false, that perception is like reality and reality is like our perceptions. That theory turns out to be false. Okay, throw that theory away. That doesn’t stop us from now postulating all sorts of other theories about the nature of reality, so it’s actually progress to recognize that one of our theories was false. So science continues as normal. There’s no problem here.

CA: So you think it’s possible – (Laughter) – This is cool, but what you’re saying I think is it’s possible that evolution can still get you to reason.

DH: Yes. Now that’s a very, very good point. The evolutionary game simulations that I showed were specifically about perception, and they do show that our perceptions have been shaped not to show us reality as it is, but that does not mean the same thing about our logic or mathematics. We haven’t done these simulations, but my bet is that we’ll find that there are some selection pressures for our logic and our mathematics to be at least in the direction of truth. I mean, if you’re like me, math and logic is not easy. We don’t get it all right, but at least the selection pressures are not uniformly away from true math and logic. So I think that we’ll find that we have to look at each cognitive faculty one at a time and see what evolution does to it. What’s true about perception may not be true about math and logic.

CA: I mean, really what you’re proposing is a kind of modern-day Bishop Berkeley interpretation of the world: consciousness causes matter, not the other way around.

DH: Well, it’s slightly different than Berkeley. Berkeley thought that, he was a deist, and he thought that the ultimate nature of reality is God and so forth, and I don’t need to go where Berkeley’s going, so it’s quite a bit different from Berkeley. I call this conscious realism. It’s actually a very different approach.

CA: Don, I could literally talk with you for hours, and I hope to do that.

Thanks so much for that. DH: Thank you. (Applause)

LeetCode - Algorithms - 130. Surrounded Regions

Problem

130. Surrounded Regions

Java

BFS

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
class Solution {
private final static int d[][] = {
{0, 1},
{1, 0},
{0, -1},
{-1, 0}
};

public void solve(char[][] board) {
int h = board.length;
int w = h==0 ? 0 : board[0].length;

if (h==0 || w==0) return;

for (int j = 0; j < w; j++) {
if (board[0][j] == 'O') bfs(0, j, board, h, w);
if (board[h - 1][j] == 'O') bfs(h - 1, j, board, h, w);
}

for (int i = 1; i < h-1; i++) {
if (board[i][0] == 'O') bfs(i, 0, board, h, w);
if (board[i][w - 1] == 'O') bfs(i, w - 1, board, h, w);
}

for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == 'B') board[i][j] = 'O';
}
}
}

private void bfs(int i, int j, char[][] board, int h, int w) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(i,j));
while (!queue.isEmpty()) {
Point curr = queue.poll();
int row = curr.x;
int col = curr.y;
if (isValid(board, h, w, row, col)) {
board[row][col] = 'B';
for (int[] c: d) {
int x = curr.x + c[0];
int y = curr.y + c[1];
queue.add(new Point(x, y));
}
}
}
}

private boolean isValid(char[][] grid, int width, int height, int row, int col) {
return (row >= 0) && (row < width) && (col >= 0) && (col < height) && grid[row][col] == 'O';
}
}

class Point {
int x;
int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}
}

Submission Detail

  • 59 / 59 test cases passed.
  • Runtime: 2 ms, faster than 55.96% of Java online submissions for Surrounded Regions.
  • Memory Usage: 41.7 MB, less than 64.29% of Java online submissions for Surrounded Regions.

ref