algorithm to reverse words of a string

This is a bit tricky algorithm and most frequently asked question in interviews. I will now show how to do it in the best time complexity of [O(2n)]. Complete source code can be downloaded from here.

Here we will make use of algorithm to reverse the string which is explained in our previous posts at O(n/2) complexity.

Steps to solve this algorithm

  • take two pointers, one pointing to the start of the array and another to the end of the array and swap the values at respective pointers.
  • While traversing the array increment starting pointer and decrement ending pointer and continue swap the values at respective pointers
  • continue this till we reach the middle of the array which will result in reversed string
  • from above generated reversed string take a pointer which runs through this string and stops at spaces which indicates the occurance of a word
  • go back to first three steps to reverse a word within this reversed string and go back to fourth step till the sentence is completed
  • by end of this algorithm, last word will not be reversed because there is no space after it and hence reverse the last word at the end

Source Code

	/**
	 * Algorithm to reverse word of a string
	 * @return reversed words array
	 */
	public char[] reverseWords(char[] arr) {
	    // reverse the string
	    reverse(arr, 0, arr.length / 2, arr.length);
	     
	    // reverse words of a string
	    int wordIdx = 0;
	    int wordMidIdx = 0;
	    int prevWordLastIdx = 0;
	 
	    // outer loop to track spaces
	    for (int sentenceIdx = 0; sentenceIdx < arr.length; sentenceIdx++) {
	        if (arr[sentenceIdx] != ' ')
	            continue;
	 
	        wordIdx = prevWordLastIdx;
	        int wordLastIdx = sentenceIdx;
	        wordMidIdx = (sentenceIdx + wordIdx) / 2;
	        // reverse each word in a string
	        reverse(arr, wordIdx, wordMidIdx, wordLastIdx);
	        prevWordLastIdx = sentenceIdx + 1;
	    }
	 
	    // reverse last word
	    wordIdx = prevWordLastIdx;
	    wordMidIdx = (arr.length + wordIdx) / 2;
	    reverse(arr, wordIdx, wordMidIdx, arr.length);
	     
	    return arr;
	}

How to arrive at the time complexity?

Step #1: reverse the complete string which is explained in our previous algorithm at O(n/2) complexity. https://tekmarathon.wordpress.com/2012/10/05/algorithm-to-reverse-a-string/

Step #2: keep a pointer which traverses through the string looking for spaces which takes O(n)

Step #3: using the above spaces reverse words within the string at O(n/2). Let us see why this is O(n/2)

'welcome to coding algorithms' would become 'smhtirogla gnidoc ot emoclew'

Now take the string 'smhtirogla gnidoc ot emoclew' and reverse each word within
 it with same logic explained in reversing the string. This will take O(n) 
 iterations, let us see how is it O(n)

At first iteration  
 'smhtirogla gnidoc ot emoclew' would become 'algorithms gnidoc ot emoclew' 
 at 5 iterations i.e (length of 'smhtirogla')/2)

At second iteration 
 'algorithms gnidoc ot emoclew' would become 'algorithms coding ot emoclew'
 at 3 iterations i.e (length of 'gnidoc')/2)

At third iteration  
 'algorithms coding ot emoclew' would become 'algorithms coding to emoclew'
 at 1 iterations i.e (length of 'ot')/2)

At fourth iteration 
 'algorithms coding to emoclew' would become 'algorithms coding to welcome'
 at 3 iterations i.e (length of 'emoclew')/2)

total length of the string = 29

total iterations = 12 + spaces = 15 (approximately half the length of the 
total string)

Total complexity from Step #1, Step #2 and Step #3 = O(n/2) + O(n) + O(n/2) = O(2n)

Complete source code can be downloaded from here.

algorithm to find if a linked list is cyclic

The best way of doing it is to take two pointers. For every step taken by one pointer, move another pointer two steps. In this manner if there is no cycle in the linked list(i.e, if the list is linear), then by the time first pointer reaches mid if the list, second pointer reaches end of the list.

The following figure depicts the cycle in Single Linked List.
CycleInSLL

