Split a Circular Linked List into two halves

 

                         Original Linked List

                         Result Linked List 1

                         Result Linked List 2

Algorithm:
1) Store the mid and last pointers of the circular linked list using tortoise and hare algorithm.
2) Make the second half circular.
3) Make the first half circular.
4) Set head (or start) pointers of the two linked lists.

In the below implementation, if there are odd nodes in the given circular linked list then the first result list has 1 more node than the second result list.

/* Program to split a circular linked list into two halves */
#include<stdio.h>
#include<stdlib.h>
/* structure for a node */
struct Node
{
  int data;
  struct Node *next;
};
/* Function to split a list (starting with head) into two lists.
   head1_ref and head2_ref are references to head nodes of
    the two resultant linked lists */
void splitList(struct Node *head, struct Node **head1_ref,
                                            struct Node **head2_ref)
{
  struct Node *slow_ptr = head;
  struct Node *fast_ptr = head;
  if(head == NULL)
    return;
 
  /* If there are odd nodes in the circular list then
     fast_ptr->next becomes head and for even nodes
     fast_ptr->next->next becomes head */
  while(fast_ptr->next != head &&
         fast_ptr->next->next != head)
  {
     fast_ptr = fast_ptr->next->next;
     slow_ptr = slow_ptr->next;
  
 /* If there are even elements in list then move fast_ptr */
  if(fast_ptr->next->next == head)
    fast_ptr = fast_ptr->next;     
  
  /* Set the head pointer of first half */
  *head1_ref = head;   
     
  /* Set the head pointer of second half */
  if(head->next != head)
    *head2_ref = slow_ptr->next;
  
  /* Make second half circular */
  fast_ptr->next = slow_ptr->next;
  
  /* Make first half circular */
  slow_ptr->next = head;      
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the begining of a Circular
   linked lsit */
void push(struct Node **head_ref, int data)
{
  struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));
  struct Node *temp = *head_ref;
  ptr1->data = data; 
  ptr1->next = *head_ref;
  
  /* If linked list is not NULL then set the next of
    last node */
  if(*head_ref != NULL)
  {
    while(temp->next != *head_ref)
      temp = temp->next;       
    temp->next = ptr1;
  }
  else
     ptr1->next = ptr1; /*For the first node */
  *head_ref = ptr1;    
}
/* Function to print nodes in a given Circular linked list */
void printList(struct Node *head)
{
  struct Node *temp = head;
  if(head != NULL)
  {
    printf("\n");
    do {
      printf("%d ", temp->data);
      temp = temp->next;
    } while(temp != head);
  }
}
/* Driver program to test above functions */
int main()
{
  int list_size, i;
  
  /* Initialize lists as empty */
  struct Node *head = NULL;
  struct Node *head1 = NULL;
  struct Node *head2 = NULL; 
  /* Created linked list will be 12->56->2->11 */
  push(&head, 12);
  push(&head, 56);  
  push(&head, 2);  
  push(&head, 11);  
  printf("Original Circular Linked List");
  printList(head);     
 
  /* Split the list */
  splitList(head, &head1, &head2);
 
  printf("\nFirst Circular Linked List");
  printList(head1); 
  printf("\nSecond Circular Linked List");
  printList(head2); 
  
  getchar();
  return 0;
}

Output:

Original Circular Linked List
11 2 56 12
First Circular Linked List
11 2
Second Circular Linked List
56 12

Time Complexity: O(n)

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Sorted insert for circular linked list

Difficulty Level: Rookie
Write a C function to insert a new value in a sorted Circular Linked List (CLL). For example, if the input CLL is following.

After insertion of 7, the above CLL should be changed to following

 

 

Algorithm:
Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.

1) Linked List is empty:
    a)  since new_node is the only node in CLL, make a self loop.
          new_node->next = new_node;
    b) change the head pointer to point to new node.
          *head_ref = new_node;
2) New node is to be inserted just before the head node:
  (a) Find out the last node using a loop.
         while(current->next != *head_ref)
            current = current->next;
  (b) Change the next of last node.
         current->next = new_node;
  (c) Change next of new node to point to head.
         new_node->next = *head_ref;
  (d) change the head pointer to point to new node.
         *head_ref = new_node;
3) New node is to be  inserted somewhere after the head: 
   (a) Locate the node after which new node is to be inserted.
         while ( current->next!= *head_ref &&
             current->next->data < new_node->data)
         {   current = current->next;   }
   (b) Make next of new_node as next of the located pointer
         new_node->next = current->next;
   (c) Change the next of the located pointer
         current->next = new_node;


