Finding loop in a singly linked-list

You can detect it by simply running two pointers through the list.
Start the first pointer p1 on the first node and the second pointer p2 on the second node.

Advance the first pointer by one every time through the loop, advance the second pointer by two. If there is a loop, they will eventually point to the same node. If there’s no loop, you’ll eventually hit the end with the advance-by-two pointer.

Consider the following loop:

head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
                  ^                        |
                  |                        |
                  +------------------------+

Starting A at 1 and B at 2, they take on the following values:

p1   p2
=    =
1    2
2    4
3    6
4    8
5    4
6    6

Because they’re equal, and P2 should always be beyond p1 in a non-looping list (because it’s advancing by two as opposed to the advance-by-one behavior of p1), it means you’ve discovered a loop.

The pseudo-code will go something like this:

  • Start with hn(Head Node )of the linked list
  • If hn==null; return false; //empty list
  • if hn.next!=null
    • p1=hn; p2=hn;
    • While p2!=null loop
      • p1=p1.next//Advancing p1 by 1
      • if p2.next!=null
        • p2=p2.next.next//Advancing p2 by 2
        • else return false
      • if p1==p2
        • return true// Loop was found
    • return false// till now no loop was found

Once you know a node within the loop, there’s an O(n) guaranteed method to find the start of the loop.

Let’s return to the original position after you’ve found an element somewhere in the loop but you’re not sure where the start of the loop is.

                                 p1,p2 (this is where p1 and p2
                                 |               first met).
                                 v
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
                  ^                        |
                  |                        |
                  +------------------------+

This is the process to follow:

  • First, advance p2 and set the loopsize to 1.
  • Second, while p1 and p2 are not equal, continue to advance p2, increasing the loopsize each time. That gives the size of the loop, six in this case.
    If the loopsize ends up as 1, you know that you must already be at the start of the loop, so simply return A as the start, and skip the rest of the steps below.
  • Third, simply set both p1 and p2 to the first element then advance p2 exactly loopsize times (to the 7 in this case). This gives two pointers that are different by the size of the loop.
  • Lastly, while p1 and p2 are not equal, you advance them together. Since they remain exactly loopsize elements apart from each other at all times, p1 will enter the loop at exactly the same time as p2 returns to the start of the loop. You can see that with the following walk through:
    • loopsize is evaluated as 6
    • set both p1 and p2 to 1
    • advance p2 by loopsize elements to 7
    • 1 and 7 aren’t equal so advance both
    • 2 and 8 aren’t equal so advance both
    • 3 and 3 are equal so that is your loop start

Now, since each those operations are O(n) and performed sequentially, the whole thing is O(n).

Source

Algorithm Name: Floyd–Warshall algorithm

Posted in Algorithms, Interview Puzzles | Tagged , , , | Leave a comment

File Sorting based on parameters

Many times our file directories are full of files that we may like to be sorted in some particular manner. Below is the code to sort the files as per the following ways:

  • Month Sorting
  • Alphabetic Sorting
  • Music Album Sorting
  • Extension Sorting
import java.io.File;

import java.text.ParseException;
import java.text.SimpleDateFormat;

import java.util.Date;
import java.util.Scanner;
import java.util.TreeSet;

import org.blinkenlights.jid3.ID3Tag;
import org.blinkenlights.jid3.MP3File;
import org.blinkenlights.jid3.MediaFile;
import org.blinkenlights.jid3.v2.ID3V2_3_0Tag;

public class FileSorter {
    private Date getLastModified(File file) {
        return new Date(file.lastModified());
    }

    private String convert(Date file) throws ParseException {
        return new SimpleDateFormat("yyyy-MM").format(file.getTime());
    }