Linear Linked List Analysis

              ---------------------------------------------------------------
Node        : 1->200 | 2->300 | 3->400 | 4->500 | 5->600 | 6->700 | 7->NULL |
              -------------------------------------------------------------
Node Address: 100    | 200    | 300    | 400    | 500    | 600    | 700     |
              ---------------------------------------------------------------
Iteration-1 : p1     |        | p2     |        |        |        |         |
              ---------------------------------------------------------------
Iteration-2 :        | p1     |        |        | p2     |        |         |
              ---------------------------------------------------------------
Iteration-3 :        |        | p1     |        |        |        | p2      |
              ---------------------------------------------------------------

If you notice by the time the first pointer reaches mid of the list, second pointer has reached end of the list.

Cyclic Linked List Analysis

              ---------------------------------------------------------------
Node        : 1->200 | 2->300 | 3->400 | 4->500 | 5->600 | 6->700 | 7->300  |
              -------------------------------------------------------------
Node Address: 100    | 200    | 300    | 400    | 500    | 600    | 700     |
              ---------------------------------------------------------------
Iteration-1 : p1     |        | p2     |        |        |        |         |
              ---------------------------------------------------------------
Iteration-2 :        | p1     |        |        | p2     |        |         |
              ---------------------------------------------------------------
Iteration-3 :        |        | p1     |        |        |        | p2      |
              ---------------------------------------------------------------
Iteration-3 :        |        |        | p2  p1 |        |        |         |
              ---------------------------------------------------------------

If you notice both the pointers are referring to the same node.

Steps to solve this Algorithm:
– For every step taken by one pointer, move another pointer two steps.
– Continue this till either second_pointer/second_pointer’s next pointer is same as that of the first pointer which means second pointer has come behind the first pointer resulting in a cycle.

Source Code

	public static boolean findCylicSLL(Node root) {
		if(root == null) {
			return false;
		}
		Node ptr1 = root;
		
		Node ptr2 = root.next.next;
		while(ptr1 != null && ptr2 != null) {
			 if(ptr2 == ptr1 || ptr2.next == ptr1) {
				 return true;
			 }
			 ptr1 = ptr1.next;
			 ptr2 = ptr2.next.next;
		}
		
		return false;
	}

A small change in this same logic will lead us to another important trick:
How do you find exact middle element of the list in O(n/2) complexity?

Steps to solve this Algorithm:
– For every step taken by one pointer, move another pointer two steps.
– Continue this till either second_pointer is null which means it reached end of the list and therefore first_pointer will be exactly in the middle of the list

	public static boolean findMiddleElementOfList(Node root) {
		if(root == null) {
			return false;
		}
		Node ptr1 = root;
		Node ptr2 = root.next.next;
		
                while(ptr2 != null) {
	            ptr1 = ptr1.next;
		    ptr2 = ptr2.next.next;
		}
		
                // When ptr2 is null, it means ptr1 reached mid of the list
                System.out.println("ptr1: "+ptr1);
	}

spiral traversal of binary tree

This can be done using two stacks in iterative manner.

The below diagram depicts the spiral traversal of BST
SpriralBST

Steps to solve
push level_1 nodes (i.e, only root node) into stack_1;
next by popping elements of level_1, push children of level_l in to stack_2 (i.e, level_2);
next by popping elements of level_2, push children of level_2 in to stack_2 (i.e, level_3);
… so on

Code:

	/**
	 * Algorithm to print binary tree in spiral manner
	 * 
	 * @param node root node of the binary tree
	 */
	public void printTreeInSpiralForm(BinaryNode node) {
		Stack<BinaryNode> stack1 = new Stack<BinaryNode>();
		Stack<BinaryNode> stack2 = new Stack<BinaryNode>();
		stack1.push(node);

		while (!stack1.empty() || !stack2.empty()) {
			//
			while (!stack1.empty()) {
				node = stack1.pop();
				if(node != null) {
					System.out.print(node.element+", ");
					if(node.left != null)
						stack2.push(node.left);
					if(node.right != null)
						stack2.push(node.right);
				}
			}

			while (!stack2.empty() && node != null) {
				node = stack2.pop();
				if(node != null) {
					System.out.print(node.element+", ");
					if(node.left != null)
						stack1.push(node.right);
					if(node.right != null)
						stack1.push(node.left);
				}
			}
		}
	}

Output:
20, 25, 15, 12, 18, 22, 28, 32, 26, 24, 21, 19, 17, 14, 6

algorithm to find if two linked lists are intersected

Two different lists will be intersected when one node of a list points to the other list’s node.

The below diagram depicts the intersection of lists
IntersectedSLL
How do you solve it:

  • Get the difference of the two lists (In above diagram it is 5-4=1)
  • Take a pointer to the bigger list and move it as many number of times as difference between the lists calculated above (bigger list with 5 nodes is moved 1 position forward with pointer1 pointing to 2)
  • Take another pointer to the second list and start comparing node of first list with the node of the second list. (Take pointer2 pointing to 18)
  • Whenever nodes are same we can say lists are intersected. (they get intersected at node 4)

Code:

/**
	 * Algorithm to detect the intersecting point of two lists
	 *
	 * @param s1 first list which is larger in size
	 * @param s2 second list
	 */
	public static void getIntersectPoint(SLLIntersection s1,SLLIntersection s2){
		int s1Len = s1.getLength(s1.root);
		int s2Len = s2.getLength(s2.root);

		int diff = s1Len-s2Len;
		System.out.println("Difference between two lists is "+diff);

		// Move the pointer in the larger list to diff places
		SLLNode s1List = s1.root;
		if((s1Len-s2Len)>0) {
			while((s1List != null) && diff>0){
				s1List = s1List.next;
				diff--;
			}
		}

		// Now check the point where the lists are intersecting
		// by checking each node in two lists simultaneously
		SLLNode s2List = s2.root;
		while(s1List != null && s1List.next != null) {
			if(s1List == s2List) {
				System.out.println("Intersection point is at "+s1List.value);
			}
			// increment the pointers
			s1List = s1List.next;
			s2List = s2List.next;
		}
	}

Output:

List1: 1 2 3 4 5
List2: 18 19 4 5
Difference between two lists is 1
Intersection point is at 4

subsequence of array with maximum sum (Kadane’s Algorithm)

This is given by Jay Kadane.

Problem Statement: In a given array, find out subarray such that the sum of its elements is maximum.

Lets take an array:
a[] = {-1,1,2,-3,3,-1,2,-2}
subarray with maximum sum is 4 i.e, {3,-1,2}

Note: If the array with all its elements are positives, then the result is the sum of all the elements. Say if a[]={1,2,3,4}, then result=10
Note: If the array with all its elements are negative, then the result is the minimum element of all the elements. Say if a[]={-1,-2,-3,-4}, then result=-1

The base rule here is that: include negative numbers if the Sum is greater than zero, if not then exclude negative numbers.

This algorithm uses dynamic programming concept to find the sum. what is dynamic programming? evaluate smaller problems first and use that smaller problems result to solve bigger problem.

/**
 * @author ntallapa
 *
 */
public class KadaneAlgorithm {

	/**
	 * Algorithm to find max subarray sum
	 * @param a array for which max subarray sum needs to be found
	 * @return max subarray sum
	 */
	public int maxSubArraySum(int a[]) {
		int totMaxSum = a[0];
		int currMaxSum = a[0];

		for (int i = 1; i < a.length; i++) {
			currMaxSum = a[i]>(currMaxSum+a[i])?a[i]:(currMaxSum + a[i]);
			totMaxSum = totMaxSum>currMaxSum?totMaxSum:currMaxSum;
		}
		return totMaxSum;
	}

	/**
	 * Test
	 * @param args
	 */
	public static void main(String[] args) {
		KadaneAlgorithm la = new KadaneAlgorithm();
		int a[] = {-1,1,2,-3,3,-1,2,-2};
		int max_sum = la.maxSubArraySum(a);
		System.out.println("Maximum contiguous sum is \n" + max_sum);
	}
}
Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey