AlgoPadawan
Consolidating random fun coding problems from novice level to the more advanced with links to the tutorials for the same.
Sunday, August 26, 2012
Friday, July 20, 2012
Installing OpenGrok on Windows
Installing OpenGrok on Windows
Steps for installing OpenGrok.
- Download the OpenGrok binary from OpenGrok Binary.
- Unzip the tar to a location say "G:\OpenGrok"
- Download Ctags from Ctags Windows Binary.
- Extract Ctags to a location say "G:\Ctags"
- Download and install Tomcat.
- OpenGrok needs the following to run
- A configuration.xml that is generated using the command in step 8.
- Location to the source being indexed. (SRC_ROOT)
- Location to the "Ctag" generated grokData, again refer to step 8. (DATA_ROOT)
- Extract the "war" file in the "lib" folder in the extracted OpenGrok location. In this case G:\opengrok-0.11.1\lib.
- Edit the WEB-INF\web.xml file to include the information discussed above (step 6)
- Copy the the extracted source.war with the modified web.xml to the tomcat webapps folder.
- Index the source and generate the configuration.xml file using the below command (G:\opengrok-0.11.1\lib has the jar file)
- Launch Tomcat after the indexing in done. Open http://localhost:8080/source and wola you have a wicked fast source browser.
- Reindex if you need to add new projects/pick new source etc.
<context-param>
<param-name>CONFIGURATION</param-name>
<param-value>G:\opengrok-0.11.1\configuration.xml</param-value>
<description>Full path to the configuration file where OpenGrok can read it's configuration</description>
</context-param>
-------Added the below------
<context-param>
<param-name>SRC_ROOT</param-name>
<param-value>G:\CodeSource</param-value>
</context-param>
<context-param>
<param-name>DATA_ROOT</param-name>
<param-value>G:\opengrok-0.11.1\grokdata</param-value>
</context-param>
java -jar opengrok.jar -W G:\opengrok-0.11.1\configuration.xml -c G:\ctags58\ctags.exe -P -S -v -s G:\CodeSource -d G:\opengrok-0.11.1\grokdata
Tuesday, May 8, 2012
K Reverse a linked list
Q. K-Reverse a linked list.
- Examples.
- Input. (K = 2) A-->B-->C-->D-->E-->NULL
- Output (K = 2) B-->A-->D-->C-->E-->NULL
- Input. (K = 3) A-->B-->C-->D-->E-->NULL
- Output (K = 3) C-->B-->A-->E-->D-->NULL
This problem is discussed in here
Reverse Alternate Nodes in a Linked List
Q. Reverse Alternate Nodes in a Linked List.
Good Resource for the basics on linked lists (Linked List 101).
Input.
A-->B-->C-->D-->NULL
Output
B-->A-->D-->C-->NULL
Possible Solutions:
- Alternate Node Data Swap.
- With two pointers(C1 and C2) we can point to the first node and second node and swap the Data in the two node and move the C1 to point to the third node and C2 to the fourth node and so on.
- Alternate Node Swap.
- With three pointers C1, C2 and C3 pointed to A, B, C we can swap the first two nodes and then move the pointers to repeat the same.
- Generic solution
- Both are linear solutions but there is a fundamental flaw that we cannot expand this to swap three node or four nodes.
- A little more thought and it is the same as reversing 'N' lists of length 'K' were
- E.g for a 3 way swap for input A-->B-->C-->D-->E-->NULL we reverse list 1 C-->B-->A and then E-->D-->NULL and join them to be C-->B-->A-->E-->D-->NULL.
- We already have the solution for reversing the linked list
- We can extend the same for K-Reverse as following
// Look at the Reversing linked list blog for class definitions, we are extending the same class here #include "linkedList.h" void LinkedList::kReverseList(unsigned int k) { Node* current = head; Node* tempHead = head; unsigned int counter = 1; while(NULL != current) { while(NULL != current && counter >= k) { current = current->next; counter++; } Node* tempNext = current->Next; Node* tail = head; // Current Head will be tail node current->next = NULL; // Break the linked list so that we can reverse it. nonRecursiveReverse(tempHead); tail->Next = tempNext; // Fix the list again. tempHead = tempNext; // New Head node for the next list current = tempNext; counter = 1; //Reset Counter } }
Monday, May 7, 2012
Linked List Reverse
Q. How to reverse a linked list.
Good Resource for the basics on linked lists (Linked List 101).
Possible Solutions:
- Linear Solution
-
- With one pointer to the Node 'A' say current we can access the node 'A' and node 'B'. (current-->next). If we point the next node for B to A we get the following (A-->B-->A) however we lose the next node 'C' and also have a loop A-->B-->A information.
- We can fix this by trying with 2 extra nodes. Node 'prev' points to A and node current points to B. So we can break the node link A-->B and point B-->A ( current points to prev) however we still lose the node C information.
- Lets us try this approach now with 3 nodes. prev = NULL , current = A, next = B. We continue traversing to the end of the list while updating the 'current' node to point to 'prev' and moving the (prev, current and next nodes by one)
- Recursive Solution
- This solution is more intutive. We are essentially trying to traverse till the end of the list and point each node next to its previous node i.e. traverse the list from the TAIL node (D here) D to C to B to A.
- We use the same logic as above however we now recurseively traverse the linked list till the end of loop and point the current node to the prev node.
- In the above example we recurse till current = 'D' and prev is 'C' then point the current D next to C i.e. D-->C.
- When we come of out the recursive call end noe current is C and prev is B so C-->B, so on till the head node
- Analysis of Solutions
No. | Solution | Space Complexity | Time Complexity |
1. | Linear | O(1) | O(N) |
2. | Recursive | O(N) to allocate stack space | O(N) |
/* * LinkedList.h * * Created on: Jul 6, 2011 * Author: vivekrajumuppalla */ #pragma once #define NULL 0 class Node{ private : int m_data; Node* m_next; public: Node(int data); ~Node(); int getNodeData(); Node* getNodeNext(); void setNextNode(Node* nextNode); }; Node::Node(int data) { m_data = data; m_next = NULL; } Node::~Node() { if(NULL != m_next) { delete m_next; } } int Node::getNodeData() { return m_data; } Node* Node::getNodeNext() { return m_next; } void setNextNode(Node* nextNode) { m_next = nextNode; }
include "listNode.h" #pragma once class LinkedList { public: LinkedList(); ~LinkedList(); void recursiveReverse(Node*& headNode); void nonRecursiveReverse(); private: Node* head; }
#include "linkedList.h" void LinkedList::nonRecursiveReverse() { Node* prev = NULL; Node* current = head; Node* next = NULL; while(NULL != current) { next = current->getNodeNext(); current->setNextNode(prev); prev = current; current = next; } head = prev; } // reference needed since we have to update the node not just its pointer void LinkedList::recursiveReverse(Node*& headNode) { if(NULL == headNode || NULL == headNode->getNodeNext()) { tail = headNode; return; } Node* nextNode = headNode->getNodeNext(); recursiveReverse(nextNode); nextNode->setNextNode(headNode); headNode->setNextNode(NULL); // This will cause last node to point to NULL }
Subscribe to:
Posts (Atom)