LeetCode - Maximum Length of a Concatenated String with Unique Characters - Day 11 (1/11/2020)

Preface

I have never seen the question using bit-manipulation to manage characters.

This question is from the question list sorted by Microsoft Interview Question.

Maximum Length of a Concatenated String with Unique Characters

Question

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which has unique characters.

Return the maximum possible length of s.

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Example 3:

Input: a rr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

Constraints:

1. 1 <= arr.length <= 16
2. 1 <= arr[i].length <= 26
3. arr[i] contains only lower case English letters.

Solution

1. Initial the result res to include the case of an empty string "". res include all possible combinations we find during we iterate the input.

2. Iterate the input strings, but skip the word that has duplicate characters. The examples are kind of misleading, but the input string can have duplicate characters, no need to considerate these strings.

3. For each string, we check if it's a conflict with the combination that we found. If they have an intersection of characters, we skip it. If not, we append this new combination to the result.

4. return the maximum length from all combinations.

public int maxLength(List<String> arr) {
    // Create the list of integer that stores strings.
    List<Integer> dp = new ArrayList<>();
    dp.add(0);
    int res = 0;
    for (String s: arr) {
        int a = 0, dup = 0;
        for (char c: s.toCharArray()) {
            // Check one string has the duplicate characters.
            dup |= a & (1 << (c - 'a'));
            // Represent the length of the string by using bit-operation.
            a |= 1 << (c - 'a');
        }
        // If there are duplicate characters in a string, then skip that string.
        if (dup > 0) {
            continue;
        }
        // Check two strings has duplicate characters. If so, skip that combination.
        // Otherwise, add two and get max length of the concatenated string.
        for (int i = dp.size() - 1; i >= 0; --i) {
            if ((dp.get(i) & a) > 0) continue;
            dp.add(dp.get(i) | a);
            res = Math.max(res, Integer.bitCount(dp.get(i) | a));
        }
    }
    return res;
}

LeetCode - Preface - Day9

Came back to Seattle

Finally, I came back to Seattle. I was so sleepy because of the jetlag, but I need to go to classes.

In addition, I received the email from Microsoft that I will move forward to a first-round interview for security engineer position.

So, I have decided to focus on solving questions showing up on Microsoft interview.

LeetCode - Linked List Cycle II - Day5 (1/5/2020)

Linked List Cycle II

Question

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Solution

This is the question we can use "Floyd's Tortoise and Hare".

private ListNode getIntersection(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return fast;
        }
    }
    return null;
}

public ListNode detectCycle(ListNode head) {
    if (head == null) {
        return null;
    }

    ListNode intersect = getIntersection(head);
    if (intersect == null) {
        return null;
    }

    ListNode ptr1 = head;
    ListNode ptr2 = intersect;
    while (ptr1 != ptr2) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
    }

    return ptr1;
}

Time complexity

The worst case runtime is O(n) since there are two cases that list has no cycle and list has a cycle.

Space complexity

O(1).

LeetCode - Linked List Cycle - Day5 (1/5/2020)

Linked List Cycle

Question

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Solution

This is also the question uses two pointers.

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

Time complexity

The worst case runtime is O(n) since there are two cases that list has no cycle and list has a cycle.

Space complexity

O(1).

LeetCode - Merge two sorted lists - Day5 (1/5/2020)

Merge two sorted lists

Question

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solution

My idea is to use sort values inside both list nodes by using priority queue and re-input them to new list node.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    ListNode res = new ListNode(0);
    ListNode head = res;

    while (l1 != null) {
        pq.offer(l1.val);
        l1 = l1.next;
    }

    while (l2 != null) {
        pq.offer(l2.val);
        l2 = l2.next;
    }

    while (!pq.isEmpty()) {
        res.next = new ListNode(pq.poll());
        res = res.next;
    }

    return head.next;
}

Time complexity

O*1. n is the length of l1 and m is the length of l2. Remove n+m times from the priority queue.

Space complexity

O(n+m).