/* Program to split a circular linked list into two halves */
#include<stdio.h>
#include<stdlib.h>
/* structure for a node */
struct Node
{
  int data;
  struct Node *next;
};
/* Function to split a list (starting with head) into two lists.
   head1_ref and head2_ref are references to head nodes of
    the two resultant linked lists */
void splitList(struct Node *head, structNode **head1_ref, struct Node **head2_ref)
{
  struct Node *slow_ptr = head;
  struct Node *fast_ptr = head;
  if(head == NULL)
    return;
 
  /* If there are odd nodes in the circular list then
     fast_ptr->next becomes head and for even nodes
     fast_ptr->next->next becomes head */
  while(fast_ptr->next != head &&
         fast_ptr->next->next != head)
  {
     fast_ptr = fast_ptr->next->next;
     slow_ptr = slow_ptr->next;
  
 /* If there are even elements in list then move fast_ptr */
  if(fast_ptr->next->next == head)
    fast_ptr = fast_ptr->next;     
  
  /* Set the head pointer of first half */
  *head1_ref = head;   
     
  /* Set the head pointer of second half */
  if(head->next != head)
    *head2_ref = slow_ptr->next;
  
  /* Make second half circular */
  fast_ptr->next = slow_ptr->next;
  
  /* Make first half circular */
  slow_ptr->next = head;      
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the begining of a Circular
   linked lsit */
void push(struct Node **head_ref, int data)
{
  struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));
  struct Node *temp = *head_ref;
  ptr1->data = data; 
  ptr1->next = *head_ref;
  
  /* If linked list is not NULL then set the next of
    last node */
  if(*head_ref != NULL)
  {
    while(temp->next != *head_ref)
      temp = temp->next;       
    temp->next = ptr1;
  }
  else
     ptr1->next = ptr1; /*For the first node */
  *head_ref = ptr1;    
}
/* Function to print nodes in a given Circular linked list */
void printList(struct Node *head)
{
  struct Node *temp = head;
  if(head != NULL)
  {
    printf("\n");
    do {
      printf("%d ", temp->data);
      temp = temp->next;
    } while(temp != head);
  }
}
/* Driver program to test above functions */
int main()
{
  int list_size, i;
  
  /* Initialize lists as empty */
  struct Node *head = NULL;
  struct Node *head1 = NULL;
  struct Node *head2 = NULL; 
  /* Created linked list will be 12->56->2->11 */
  push(&head, 12);
  push(&head, 56);  
  push(&head, 2);  
  push(&head, 11);  
  printf("Original Circular Linked List");
  printList(head);     
 
  /* Split the list */
  splitList(head, &head1, &head2);
 
  printf("\nFirst Circular Linked List");
  printList(head1); 
  printf("\nSecond Circular Linked List");
  printList(head2); 
  
  getchar();
  return 0;

 

 

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Linked List vs Array

Difficulty Level: Rookie

Both Arrays and Linked List can be used to store linear data of similar types, but they both have some advantages and disadvantages over each other.

Following are the points in favour of Linked Lists.

(1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, upper limit is rarely reached.

(2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.

For example, suppose we maintain a sorted list of IDs in an array id[].

id[] = [1000, 1010, 1050, 2000, 2040, …..].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

So Linked list provides following two advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion

Linked lists have following drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
3) Arrays have better cache locality that can make a pretty big difference in performance.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Linked List | Set 1 (Introduction)

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.

linkedlist

Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.

For example, in a system if we maintain a sorted list of IDs in an array id[].

id[] = [1000, 1010, 1050, 2000, 2040].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).
Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion

Drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.

Representation in C:
A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL.
Each node in a list consists of at least two parts:
1) data
2) pointer to the next node
In C, we can represent a node using structures. Below is an example of a linked list node with an integer data.
In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

// A linked list node
struct Node
{
  int data;
  struct Node *next;
};

First Simple Linked List in C Let us create a simple linked list with 3 nodes.

// A simple C program to introduce
// a linked list
#include<stdio.h>
#include<stdlib.h>

struct Node
{
  int data;
  struct Node *next;
};

