Tag Archives: Data structure

Reverse Linked List II

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->NULLm = 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:

Enhanced by Zemanta

Detect the first node of the cycle in a singly-linked list

If a singly-linked data structure contains a cycle, determine the first node that participates in the cycle. you may use only a constant number of pointers into the list (and no other variables). The running time of your algorithm should be linear in the number of nodes in the data structure. You are given the pointer to the first node of the list.

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

My thoughts and solutions:

This is the third time I encountered this question and once again, failed. Well I remembered how to write the code, but I couldn’t figure out the complete reasoning, which made the code kind of useless. Memorizing the code is never my intention but it seems that my brain disagrees…The following is a conversation:

Q: What is the unknown? What are the data? Any conditions or constraints?

A: The unknown is the where the cycle begins. The data is a pointer to the first node of the list. The constraints are that we can only use constant numbers of pointers and the running time should be linear.

Q: Have you seen a similar question before? If yes, can we use its result or method here?

A: Yes, a similar question is to detect if a cycle exists. Hmm, we used a fast runner and slow runner approach. I guess it’s a common strategy to use when dealing with cycles. So we can still consider using it here.

Q: Describe the approach above.

A: We have two pointers F and S, with S moving at rate 1 and F moving at rate 2.

Q: OK, can we introduce a symbol for our unknown? Quantify it?

A: Sure, suppose that node is k steps away from the first node of the list.

Q: Now suppose S moved k steps, where are F?

A: In that case, S is at that starting node of the cycle while F is k steps into the cycle because F moved 2k steps when S moved k steps.

Q: Relatively speaking, what’s the location of F according to S and vice-versa?

A: Then S is k steps behind F and F is CYCLE_SIZE – k steps behind S.

Q: What if k is bigger than CYCLE_SIZE?

A: Hmm, then we can replace k with K = k % CYCLE_SIZE. Whether k or K steps into the cycle points to the same node.

Q: Good, now rephrase the answer to the relative location question.

A: OK, S is K steps behind F and F is CYCLE_SIZE – K steps behind S.

Q: If F and S keep moving, they will meet somewhere in the cycle. When and where will they meet?

A: Aha, suddenly it looks like a junior high physics question…F will catch up S at a rate of 1. So after CYCLE_SIZE – K unit times, they will meet. Since at the beginning S is at entrance of the cycle, after CYCLE_SIZE – K time, S is CYCLE_SIZE – K steps into the cycle. Hmm so when F and S meet, they are simply K steps behind the entrance of the cycle.

Q: Great. Now who else is K steps behind the entrance of the cycle besides F and S?

A: Eh, no one?

Q: OK look at our data. Did we use all the data?

A: Eh the data is the first node of the list. Hmm, but it’s k steps from the cycle…

Q: What’s the relationship between k and K?

A: Oh right, K = k % CYCLE_SIZE. In the cycle, K and k are interchangeable. So F, S and the first node of the list are all k steps behind the cycle! If now we start from the first node of the list with a pointer T and keep move, the place where S and T meet is our answer!

Q: You got it.

Summary: 

  • Locate the unknown. Symbolize and quantify it!
  • When dealing with loops or cycles, think about multiple pointers with different moving rates.
  • In this catch and run problem, ask both when and where.
  • In a cycle, K (= k % CYCLE_SIZE) and k steps into the cycle point to the same node.
  • To find a location, imagine how you get there and when you get there, what are other things like? (when S is at the entrance of the cycle, where is F?)

Code on github:

Enhanced by Zemanta

Algorithm I, Part I — 3 SUM

Q: 3-SUM in quadratic time. Design an algorithm for the 3-SUM problem that takes time proportional to N^2 in the worst case. You may assume that you can sort the N integers in time proportional to N^2 or better.

Quoting from Wikipedia: “In computational complexity theory, the 3SUM problem asks if a given set of n integers, each with absolute value bounded by some polynomial in n, contains three elements that sum to zero.” Suppose we have the following array [1, -9, 21, 2, 4, -5, -7, 10, 6, -8, -2, 0], we need to find all sets of integers (a, b, c) from the array such that a+b+c = 0

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

My thoughts and solutions:

For each pair of a and b, we are trying to find if c = -(a+b) exists in the array. So to pair a and b, that is O(N^2). And to find c in the array, with linear search is O(N). In total it is O(N^3). This is the brutal force algorithm.

How can we improve? Or we should ask where we can improve: Either the pairing of a and b or the search for c.

For the search for c, it costs O(N) time. We can only improve it to O(logN) or O(1) time.

  • What search algorithm takes O(logN)? Well binary search does but it works on a sorted array.  So we sort the array first with MergeSort, which takes O(NlogN) time. Then in total we get O(N^2) * O(logN) + O(NlogN) = O(N^2logN), pairing of a and b times binary-search for c plus the sorting. So it is better, but not enough.
  • What search algorithm takes O(1)? Eh, none? Maybe we are constraining ourselves too much. It does not have to be a “famous algorithm” out there. Consider the following question: can we use some help, like additional data structure? If we can, what data structure helps you find something in O(1) time? Hashtable. So we need a hashtable to save all the integers and problem solved.
  • What if we cannot use additional data structure? Well for this one I didn’t figure it out so I peek at Wiki…They got a clever algorithm. I guess that part of my brain is just not wired to come up with the following idea. There are 3 cases: a + b + c = 0, > 0, and < 0.

Code on github:

 

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

Does a string consist of unique characters —- 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.

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

Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
Q: Let’s look at the first part of the question. What is the unknown? What is our goal?
A: To find a way to determine if a string has all unique characters.
Q: What are the data?
A: Just a string that may or may not have unique characters. Can we assume that all these characters are ASCII characters? (Note that this is a question you have to ask…)
Q: Sure, let’s do that. Now, could you restate the problem since you know they are ASCII characters?
A: OK. to design an algorithm to determine if a string consists of unique ASCII characters.
Q: Have you seen a similar problem before?
A: Not really…But I can imagine the case: for example a string “abc” is unique while “sdsty” is not.
Q: What does it mean by unique character?
A: It means a character only appear once in the string.
Q: How do you know if a character appears only once or more?
A: Eh I guess I just need to keep track one the number of occurrence of different characters.
Q: Good call. To do that, what do you need?
A: Eh I guess I could use a hashtable to keep track of the frequency.
Q: OK, can you think of another way to do it?
A: ….
Q: Look at the unknown. Have you used all the conditions?
A: …
Q: What kind of characters are they?
A: ASCII characters.
Q: How many are there…?
A: 256. Ah I see where this is going. The character set is limited so we can also use something with a constant size other than hashtable. Hmm, I would say an array of size 256.
Q: Good call. Remember that this is a very useful trick when dealing with characters and strings. So how do you use this array?
A: Eh array works with index. If you check the ASCII table, you will see that every character corresponds to a decimal number from 0 to 255. In fact, if you assign ‘A’ to an integer variable n, n will get the value 64, which is the index of A in the ASCII table.
Q: Good. Now tell me some details. How would you solve this problem with your hastable or array?
A: Well, since I need to check the occurrence of each character, I guess I should scan the character in the string one by one. At each position, I’ll check if this character shows up in my record (the hashtable or array). If it’s the second time one shows up, then we find a duplicate.
Q: Nice, now you have a plan. Be sure to test your code thoroughly after implementing the algorithm.
=============================================================================
Q: Now what if you cannot use additional data structures like hashtable or array?
A: Say what…? Then how am I be able to keep track of the occurrence of characters?
Q: Sorry, that’s rule. So you can try think about how to do it without keeping a record.
A: Hmm if I don’t have anything as reference when I’m dealing with the current character, then I guess the program has to check the uniqueness of each character one by one. Otherwise it will have no idea if the current character has shown up or not.
Q: Good. What exactly do you need to do to check the uniqueness of the current character?
A: I’ll have to iterate over the characters after the current one and compare them one by one. If we hit a duplicate, end of story. Otherwise, we will move on to the next character and repeat this process until we hit the end of the string.
Q: OK. This sounds like a plan.
=============================================================================
Q: Now what is the running time of your former algorithm?
A: If I can use additional data structure, it is O(n). If I can’t, then O(n^2).
Q: OK, let’s stick to the last one. It is O(n^2), can you think about a faster one? We also narrow down the characters to only ‘a’ to ‘z’ (OK, this is just the solution on the book. And this condition just comes out from nowhere. Nothing I can do…).
A: Still no additional data structure?
Q: Yep.
A: I don’t know…. (dude why are you doing this?!)
Q: OK previously you used hashtable or array. What did you do with them?
A: I used them to keep track of the occurrence of the characters. But now I cannot use them.
Q: Don’t limit yourself to only two options. Can you think of another way to do the job?
A: Well if I cannot use other data structures, what options do I have? I think only variables are left. I don’t think it is possible. A variable can only represent one value. We will need many variables…
Q: How many do you think we will need?
A: Eh…26? OK this is not feasible. I can’t define that many variables…doing that is the same as defining an array…
Q: You are right. Think about just one variable.
A: Seriously? One? One variable can only represent one value.
Q: Is it? Let me ask this question. How is everything represented so that computer can understand what we mean?
A: binary bits….OK…Now I start to see where this is heading (OK, who really does this in everyday life?). If we represent a variable using bit format, we get more stuff to work with.
Q: That’s right. Let’s think about an integer (in Java) 1. How is it represented in bits?
A: 0000 0000 0000 0000 0000 0000 0000 0001
Q: So is there anyway to use it to distinguish several characters like ‘a’, ‘b’ and ‘d’?
A: ….
Q: OK Suppose ‘a’ is represented as 0000 * 7 0001, can you think another way to represent ‘b’?
A: Eh sure, 0000*7 0010 or 0000*7 0100… Wait I see what is going on. When the bit 1 is on different position, we can use it to represent different characters. And since we have limited the characters from a to z, we have enough space (32 > 26).
Q: Great. Now if you have seen a, b and c 3 characters in the string, how would you represent them all together?
A: Hmm a could be 0001
                 b could be 0010
                  c could be 0100….so if I have seen all 3, then probably 0111?
Q: Good call.  Now what kind of operation do you think we should use to get 0111 from 0001, 0010 and 0100?
A: Eh… add them up?
Q: That’s one way. Think about the bit operations we usually use. What do you have in mind?
A: Probably &, | and <<(>>). Hmm I would say bit-wise or.
Q: Good. Now suppose you have seen abc (0111). What happens if you see a ‘d’ next?
A: Eh d is new so I’ll probably change the record to 1111 since d is 1000.
Q: Well, you know ‘d’ is new. But the computer is not that smart, You have to program the computer to make the decision.
A: I’m not quite sure.
Q: OK, let’s say the next character is ‘a’ again. Write down the current record, d and a in bit format.
A: record is 0111
     char a  is 0001
     char d is 1000
Q: A decision should be made based on the interaction between the record and the character in consideration. What kind of interaction do you think is the right choice?
A: Hmm, like you said, in bit format we can try &, | and << (>>). We’ve tried |. Let’s try & this time…a & 0111 is 0001 while d $ 0111 is 0000. Hmm I guess if the character is new, the result from & operation is always 0000. But if it is not, the result must be greater than 0000.
Q: Here you go. One more thing, how do you convert the characters to the bit format we are using here? ‘a’ to 0001. ‘b’ to 0010 and so on.
A: ‘a’ 0001
     ‘b’ 0010
     ‘c’ 0100
     ‘d’ 1000
Hmm so the difference is the position of the bit 1. in ‘b’, the bit 1 moves 1 position to the left, in ‘c’ it is 2, and in ‘d’ it is 3.
Hmm b-1, c-2, d-3…Ah so b-a = 1, c-a=2 and d-a=3. And a-a=0 (In ASCII). So if a character x is represented by 1 << (x-‘a’)
Q: You got it! Now you have the plan. Carry it out carefully.
Link to the Java Code on GitHub:
===============================================================
A few more things to keep in mind:
  • It’s always about asking yourself the right questions. Ask questions to clarify ambiguity in the problem statement. Make sure you know the definition of each word. Sometimes the definition provides more information or leads for you (Like ASCII table has 256 characters). Never assume anything. Ask!
  • Bit format provides more stuff for us to work with. Well one variable => multiple bits. If you cannot use other data structures, take a look at this option.
Enhanced by Zemanta