50 DSA-Questions: #23, #24, #25

#23. Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and decoded back to the original list of strings.

public class Exercise23 {
    private static final String[] INPUT = {"Gina89", "loves_", "Pluto"};
    private static final String FIRST_SEP = "::";
    private static final String WORD_SEP = "#";
    private static final String INSIDE_SEP = "=";

    private String encode() {
        // format NR_CUVINTE::NR_CHAR=STR#NR_CHAR=STR#.....
        StringBuilder code = new StringBuilder(INPUT.length + FIRST_SEP);
        for (String word : INPUT) {
            code.append(word.length()).append(INSIDE_SEP).append(word).append(WORD_SEP);
        }
        return code.toString();
    }

    private String[] decode(String coded) {
        int numberOfWords = Integer.parseInt(coded.substring(0, coded.indexOf(FIRST_SEP)));
        String result[] = new String[numberOfWords];
        String splitCode[] = coded.substring(coded.indexOf(FIRST_SEP) + FIRST_SEP.length()).split(WORD_SEP);

        int i = 0;
        for (String code : splitCode) {
            result[i++] = code.substring(code.indexOf(INSIDE_SEP)+1);
        }

        return result;
    }

    private void solve() {
        String coded = encode();
        System.out.println(coded);

        String[] result = decode(coded);
        for (String res : result) {
            System.out.print(res + " ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        new Exercise23().solve();
    }
}

#24. Reverse Linked Lists

Given the head of a singly linked list, reverse the list, and return the reversed list.

public class Exercise24 {
    private static final int[] elements = {1,2,3,4,5,6};

    private void reverse(Node head) {
        Node.printList(head);
        Stack<Integer> stack = new Stack<>();
        while (head!= null) {
            stack.push(head.getData());
            head = head.getNext();
        }

        Node result = stack.empty() ? new Node() : new Node(stack.pop());
        Node node = result;
        while (!stack.empty()) {
            Node newNode = new Node(stack.pop());
            node.setNext(newNode);
            node = newNode;
        }

        Node.printList(result);
        // O(n) spatial (stiva + rezultat)
    }

    private void reverseinPlace(Node head) {
        Stack<Node> stack = new Stack<>();
        Node p1 = head, p2 = head;

        while (p2 != null && p2.getNext() != null) {
            stack.push(p1);
            p1 = p1.getNext(); // pas 1
            p2 = p2.getNext().getNext(); // pas 2, ajunge la mijloc
        }

        boolean odd = p2 != null && p2.getNext() == null;
        if (odd) {
            p1 = p1.getNext();
        }

        while (p1 != null) {
            swapData(p1, stack.pop());
            p1 = p1.getNext();
        }

        Node.printList(head);
        // in place
    }

    private void swapData(Node pluto, Node jupiter) {
        Integer data = pluto.getData();
        pluto.setData(jupiter.getData());
        jupiter.setData(data);
    }

    public static void main(String args[]) {
        Node head = Node.buildFrom(elements);

        new Exercise24().reverse(head);

        new Exercise24().reverseinPlace(head);
    }
}

#25. Linked List Cycle

Given the head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Return true if there is a cycle in the linked list. Otherwise, return false.

public class Exercise25 {
    private static final int[] elements = {1,2,3,4,5,6,7,8};

    private void solve(Node head) {
        Node p1 = head, p2 = head;
        while (p1.getNext() != null &&  p2.getNext() != null && p2.getNext().getNext() != null) {
            p1 = p1.getNext(); // 1 step
            if (p1 == null) {
                System.out.println("Linear");
                return;
            }

            p2 = p2.getNext();
            if (p2 == null) {
                System.out.println("Linear");
                return;
            } else {
                p2 = p2.getNext(); // 2 steps
            }

            if (p1 == p2) {
                System.out.println("Has a cycle!");
                return;
            }
        }
        System.out.println("Linear");
    }

    public static void main(String args []) {
        new Exercise25().solve(buildLinearList());
        new Exercise25().solve(buildFirstCircularList());
        new Exercise25().solve(buildSecondCircularList());
        new Exercise25().solve(buildThirdCircularList());
    }

    private static Node buildLinearList() {
        return Node.buildFrom(elements);
    }

    private static Node buildFirstCircularList() {
        Node node = Node.buildFrom(elements);
        node.getNext().getNext().getNext().setNext(node.getNext()); // 4 -> 2
        return node;
    }

    private static Node buildSecondCircularList() {
        Node node = Node.buildFrom(elements);
        node.getNext().getNext().getNext().getNext().setNext(node.getNext().getNext().getNext()); // 5 -> 4
        return node;
    }

    private static Node buildThirdCircularList() {
        Node node = Node.buildFrom(elements);
        node.getNext().getNext().getNext().getNext().setNext(node); // 5 -> 1
        return node;
    }
}