// Program to create a simple linked
// list with 3 nodes
int main()
{
  struct Node* head = NULL;
  struct Node* second = NULL;
  struct Node* third = NULL;

  // allocate 3 nodes in the heap
  head = (struct Node*)malloc(sizeof(struct Node));
  second = (struct Node*)malloc(sizeof(struct Node));
  third = (struct Node*)malloc(sizeof(struct Node));

  /* Three blocks have been allocated  dynamically.
     We have pointers to these three blocks as first, second and third
       head           second           third
        |                |               |
        |                |               |
    +---+-----+     +----+----+     +----+----+
    | #  | #  |     | #  | #  |     |  # |  # |
    +---+-----+     +----+----+     +----+----+

   # represents any random value.
   Data is random because we haven’t assigned anything yet  */

  head->data = 1; //assign data in first node
  head->next = second; // Link first node with the second node

  /* data has been assigned to data part of first block (block
    pointed by head).  And next pointer of first block points to
    second.  So they both are linked.

       head          second         third
        |              |              |
        |              |              |
    +---+---+     +----+----+     +-----+----+
    | 1  | o----->| #  | #  |     |  #  | #  |
    +---+---+     +----+----+     +-----+----+
  */

  second->data = 2; //assign data to second node
  second->next = third; // Link second node with the third node

  /* data has been assigned to data part of second block (block pointed by
     second). And next pointer of the second block points to third block.
    So all three blocks are linked.

       head         second         third
        |             |             |
        |             |             |
    +---+---+     +---+---+     +----+----+
    | 1  | o----->| 2 | o-----> |  # |  # |
    +---+---+     +---+---+     +----+----+      */

  third->data = 3; //assign data to third node
  third->next = NULL;

  /* data has been assigned to data part of third block (block pointed
    by third). And next pointer of the third block is made NULL to indicate
    that the linked list is terminated here.

     We have the linked list ready.

           head
             |
             |
        +---+---+     +---+---+       +----+------+
        | 1  | o----->|  2  | o-----> |  3 | NULL |
        +---+---+     +---+---+       +----+------+


    Note that only head is sufficient to represent the whole list.  We can
    traverse the complete list by following next pointers.    */

  return 0;
}

Linked List Traversal
In the previous program, we have created a simple linked list with three nodes. Let us traverse the created list and print the data of each node. For traversal, let us write a general purpose function printList() that prints any given list.

// A simple C program for traversal of a linked list
#include<stdio.h>
#include<stdlib.h>

struct Node
{
  int data;
  struct Node *next;
};

// This function prints contents of linked list starting from
// the given node
void printList(struct Node *n)
{
  while (n != NULL)
  {
     printf(" %d ", n->data);
     n = n->next;
  }
}

int main()
{
  struct Node* head = NULL;
  struct Node* second = NULL;
  struct Node* third = NULL;

  // allocate 3 nodes in the heap
  head  = (struct Node*)malloc(sizeof(struct Node));
  second = (struct Node*)malloc(sizeof(struct Node));
  third  = (struct Node*)malloc(sizeof(struct Node));

  head->data = 1; //assign data in first node
  head->next = second; // Link first node with second

  second->data = 2; //assign data to second node
  second->next = third;

  third->data = 3; //assign data to third node
  third->next = NULL;

  printList(head);

  return 0;
}

Output:

 1  2  3

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Linked List | Set 2 (Inserting a node)

All programs discussed in this post consider following representations of linked list .

// A linked list node
struct Node
{
  int data;
  struct Node *next;
};

In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list.

Add a node at the front: (A 4 steps process)
The new node is always added before the head of the given Linked List. And newly added node becomes the new head of the Linked List. For example if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. Let us call the function that adds at the front of the list is push(). The push() must receive a pointer to the head pointer, because push must change the head pointer to point to the new node .
linkedlist_insert_at_start

Following are the 4 steps to add node at the front.

/* Given a reference (pointer to pointer) to the head of a list
   and an int,  inserts a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
    /* 1. allocate node */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
 
    /* 2. put in the data  */
    new_node->data  = new_data;
 
    /* 3. Make next of new node as head */
    new_node->next = (*head_ref);
 
    /* 4. move the head to point to the new node */
    (*head_ref)    = new_node;
}

Time complexity of push() is O(1) as it does constant amount of work.

Add a node after a given node: (5 steps process)
We are given pointer to a node, and the new node is inserted after the given node.

linkedlist_insert_middle

/* Given a node prev_node, insert a new node after the given
   prev_node */
