Tag Archives: George Pólya

Delete a middle node from a singly linked list with only the access to this node—A conversation

Algorithm is one the fundamental components that a programmer should master. But every time I read a book about it, I see intrusive instructions about how to solve a problem using several algorithms. Well they just tell you that you should use this and that. Sure, they are brilliant ideas, but how do those ideas come up? If we do not know this process, it is hard to say we have really learned.

I’ve been reading the book “How to solve it” by George Pólya. It is a great book that shows you how to approach a problem using various steps. You can ask about certain questions and answer them to get a better chance to obtain the final solution. Although this book is about mathematics, I think it also applies for algorithms or even just problems in general. So I’d like to write the conversation I made myself to show the process of how we get an algorithm without giving intrusive instructions. These are just my humble ideas and suggestions are always welcome.

====================================================================

Q: What is the unknown? What is our goal?

A: Eh a way to delete a node in a linked list.

Q: What are the data?

A: A node and a linked list.

Q: What are the conditions and restrictions?

A: The list is singly linked. The node is in the middle of the list. And we only have access to the node to delete.

Q: What does it mean by singly linked?

A: It means the node only knows which node is the next but not the one precedes it.

Q: What does it mean by in the middle?

A: It means the node is not the head or the tail of the linked list.

Q: What does it mean by “only access to this node”?

A: Eh I guess it means we do not have access to the head of the list…only the node we want to delete is provided…man this is impossible!

Q: Why do you think it is impossible?

A: Well, to delete a node in a singly linked list, we have to know which node precedes it at least. That means we need to know the head node…

Q: Well the head is not provided.  Let’s forget about the restriction and look at an example. Can you think of an example of deleting a middle node from a singly linked list?

A: Sure. Say we have a->b->c->d->e->null and we want to delete c.

Q: So what does the linked list looks like after the deletion?

A: a->b->d->e->null.

Q: Is there any other way other deletion you can use to get this result?

A: ….

Q: What are the differences between these two lists? (Comparison side by side!)

    a->b->c->d->e->null

    a->b->d->e->null

A: Well their lengths are different. Actually I don’t think we know what precedes c. So I would write the lists like the following:

   x->x->c->d->e->null;

   x->x->d->e->null;

Q: You got a point. We should only focus on things after c. Maybe I should ask a different question. Are there any differences for node d and e before and after the deletion?

A: I don’t know. Their values stay the same…wait, but their position changed after the deletion.

Q: You mentioned the value in the node. So deleting a node means…?

A: That we don’t want this value any more.

Q: Think about these two factors: value, and position shift…node can shift. What about value?

A: Eh we can shift the value too…Ah right instead of shifting the nodes…So I just need to copy the value of the nodes following c to the previous nodes and delete the last node…

Q: Correct.

A: Orz…OK.

Q: Yeah I know it may not come into your mind at first glance. The restrictions confine your mind. Compare the example before and after an operation. Think about different ways to achieve the same effect. 

Features of a LinkedListNode: data, next node and position!

 Link to the code on github (You will need the first one to run the second one):

https://github.com/jingz8804/Algorithms-and-Problems/blob/master/src/careerCup/LinkedListNode.java

https://github.com/jingz8804/Algorithms-and-Problems/blob/master/src/careerCup/DeleteAMiddleNode.java

Enhanced by Zemanta

Determine if one string is a rotation of another string — A conversation

Algorithm is one the fundamental components that a programmer should master. But every time I read a book about it, I see intrusive instructions about how to solve a problem using several algorithms. Well they just tell you that you should use this and that. Sure, they are brilliant ideas, but how do those ideas come up? If we do not know this process, it is hard to say we have really learned.

I’ve been reading the book “How to solve it” by George Pólya. It is a great book that shows you how to approach a problem using various steps. You can ask about certain questions and answer them to get a better chance to obtain the final solution. Although this book is about mathematics, I think it also applies for algorithms or even just problems in general. So I’d like to write the conversation I made myself to show the process of how we get an algorithm without giving intrusive instructions. These are just my humble ideas and suggestions are always welcome.

====================================================================

Assume you have a method isSubstring which checks if one word is a substring of another Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”).

Q: What is the unknown? What is the goal?

A: To determine if one string is a rotation of another string.

Q: What are the data? Or can you imagine any examples for this problem?

A: Eh sure. We have an example already right? waterbottle and erbottlewat.

Q: What are the conditions or restrictions?

A: We have a method isSubstring which checks if one is a substring of another. But we can only use it once…

Q: Good. Have you seen it before? Or a similar problem in a different form?

A: Eh not really…Although I did solve a problem about if a string is a substring of another. But we’ve already have the solution for it here.

Q: That’s right. Is it possible to use it?

A: Eh OK, one string is a substring of another… how can I use it on this problem…

Q: Can you use it on our data? On the strings we have here?

A: Well, waterbottle is certainly not the substring of erbottlewat…

Q: That’s true. But waterbottle can be a substring of something, right?

A: Eh sure…

Q: What could that string be like?

A: Eh something string with “waterbottle” as a part, for example XXXwaterbottleXXX.

Q: Correct. So can we create such a string?

A: Sure…waterbottlewaterbottle.

Q: OK that’s one way. Any other way?

A: ….

Q: Have you used all the data?

A: Eh no, I still have erbottlewat… Ah you mean use it twice too? OK erbottlewaterbottlewat.

Q: Look at them carefully. What do you see?

A: ….

Q: When you concatenate waterbottle twice, does the new string contain something special? Same question for concatenate erbottlewat twice…

A: Something special…Ah I see erbottlewat in waterbottlewaterbottle and waterbottle in erbottlewaterbottlewat!

Q: Correct! Now do you see a connection between this and the rotation?

A: Hmm probably, if A is a rotation of B, then B will be a substring of AA. Otherwise this is not true.

Q: This is an assumption, we have an example which satisfies the first part. Think of an example of the latter situation.

A: OK, water and erwta. Is water a substring of erwtaerwta? I guess not. Man this is a bit tricky…If you don’t start on this direction, you probably will never land on this solution.

Q: Yeah it is possible. The question gives you something to use. So just try to apply it without any complicated thought. You may find it useful. One more thing here: What if the strings have different length?

A: Well certainly they do not satisfy the conditions. But we didn’t check it yet. Ah so we should check the length first, or even check the null first! Good catch.

link to the Java code on github (I have to say the code is really simple but the concept here is a really good one):

https://github.com/jingz8804/Algorithms-and-Problems/blob/master/src/careerCup/IsRotation.java

Enhanced by Zemanta

Rotate an n-by-n matrix 90 degrees clockwise in place — A conversation

Algorithm is one the fundamental components that a programmer should master. But every time I read a book about it, I see intrusive instructions about how to solve a problem using several algorithms. Well they just tell you that you should use this and that. Sure, they are brilliant ideas, but how do those ideas come up? If we do not know this process, it is hard to say we have really learned.

I’ve been reading the book “How to solve it” by George Pólya. It is a great book that shows you how to approach a problem using various steps. You can ask about certain questions and answer them to get a better chance to obtain the final solution. Although this book is about mathematics, I think it also applies for algorithms or even just problems in general. So I’d like to write the conversation I made myself to show the process of how we get an algorithm without giving intrusive instructions. These are just my humble ideas and suggestions are always welcome.

====================================================================

Rotate an n-by-n matrix 90 degrees clockwise in place.
Q: What is the unknown? What is our goal?
A: A way to rotate a matrix in place.
Q: What are the conditions?
A: The matrix is n-by-n. We rotate 90 degrees clockwise. And we have to do it in place.
Q: What does it mean by “in place”?
A: That means you have to do this on the matrix itself with no support from other data structures.
Q: What are the data?
A: An n-by-n matrix.
Q: Can you give me some examples?
A: Sure. Say a 3-by-3 matrix is
                                               [1,2,3]
                                               [4,5,6]
                                               [7,8,9]
     And a 4-by-4 matrix is
                                               [1,2,3,4]
                                               [5,6,7,8]
                                               [9,10,11,12]
                                               [13,14,15,16]
Q: Have you seen it before? Or have you seen a similar problem in a slightly different form?
A: Not really, although I did work on something else on matrix.
Q: And what is that?
A: Ah simply switch the elements of a matrix across a diagonal.
Q: Do you think you can use it including its result and method?
A: I don’t know…
Q: OK, let’s look at your example here. Suppose you rotate the 3-by-3 matrix. What will you get in the end?
A: Well I will get the following matrix:
                                               [7,4,1]
                                               [8,5,2]
                                               [9,6,3]
Q: What if you switch elements across the diagonal? What will you get?
A: I will get:
                                               [1,4,7]
                                               [2,5,8]
                                               [3,6,9]
Q: So how far is this matrix to the expected matrix?
A: Let me see. Oh I get it! It is a mirror switch!
Q: Correct. What steps did we do to rotate the matrix?
A: switch the elements across the diagonal and then mirror switch the elements across the middle column of the matrix.
Q: Good. But is it also true for a 4-by-4 matrix? 
A: Let me test it….Yeah it is also true.
Q: Nice. Now you have a plan. Implement it carefully.
(Note: The solution on the book use a different approach which I think is a bit complicated to implement. The running time is O(n^2) too. But it does provide
a different perspective: rotate the matrix layer by layer–start with the outer layer then move into the next one…)
If you do not know a similar problem (like the switch elements across the diagonal), ask yourself what kind of switching operation can you do on a matrix? (Similar to the question: What operation can you do with bits?)
That may help you list a few operations which include the diagonal and mirror switch. Try those switch and compare the result with the expected result.
If you cannot do it in one step, try to do it in several steps.
Link to the Java Code on GitHub:
Enhanced by Zemanta

Sorting Algorithm —- A Conversation

Algorithm is one the fundamental components that a programmer should master. But every time I read a book about it, I see intrusive instructions about how to solve a problem using several algorithms. Well they just tell you that you should use this and that. Sure, they are brilliant ideas, but how do those ideas come up? If we do not know this process, it is hard to say we have really learned.