*1:n+m)log(n+m

LeetCode - Remove Nth Node From End of List - Day5 (1/5/2020)

Remove Nth Node From End of List

Question

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution

I solved this question by using two pointers that are slow and fast. It is much easier to see this image from the solution page.

In addition, it is important for this question to set a dummy head in front of the head since a dummy head makes it easy to mange when we need to remove 1st node.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode slow = dummyHead;
    ListNode fast = dummyHead;
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return dummyHead.next;
}

Time complexity

O(L). L is the number of nodes in the head.

Space complexity

O(1) since we manage head itself.

LeetCode - Flatten a Multilevel Doubly Linked List - Day5 (1/5/2020)

Flatten a Multilevel Doubly Linked List

Question

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation:

The input multilevel linked list is as follows:

  1---2---NULL
  |
  3---NULL

Example 3:

Input: head = []
Output: []

Constraints:

• Number of Nodes will not exceed 1000.

• 1 <= Node.val <= 10⁵

Solution

To be honest, I couldn't come up with any idea to solve this problem. Also, I wondered which scenario that one would use such an awkward data structure.

The author said one fo the scenarios could be a simplified version of git branching. That makes sense. I wanna see how git branching system is implemented.

Maybe gitlab is good since it's OSS?

Approach 1: DFS by Recursion

Anyways, let's start solving this question. According to the solution, we can interpret this data structure as a binary tree string below.

Also, the process of flattening can be pre-order DFS (Depth-First Search) traversal.

So, let's think the chiled pointer as the left pointer in a binary tree and similarly, the next pointer as the right pointer in a binary tree.

Here it goes with the recursive DFS algorithm:

1. First of all, we define our recursive function as flattenDFS which takes two pointers as input and returns the pointer of tail in the flattened list. The curr pointer leads to the sub-list that we would like to flatten, and the prev pointer points to the element that should precede the curr element.

2. Within the recursion function, we first establish the double links between the prev and curr nodes, as in the pre-order DFS we take care fo the current state first before looking into the children.

3. Further in the function, we then go ahead to flatten the left subtree with the call of flattenDFS, which returns the tail element to the flattened sublist. Then with the tail element of the previous sublist, we then further flatten the right subtree, with the call of falttenDFS.

4. There are two additional important details that we should attend to, in order to obtain the correct result:

   • We should make a copy of the curr.next pointer before the first recursive call of flattenDFS), since the curr.next pointer might be altered within the function.

   • After we flatten the sublist pointed by the curr.child pointer, we should remove the child pointer since it is no longer needed in the final result.

5. Last by not the least, one would notice in the following implementation that we create a pseudoHead variable in the function. This is not absolutely necessary, but it would help us to make the solution more concise and elegant by reducing the null pointer checks (e.g. if prev == null). And with less branching tests, it certainly helps with the performance as well. Sometimes people might call it sentinel node. As one might have seen before, this is a useful trick that one could apply to many problems related with linked lists (e.g. LRU cache).

public Node flatten(Node head) {
    if (head == null) {
        return head;
    }

    Node pseudoHead = new Node(0, null, head, null);

    flattenDFS(pseudoHead, head);

    pseudoHead.next.prev = null;
    return pseudoHead.next;
}

public Node flattenDFS(Node prev, Node curr) {
    if (curr == null) {
        return prev;
    }
    curr.prev = prev;
    prev.next = curr;

    Node tempNext = curr.next;

    Node tail = flattenDFS(curr, curr.child);
    curr.child = null;

    return flattenDFS(tail, tempNext);
}

public class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
}

Approach 2

Use iteration.

public Node flatten(Node head) {
    if (head == null) return head;

    Node pseudoHead = new Node(0, null, head, null);
    Node curr, prev = pseudoHead;

    Deque<Node> stack = new ArrayDeque<>();
    stack.push(head);

    while (!stack.isEmpty()) {
      curr = stack.pop();
      prev.next = curr;
      curr.prev = prev;

      if (curr.next != null) stack.push(curr.next);
      if (curr.child != null) {
        stack.push(curr.child);
        // don't forget to remove all child pointers.
        curr.child = null;
      }
      prev = curr;
    }
    // detach the pseudo node from the result
    pseudoHead.next.prev = null;
    return pseudoHead.next;
  }