SKP's Java Problem Solving Series : Van Eck's Sequence (Naive & Fast Lookup)

[Question/Problem Statement is from GeeksforGeeks]

Algorithms/Data Structures - [Problem Solving] 

Given a Positive Integer N, The Task is to Print N Terms of the Van Eck’s Sequence. In Maths, Van Eck’s sequence is an Integer Sequence which is defined recursively as given below.    

-

-

 Let the First Term Be 0 i.e, a[0] = 0.
 Then for n>=0, If There Exists an m<n, such that a[m] = a[n]
 -
 Take the Largest such m and set a[n+1] = [n − m];
 Otherwise a[n+1] = 0, Start with a(1) = 0.
 

Example

[ First Few Terms of Van Eck’s Sequence are as Follows: ] 

0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5 …
 

Constraints
• [No Special Constraints Exist]

Input Format

[N is a Constant in the Java Code, For Example N=50]

 

 

Sample Output (Each Should Be on a Separate Line)

0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, 2, 9, 0, 4, 9, 3, 6, 14, 0, 6, 3, 5, 15, 0, 5, 3, 5, 2, 17, 0, 6, 11, 0, 3, 8, 0, 3, 3,

  

______________ 

 

 

 

/**
 * The Mathematical Puzzle of Van Eck's Sequence - Xebia Interview - 07-Dec-2021
 * [At the Experience Level of 17y - Was Interviewing for Java/Java EE Architect]
 */

// Given a Positive Integer N, The Task is to Print Nth Term of the Van Eck’s Sequence.
// In Maths, Van Eck’s sequence is an Integer Sequence which is defined Recursively As: 
//   
// Let the First Term Be 0 i.e, a[0] = 0.
// Then for n>=0, If There Exists an m<n 
// such that a[m] = a[n]
// -
// Take the Largest such m and set a[n+1] = [n − m];
// Otherwise a[n+1] = 0, Start with a(1) = 0.
// -  
// [ First Few Terms of Van Eck’s Sequence are as Follows: ] 
//  
// 0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5 … 
//  
// Input: N = 05, Output: 2
//  
// Input: N = 10, Output: 6 


/**
 * @author sumith.puri
 *
 */
public class VanEckSequence {

  static final int N=50;
  
  int[] printSeq    = null;
  int[] index1      = null;
  int val           = 0;
  int index         = 3;
 


  VanEckSequence() {

    init();
  }


  private void init() {

    printSeq    = new int[50];
    index1      = new int[200];
    val         = 0;
    index       = 3;
    index1[val] = 1;
  }


  public void linearVanEckSequence() {
    for (int i = 2; i < N; i++) {

      for (int j = i - 1; j > 0; j--) {
        if (printSeq[i - 1] == printSeq[j - 1]) {

          printSeq[index - 1] = i - j;          
          break;
        }
      }
      index++;
    }
  }


  public void fasterVanEckSequence() {
    
    int i = 0;
    
    for (int j = 2; j < N; j++) {

      i = j - 1;
      val = printSeq[i];

      // System.out.println("index:" + index + ":"+ val);
      if (index1[val] == 0) {

        printSeq[index-1] = 0;
        index1[val] = i + 1;
      } else {
        printSeq[index-1] = (i + 1) - index1[val];
        // optimal - fast lookup
        index1[val] = (i + 1);
      }
      index++;
    }
  }



  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub


    VanEckSequence vancEckSequence = new VanEckSequence();
    vancEckSequence.linearVanEckSequence();

    System.out.println("Van Eck Sequence (Linear/Naive Algorithm)");
    System.out.println("----------------------------------------)");
    for (int i = 0; i < N; i++) {

      System.out.print(vancEckSequence.printSeq[i] + ", ");
    }

    System.out.println("\n");
    vancEckSequence.init();
    vancEckSequence.fasterVanEckSequence();

    System.out.println("Van Eck Sequence (Fast Lookup Algorithm)");
    System.out.println("----------------------------------------)");


    for (int i = 0; i < N; i++) {

      System.out.print(vancEckSequence.printSeq[i] + ", ");
    }

    System.out.println("");
    System.out.println("\n");
    System.out.println("Sumith Kumar Puri");
    System.out.println("SCJP 1.4, SCJP 5.0 / SCBCD 1.4, SCBCD 5.0");
    System.out.println("BB Spring 2.x, Hibernate 3.x, Java EE 6.x");
    System.out.println("Quest C, Quest C++, Quest Data Structures");
    System.out.println("Google India Code Jam 2005 Semi-Finalist.");
    System.out.println("Techgig Code Gladiators '15 Semi-Finalist");
    System.out.println("Societe Generale Brainwaves '15 Finalist.");
    System.out.println("Mphasis (Internal) Hackathon - Rank#7/106");
    System.out.println("Java Code Geeks, DZone MVB* & DZone Core*");
    System.out.println("Senior Member, ACM & Senior Member, IEEE.");
    System.out.println("Member*, CSI*; Foojay.IO & Developer.com*");
  }

}

SKP's Java Problem Solving Series : Usernames Changes (HackerRank)

[Question/Problem Statement is Adapted from HackerRank]

Algorithms/Data Structures - [Problem Solving] 

There is a Specific Need for Changes in a List of Usernames. In a given List of Usernames - For Each Username - If the Username can be Modified and Moved Ahead in a Dictionary. The Allowed Modification is that Alphabets can change Positions in the Given Username.

Example

usernames[] = {"Aab", "Cat"}

 

"Aab" cannot be changed to another unique string matching the above rule - Hence, It can Never Find a Place Ahead in the Dictionary. Hence, Output will be "NO". "Cat" can be Changed to "Act", "Atc", "Tca", "Tac", "Cta" and Definitely "Act" will Find a Place Before "Cat" in the Dictionary. Hence, Output will be "YES".

[Function Description]
Complete the function possibleChanges in the Editor Below.
 

possibleChanges has the Following Parameters:
String usernames[n]: An Array of User Names
 

Returns String[n]: An Array with "YES" or "NO" Based on Feasibility
(Actual Question Says String Array, But Signature is List of Strings)

Constraints
• [No Special Constraints Exist, But Cannot Recall Exactly]

Input Format
"The First Line Contains an Integer, n, the Number of Elements in Usernames.", 

"Each Line of the n Subsequent Lines (where 0 < i < n) contains a String usernames[i]."        

[Sample Case 0 - Sample Input For Custom Testing]        
8      
Aab 

Cat

Pqrs

Buba

Bapg

Sungi

Lapg

Acba

       

Sample Output (Each Should Be on a Separate Line)

NO YES NO YES YES YES YES YES

  

______________ 

 

 
[Explanation of the Solution]
This is again a Good Question from Hacker Rank to Test Your Logic / Problem Solving Abilities. The Core Point to Handle is that For Each Combination of 2 Alphabets that Exists in the Username String > We Need to Check if the Latter Occuring Character (ASCII) is Less than the Former Occuring Character (ASCII). For Example in the String "Bapg" - For a Selection of "Ba" from "Bapg" - We have "a" Occuring Before "B" in the English Alphabet. We can Have Two Loops (One Nested) to Decide for a Combination of Each Two Alphabets. The Time Complexity of this Solution is O(n^2).

 

________________  

 

[Source Code, Sumith Puri (c) 2021 - Free to Use & Distribute]

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/*
 * HackerRank Problem Solving - Speak Ur Mind, But Ride a Fast Horse.
 * ~ Sumith Kumar Puri (c) 2021 ~ -- ~ Bengaluru, Karnataka, India ~
 * 
 */
class UsernamesChangesLogic {

