Category Archives: Uncategorized

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What’s the unknown?

A: The next permutation of the current sequence.

Q: What’re the data?

A: An integer array representing a number.

Q: Any Constraints?

A: No extra memory allocation allowed. But I think it means extra memory proportional to the input size N. Besides, at the beginning of solving this problem, we can ignore this constraint.

Q: True. Now what’s the meaning of next permutation?

A: Hmm, I think it means the next number sequence of the current sequence in lexicographic order, e.g., (1,2, 5, 3,4) -> (1,2, 5, 4,3), (1, 5, 3,4,2) -> (1, 5, 4,2,3) and (5, 4,3,2,1) -> (1,2,3,4,5).

Q: Now as a human being, how do you do this?

A: Eh..just think of the smallest number comprised of these digits that is greater than the current sequence. If there is none, we go back to the smallest possible number in all permutation.

Q: OK, but a computer can’t just “think of” the next number. Now how would a computer do that?

A: Hmm, I think we probably need to start with the least digit on the right side. But what next?

Q: Look at the example you listed above. What did you do with each example?

A: In (1,2, 5, 3,4) -> (1,2, 5, 4,3), I start with 4 and look at its left digit, 3. Since 3 < 4, I switch them. Hmm this works for all cases where the second digit is less than the first one. In (1, 5, 3,4,2) -> (1, 5, 4,2,3), I can’t switch 4 and 2 since (1,5,3,2,4) precedes (1,5,3,4,2). Well 3 < 4, I could switch them to get (1,5,4,3,2) but that’s not the correct answer. Hmm…

Q: So how do you get from (1,5,4,3,2) to (1,5,4,2,3)?

A: I could just switch 3 and 2.

Q: OK, what about (1,5,3,4,2,0) to (1,5,4,0,2,3)?

A: Hmm if I switch 3 and 4, I get (1,5,4,3,2,0). To get (1,5,4,0,2,3), I need to reverse 3,2,0 to 0,2,3. OK, I guess we should do like this: scan from the right, find the first digit at index Ind that is less than its previous digit, switch them and reverse the sequence to the right side of Ind.

Q: Well, almost there, but not yet. What about (1,6,3,5,4,0)? According to your algorithm above, the next permutation becomes (1,6,5,0,4,3) while it should be (1,6,4,0,3,5). See the problem?

A: Hmm, so 3 should be the switch point. I got that right, but it should switch with 4 instead of 5. Ah, so 3 should switch its ceiling in the sequence on its right side! We need to go back to find it and swap. Then do the reverse operation.

Q: Correct, what about the time complexity?

A: We scan the sequence and once find the switch point, we go back and find its ceiling, then switch and reverse. End of story. So it’s actually O(n), an linear time algorithm.

Code on github:

 

Enhanced by Zemanta

Nuts and bolts

Nuts and bolts. A disorganized carpenter has a mixed pile of N nuts and N bolts. The goal is to find the corresponding pairs of nuts and bolts. Each nut fits exactly one bolt and each bolt fits exactly one nut. By fitting a nut and a bolt together, the carpenter can see which one is bigger (but the carpenter cannot compare two nuts or two bolts directly). Design an algorithm for the problem that uses NlogN compares (probabilistically).

My thoughts and solution:

Well, according to the question, the nut and bolt has a one-to-one relation. So the first thing come into my mind is to sort the nuts and bolts into ascending order and then we can put them together to a pair one by one.

However, we cannot compare two nuts or bolts directly. So we have to think about indirect ways. Say we have two nuts N1 and N2. Well, since the nut and bolt has a one-to=one relation, there must exist two bolts B1 and B2 which exactly fit with N1 and N2. So if we try to fit both nuts with B1 (or B2), we can tell which nut is bigger. This is also suggested by the question that By fitting a nut and a bolt together, the carpenter can see which one is bigger”. The same works for comparing B1 and B2 indirectly.

OK, the question did mention NlogN compares probabilistically. Well that reminds me of QuickSort. So how does it apply here? QuickSort requires partitioning and recursion. OK, let’s look at partitioning.

To partition the nuts, we need to randomly select one nut, then compare it with the rest. But we cannot, at least not directly. So the alternative is to randomly select one bolt “B”, then compare each nut with it. In the end, we will have two small piles of nuts (one smaller than the bolt “S” and the other larger “L”) and the right one fits in the bolt “N”. Done!

Then we can do recursion, right? for both piles of nuts, randomly choose a bolt to partition…But wait! Whatever bolt we pick for “S” should come from the set of bolts that correspond to the nuts in “S” and so is the case for “L”. Otherwise, we cannot guarantee the correctness of the QuickSort algorithm.

So before we do the recursion, we have to find out the corresponding piles of bolts for “S” and “L”. How? Well, we do know the nut “N” that fits into “B” perfectly. We can do a partition of the bolts based on “N”. Then we will get our desired piles of bolts for “S” and “L”.

Now we can go on to the recursion.

About the comparison, it is O(NlogN). But I’m afraid we are using 2NlogN since we compared 2N in partitioning  the bolts and nuts. If you have some good ideas, please leave some comments.

Enhanced by Zemanta

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

A short summary of problems with strings and arrays

This is just a short summary of what I have learned from the previous problems.

  1.  If you are dealing with Java Strings, converting it to character array might be helpful.
  2. Ask about the type of characters in the string. Are they ASCII characters?
  3. Sometimes you will count the frequency of the characters in the string, so ask the second question is important. If they are all ASCII characters, you can just use an array of size 256.
  4. If you are not allowed to use additional data structures doing string manipulation, think about bit manipulation. The bit format provides you more stuff to work on. You may also want to consider using two index variables to keep track of the character’s position.
  5. Two ways to exam characters in a string: from the current position and look into the latter parts of the string; or from the current position and look back into the previous parts of the string (which you can keep track of, e.g., character frequency).
  6. If you are dealing with expanding, consider starting from the end of the string. Otherwise, start from the beginning of the string.
  7. If the question gives you something (for example, a known function) and you can’t relate it to the question directly, try apply the function simply on the data that are given. See how far the result of that is from the expectation.
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