void insertAfter(struct Node* prev_node, int new_data)
{
    /*1. check if the given prev_node is NULL */
    if (prev_node == NULL)
    {
       printf("the given previous node cannot be NULL");      
       return
    
         
    /* 2. allocate new node */
    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));
 
    /* 3. put in the data  */
    new_node->data  = new_data;
 
    /* 4. Make next of new node as next of prev_node */
    new_node->next = prev_node->next;
 
    /* 5. move the next of prev_node as new_node */
    prev_node->next = new_node;
}

Time complexity of insertAfter() is O(1) as it does constant amount of work.

Add a node at the end: (6 steps process)
The new node is always added after the last node of the given Linked List. For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.
Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node.

linkedlist_insert_last

Following are the 6 steps to add node at the end.

/* Given a reference (pointer to pointer) to the head
   of a list and an int, appends a new node at the end  */
void append(struct Node** head_ref, int new_data)
{
    /* 1. allocate node */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    struct Node *last = *head_ref;  /* used in step 5*/
 
    /* 2. put in the data  */
    new_node->data  = new_data;
    /* 3. This new node is going to be the last node, so make next
          of it as NULL*/
    new_node->next = NULL;
    /* 4. If the Linked List is empty, then make the new node as head */
    if (*head_ref == NULL)
    {
       *head_ref = new_node;
       return;
    
     
    /* 5. Else traverse till the last node */
    while (last->next != NULL)
        last = last->next;
 
    /* 6. Change the next of last node */
    last->next = new_node;
    return;   
}

Time complexity of append is O(n) where n is the number of nodes in linked list. Since there is a loop from head to end, the function does O(n) work.
This method can also be optimized to work in O(1) by keeping an extra pointer to tail of linked list/

Following is a complete program that uses all of the above methods to create a linked list.

// A complete working C program to demonstrate all insertion methods
// on Linked List
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct Node
{
  int data;
  struct Node *next;
};
/* Given a reference (pointer to pointer) to the head of a list and
   an int, inserts a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
    /* 1. allocate node */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    /* 2. put in the data  */
    new_node->data  = new_data;
    /* 3. Make next of new node as head */
    new_node->next = (*head_ref);
    /* 4. move the head to point to the new node */
    (*head_ref)    = new_node;
}
/* Given a node prev_node, insert a new node after the given
   prev_node */
void insertAfter(struct Node* prev_node, int new_data)
{
    /*1. check if the given prev_node is NULL */
    if (prev_node == NULL)
    {
      printf("the given previous node cannot be NULL");
      return;
    }
    /* 2. allocate new node */
    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));
    /* 3. put in the data  */
    new_node->data  = new_data;
    /* 4. Make next of new node as next of prev_node */
    new_node->next = prev_node->next;
    /* 5. move the next of prev_node as new_node */
    prev_node->next = new_node;
}
/* Given a reference (pointer to pointer) to the head
   of a list and an int, appends a new node at the end  */
void append(struct Node** head_ref, int new_data)
{
    /* 1. allocate node */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    struct Node *last = *head_ref;  /* used in step 5*/
    /* 2. put in the data  */
    new_node->data  = new_data;
    /* 3. This new node is going to be the last node, so make next of
          it as NULL*/
    new_node->next = NULL;
    /* 4. If the Linked List is empty, then make the new node as head */
    if (*head_ref == NULL)
    {
       *head_ref = new_node;
       return;
    }
    /* 5. Else traverse till the last node */
    while (last->next != NULL)
        last = last->next;
    /* 6. Change the next of last node */
    last->next = new_node;
    return;
}
// This function prints contents of linked list starting from head
void printList(struct Node *node)
{
  while (node != NULL)
  {
     printf(" %d ", node->data);
     node = node->next;
  }
}
/* Driver program to test above functions*/
int main()
{
  /* Start with the empty list */
  struct Node* head = NULL;
  // Insert 6.  So linked list becomes 6->NULL
  append(&head, 6);
  // Insert 7 at the beginning. So linked list becomes 7->6->NULL
  push(&head, 7);
  // Insert 1 at the beginning. So linked list becomes 1->7->6->NULL
  push(&head, 1);
  // Insert 4 at the end. So linked list becomes 1->7->6->4->NULL
  append(&head, 4);
  // Insert 8, after 7. So linked list becomes 1->7->8->6->4->NULL
  insertAfter(head->next, 8);
  printf("\n Created Linked list is: ");
  printList(head);
  return 0;
}

Output:

 Created Linked list is:  1  7  8  6  4

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Java String Matches Example – Regular Expression Tutorial

String Matching Example in Java
String matches method in Java can be used to test String against regular expression in Java. String matches() method is one of the most convenient way of checking if String matches to a regular expression in Java or not. Quite often we need to write code which needs to check if String is numeric, Does String contains alphabets e.g. A to Z or a to Z, How to check if String contains a particular digit 6 times etc. There are so many cases in Java programming where we need regular expression. If you are familiar with Java’s regular expression API than you must know about java.util.regex.Pattern and java.util.regex.Matcher class, these class provides regular expression capability to Java API. matches method of String class actually delegate request to these classes. Anyway regular expression can be best learn by seeing few examples and this is what we are going to do in this Java String matches example tutorial.

String matches example Java

In this String matches tutorial we will see two examples of matches function of String class :

1) How to check if string contains any alphabetic characters or not in both e.g. A-Z or a-Z

2) How to check if string contains any numeric digits e.g. digits from 1-9 or 0-9

In following example of matching String using regular expression we have used two regular expression meta characters e.g. dot (.) which matches any character and astrick or star (*) which matches any number of times. By using .* we are effectively matching any character coming any number of time in source String in Java.

 

/**
* Java program to demonstrate how to use use String matches method

* to match regular expression in String.

*
* @author Javin
*/
public class StringMatchExample {

public static void main(String args[]) {
String[] alphabets = {“”, “12345”, “A12345”, “12345B”,

“12345a” , “abcd” , “aa343”};

for(String alphabet : alphabets) {
System.out.println(” does ” + alphabet +
” contains alphabetic words : ” + alphabet.matches(“.*[A-Za-z].*”));

}

//checking if String contains digits or not
String[] numbers = {“1234” , “+1234”, “234a”};
for(String number : numbers) {
System.out.println(” number ” + number + ” contains only 1-9 digits : ”
+ number.matches(“.*[1-9].*”));
}

}
}

Output:
does  contains alphabetic words : false
does 12345 contains alphabetic words : false
does A12345 contains alphabetic words : true
does 12345B contains alphabetic words : true
does 12345a contains alphabetic words : true
does abcd contains alphabetic words : true
does aa343 contains alphabetic words : true
number 1234 contains only 1-9 digits : true
number +1234 contains only 1-9 digits : true
number 234a contains only 1-9 digits : true

Though you can use Pattern and Matcher class for regular expression in Java. matches method of String is nice shortcut and you can quickly check if a particular String matches to a regular expression or not. These String match examples are just tip of iceberg in terms of regular expression but it does show how to use match method of String in Java.

 

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

How to reverse String in Java with or without StringBuffer Example

Reverse String in Java

There are many ways to reverse String in Java. You can use rich Java API to quickly reverse contents of any String object. Java library provides StringBuffer and StringBuilder class with reverse() method which can be used to reverse String in Java. Since converting between String and StringBuffer or StringBuilder is very easy it’s the most easy way available to reverse String in Java. At the same time Writing Java program to reverse String in Java without StringBuffer is one of the popular Java String interview question, which requires you to reverse String by applying logic and by not using API methods. Since reverse is a recursive job, you can use recursion as well as loop to reverse String in Java. In this Java tutorial I have shown How to reverse String using StringBuffer, StringBuilder and using pure loop with logic. You can also check How to reverse String with recursion in Java, if you want to see recursive code. let’s see complete Java program for this beautiful Java programming exercise.

 

Java program to reverse String in Java

Here is my complete code program to reverse any String in Java. In main method we have first used StringBuffer and StringBuilder to reverse contents of String and then we wrote our own logic to reverse String. This uses toCharArray() method of String class which return character array of String. By looping through character array and appending it into empty String we can get reversed String in Java, as shown in following example.

 

/**
*
* Java program to reverse String in Java. There are multiple ways to reverse
* String in Java, you can either take help of standard Java API StringBuffer
* to reverse String in Java. StringBuffer has a reverse() method which return StringBuffer
* with reversed contents. On the other hand you can also reverse it by applying your
* own logic, if asked to reverse String without using StringBuffer in Java. By the way
* you can also use StringBuilder to reverse String in Java. StringBuilder is non thread-safe
* version of StringBuffer and provides similar API. You can use StringBuilder’s reverse()
* method to reverse content and then convert it back to String
*
* @author http://java67.blogspot.com
*/
public class StringReverseExample {

public static void main(String args[]) {

//quick wasy to reverse String in Java – Use StringBuffer
String word = “HelloWorld”;
String reverse = new StringBuffer(word).reverse().toString();
System.out.printf(” original String : %s , reversed String %s  %n”, word, reverse);

//another quick to reverse String in Java – use StringBuilder
word = “WakeUp”;
reverse = new StringBuilder(word).reverse().toString();
System.out.printf(” original String : %s , reversed String %s %n”, word, reverse);

//one way to reverse String without using StringBuffer or StringBuilder is writing

        //own utility method
word = “Band”;
reverse = reverse(word);
System.out.printf(” original String : %s , reversed String %s %n”, word, reverse);
}

public static String reverse(String source){
if(source == null || source.isEmpty()){
return source;
}
String reverse = “”;
for(int i = source.length() -1; i>=0; i–){
reverse = reverse + source.charAt(i);
}

return reverse;
}

}

Output:
original String : HelloWorld , reversed String dlroWolleH
original String : WakeUp , reversed String pUekaW
original String : Band , reversed String dnaB

That’s all on How to reverse String in Java with and without StringBuffer and StringBuilder.

 

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

How to count a number of words in given String in Java?

Can you write a method in Java which accepts a String argument and returns a number of words in it? A word is a sequence of one or more non-space character i.e. any character other than ” (empty String). This should be your method signature:

public int count(String word);

This method should return 1 if the input is “Java” and return 3 if the input is “Java, C++, Python”. Similarly a call to wordCount(”    “) should return 0.  This is one of the several String algorithmic questions you can expect in a programming job interview.  This is used to test the coding skills of the candidate and that’s why it’s very important to prepare for these questions anytime you go for an interview.

Many programmers have personal collections of such questions which they revise every time they go for a Programming job interview, but if you don’t have any yet, then don’t worry. You can always use the Cracking the Coding Interview, it contains 190 programming questions and solutions on every important topic e.g. String, array, linked list, hash table, binary tree and other data structures.

Solution – Counting words in String

The solution of this problem is very simple if you know a little bit of regular expression and how to split String in Java using regex . Since problem says that words are separated by white space, which could be space or tabs. So if you split the String by whitespace as shown , you can get an array of String which is nothing but words.  Now the length of this array is your number of words, just return that.
Though, you need to be a little bit careful because there is also a possibility of more than one space between two words. So simply using a regular expression to catch space or tab will not be enough, you need to use a greedy regular expression to catch multiple spaces as well.

In Java, you can use the regular expression pattern “\\s+” to catch multiple spaces. The “\s” is a character class to find white space, which could match both space and tabs and “+” makes it greedy because it will match one or more of “\s” pattern i.e. one or more space. Now, since you need to escape the “\”  backward slash in Java, the whole pattern becomes “\\s+”. Se Mastering regular expression to learn more about regex in Java.

Java Program to count number of words in String

/**
 * Java Program to count number of words in a given
 * sentence. Words are separated by whitespace in
 * String.
 * @author WINDOWS 8
 *
 */
public class StringCounter {


    public static void main(String[] args) {

        // testing with non-empty String
        String input = "Java is great";
        int numOfWords = count(input);

        System.out.println("input: " + input);
        System.out.println("count of words: " + numOfWords);

        // testing with empty String
        input = "";
        numOfWords = count(input);

        System.out.println("input: " + input);
        System.out.println("count of words: " + numOfWords);

        // testing with null String
        input = null;
        numOfWords = count(input);

        System.out.println("input: " + input);
        System.out.println("count of words: " + numOfWords);

    }

    /**
     * Return the number of words in given String
     * @param sentence, words are separated by whitespace
     * @return count of words in sentence
     */
    public static int count(String sentence){
        if(sentence == null || sentence.isEmpty()){
            return 0;
        }

        String[] words = sentence.split("\\s+");
        return words.length;
    }


}

Output:
input: Java is great
count of words: 3
input:
count of words: 0
input: null
count of words: 0

That’s all about how to count a number of words in a given String in Java. The regular expression trick really solves this problem in a couple of lines, but as a challenge, can you solve this problem without using regular expression? If you go on real interview, that would be surely a follo-up questions given how easy the split() method solves this problem.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Difference between ArrayList and HashSet in Java

ArrayList vs HashSet Java

