# ZigZag Conversion

The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

```P   A   H   N
A P L S I I G
Y   I   R
```

And then read line by line: `"PAHNAPLSIIGYIR"`

Write the code that will take a string and make this conversion given a number of rows:

`string convert(string text, int nRows);`

`convert("PAYPALISHIRING", 3)` should return `"PAHNAPLSIIGYIR"`.

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

My thoughts and solutions:

OK, I actually saw a similar question before when I was tutoring a student learning a 100 level class. It was in python and instead of ZigZag, it was called something about building fence blocks. I know this provides no info for solving this problem to whoever is reading this, but I’m just trying to make a point that whatever we’ve done may help us in the future in different ways. So let’s keep trying out new things in our lives 🙂

A good way to solve this question is to play with the example.

Example 1:  “PAYPALISHIRING” and 3

To create the ZigZag version, we go through “PAY”, then “P”, then “ALI”, … till the end. That is to say:

1. scan and process 3 characters
2. scan and process 1 character
3. and repeat the first two steps till the end

Example 2: “PAYPALISHIRING” and 4

To create the ZigZag version, we go through “PAYP”, then “AL”, then “ISHI”, … till the end. That is to say:

1. scan and process 4 characters
2. scan and process 2 characters
3. and repeat the first two steps till the end

Now you can try more examples, but based on these two examples, we can at least generalize the following:

1. scan and process nRows characters
2. scan and process nRows – 2 characters
3. repeat the first two steps till the end

Here nRows have to be larger than 1. If nRows equals 1, we can simply just return the original string.

OK, now how do we process those characters in step 1? Look at the following figure, we see three rows. The first character P is on row 1, A on row 2 and Y on row 3. Each character processed in step 1 ended up in different places. Well, this indicates that we may need nRows number of containers to store the characters.

```P   A   H   N
A P L S I I G
Y   I   R```

What about the characters in Step 2? First of all, we have an order here. Once we are done with characters in the step 1, we should somehow notify the program that we are now in step 2. There’s no difference of how we process these characters between step 1 and 2, except that we should think about in which container we should put these characters.

Say we have nRows containers labeled as 0 to nRows – 1. So the characters in step 1 should be put into container_0 to container_nRows-1 one by one in this order. For those in step 2, they should be put into container_nRows-1-1 to container_1.

Since these are characters, we could use a StringBuilder object as a container. So, we got a basic plan now. We do need to think about some corner cases:

• The string is null or is an empty string
• nRows equals 1
• nRows equals 2 (better to check for this than being sorry later)

And we also need to think about creating variables to indicate whether we are in step 1 or 2.

Code on github:

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given `1->2->3->4->5->NULL`m = 2 and n = 4,

return `1->4->3->2->5->NULL`.

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

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

My thoughts and solutions:

Well, I did a similar question before, but that experience didn’t come to me immediately. So this is how I proceeded:

1. When I see reverse, I think about the Stack structure.
2. Reversing a linked list does not necessarily mean moving the whole node around. It may just require you to reverse the value in the node.
3. Moving the node somehow to reverse the list.

The question explicitly requires one pass and in-place, so idea No.1 is a no, but still valuable thought for other problems. I moved on to idea No. 2 and I got stuck for while. So maybe it is not the right direction for this question. OK, so move on to idea  No.3. I kept asking myself this question: have you seen it before? Then suddenly something came up: I solved a question of reversing a whole list in-place and one pass before. And this question is just a more general version.

Say we have a list:

N1 -> N2 -> N3 -> NULL

If we reverse the whole list, it becomes:

N3 -> N2 -> N1 -> NULL

OK. to get N1 -> NULL is easy, we just set N1.next = NULL. What about N2 -> N1 ? The same, we set N2.next = N1. Wait! How do we get to N2? Eh, N2 = N1.next. But did we just set N1.next = NULL? So we won’t be able get N2 now, unless we save the reference to N2 somewhere else before setting N1.next = NULL.

```Node current = N1;
Node previous = NULL;

Node nextNode = current.next;
current.next = previous;
previous = current; //previous points to N1;
current = nextNode; //current points to N2;
```

I hope you get the idea. This code snippet should be wrapped in a loop to process the whole list. But knowing this does not make things easier. The corner cases can be tricky and it took me a while to make sure the answer was bug-free. Do it manually, not in any IDE.

Things to check:

• when there is only one node in the list.
• when m = 1
• when m == n

Code on github:

# Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

```    1
/ \
2   2
/ \ / \
3  4 4  3```

But the following is not:

```    1
/ \
2   2
\   \
3    3```

