Tag Archives: How to Solve It

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