Main difference between ArrayList and HashSet is that one is a List implementation while other is a Set implementation. It means all the differences between a List data structure and a Set data structure also applies to this pair. For example, List implementations are ordered, it store element in the order they were added, while Set implementation doesn’t provide such guarantee. Similarly, since List provides Random access, you can access any element directly if you know the index, but Set doesn’t provide such facility. You need to Iterate through whole collection to get access of any elements. We will see couple of more difference in this Java tutorial. By the way ArrayList and HashSet are two most common Collection class used in Java programming language and before discussing difference between ArrayList vs HashSet, let’s see some similarities between them :

 

Similarities ArrayList and HashSet

Here are couple of similarities between ArrayList and HashSet in Java:

1) Both ArrayList and HashSet are non synchronized collection class and not meant to be used in multi-threading and concurrent environment. You can  make ArrayList and HashSet synchronized by using Collections.synchroinzedCollection() just like we make ArrayList and HashSet read only other day.

2) Both ArrayList and HashSet can be traversed using Iterator. This is in fact a preferred way if you want to perform operation on all elements.

 

3) Iterator of ArrayList and HashSet both are fail-fast, i.e. they will throw ConcurrentModificationException if ArrayList or HashSet is modified structurally once Iterator has been created.

Now let’s see some differences between ArrayList and HashSet in Java

 

Difference between ArrayList vs HashSet in Java

Here are couple of differences between ArrayList and HashSet in Java:

1) First and most important difference between ArrayList and HashSet is that ArrayList implements List interface while HashSet implements Set interface in Java.

2) Another difference between ArrayList and HashSet is that ArrayListallow duplicates while HashSet doesn’t allow duplicates. This is the side effect of fist difference and property of implementing List and Set interface.

3) Third difference between ArrayList and HashSet is that ArrayList is an ordered collection and maintains insertion order of elements while HashSet is an unordered collection and doesn’t maintain any order.

4) Fourth difference between ArrayList and HashSet is that ArrayList is backed by an Array while HashSet is backed by an HashMap instance.

5) Fifth difference between HashSet and ArrayList is that its index based you can retrieve object by calling get(index) or remove objects by calling remove(index) while HashSet is completely object based. HashSet also doesn’t provide get() method.

That’s all on difference between ArrayList and HashSet. these differences helps you to decide where to use ArrayList and where to use HashSet in Java. in terms of performance between ArrayList and HashSet, choose what suits best to you. raw array is fasted among them.

 

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

How to convert an array to ArrayList in Java

Have you encountered any situation where you quickly wanted to convert your array to ArrayList or ArrayList to array in Java? I have faced many such situations which motivate me to write these quick Java tips about converting an array to ArrayList and ArrayList to array in Java. Both array and ArrayList are quite common and every Java developer is familiar with this. Former is used to store object and primitive type while later can only hold objects. The array is part of standard Java fundamental data structure while ArrayList is part of collection framework in Java. Most of the time we store data in the form of an object in either Array or ArrayList or sometimes we find either of them suitable for processing and we want to convert from one array to ArrayList or ArrayList to array in Java.

This short array to ArrayList tutorial in Java will explain how quickly you can convert data from each other. So when you face such situation don’t bother just remember this tips and you will get through it. If you compare array vs ArrayList only significant different is one is fixed size while other is not.

On related not from Java 5 onwards, ArrayList class supports Generics in Java, which means you ca convert an ArrayList of String into an String array or ArrayList of Integer into an Integer Array. The generic provide type safety and remove casting during runtime.

How to convert Array to ArrayList in Java

In first section of this Java tutorial we will see how to convert from Array to ArrayList while in second section we will see opposite of it i.e. from ArrayList to Array. Main difference between these two is that once declared you can not change the size of former while later is dynamic which re-sizes itself whenever its capacity crossed threshold specified by load factor.

Using Arrays.asList() method

Look at the below example, we have an array which contains different kind of asset class e.g. equity, gold and foreign exchange etc and we want to convert into an arraylist. This is the simplest way of converting from array to ArrayList.

String[] asset = {"equity", "stocks", "gold", "foreign exchange","fixed income", "futures", "options"};
List<String> assetList = Arrays.asList(asset);

Its worth to note following point while using Arrays.asList() method for array to arraylist conversion:

1) This method returns a List view of underlying array.

2) List returned by this method would be fixed size.