Note:
Bonus points if you could solve it both recursively and iteratively.

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

My thoughts and solutions:

This problem looks simple, but actually is a little tricky. Usually when I see a problem like this I immediately think of recursion and come to the following wrong conclusion: the whole tree is symmetric when subtrees are symmetric. I stuck with this idea for a few minutes and then realized that this is not true.

```     1
/   \
2     4
/ \   / \
3   3 3   3```

The subtrees of the tree above are symmetric but the whole tree is not.

How do we human check if something is symmetric? In this case, we would probably check one node on the left side and compare with node at its mirroring position on the right. If they are the same, we move on to another node. Otherwise it is not symmetric.

So we are actually traversing the trees and along the way we check if a certain pair of nodes in mirroring positions have the same value.

As for tree traversal, we have breadth-first and depth-first traversals. But we may have to make some modifications.

Using the following tree as an example:

```     N1
/   \
N2    N3
/ \   / \
N4 N5 N6 N7```
• Breadth-First: in a normal situation, we would use a queue, starting from the root and keeping adding the child nodes.  The queue would be N1, N2, N3, N4, N5, N6, N7. But since we need the mirroring effect, the queue should be N1, N2, N3, N4, N7, N5, N6. So think about how to achieve this order when dealing with nodes. When comparing, we have to dequeue two nodes at a time (except for the root of the tree N1).
• Depth-First: in this case, say we want to use recursion. Basically we traverse the left subtree from N2 and do the same for N3. We won’t be able to compare two nodes in mirroring position along the way. So we have to save the values somewhere. I say we use a stack. The order of the two traversals should be like this: left side should be N2, N4, N5 while right side should be N3, N7, N6. Each time we meet a node, we push its value to the stack and go to their child nodes. If a child node is null, we must push null to the stack too! Otherwise it will fail on the second example in this post.

Code on github:

# Path simplify

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = `"/home/"`, => `"/home"`
path = `"/a/./b/../../c/"`, => `"/c"`

Corner Cases:

• Did you consider the case where path = `"/../"`?
In this case, you should return `"/"`.
• Another corner case is the path might contain multiple slashes `'/'` together, such as `"/home//foo/"`.
In this case, you should ignore redundant slashes and return `"/home/foo"`.

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

My thoughts and solutions:

Well it’s not difficult, but there are something worth noting. The examples above should also tell us that the path may or may not end with ‘/’. So be sure to deal with cases like /abc/…

So when we are evaluating the path ourselves,  we do in the following way (e.g., ‘/a/./b/../../c/’)

1. ‘a’ means /a
2. ‘.’ means we stay on the current level, so still ‘/a’
4. ‘..’ means we have to go up, so we get ‘/a’ again
5. ‘..’ the same as above, so we get ‘/’
7. There is no more, so we end with ‘/c’

I don’t know if you notice anything here but I was reading about data structures for a while and one thing that caught my eyes was the string ‘..’ and its effect on the final path. If the string between two ‘/’ are not empty string, ‘.’ or ‘..’, we are adding them to the end of the final path. If it is ‘..’, we are removing it from the path. Well this sounds like push and pop operation to me. That’s it. Nothing fancy.

We will scan through the input and look for the strings (I used a StringBuilder here and be sure to initialize a new one for the new string you are trying to find here, otherwise the former string is still in the builder and you will get bugs) between two ‘/’s and push/pop them to/from the stack based on their values. Once the scan is completed, we can move the items in the stack to an array and use a StringBuilder to create the final path.

Code on github:

# Best Time to Buy and Sell Stock I

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

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

My thoughts and solutions:

Well in fact there are 3 questions in the series. I was actually working on the 3rd one because the OJ randomly picked it for me. I couldn’t figure it out but it helped me solving this one. Two thing worth mentioning:

• if you buy high sell low, your profit is 0, not negative (well that’s what the test result told me and you should ask this first in reality).
• You are not really making transactions until you figure out where to buy in and sell out to maximize the profit.

So suppose you can predict the future and have the price array in hand:

[5, 4, 1, 2, 8, 6, 9]

In this case you should buy in at price 1 and sell out at 9. It looks like a simple question looking for just min and max value. However, consider the following:

[5, 4, 9, 2, 8, 6, 1]

Well in this case, you should buy in at price 2 but sell out at 8, but the min is still 1 and max is still 9. So be careful.

The simplest way would be using 2 loops and find out the max profit of you buying at each price. But that would take O(n^2) time. So can we do better than that?

From here I have two ways of thinking: one that is a bit more logical that following the above question (but I figured it out after I solved the problem) and the other that is a bit jumpy (but that was how I solved the problem in the first place).

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