	public static List<String> possibleChanges(List<String> usernames) {

		List<String> solutionStr = new ArrayList<String>();
		boolean bobbysFlag = false;
		for (String username : usernames) {

			bobbysFlag = false;
			String currName = username.toLowerCase();
			for (int i = 0; i < currName.length(); i++) {

				int a = currName.charAt(i);
				for (int j = i + 1; j < currName.length(); j++) {

					int b = currName.charAt(j);
					if (b < a) {
						bobbysFlag = true;
						break;
					}
				}
				if (bobbysFlag) {
					solutionStr.add("YES");
					break;
				}
			}
			if (!bobbysFlag)
				solutionStr.add("NO");
		}

		return solutionStr;
	}
}

public class UsernamesChanges {

	public static final String OUTPUT_PATH = "PROVIDE_ABSOLUTE_INPUT_FILE_NAME";

	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(OUTPUT_PATH));

		int usernamesCount = Integer.parseInt(bufferedReader.readLine().trim());

		List<String> usernames = IntStream.range(0, usernamesCount).mapToObj(i -> {
			try {
				return bufferedReader.readLine();
			} catch (IOException ex) {
				throw new RuntimeException(ex);
			}
		}).collect(toList());

		List<String> result = UsernamesChangesLogic.possibleChanges(usernames);

		bufferedWriter.write(result.stream().collect(joining("\n")) + "\n");

		bufferedReader.close();
		bufferedWriter.close();
	}
}

Happy Problem Solving using Java!

SKP's Java Problem Solving Series : Active Traders (HackerRank)

[Question/Problem Statement is the Property of HackerRank]

Algorithms/Data Structures - [Problem Solving] 

An Institutional Broker wants to Review their Book of Customers to see which are Most Acctive. Given a List of Trades By "Customer Name, Determine which Customers Account for At Least 5% of the Total Number of Trades. Order the List Alphabetically Ascending By Name."

Example
n = 23
"customers = {"Bigcorp", "Bigcorp", "Acme", "Bigcorp", "Zork", "Zork", "Abe", "Bigcorp",  "Acme", "Bigcorp", "Bigcorp" , "Zork", "Bigcorp", "Zork", "Zork", "Bigcorp", "Acme", "Bigcorp", "Acme", "Bigcorp", "Acme",""Littlecorp" , "Nadircorp "}."

"Bigcorp had 10 Trades out of 23,which is 43.48% of the Total Trades."
"Both Acme and Zork had 5 trades,which is 21.74% of the Total Trades."
"The Littlecorp, Nadircorp and Abe had 1 Trade Each, which is 4.35%..."

"So the Answer is [""Acme"", "" Bigcorp  ,""Zork""] (In Alphabetical Order) Because only These Three Companies Placed atleast 5% of the Trades.


Function Description
Complete the Function mostActive in the Editor Below.

mostActive has the following parameter:
String customers[n] : An Array Customer Names
(Actual Question Says String Array, But Signature is List of Strings)

Returns String[] : An Alphabetically Ascending Array


Constraints
• 1 < n < 10^5
• 1 < Length of customers[] < 20
• The First Character of customers[i] is a Capital English letter.
• All Characters of customers[i] except for the First One are Lowercase.
• Guaranteed that At least One Customer makes atleast 5% of Trades.


Input Format            
"The First Line contains an integer, n, The Number of Elements in customers."       
"Each Line iof the n Subsequent Lines (where 0 s i< n) contains a string, customers[i]."      


Sample Case 0 Input For Custom Testing
20       
Omega Alpha Omega Alpha Omega Alpha Omega Alpha Omega Alpha Omega Alpha Omega Alpha Omega Alpha Omega Alpha Omega Beta      


Function mostActive      
customers[] size n =  20       
customers[] = [As Provided Above]       


Sample Output
Alpha       
Beta
Omega       


Explanation
"Alpha made 10 Trades out of 20 (50% of the Total), Omega made 9 Trades (45% of the Total). and Beta made 1 Trade (5% of the Total).All of them have met the 5% Threshold, so all the Strings are Returned in an Alphabetically Ordered Array."        

 

______________ 

 

 
[Explanation of the Solution]
This is Good Practice for the Brain for Problem Solving - Involves Simple Arithmetic and Mathematical Application. Ideally, A Programmer would want to Optimize the Solution in Space and Time (Which I Did Not :-)

 

