学海无涯

Insersection of Two Linked Lists

Posted on

Write a program to find the node at which the intersection of two singly linked lists begins.

 

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

 

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {        if (headA == null || headB == null) {return null;}
int lenA = getLen(headA);        int lenB = getLen(headB);        while (headA != null && headB != null) {        if (lenA > lenB) {        headA = headA.next;        lenA -= 1;        } else if (lenA < lenB) {        headB = headB.next;        lenB -= 1;        } else {        if (headA == headB) {        return headA;        }         headA = headA.next;        headB = headB.next;        lenA -= 1;        lenB -= 1;        }        }
return null;    }    public static int getLen(ListNode head) {    int len = 0;    while (head != null) {    len += 1;    head = head.next;    }    return len;    }


This problem is about traversing the linked list. Use the length of the list to mark the progress. My way of solution is a common one and the complexity is O(m+n).

Semaphores in Java

Posted on

 

References:

java-util-concurrency-semaphore

Semaphores have two usages:

  1. Guard the critical section and resources, to provide the mutual exclusion
  2. Send signals between two processes or threads

In the constructor, one can specify the fairness settings. Fairness is each time when a permit is released, the longest thread waiting in queue will acquire it. This can guarantee no thread needs to wait in the queue all the time. Therefore, starvation can be prevented in this way.

Linked List Cycle

Posted on

 

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

public class Solution {

public boolean hasCycle(ListNode head) {

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


A nice trick about Linked List is the slow and fast pointers/runners. If both runners start at the same nodes, sooner or later they’ll meet at a specific node with the existence of the cycle. If there’s no cycle, then the fast runner will encounter null finally. Since fast.next also needs to visit its own next node, so the null check is also needed for fast.next. This case must be included in the condition of ending while-loop.

Be careful about the edge cases. The null list or single node list request the specific null check. Also, when there are only two nodes in the list, the slow and fast runners start at the same node. So the condition check of slow == fast is put after they both go forward their steps (I used “slow = head; fast = head”, if using “slow = head; fast = head.next”, will be different).

 

BST to Greater Tree

Posted on Updated on

/*
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is 
changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13
*/

public class convertBST{
   static int sum = 0; // trace the sum of previous nodes
   public static TreeNode convertBST(TreeNode root) {
      if (root == null) {return null;}
      convert(root);
      return root;
    }
    public static void convert(TreeNode node) {
       if (node == null) {return;}
       convert(node.right);
       sum += node.val;
       node.val = sum;
       convert(node.left);

    }

   public static void main(String[] args) {

   }
}

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

In a BST, every node only needs to add the values of nodes on the right. So use recursion to find the rightmost node first. Use a variable “sum” to store the accumulating values. Each time use “sum” to replace current value. Nothing to be accumulated to the left side.

Convert Sorted Array to Binary Search Tree

Posted on

Given an array where elements are sorted in ascending order, convert 
it to a height balanced BST.
1 2 3 4 5 6 7 8 

         4
      2     6  
     1      3      5    7
                8

1 2 3 4 5 6 7 8 9 10 11 12 
         
         6
      3     9
    1   4      7       11
       2    5   8 10  12

*/

public class sortedArrayToBST{
   public static TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {return null;}

        int low = 0;
        int high = nums.length - 1;
       
        return helper(nums, low, high);
    }

    public static TreeNode helper(int[] nums, int l, int h) {
       if (l > h) {return null;}
       int m = (l + h) / 2;
       TreeNode root = new TreeNode (nums[m]);
    
       root.left = helper(nums, l, m - 1);
       root.right = helper(nums, m + 1, h);
       return root;
    }


   public static void main(String[] args) {
      int[] a = new int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
      TreeNode root = sortedArrayToBST(a);
   }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
 }
First, one must be clear about what is a height balanced BST.
1. BST must satisfy value of left child <= root value <= value of right child.
2. Height balance means the height difference between the left subtree and right subtree can not be more than 1.
Therefore, mid value must be root from the start. Each time within each half in the array, always the mid point is root of the subtree. For tree problems, recursion is the best solution. So the same helper method can be applied to subtrees on and on. For the left half, the high boundary changes. Calculate new middle, and apply (middle – 1) as the new high boundary. For the right half, the low boundary changes. Calculate new middle, and apply (middle + 1) as the new low boundary.

Two Sum

Posted on

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
public static int[] twoSum(int[] nums, int target) {
    if (nums == null) {return null;}

    /* the size of the result int[] is fixed: 2. Because assumed only one group of solution */
    int[] result = new int[2];

    /* HashMap: key is the element, value is the index of the element in array nums */
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {
       if (map.containsKey(target - nums[i])) {
          result[1] = i;
          result[0] = map.get(target - nums[i]);
          return result;
       } 
       map.put(nums[i], i);
    }

    return result;

   }

The tricky part is that the size of the result int[] is fixed. Because the problem assumes only one solution exists. The size must be 2. So no need to use ArrayList and once find one pair, can just return the result.

Use HashMap with element as the key and index in the array as the value. Be careful about the sequence of the index in the result array. The difference element should exist already so its index should be 0 in result int[].

Intersection of two arrays II

Posted on

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2, 2].

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.
public static int[] intersect(int[] nums1, int[] nums2) {
       
       if (nums1 == null || nums2 == null) {
          return null;
       }
       /* use Hashmap to store the first array, element as the key, the number of existence as the value */
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums1.length; i++) {
       if (map.containsKey(nums1[i])) {
          map.put(nums1[i], map.get(nums1[i]) + 1);
       } else {
          map.put(nums1[i], 1);
       }
    }

    /* use ArrayList to generate the result */
    List<Integer> list = new ArrayList<Integer>();
    for (int j = 0; j < nums2.length; j++) {
       if (map.containsKey(nums2[j]) && (map.get(nums2[j]) > 0)) {
          list.add(nums2[j]);
          map.put(nums2[j], map.get(nums2[j]) - 1);
       }
    }

    /* convert ArrayList format of result into int[] */
    int[] result = new int[list.size()];
    for (int k = 0; k < list.size(); k++) {
       result[k] = list.get(k);
    }
    return result;
   }

The difference between this problem and Intersection of two arrays (I) is about the duplicate common elements. So cannot use the Set class to store elements anymore.

Here I used HashMap with the element as the key and the times of appearance as the value. Then the value can control how many times this key should be added into the final result integer array. The complexity is still O(m+n).