The first way:

Well what is taking so long is that we are going two passes, what if we could just use one pass? We scan the array and keep updating the max profit along the way? How can we do that? Well surely we need something to keep track of the max profit. Do we need something else? I’m stuck here. And when you are stuck, try a simple example:

[5, 4, 1, 2, 8, 6, 9]

Suppose we are scanning and at price 8. And this moment, what is the max profit we can get? It’s 7. How do we get it? We buy in at price 1 and sell at 8.  But wait, right now we only keep track of the max profit. We don’t know where we are planning to buy (well I know, and you know, in the brain, but the computer doesn’t since nothing is keeping track of it). So, it looks like we should keep track of two things:

• Based on what we have scanned, the price we are going to buy in (the current minimum).
• Based on what we have scanned, the current maximum profit we can make.

How to update?

• If the current price is lower than the current min, we can’t make any profit, so we keep the current max profit but update the current min price (and hope this new min can give us a higher profit later. Sadly we can’t go back in the opposite direction. See the first two examples).
• If the current price is higher than the current min, then we can make a profit: If the new profit is higher, we update the current max profit but keep the same min price. Otherwise, we do no update on both variables.

I believe this is an O(n) time algorithm since we are doing one scan and nothing more.

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

The second way:

Well this one is a bit jumpy. I have been reading about recursion lately. So I thought why not try solving it with recursion? So use recursion, we need to identify a similar problem with a smaller size. For example, to find the max profit of [5, 4, 1, 2, 8, 6, 9], is to find the max profit of [4, 1, 2, 8, 6, 9] and then do something with 5. But what exactly? Well, our goal is to get the max profit. Is it possible that we could update the max profit with 5? That depends. If the difference between 5 and the maximum of [4, 1, 2, 8, 6, 9] is greater than the older max profit, we update. Otherwise we don’t. This indicate that we need to keep track of the max profit and the maximum price at the same time. Unfortunately, Java cannot return multiple values but we can wrap them in an object, or wrap one of them in an Integer object. This algorithm works, until it hit a big input and reported a stackoverflow error. We will fix it later.

We can also think of another way: a similar problem but in the opposite direction. We look at [5, 4, 1, 2, 8, 6] and 9. We get the max profit of the latter and do something with 9. Whether to update the max profit depends on the difference between 9 and the previous low price we are supposed to buy in. This algorithm works, and it has a nice tail recursion form, until it hit a big input with stackoverflow error.

Usually when this happens, we could think about converting the recursion to iterative form, especially if we have tail recursions:

• If our recursion is not tail recursion, try making it tail recursion. One tip I find useful is to look at similar problem with smaller size in the opposite direction, like the example above. And the recursion function should take the returning value as an argument along with whatever we are keeping track of. Then return the result in the base case. It’s a bit vague here so see the code for clarification.  I got this though from the Scala course on Coursera. Maybe it helped. Well correlation doesn’t mean causation.
• Once we have the tail recursion, we change it to iterative form by using our own Stack. We may need more than one stack, depending on how many variables we are keeping track of, in our case, two–one for max profit and the other for the low price to buy in. Put the body of the recursion in a while loop. At the beginning of the loop, pop out values from the Stack. For those tail recursion calls, we can just push the values of the arguments we are passing back to the stack. Again, check the code.

This actually ends up with the same iterative algorithm in the first approach. It has been a very interesting experience. I learned a lot in the second approach but it took longer. However, if I started with the first approach in the first place, would I be able to figure out the solution?

Summary:

• Always keep recursion in your toolkit and think about smaller problems in both directions.
• You can convert tail recursion into iterative algorithm.
• Start with brutal-force and think about where and how we can improve (the running time of each procedure and which one can be faster?). By think, I mean really put ourselves in the situation and walk through (like “if we can solve it in one pass, what would it be like? To realize it, what do we need? Can we get it somehow?”).

Code on github:

# Search in 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

```[
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]```

Given target = `3`, return `true`.

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

My thoughts and solutions:

Well I guess anyone knows binary search can think of a straightforward solution: just think of this matrix as a long array with m*n elements and apply binary search on it. So it takes O(logmn) = O(logm) + O(logn) But we should probably ask: is m*n still in the range of Integer in Java? If true, good. Go ahead.

If not, and if m and n are in the range of Integer in Java, we could do it in another way: use two passes of binary search, one to locate the possible row that the target could reside in, and the other to search the target on that row. But this one is a bit tricky and be sure to check boundary cases.

Code on github: