Yesterday morning I attended a one hour webinar sponsored by the Association for Computing Machinery titled ACM Queue Case Study Q&A: Always-On Time-Series Database. It was very interesting. There was no presentation segment. There were only questions. The presenter, Theo Schlossnagle which is the founder of Circonus was very eloquent and seems very versed in the technology and their products.
During the conference I made several notes and searched for several topics that I found of interest. I will be reading the associated pages later this week.
Early today I visited a link from Facebook in which you can find multiple coding interview problems. I selected one called Reverse Operations and started to think about it. It felt like I had seen this problem before. Checked on my blog and found the post Reverse Operations. Since there are many ways to skin a cat, I decided to give it a fresh try.
You are given a singly-linked list that contains N integers. A subpart of the list is a contiguous set of even elements, bordered either by either end of the list or an odd element. For example, if the list is [1, 2, 8, 9, 12, 16], the subparts of the list are [2, 8] and [12, 16]. Then, for each subpart, the order of the elements is reversed. In the example, this would result in the new list, [1, 8, 2, 9, 16, 12]. The goal of this question is: given a resulting list, determine the original order of the elements. Constraints: 1 <= N <= 1000, where N is the size of the list 1 <= Li <= 10^9, where Li is the ith element of the list
The requirements are well presented. We are given a singly linked list with integer values. The idea is to reverse the sets of contiguous even numbers. The numbers can be in any order.
class Node {
int data;
Node next;
}
Node reverse(Node head) {
}
The Node class is used to define the nodes in the linked list. We have a value and a reference to the next node in the list. The signature for the function we need to develop is provided. We receive a linked list, process it by reversing the sets of even numbers, and return the new linked list.
I will be solving the problem on my own computer. I will be using the Java programming language, a Windows 10 computer and the VSCode IDE. When completed I will copy and paste the code into the IDE provided by Facebook. There are only two JUnit test cases we need to pass to clear the solution. Please note that if you are interested in applying you should use the IDE provided by Facebook.
1, 2, 3, 4, 5, 6 main <<< strArr: [1, 2, 3, 4, 5, 6] main <<< head: 1, 2, 3, 4, 5, 6 main <<< revHead: 6, 5, 4, 3, 2, 1 main <<< head: 1, 2, 3, 4, 5, 6 main <<< revHead: 6, 5, 4, 3, 2, 1 main <<< head: 1, 2, 3, 4, 5, 6 main <<< revHead: 1, 2, 3, 4, 5, 6 1, 2, 8, 9, 12, 16 main <<< strArr: [1, 2, 8, 9, 12, 16] main <<< head: 1, 2, 8, 9, 12, 16 main <<< revHead: 16, 12, 9, 8, 2, 1 main <<< head: 1, 2, 8, 9, 12, 16 main <<< revHead: 16, 12, 9, 8, 2, 1 main <<< head: 1, 2, 8, 9, 12, 16 main <<< revHead: 1, 8, 2, 9, 16, 12 2, 4, 6, 9, 11, 12, 14, 16 main <<< strArr: [2, 4, 6, 9, 11, 12, 14, 16] main <<< head: 2, 4, 6, 9, 11, 12, 14, 16 main <<< revHead: 16, 14, 12, 11, 9, 6, 4, 2 main <<< head: 2, 4, 6, 9, 11, 12, 14, 16 main <<< revHead: 16, 14, 12, 11, 9, 6, 4, 2 main <<< head: 2, 4, 6, 9, 11, 12, 14, 16 main <<< revHead: 6, 4, 2, 9, 11, 16, 14, 12 2, 4, 6, 9, 11, 12, 14, 16, 17 main <<< strArr: [2, 4, 6, 9, 11, 12, 14, 16, 17] main <<< head: 2, 4, 6, 9, 11, 12, 14, 16, 17 main <<< revHead: 17, 16, 14, 12, 11, 9, 6, 4, 2 main <<< head: 2, 4, 6, 9, 11, 12, 14, 16, 17 main <<< revHead: 17, 16, 14, 12, 11, 9, 6, 4, 2 main <<< head: 2, 4, 6, 9, 11, 12, 14, 16, 17 main <<< revHead: 6, 4, 2, 9, 11, 16, 14, 12, 17
Since we will be developing the code on my machine, we will need to develop a simple piece of code to collect the input data, generate the linked list, call the function / method in question and display the results.
The input line contains the integer values for our linked list. The test scaffolding seems to read in the values and display them in string array. The data is probably used to generate the linked list and is displayed. So far all seems to be good.
The test code tries a couple experiments that appear to read the linked list and return the linked list in reversed order. The idea was to experiment with a couple ways in which we can reverse all the elements in a linked list.
With the information on hand, we then try reversing only the consecutive even numbers. If you look at the last two lines of each test set it appears that only the even numbers are placed in reverse order.
One of the tests is provided by Facebook. The others were generated by me to further test the code.
/**
* Node class to implement linked list.
*/
class Node {
int data;
Node next;
// **** ****
@Override
public String toString() {
return this.data + " ";
}
}
This is the class provided by Facebook. Note that I have added for my testing the toString() method. This is used to display the linked lists. This method should not affect the logic of the code we need to develop.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read String[] with values for the nodes in the linked list ****
String[] strArr = br.readLine().trim().split(", ");
// **** closed buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** initialize linked list ****
Node head = null;
Node tail = head;
// **** populate linked list (FILO) ****
for (String s : strArr) {
Node node = new Node();
node.data = Integer.parseInt(s);
if (head == null) {
head = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
}
// ???? ????
System.out.print("main <<< head: ");
for (Node p = head; p != null; p = p.next) {
System.out.print(p.data);
if (p.next != null)
System.out.print(", ");
}
System.out.println();
// **** reverse the entire linked list ****
Node revHead = reverse1(head);
// **** display output list ****
System.out.print("main <<< revHead: ");
for (Node p = revHead; p != null; p = p.next) {
System.out.print(p.data);
if (p.next != null)
System.out.print(", ");
}
System.out.println();
// **** restore initial linked list ****
head = reverse1(revHead);
// ???? ????
System.out.print("main <<< head: ");
for (Node p = head; p != null; p = p.next) {
System.out.print(p.data);
if (p.next != null)
System.out.print(", ");
}
System.out.println();
// **** reverse the linked list ****
revHead = reverse2(head);
// **** display output list ****
System.out.print("main <<< revHead: ");
for (Node p = revHead; p != null; p = p.next) {
System.out.print(p.data);
if (p.next != null)
System.out.print(", ");
}
System.out.println();
// **** restore initial linked list ****
head = reverse1(revHead);
// ???? ????
System.out.print("main <<< head: ");
for (Node p = head; p != null; p = p.next) {
System.out.print(p.data);
if (p.next != null)
System.out.print(", ");
}
System.out.println();
// **** reverse the linked list ****
revHead = reverse3(head);
// **** display output list ****
System.out.print("main <<< revHead: ");
for (Node p = revHead; p != null; p = p.next) {
System.out.print(p.data);
if (p.next != null)
System.out.print(", ");
}
System.out.println();
}
The test code is simple and appears to follow the description we read for the test code results.
We start by reading the input line with the integer values into a String[]. We display the String[] to make sure we read the values properly.
We then initialize and populate the linked list. The linked list is represented by the head variable.
We then enter a loop and traverse the String[] converting the elements into integers which we place in individual nodes. The nodes are the inserted into the linked list which represents a FIFO data structure. We insert at the tail of the linked list and remove from the head of the queue (or linked list). Not too many applications tend to use singly linked lists.
Once we have our linked list we display it. The values should be in the same order as the String[].
We then make a call to the traverse1() function / method. Note that the method should reverse the entire linked list. This is doe as an exercise so we can decide on an approach we can use to solve the actual problem.
We display the reversed list. It seems to have worked fine.
We then reverse the reversed list to get back to our initial linked list.
We the try a second approach to reverse the entire linked list. It also seems to work as expected. Once again we reverse the linked list in preparation for the actual solution.
The solution is implemented using the traverse3() function / method. After the reverse operation is completed we display the reversed linked list. The results seem to comply with the requirements.
/**
* Given a resulting list (head),
* determine the original order of the elements.
* Will reverse all elements using a recursive approach.
*
* !!! NOT PART OF THE SOLUTION !!!!
*/
static Node reverse1(Node head) {
// **** base case ****
if (head == null || head.next == null)
return head;
// **** recursive case (set head for reversed list) ****
Node revHead = reverse1(head.next);
// ???? ????
// System.out.println("reverse1 <<< newHead: " + revHead.data + " head: " + head.data);
// **** point to the next element in the reversed linked list ****
head.next.next = head;
// **** tail node of reversed linked list ****
head.next = null;
// **** return reversed linked list head ****
return revHead;
}
This is a recursive approach. We start with the base case. We then make a recursive call. This is used to traverse the linked list past the end node. After the recursive call we will be processing the tail of the linked list and moving back to the head.
We then set the revHead variable which is intended to hold the head of the reversed linked list. For each element we reverse the link (reference) and make sure we point to null. If we do not do this we might (will) end up with a circular queue. The head of the reversed linked list is returned.
/**
* Given a resulting list (head),
* determine the original order of the elements.
* Will reverse all elements using a stack.
*
* !!! NOT PART OF THE SOLUTION !!!!
*/
static Node reverse2(Node head) {
// **** sanity check(s) ****
if (head == null || head.next == null)
return head;
// **** initialization ****
Node revHead = null;
Node revTail = null;
Stack<Node> stack = new Stack<>();
// **** push all nodes into the stack ****
for (Node p = head; p != null;p = p.next)
stack.push(p);
// ???? ????
// System.out.println("reverse2 <<< stk: " + stk.toString());
// **** pop the stack building the reversed linked list ****
while (!stack.isEmpty()) {
// **** pop next node ****
Node node = stack.pop();
// **** reset next reference ****
node.next = null;
// **** set new head ****
if (revHead == null)
revHead = node;
else
revTail.next = node;
// **** update the reversed queue tail ****
revTail = node;
}
// **** return the reversed linked list head ****
return revHead;
}
In this approach we will use a stack. The idea is simple. We traverse the linked list pushing into the stack the nodes until we hit the last one.
We then loop popping the elements from the stack. This operation will reverse the values of the elements. We still need to take care of the next reference for each node.
After all is said and done, the reversed linked list is returned.
/**
* Given a resulting list (head),
* determine the original order of the elements.
* Will reverse only even segments.
*/
static Node reverse3(Node head) {
// **** sanity check(s) ****
if (head == null || head.next == null)
return head;
// **** initialization ****
Node revHead = null;
Node revTail = null;
Stack<Node> stack = new Stack<>();
// **** traverse the linked list - O(n) ****
for (Node p = head; p != null; p = p.next) {
// ???? ????
// System.out.println("<<< p: " + p.data);
// **** even node ****
if (p.data % 2 == 0) {
stack.push(p);
}
// **** odd node ****
else {
// **** pop all nodes from the stack ****
while (!stack.isEmpty()) {
// **** pop next node ****
Node node = stack.pop();
// **** reset next reference ****
node.next = null;
// **** set new head ****
if (revHead == null)
revHead = node;
else
revTail.next = node;
// **** update the reversed queue tail ****
revTail = node;
}
// **** set new head ****
if (revHead == null)
revHead = p;
else
revTail.next = p;
// **** update the reversed queue tail ****
revTail = p;
}
}
// **** pop all nodes from the stack ****
while (!stack.isEmpty()) {
// **** pop next node ****
Node node = stack.pop();
// **** reset next reference ****
node.next = null;
// **** set new head ****
if (revHead == null)
revHead = node;
else
revTail.next = node;
// **** update the reversed queue tail ****
revTail = node;
}
// **** return head of reversed linked list ****
return revHead;
}
This function / method implements the solution for the problem at hand.
We start by performing some sanity checks and initialization. Note that we will be using a stack to reverse the order of the even integers.
We then enter a look in which we traverse the linked list. For each node we check if it is even or odd. If the value is even we just push the node into the stack.
If a node is odd, we need to restore any positive nodes we might have in reverse order. We enter the values into the revTail queue. Note that we are keeping a tail pointer to speed up operations eliminating the need to get to the tail each time we need to insert a node.
Once we are done with the loop, we need to make sure that there are no even numbers in the stack. If they are we repeat the process we used in the main loop. We could have written an auxiliary function but we did not. In production code it would be a good idea to do so.
The reversed head is returned. Our test scaffolding displays the results. All seems to be fine.
I checked the code from the Reverse Operations post. It seems we now have two different approaches to solve the problem.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,796 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com