3) Most important point to note is when you change an element into this List corresponding element in original array will also be changed.

4) Another important point is since List is fixed size, you can not add element into it. If you try you will get exception.

5) This is the most efficient way of converting array to arraylist as per my knowledge because it doesn’t copy the content of underlying array to create list.

6) From Java 5 or JDK 1.5 onwards this method supports generic so you can generate type safe ArrayList from array. to know more about Generic see my post How Generic works in Java

One of the most important point related to Arrays.asList() method is that it returns a fixed size List not a read only List, although you can not add() or remove() elements on this List you can still change existing elements by using set method. If you are using this to create read only List than its wrong, Use Collections.unmodifiableList method to create read only collection in Java.

Array to ArrayList by using Collections.addAll method

This example of converting an array to ArrayList is not that efficient as the earlier method but its more flexible.

List<String> assetList = new ArrayList();
String[] asset = {"equity", "stocks", "gold", "foriegn exchange", "fixed income", "futures", "options"};

Collections.addAll(assetList, asset);

Important point about this method of array to ArrayList conversion is :

1) Its not as fast as Arrays.asList() but more flexible.

2) This method actually copies the content of the underlying array into ArrayList provided.

3) Since you are creating copy of original array, you can add, modify and remove any element without affecting original one.

4) If you wan to provide individual element you can do so by specifying them individually as comma separated. Which is a very convenient way of inserting some more elements into existing list for example we can add some more asset classes into our existing assetlist as below?

Collections.addAll(assetList, "Equity Derivatives", "Eqity Index Arbitrage" , "Mutual Fund");

 

Example of Converting ArrayList to Array using Collection’s addAll method

This is another great way of converting an array to ArrayList. We are essentially using Collection interface’s addAll() method for copying content from one list to another. Since List returned by Arrays.asList() is fixed-size it’s not much of use, this way we can convert that into proper ArrayList.

Arraylist newAssetList = new Arraylist();
newAssetList.addAll(Arrays.asList(asset));

These were the three methods to convert an array to ArrayList in Java. By the way, you can also create arrays of ArrayList because list can hold any type of object.

Array to List in Java using Spring Framework

There is another easy way of converting array to ArrayList if you are using spring framework. spring framework provides several utility method in class CollectionUtils, one of the is CollectionUtils.arrayToList() which can convert an array into List as shown in below example of array to List conversion using spring framework. It’s worth noting though List returned by arrayToList() method is unmodifiable just like the List returned by Arrays.asList(), You can not add() or remove() elements in this List. Spring API also provides several utility method to convert an ArrayList into comma separated String in Java.

String [] currency = {"SGD", "USD", "INR", "GBP", "AUD", "SGD"};
System.out.println("Size of array: " + currency.length);
List<String> currencyList = CollectionUtils.arrayToList(currency);

//currencyList.add("JPY"); //Exception in thread "main" java.lang.UnsupportedOperationException
//currencyList.remove("GBP");//Exception in thread "main" java.lang.UnsupportedOperationException

System.out.println("Size of List: " + currencyList.size());
System.out.println(currencyList);

How to convert ArrayList to Array in Java

Now this is a opposite side of story where you want to convert from Arraylist to Array, instead of array to ArrayList, interesting right. Just now we were looking at converting array to arraylist and now we need to back to former one. Anyway it’s simpler than you have probably thought again we have java.util.Arrays class as our rescue. This class acts as bridge between ArrayList to array.

Example of converting ArrayList to Array in Java

In this example of ArrayList to array we will convert our assetTradingList into String array.

ArrayList assetTradingList = new ArrayList();

assetTradingList.add("Stocks trading");
assetTradingList.add("futures and option trading");
assetTradingList.add("electronic trading");
assetTradingList.add("forex trading");
assetTradingList.add("gold trading");
assetTradingList.add("fixed income bond trading");
String [] assetTradingArray = new String[assetTradingList.size()];
assetTradingList.toArray(assetTradingArray);

After execution of last line our assetTradingList will be converted into String array. If you like to learn more about How to use ArrayList in Java efficiently check the link it has details on all popular operation on Java ArrayList.

Getting a clear idea of converting array to Array List and back to ArrayList and array saves a lot of time while writing code. It’s also useful if you like to initialize your ArrayList with some default data or want to add some elements into your existing ArrayList. these examples of converting array to ArrayList is by no means complete and please share your own ways of converting from ArrayList to array and vice-versa.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide