AlgoPadawan

Gen Y work place infographic

2012-08-26T10:06:00.001-07:00

from(http://www.payscale.com/gen-y-at-work)

Installing OpenGrok on Windows

2012-07-20T16:15:00.001-07:00

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)

 <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>

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)

 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

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.

K Reverse a linked list

2012-05-08T21:55:00.000-07:00

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

2012-05-08T21:50:00.000-07:00

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

C++ code

// 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
 }
}

Linked List Reverse

2012-05-07T23:18:00.001-07:00

Q. How to reverse a linked list.

Good Resource for the basics on linked lists (Linked List 101).

Possible Solutions:

Linear Solution

Consider the following linked list ( A-->B-->C-->D-->NULL) the expected output is (D-->C-->B-->A-->NULL).

- 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)

C++ code

/*
 * 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
}