Linked List Problems

1. Find the nth element from the end of a singly linked list.

    Approach 1:  Traverse the list  and find the length L of the list. Traverse the list second time and find (L-(n-1))th element from the head/start of the linked list.   Total traversal cost (L-n+1).

   Approach 2: Take two pointers A and B. Initialize both pointers to the head of the list. First move B to point to the nth node in the list. Next, move both pointers A and B together. Terminate the process when B points to the last node. At termination. A points to the nth node from the end of the linked list.  

2. What are  important types of linked lists.
  Singly Linked List,  Doubly Linked List, XOR-Linked List, and Circular Linked List.

3. Given a   circular linked list (singly-connected) and a pointer (head) to a node in the list , insert a node just before the head without fully traversing the list.

   Hint:  Insert a node after the head, switch values of head node and new node, move the head  to next

4. Give an algorithm to find if a linked list is circular or not.

5.  Give an algorithm to find  if a  linked list has a cycle/loop.
     Floyd's Cycle Detection Algorithm
     Some other solutions

6.  How to construct an efficient doubly-connected linked list.

     Hint: XOR-Linked List

7.  Given a forked linked list, find the point of fork.

                              G---H---I
                                           |
      A---B---C---D---E---F---J---K---L--M
                             
     In the above forked linked list, we see that J is the forking point.

8. Code to simulate Josephus problem.

    Hint: Use circular linked list.

Interesting String Problems

 1.  Longest common substring problem 

    Variant 1:      Longest common substring in two given strings. Let "aabcdefgh"  and  "ccbcdefff"  be two strings. Then the longest common substring is "bcdef".

    Variant  2: Longest repeating substring in a given string.  Let  "aabcdefghccbcdefff " be a string. Then, the longest repeating substring is again "bcdef".


2.   Longest palindromic substring

Given a string, the problem is to find the longest substring which is also a palindrome. Let "bananas" be a string, then the substring "anana" is the longest substring that is palindrome.

3.   String search / matching problem

Given a string S1 of size n and a string S2 of size m, where m < n, find the first or all the occurrences of string S2 in S1.  There are many algorithms to solve this problem in linear time. The most famous being Kunth-Morris-Pratt algorithm.

4. Strings  Anagram

Given two strings S1 and S2, find whether they are Anagram.

A string S1 is an Anagram of String S2 if S1 is formed by rearranging the letters of S2.

5. Reverse a string in place, e.g., "I LIKE IPHONE" -> "ENOHPI EKIL I".

6. Reverse characters of each word of string, e.g.,  "I LIKE IPHONE" -> "I EKIL ENOHPI".

7. Reverse a string such that the position of the words are reversed but the characters of the words are not reversed, e.g., "I LIKE IPHONE" -> "IPHONE LIKE I".

8. Find all the palindromes in a given string

Defintions, Data Structures, and Algorithms used for solving above problems

1.  Defining Substring, Subsequence, Prefix, and Suffix
2.  Defining Palindrome
3.  Difference between Substring and Subsequence
4.  Generalized Suffix Tree
5.  Dynamic Programming (DP)
      5.1   DP Practice Problems
      5.2   Tutorial on DP
      5.3   MIT Lecture Video

In-Place Interleaving of Two Strings

Question

 Given a string, e.g., str=substr1substr2, interleave the substrings substr1 and substr2 in-place. 
 This can be extended to three strings or more. For three strings str = substr1substr2substr3, interleave the sub strings to generate a unified string.

 Example

For two strings:
Given str = A1 A2 A3 B1 B2 B3, interleave  substr1= A1 A2 A3 and substr2= B1 B2 B3 in-place to obtain A1 B1 A2 B2 A3 B3.

For three strings:
A1 A2 A3 b1 B2 B3 C1 C2 C3, interleave substr1 = A1 A2 A3, substr2 = B1 B2 B3, and substr3 = C1 C2 C3, interleave to get A1 B1 C1 A2 B2 C2 A3 B3 C3

Solution Idea

 

 

 

Java Code

public class SeqInterleave {

    /**

     * @param args

     */

   

    public static void main(String[] args) {

        

        /*

         * Input

         */

        String[] strIn = {"A1","A2","A3","A4","A5", "A6", "A7","B1", "B2", "B3", "B4", "B5", "B6", "B7"};

        

        

        /*

         * We assume that the elements in the array are valid

         * The size of the array is even

         * The size of each type is half of the total array length

         */

        SeqInterleave seqObj = new SeqInterleave();

        seqObj.interleave(strIn);

        seqObj.printOutput(strIn);

    }

   

   

    public void interleave(String[] strIn)

    {

        int stringHalfLen = strIn.length/2;

        

        //start swapping from A7
       // Loop 1

        for(int i = stringHalfLen-1, j = 0; i > 0 ; i--, j++)

        {

            int exStartPoint = i;

            int exEndPoint = stringHalfLen+j;

          
           // Loop2

            for(int k = exStartPoint ; k <= exEndPoint; k=k+2)

            {

                String temp = strIn[k];

                strIn[k] = strIn[k+1];

                strIn[k+1]= temp;

            }

            printOutput(strIn);

            System.out.println();

        }

        

    }

   

    public void printOutput(String[] strIn)

    {

        for(int i = 0; i < strIn.length ; i++)

            System.out.print(strIn[i]+" ");

    }

}

Input

A1 A2 A3 A4 A5 A6 A7 B1 B2 B3 B4 B5 B6 B7

 

Execution Output Sequence

A1 A2 A3 A4 A5 A6 B1 A7 B2 B3 B4 B5 B6 B7
A1 A2 A3 A4 A5 B1 A6 B2 A7 B3 B4 B5 B6 B7
A1 A2 A3 A4 B1 A5 B2 A6 B3 A7 B4 B5 B6 B7
A1 A2 A3 B1 A4 B2 A5 B3 A6 B4 A7 B5 B6 B7
A1 A2 B1 A3 B2 A4 B3 A5 B4 A6 B5 A7 B6 B7
A1 B1 A2 B2 A3 B3 A4 B4 A5 B5 A6 B6 A7 B7 

 

Complexity

For an array of length n, it has  O( n^2) time complexity.

Loop1 has  ((n/2)-1) iterations.

In each iteration i, we perform i swappings. In each swap, two elements of the array are used.