    public static void main(String[] args) {
        FileSorter p = new FileSorter();
        Scanner in = new Scanner(System.in);
        System.out.println("Please enter the folder path that you want sorted: ");
        String filePath = in.nextLine();
        System.out.println("Please enter what kind of sorting you want??");
        System.out.println("   1. Month Sorting");
        System.out.println("   2. Alphabetic Sorting");
        System.out.println("   3. Music Album Sorting");
        System.out.println("   5. Extension Sorting");
        try {
            int s = Integer.parseInt(in.nextLine());
            switch (s) {
            case 1:
                p.startSort(filePath);
                break;
            case 2:
                p.alphaSort(filePath);
                break;
            case 3:
                p.startMusicSort(filePath);
                break;
            case 5:
                p.extnSort(filePath);
                break;
            default:
                System.out.println("Invalid Option");
                break;
            }

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public String getRange(String path) {
        String ret_String = "";
        for (int i = 97; i <= 122; i++) { if ((int) path.toLowerCase().charAt(0) >= i && (int) path.toLowerCase().charAt(0) <= (i + 3)) { ret_String = ((char) i + "-" + ((char) (i + 3))); break; } else if ((int) path.toLowerCase().charAt(0) >= 32 && (int) path.toLowerCase().charAt(0) <= 64) {
                ret_String = ("#0-9");
                break;
            } else {
                i += 3;
            }
        }
        return ret_String;
    }

    public void startSort(String filePath) throws Exception, ParseException {

        File dir = new File(filePath);
        File folder = null;
        String newFilePath = null;
        TreeSet ts = new TreeSet();

        if (dir.isDirectory()) {

            for (File file : dir.listFiles()) {
                newFilePath = convert(getLastModified(file));
                ts.add(newFilePath);
            }

            for (String o : ts) {
                folder = new File(filePath + "\\" + o);
                folder.mkdirs();

                for (File file : dir.listFiles()) {
                    newFilePath = convert(getLastModified(file));
                    if (newFilePath.equals(o)) {
                        if (file.isFile()) {
                            file.renameTo(new File(filePath + "\\" + o + "\\" + file.getName()));
                        }
                    }
                }
            }
        }
    }

    public void alphaSort(String filePath) throws Exception, ParseException {

        File dir = new File(filePath);
        File folder = null;
        String newFilePath = null;
        TreeSet ts = new TreeSet();

        if (dir.isDirectory()) {

            for (File file : dir.listFiles()) {
                newFilePath = getRange(file.getName());
                ts.add(newFilePath);
            }

            for (String o : ts) {
                folder = new File(filePath + "\\" + o);
                folder.mkdirs();

                for (File file : dir.listFiles()) {
                    newFilePath = getRange(file.getName());
                    if (newFilePath.equals(o)) {
                        if (file.isFile()) {
                            file.renameTo(new File(filePath + "\\" + o + "\\" + file.getName()));
                        }
                    }
                }
            }
        }
    }

    public void extnSort(String filePath) throws Exception, ParseException {

        File dir = new File(filePath);
        File folder = null;
        String newFilePath = null;
        TreeSet ts = new TreeSet();

        if (dir.isDirectory()) {

            for (File file : dir.listFiles()) {
                if (file.getName().lastIndexOf(".") > 0) {
                    newFilePath =
                        (file.getName().substring(file.getName().lastIndexOf(".") + 1,
                                                  file.getName().length())).toLowerCase();
                } else {
                    continue;
                }
                ts.add(newFilePath);
            }

            for (String o : ts) {
                folder = new File(filePath + "\\" + o);
                folder.mkdirs();

                for (File file : dir.listFiles()) {
                    if (file.getName().lastIndexOf(".") > 0) {
                        newFilePath =
                            (file.getName().substring(file.getName().lastIndexOf(".") + 1,
                                                      file.getName().length())).toLowerCase();
                    } else {
                        continue;
                    }

                    if (newFilePath.equals(o)) {
                        if (file.isFile()) {
                            file.renameTo(new File(filePath + "\\" + o + "\\" + file.getName()));
                        }
                    }
                }
            }
        }
    }

    public void startMusicSort(String filePath) throws Exception, ParseException {

        File dir = new File(filePath);
        File folder = null;
        String newFilePath = null;
        TreeSet ts = new TreeSet();

        if (dir.isDirectory()) {

            for (File file : dir.listFiles()) {
                newFilePath = (getAlbumName(file));
                ts.add(newFilePath);
            }

            for (String o : ts) {
                folder = new File(filePath + "\\" + o);
                folder.mkdirs();

                for (File file : dir.listFiles()) {
                    newFilePath = (getAlbumName(file));
                    if (newFilePath.equals(o)) {
                        if (file.isFile()) {
                            file.renameTo(new File(filePath + "\\" + o + "\\" + file.getName()));
                        }
                    }
                }
            }
        }
    }

    private String getAlbumName(File oSourceFile) {
        MediaFile oMediaFile = new MP3File(oSourceFile);
        ID3Tag[] aoID3Tag;
        try {
            aoID3Tag = oMediaFile.getTags();
            for (int i = 0; i < aoID3Tag.length; i++) {
                if (aoID3Tag[i] instanceof ID3V2_3_0Tag) {
                    ID3V2_3_0Tag oID3V2_3_0Tag = (ID3V2_3_0Tag) aoID3Tag[i];
                    try {
                        return ("".equals(oID3V2_3_0Tag.getAlbum().trim()) ? "Misc" :
                                oID3V2_3_0Tag.getAlbum().replaceAll("\"", "")); // reads TYER frame
                    } catch (Exception e) {
                        e.getStackTrace();
                    }
                }
            }
        } catch (Exception e) {
            e.getStackTrace();
        }
        return "Misc";
    }

    public String toString() {
        return super.toString();
    }
}

Libraries can be found at:

Posted in Java, Open Source | Tagged , , , , , , | Leave a comment

Code to Encrypt Folder Structure Completely

Below is the code to encrypt/decrypt complete folder structure in java

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;

import javax.crypto.Cipher;
import javax.crypto.CipherInputStream;
import javax.crypto.CipherOutputStream;
import javax.crypto.spec.SecretKeySpec;

public class CryptoX {
    static String pwd = "";

    private static String compressPassword(String pass) {
        char[] tmp = new char[8];
        if (pass.length() > 8) {
            for (int i = 0; i < pass.toCharArray().length; i++) {
                tmp[i % 7] += pass.toCharArray()[i];
            }
            pass = new String(tmp);
        }
        return pass;
    }

    public void beginEncrypt(String in, String pass, String outputPath) throws Exception {
        try {
            pass = compressPassword(pass);
            processEncrypt(in, outputPath, (pass));
        } catch (IOException e) {
            e.printStackTrace();
            throw e;
        }
    }

    private String encryptName(String str) {
        String encrypted = "";
        int keyLength = pwd.length();
        for (int i = 0; i < str.length(); i++) { int c = str.charAt(i); if (Character.isUpperCase(c)) { // 26 letters of the alphabet so mod by 26 c = c + (keyLength % 26); if (c > 'Z')
                    c = c - 26;
            } else if (Character.isLowerCase(c)) {
                c = c + (keyLength % 26);
                if (c > 'z')
                    c = c - 26;
            }
            encrypted += (char) c;
        }
        return encrypted;
    }

    private void encrypt(File fileIn, File fileOut, String pass) throws Exception {
        fileIn.setReadable(true);
        fileOut.setWritable(true);
        fileOut.setReadable(true);
        FileInputStream fis = new FileInputStream(fileIn);
        FileOutputStream fos = new FileOutputStream(fileOut);
        byte k[] = pass.getBytes();
        final String algo = "DES/ECB/PKCS5Padding";
        SecretKeySpec key = new SecretKeySpec(k, algo.split("/")[0]);
        Cipher encrypt = Cipher.getInstance(algo);
        encrypt.init(Cipher.ENCRYPT_MODE, key);
        CipherOutputStream cout = new CipherOutputStream(fos, encrypt);

        byte[] buf = new byte[1024];
        int read;
        while ((read = fis.read(buf)) != -1) {
            cout.write(buf, 0, read);
            //            System.out.print(".");

        }

        fis.close();
        cout.flush();
        cout.close();
    }

    private void processEncrypt(String in, String out, String pass) throws IOException {

        File fin = new File(in);
        File fout = new File(out);
        fout.setWritable(true);
        fout.setReadable(true);
        fin.setReadable(true);

        if (fin.getName().startsWith(".")) {
            return;
        }

        if (!fout.exists() && fin.isDirectory() && !fin.getName().equals("Encrypt")) {
            fout.mkdirs();
            fout.setWritable(true);
        } else if (!fin.isDirectory()) {
            try {
                encrypt(fin, new File(out), pass);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        if (fin.isDirectory() && !fin.getName().equals("Encrypt")) {
            for (int i = 0; i < fin.list().length; i++) {
                processEncrypt(in + "/" + fin.list()[i], out + "/" + encryptName(fin.list()[i]), pass);
            }
        }
    }

    public void beginDecrypt(String in, String pass, String output) throws Exception {
        try {
            processDecrypt(in, output, compressPassword(pass));
        } catch (Exception e) {
            e.printStackTrace();
            throw e;
        }
    }

    private String decryptName(String str) {
        String decrypted = "";

        int keyLength = pwd.length();
        for (int i = 0; i < str.length(); i++) {
            int c = str.charAt(i);
            if (Character.isUpperCase(c)) {
                c = c - (keyLength % 26);
                if (c < 'A')
                    c = c + 26;
            } else if (Character.isLowerCase(c)) {
                c = c - (keyLength % 26);
                if (c < 'a')
                    c = c + 26;
            }
            decrypted += (char) c;
        }
        return decrypted;
    }

    private void processDecrypt(String in, String out, String pass) throws Exception {

        File fin = new File(in);
        File fout = new File(out);

        if (!fin.exists()) {
            return;
        }

        if (fin.getName().startsWith(".")) {
            return;
        }

        if (!fout.exists() && fin.isDirectory()) {
            fout.mkdirs();
            fout.setWritable(true);
        } else if (!fin.isDirectory()) {
            try {
                // out = out.substring(0, out.length()
                // - encryptName(".enc").length());

                decrypt(fin, new File(out), pass);

            } catch (Exception e) {
                e.printStackTrace();
                throw e;
            }
        }

        if (fin.isDirectory()) {
            for (int i = 0; i < fin.list().length; i++) {
                processDecrypt(in + "/" + fin.list()[i], out + "/" + decryptName(fin.list()[i]), pass);
            }
        }
    }

    private void decrypt(File fileIn, File fileOut, String pass) throws Exception {
        fileOut.setWritable(true);
        fileOut.setReadable(true);
        fileIn.setReadable(true);
        final String algo = "DES/ECB/PKCS5Padding";
        FileInputStream fis = new FileInputStream(fileIn);
        FileOutputStream fos = new FileOutputStream(fileOut);
        byte k[] = pass.getBytes();
        SecretKeySpec key = new SecretKeySpec(k, algo.split("/")[0]);
        Cipher decrypt = Cipher.getInstance(algo);
        decrypt.init(Cipher.DECRYPT_MODE, key);
        CipherInputStream cin = new CipherInputStream(fis, decrypt);

        byte[] buf = new byte[1024];
        int read = 0;
        while ((read = cin.read(buf)) != -1) {
            fos.write(buf, 0, read);
        }
        cin.close();
        fos.flush();
        fos.close();
    }

    public CryptoX() {
        super();
    }
}

The Code takes 3 parameters:

  • in: String: input path of the folder that u want to encrypt
  • password: String: Used to encrypt/decrypt the files
  • output: String: Folder path in which u wish to publish the encrypted/decrypted files
Posted in Java | Tagged , , , , , , , | Leave a comment

Code to Download File from URL in Java

Below is the code to download the complete contents of a URL to your local hard drive.

//IMPORTS
import java.io.BufferedInputStream;
import java.io.ByteArrayOutputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.net.URL;
import java.io.File;
METHOD CODE
    private static void download(String url) throws IOException {

        String fileName="Path\\to\\File.extn";//The file that will be saved on your computer
        
        URL link = new URL(url); //The file that you want to download

        //Code to download
        InputStream in = new BufferedInputStream(link.openStream());
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        byte[] buf = new byte[2048];
        int n = 0;
        while (-1 != (n = in.read(buf))) {
            out.write(buf, 0, n);
            System.out.print("|");//Progress Indicator
        }
        out.close();
        in.close();
        byte[] response = out.toByteArray();

        FileOutputStream fos = new FileOutputStream(fileName);
        fos.write(response);
        fos.close();
        //End download code
        System.out.println("#");

    }

Note: For large file downloads, the JVM may throw OutOfMemoryError

Posted in Java | Tagged , , , , , , | Leave a comment

Combinations of a String

Problem:
Write an algorithm to print all possible combinations of characters in a string.

Solution:
Since we need to generate combinations, we can start with a single character and then continue to add a character to combinations we have seen so far.

Let’s use “XYZ” as an example.

public void buildTree(String input, StringBuffer output, int k)
{
    for (int i = k; i < input.length(); i++)
    {
        output.append(input.charAt(i));
        buildTree(input, output, i + 1);
        output.deleteCharAt(output.length() - 1);
    }
} 

public static void main(String[] args){
     buildTree("XYZ", new StringBuffer(), 0);
}

Dry Run just to give an idea:

X–>Y–>Z
–>Z–>Y

Y–>X–>Z
–>Z–>X

Z–>Y–>X
–>X–>Y

Posted in Interview Puzzles | Tagged , , , , , | 1 Comment

Gold for 7 Days of Work Puzzle

Problem Statement:

You’ve got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?
(Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day)

Answer

The trick is not to try and how to cut in such a way to make 7 equal pieces but rather to make transactions with the worker. Make two cuts on the gold bar such that you have the following sizes of bars.

1/7, 2/7 and 4/7.

Day Pay Take Back Total Paid Amount Balance Amount
1 1/7 N/A 1/7 2/7, 4/7
2 2/7 1/7 2/7 1/7, 4/7
3 1/7 N/A 3/7 4/7
4 4/7 1/7, 2/7 4/7 2/7, 1/7
5 1/7 N/A 5/7 2/7
6 2/7 1/7 6/7 1/7
7 1/7 N/A 7/7 N/A
Posted in Interview Puzzles | Tagged , , | Leave a comment