________________  

 

[Source Code, Sumith Puri (c) 2021 - Free to Use & Distribute]

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.stream.IntStream;

/*
 * HackerRank Problem Solving - Ain't a Horse that Can't be Rode
 * Sumith Kumar Puri (c) 2021 - ~ Bengaluru, Karnataka, India ~
 * 
 */
class ActiveTradersLogic {
	
	public static List<String> mostActive(List<String> customers) {

		// How About Arrays or Custom LinkedList for a 'Very Fast' Traversal?
		Map<String, Integer> customerMap = new TreeMap<String, Integer>();
		List<String> solutionStr = new ArrayList<String>();
		int customerMapSize = customers.size();

		for (int i = 0; i < customerMapSize; i++) {

			String customerKey = customers.get(i);

			if (customerMap.containsKey(customerKey)) {

				Integer customerCount = customerMap.get(customerKey);
				customerMap.put(customerKey, ++customerCount);
			} else {
				customerMap.put(customerKey, 1);
			}
		}

		Set<String> customerMapKeys = customerMap.keySet();
		for (String customerKey : customerMapKeys) {

			Integer customerCount = customerMap.get(customerKey);
			double currentCustomerPercent = (double) (customerCount) / (double) customerMapSize;

			if (currentCustomerPercent * 100 >= 5.0) {

				solutionStr.add(customerKey);
			}
		}

		return solutionStr;
	}
}

public class ActiveTraders {
	
	public static final String OUTPUT_PATH = "PROVIDE_ABSOLUTE_INPUT_FILE_NAME";
	
	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv(OUTPUT_PATH)));

		int customersCount = Integer.parseInt(bufferedReader.readLine().trim());

		List<String> customers = IntStream.range(0, customersCount).mapToObj(i -> {
			try {
				return bufferedReader.readLine();
			} catch (IOException ex) {
				throw new RuntimeException(ex);
			}
		}).collect(toList());

		List<String> result = ActiveTradersLogic.mostActive(customers);

		bufferedWriter.write(result.stream().collect(joining("\n")) + "\n");

		bufferedReader.close();
		bufferedWriter.close();
	}
}

Happy Problem Solving using Java!

Java Memory Architecture (Model), Garbage Collection and Memory Leaks

Java Memory Architecture (Java Memory Model)

The above is the Java Memory Model for the Heap as well as the PermGen for any Java Application running in the Java Virtual Machine (JVM). The ratios are also provided to get a fair understanding of how the distribution of allowed memory is done across each of the generation types. All of the above is completely applicable up to Java release 1.7 (inclusive). The above is also known as the 'Managed Area' of the Memory Model.

In addition to the above, there is a Stack Area, which can be configured use the -Xss option. This area holds the references on the heap, native references, pc registers, code cache and local variables for all threads. This is also known as the 'Native Area' of the Memory Model.

Managed Area of the Java Memory Model (Java Memory Architecture)
[Young Generation/Nursery] Eden Space

All new objects are first created in the Eden Space. As soon as it reaches an arbitrary threshold decided by the JVM, a minor garbage collection (Minor GC) kicks in. It first removes all the non-referenced objects and moves referenced objects from the 'eden' and 'from' into the 'to' survivor space. Once the GC is over, the 'from' and 'to' roles (names) are swapped.

[Young Generation/Nursery] Survivor 1 (From)

This is a part of the survivor space (You may think of this a role in the survivor space). This was the 'to' role during the previous garbage collection (GC).

[Young Generation/Nursery] Suvrivor 2 (To)

This is also a part of the survivor space (You may think of this also a role in the survivor space). It is here, where during the GC, all the referenced objects are moved to, from 'from' and 'eden' .

 

[Old Generation] Tenured

Depending on the threshold limits, which can be checked by using -XX:+PrintTenuringDistribution, which shows the objects (space in bytes) by age - Objects are moved from the 'to' Survivor space to the Tenured space. 'Age' is the number of times that it has moved within the survivor space. There are other important flags like, -XX:InitialTenuringThreshold, -XX:MaxTenuringThreshold and -XX:TargetSurvivorRatio which lead to an optimum utilization of the tenured as well as the survivor spaces. By setting -XX:InitialTenuringThreshold and -XX:MaxTenuringThreshold we allow an initial value and an maximum value for 'Age' while maintaining the percentage utilization in the 'Survivor (To)' as specified by the -XX:+NeverTenure and -XX:+AlwaysTenure, as they suggest are used to either never tenure an object (risky to use) and the opposite usage is to always tenure, which is to always use the 'old generation'. The garbage collection that happens here is the major garbage collection (Major GC). This is usually triggered when the heap is full or the old generation is full. This is usually a 'Stop-the-World' event or thread that takes over to perform the garbage collection. There is another type of GC named as the full garbage collection (Full GC) which involves other memory areas such as the permgen space. Other important and interesting flags related to the overall heap are -XX:SurvivorRatio and -XX:NewRatio which specify the eden space to the survivor space ratio and old generation to the new generation ratio.

[Permanent Generation] Permgen space

The 'Permgen' is used to store the following information: Constant Pool (Memory Pool), Field & Method Data and Code. Each of them related to the same specifics as their name suggests.

Garbage Collection Algorithms

Serial GC (-XX:UseSerialGC): GC on Young Generation and Old Generation

Use the simple mark-sweep-compact cycle for young and tenured generations. This is good for client systems and systems with low memory footprint and smaller cpu.

Parallel GC (-XX:UseParallelGC): GC on Young Generation and Old Generation

This used N threads which can be configured using -XX:ParallelGCThreads=N, here N is also the number of CPU cores. for garbage collection. It uses these N threads for GC in the Young Generation but uses only one-thread in the Old Generation.

Parallel Old GC (-XX:UseParallelOldGC): GC on Young Generation and Old Generation

This is same as the Parallel GC, except that it uses N threads for GC in both Old and Young Generation.

Concurrent Mark and Sweep GC (-XX:ConcMarkSweepGC): GC on Old Generaton

As the name suggest, the CMS GC minimzes the pauses that are required for GC. It is most useful to create highly responsive applications and it does GC only in the Old Generation. It creates multiple threads for GC that work concurrently with applications threads, which can be specified using the -XX:ParallelCMSThreads=n.

G1 GC (-XX:UseG1GC): GC on Young and Old Generation (By Dividing Heap into Equal Size Regions)

This is  a parallel, concurrent and incrementally compacting low-pause garbage collector. It was introduced with Java 7 with the ultimate vision to replace CMS GC. It divides the heap into multiple equal sized regions and then performs GC, usually starting with the region that has less live data - Hence, "Garbage First".

Most Common Out of Memory Issues

The most common out of memory issues, which all Java Developers should know, so as to start debugging in the right earnest are as follows:

• Exception in thread "main": java.lang.OutOfMemoryError: Java heap space
  This does not necessarily imply a memory leak - as it could be due to lesser space configured for the heap. Otherwise, in a long-lived application it could be due to unintentionally references being mentioned to heap objects (memory leak). Even the APIs that are called by the application could be holding references to objects that are unwarranted for. Also, in applications that make excessive use of finalizers, sometimes the objects are queued into a finalization queue. When such an application creates higher priority threads and that leads to more and more objects in the finalizaton queue, It can cause an Out-of-Memory. 
• Exception in thread "main": java.lang.OutOfMemoryError: PermGen space
  If there are many classes and methods loaded or if there are very many string literals created, especially through the use of intern() (From JDK 7, interned strings are no longer part of the PermGen) - then this type of error occurs. When this kind of error occurs, the text ClassLoader.defineClass might appear near the top of the stack trace that is printed.
• Exception in thread "main": java.lang.OutOfMemoryError: Requested array size exceeds VM limit
  This again happens when the requested array size is greater than the available heap size. It may usually  occur due to programmatic errors during runtime, if an incredibly large value is requested for an array size.