I’ve been reading the book “How to solve it” by George Pólya. It is a great book that shows you how to approach a problem using various steps. You can ask about certain questions and answer them to get a better chance to obtain the final solution. Although this book is about mathematics, I think it also applies for algorithms or even just problems in general. So I’d like to write the conversation I made myself to show the process of how we get an algorithm without giving intrusive instructions. These are just my humble ideas and suggestions are always welcome.

This problem is about sorting: Suppose you have 100 numbers. They are 100 different cards and out of order. How can you sort them in ascending order?

Q: What is the unknown? What is your goal?
A: Find out a way to sort the numbers.
Q: What are the data?
A: 100 numbers written on cards that are not in order.
Q: Have you seen it before?
A: Well it is not hard to imagine. Just like you are sorting poker cards.
Q: OK Now tell me, how would you sort those cards?
A: Well, to start, I just pick a number and put it on the table. Then pick another one and compare this one with the former one. Based on the comparison, place it in the right position. And pick another one and compare this one with the former two and then place it in the right position. So this procedure just repeats: pick a new one, compare with the former ones and place it in the right position until there are no more new numbers to pick. I think this is a natural process to do.
Q: OK so you are doing a procedure repeatedly. What kind of component in programming is related to this?
A: Well loops. Eh and recursion?
Q: OK, so which one matches your need here?
A: I would say loop.
Q: So what should you do in the loop?
A: Like I said, pick a new number, compare with the former ones and place it in the right place.
Q: What is the ending condition?
A: The ending condition is that there is no more new number to pick.
Q: OK, you are comparing new number with former ones. what pattern do they have?
A: I’m not sure what you mean…
Q: OK, look at the unknown. What do we want to do with the data?
A: Sort the data and make sure they are in order.
Q: Now do the former numbers satisfy this condition when you exam them?
A: Eh, yeah sure.
Q: So they are…?
A: Sorted. in order.
Q: So every time you pick a new number, you are comparing it to data that are…?
A: Sorted. Yes I always compare the new number with data that are already sorted.
Q: Good. Now you mentioned that you need to place the new number correctly. Can you explain how to do it?
A: Well, we could start comparing the new number with the ones in the former sorted part one by one. If we found one N that is greater than the new number, then we should put it right before N.
Q: Well, what if the new number is larger than all numbers in the former sorted numbers?
A: In that case, we just put it at the end of the sorted numbers.
Q: Good. Do the former numbers have any other patterns?
A: Eh, every time I put a new number to the sorted part. So they are changing, if that counts.
Q: Sure. So it is changing and you need to use it every time. What should you do about it?
A: I guess I need to keep track of it.
Q: Good. Now you know you need a loop and what to do in the loop. Sounds like you have a plan. Be sure to check each step. Consider special cases. And when you are done, test it with some data to make sure you have the right algorithm.
=============================================================================
Q: Great now you have a solution for this problem. Is it possible to do it differently?
A: Eh, I don’t know.
Q: You mentioned recursion. Is it possible to solve this problem using recursion?
A: ….
Q: How does recursion usually works? What kind of problem does recursion apply to?
A: If you can solve a problem by dividing it into one or several sub-problems with smaller size that are similar or the same to the original problem, then you can consider recursion.
Q: Good, so can we apply it on our problem? What is the smaller problem here?
A: Well I can try. A smaller problem for us would be to sort a smaller collection of numbers. Say you have 50 numbers instead of 100.
Q: OK but your sub-problem must relate to the original problem. So these 50 numbers must be inside…
A: Oh right, these 50 numbers must be a subset of the original 100 numbers.
Q: Good. Now we only considered 50 numbers. What about the rest 50?
A: …
Q: You sorted 50 numbers. To get all 100 numbers sorted, what should you do about the rest?
A: Eh I guess we should sort them too. But I don’t know if we are heading to the right direction. At most we get two separately sorted collections. That is not the solution for the original problem.
Q: I’m glad you ask this question. Now the problem is whether we could get the sorted 100 numbers from two sorted subsets. Can you think about if this is possible?
A: …
Q: Can you think about an example of this situation?
A: OK, say we have 10 numbers: 3, 2, 1, 5, 6, 7, 9, 0, 8, 4. The final sorted array should be R(0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Assume we have two sorted subsets A (1,3,5,7,8) and B(0, 2, 4, 6, 9).  We are trying to get R from A and B. Hmm… interesting. We could just compare the head elements of both A and B, extract the smaller one from the collection it belongs to and put it in another collection C. W should repeat this process until one collection is empty (because of the extraction). Then if the other collection is not empty, just add the rest elements to C.
Q: Good call. Now for recursion, there are two cases. What are they?
A: Base case and recursive case.
Q: What is the base case?
A: The base case should be the case that the collection we are sorting only has one element and we can just return it.
Q: What about the recursive case?
A: eh we can divide the current collection in consideration into two subsets. Call the sort function on them and merge their results together and return it!
Q: Nice. Now you have a plan. Make sure you check each step and use some test cases on your algorithm.
Link to the Java Code on GitHub
Enhanced by Zemanta