• Exception in thread "main": java.lang.OutOfMemoryError: request <s> bytes for <r>. Out of swap space?
  It may usually be the root cause for a memory leak. It happens when either the Operating System does not have sufficient swap space or when Another Process hogs all the available memory resources on the system. In simple terms, it was unable to provide the request space from heap due to exhaustion of space. The message indicates the size 's' (in bytes) of the request that failed and the reason 'r' for the memory request. In most cases the <r> part of the message is the name of a source module reporting the allocation failure, although in some cases it indicates a reason.
• Exception in thread "main": java.lang.OutOfMemoryError: <reason> <stack trace> (Native method)
  This indicates that a Native method has met with an allocation failure. The root cause was that the error occurred in JNI rather than in the code executing inside the JVM.
  When the native code does not check for memory allocation errors, then the application crashes instead of going out of memory.

 

Definition of Memory Leak

"Think of memory leakage as a disease and the OutOfMemoryError as a symptom. But not all OutOfMemoryErrors imply memory leaks, and not all memory leaks manifest themselves as OutOfMemoryErrors. "

In Computer Science, a memory leak is a type of resource leak that occurs when a computer program incorrectly manages memory allocations in such a way that memory which is no longer needed is not released. In Object-Oriented Programming, a memory leak may happen when an object is stored in memory but cannot be accessed by the running code.

Common Definitions of Memory Leak in Java:  

A Memory Leak occurs when Object References that are no Longer needed are Unnecessarily Maintained.

Memory Leak in Java is a situation where some objects are not used by Application any more, but GC fails to Recognize them as Unused. 

A Memory Leak appears when an object is no longer used in the program but is still referenced somewhere at a location that is not reachable. Thus, the garbage collector cannot delete it. The memory space used for this object will not be released and the total memory used for the program will grow. This will degrade performances over time and the JVM may run out of memory.

In a way, Memory Leak would occur when No Memory can be Allocated in the Tenured Space.

Some of the Most Common Causes of Memory Leaks are:

1. ThreadLocal Variables
2. Circular and Complex Bi-Directional References
3. JNI Memory Leaks
4. Static Fields that are Mutable (Most Common)

I recommend the usage of Visual VM bundled with the JDK to start Debugging your Memory Leak Issues.

Common Debugging of Memory Leaks

1. NetBeans Profiler
2. Using the jhat Utility
3. Creating a Heap Dump
4. Obtaining a Heap Histogram on a Running Process
5. Obtaining a Heap Histogram at OutOfMemoryError
6. Monitoring the Number of Objects Pending Finalization
7. Third Party Memory Debuggers

The common strategies or steps for going about debugging memory leak issues include:

• Identify Symptoms
• Enable Verbose Garbage Collection
• Enable Profiling
• Analyze the Trace

Wishing Happy Times, Fixing Java Memory Issues!

 

Common Interview Questions - Algorithms & Data Structures

Auto Complete (Word Search) using Trie [Java]

 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.ListIterator; 
 
 /**  
  * @author sumith.puri  
  *   
  * AutoComplete using Trie  
  */  
 public class AutoComplete {  

      TrieC root = null;  

      public static void main(String[] args) {  

           // tea party, tea park, tea parking, ten park, tee park, tel number  
           AutoComplete autoComplete = new AutoComplete();  
           autoComplete.loadTrie("tea party");  
           autoComplete.loadTrie("taa park");  
           autoComplete.loadTrie("tal park");  
           autoComplete.loadTrie("tea pair object f");  
           autoComplete.loadTrie("tea party was long");  
           autoComplete.loadTrie("tea party america");  
           autoComplete.loadTrie("tea par japan");  
           autoComplete.loadTrie("tea nol");  
           List<String> ac=autoComplete.search("tea");  
           for(String s: ac) System.out.println(s);  
      }  

      public void loadTrie(String word) {  

           boolean isRoot=false;  
           if(root==null) {  
                TrieC trie = new TrieC(new Character(' '));  
                root = trie;                                
           }   

           TrieC start = root;  
           char[] characters = word.toCharArray();  

           for(char c: characters) {                      

                if(start.getNext().size()==0) {                      
                     start=start.setNext(c);                           
                } else {  
                     ListIterator<TrieC> it = start.getNext().listIterator();  
                     TrieC ch = null;  
                     while(it.hasNext()) {  
                          ch = it.next();                           
                          if(ch.getNode() == c) {                                
                               break;                                
                          }  
                     }       
                     if(ch.getNode()==c) {                                     
                          start=ch;                      
                     } else {                                     
                          start=start.setNext(c);  
                     }  
                }  
           }  
      }  

      public List<String> search(String prefix) {  

           List<String> list = new ArrayList<String>();  
           if(prefix==null || prefix.length()==0) return list;  
           TrieC start = root;  
           char[] chars = prefix.toCharArray();  
           boolean flag=true;  

           for(char c: chars) {  

                if(start.getNext().size() > 0) {  

                     for(TrieC ch: start.getNext()) {  
                          if(ch.getNode()==c) {  
                               start=ch;  
                               flag=true;  
                               break;  
                          }  
                     }  
                } else {  
                     flag=false;  
                     break;  
                }  
           }  

           if(flag) {  
                System.out.println(start.getNode()+":"+prefix);  
                List<String> matches = this.getAllWords(start, prefix);  
                return matches;  
           }  

           return list;  
      }  

      private List<String> getAllWords(TrieC start, String prefix) {  

           if(start==null || start.getNext().size() == 0) {  

                List<String> list = new java.util.LinkedList<String>();  
                list.add(prefix);  
                return list;  
           } else {                 

                List<String> list = new java.util.LinkedList<String>();  
                for(TrieC ch: start.getNext()) {  
                     if(start!=null) {  
                          start = ch;  
                     }  
                          list.addAll(getAllWords(start, prefix+ch.getNode()+""));  
                }  
                return list;  
           }  
      }  
 }  

 class TrieC {  

      Character node;  
      List<TrieC> next;  

      TrieC(Character c) {  
           this.node=c;  
           next=new java.util.LinkedList<TrieC>();  
      }  

      public TrieC setNext(Character c) {  
           TrieC trie = null;  
           trie=new TrieC(c);  
           next.add(trie);  
           return trie;  
      }  

      public TrieC getNextByCharacter(Character c) {  
           return next.get(c);  
      }  

      public List<TrieC> getNext() {  
           return next;  
      }  

      public Character getNode() {  
           return node;  
      }  
 }  

Longest Palindrome (Continuous Substring) in a String [Java]

 /**  
  * @author sumith.puri  
  *   
  * O(n*n) : Time Complexity   
  */  
 public class LongestPalindrome {  
      
    public static String longestPalindrome(String gString) {  

           String lString=gString.substring(0,1), pString=null;            

           for(int i=0;i<gString.length()-1;i++) {                 

                pString=findPalindrome(gString, i, i);  

                if(pString.length()>lString.length()) {  
                     lString = pString;  
                }                 

                pString=findPalindrome(gString, i, i+1);  

                if(pString.length()>lString.length()) {  
                     lString = pString;  
                }  
           }  
           return lString;  
      }  

      public static String findPalindrome(String gString, int start, int end) {            

           int length=gString.length();  
           if(start > end) return null;  

           while(start>=0 && end < length && gString.charAt(start)==gString.charAt(end)) {  
                start--;  
                end++;  
           }            

           return gString.substring(start+1, end);  
      }  

      public static void main(String[] args) {            

           String iString="12232133123111";  
           System.out.println(longestPalindrome(iString));  
      }  
 }  

Data Structure - Interview Questions

Continuing on the quick revision of important questions for my Interviews. These are good puzzles or questions related to Data Structures. (All are in Java)

Reverse a Linked List
Circular Linked List
Dijkstra's Algorithm
Self-Balancing Tree

Enjoy!

Sorting Algorithms in Java

Just Doing a Quick Revision of Important Sorting Algorithms for my Interviews.

Quick Sort
Merge Sort
Heap Sort

All of Them are Targeted for Java SE 7!