HOW TO ROOT (UNROOT) MOTO X

ROOT AN MOTO X

1. UNLOCK BOOT LOADER

    through moto x website

2. INSTALL TWPR

    download the lastest TWPR img for your phone.

    use

    adb reboot bootloader
    fastboot flash recovery recovery.img (rename img file to recovery.img)
 

3. INSTALL SUPERSU.ZIP

     reboot into bootloader
           hold vol down
           press power + vol down
           release power

     INSTALL
     UPDATE-SuperSU-Vx.xx.zip
   
4. OTHERS CREATE BACKUP

     You  TWPR backup folder is not visible in adb mode, but visible in fastboot mode

      USB OTG supported, but only to FAT32 format.

UNROOT MOTO X

OTA updates is not available in rooted devices. We have to unroot devices for kernel updates.

1. Get Stock Firmware

    We can download somewhere else, but it usually does not work. Head for moto x official website

    "RE-LOCK YOUR BOOTLOADER, FACTORY IMAGES FOR DEVELOPER EDITION DEVICES"

       https://motorola-global-portal.custhelp.com/app/standalone/bootloader/recovery-images

2. Flash Unzipped image using fastboot flash xxx xxx.img

fastboot flash partition gpt.bin
fastboot flash motoboot motoboot.img
fastboot reboot-bootloader
fastboot flash logo logo.bin
fastboot flash boot boot.img
fastboot flash recovery recovery.img
fastboot flash system system.img
fastboot flash modem NON-HLOS.bin
fastboot erase modemst1
fastboot erase modemst2
fastboot flash fsg fsg.mbn
fastboot reboot

[LeetCode] 29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

INT_MAX AND INT_MIN is not symmetric. Java abs(INT_MIN) returns INT_MIN as well. 1. Use long to solve it.

public class Solution {
    public int divide(int dividend, int divisor) {
        
        // 00100101
        // 00000011

        if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

        int res = 0;
        
        boolean sign  = dividend > 0 ^ divisor > 0 ? false : true;
        
        long dividendl = Math.abs((long)dividend), divisorl = Math.abs((long)divisor);
        
        while(dividendl >= divisorl){
            long k = divisorl;
            int q = 1;
            while((k << 1) <= dividendl){
                k <<= 1;
                q <<= 1;
            }
            res += q;
            dividendl -= k;
        }
        
        if(sign)
            return res;
        else
            return (res^-1) + 1;
    }
}

2. Handle the boarder condition, when INT_MIN as dividend: dividend - divisor, ++res will solve the boarder problem.

[LeetCode] 28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Subscribe to see which companies asked this question

1. Brute Force.

public class Solution {
    public int strStr(String haystack, String needle) {
        int lenH = haystack.length();
        int lenN = needle.length();
        
        if(0 == lenH){
            if(0 == lenN){
                return 0;
            }else{
                return -1;
            }
        }
        
        // error: i < lenH - lenN 
        for(int i = 0; i < lenH - lenN +1 ; ++i){
            boolean match = true;
            
            // error: indexing error multiple times
            for(int j = 0; j < lenN; ++j){
                if(haystack.charAt(i + j) != needle.charAt(j)){
                    match = false;
                    break;
                }
            }
            if(match){
                return i;
            }
        }
        return -1;
    }
}

2. KMP algorithm. Laters.

[LeetCode] 27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Show Hint 

public class Solution {
    public int removeElement(int[] nums, int val) {
    // Given input array nums = [3,2,2,3], val = 3
        int len = nums.length;
        int j = len -1;
        for(int i = len-1; i >= 0; --i){
            if(nums[i] == val){
                nums[i] = nums[j--];
            }
        }
        return j+1;
    }
}

[LeetCode] 26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

public class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(0 == len)
            return 0;
        
        int j = 1;
        
        for(int i = 1; i < len; ++i){
            if(nums[i-1] == nums[i])
                continue;
            else{
                nums[j] = nums[i];
                j++;
            }
        }
        
        return j;
        
    }
}

[LeetCode] 25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(null == head)
            return null;
            
        ListNode[] lArr = new ListNode[k];
        
        ListNode resPreHead = new ListNode(0);
        ListNode resIndex = resPreHead;
        
        ListNode preHead = new ListNode(0);
        preHead.next = head;
        // index pointer indexP
        ListNode indexP = new ListNode(0);
        indexP.next = preHead.next;
        
        while(null != indexP.next){
            ListNode kIndex = indexP;
            for(int i = 0; i < k; ++i){
                if(null == kIndex.next){
                    resIndex.next = indexP.next;
                    return resPreHead.next;
                }else{
                    lArr[i] = kIndex.next;
                    kIndex = kIndex.next;
                }
            }
            
            // assign indexP to next back
            indexP.next = kIndex.next;
            
            for(int i = k-1; i >=0; --i){
                resIndex.next = lArr[i];
                resIndex = resIndex.next;
                if(i == 0){
                    resIndex.next = null;
                }else{
                    resIndex.next = lArr[i-1];
                }
            }
        }
        
        return resPreHead.next;
        
    }
}

[LeetCode] 24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(null == head)
            return null;
        
        ListNode resPreHead = new ListNode(0);
        ListNode resIndex = resPreHead;
        
        ListNode preHead = new ListNode(0);
        preHead.next = head;
        ListNode index = preHead;
        
        while(null != index.next){
            ListNode a = index.next;
            ListNode b = null;
            if(null != a)
                b = a.next;
            if(null == b){
                index.next = null;
            }else{
                index.next = b.next;
            }
                
            if(null != b){
                resIndex.next = b;
                resIndex = b;
                resIndex.next = null;
            }
            
            if(null != a){
                resIndex.next = a;
                resIndex = a;
                resIndex.next = null;
            }
        }
        
        return resPreHead.next;
    }
}

[LeetCode] 23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Subscribe to see which companies asked this question

1. Use priority queue, organize ListNodes at head of all queues.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    class ListNodeComp implements Comparator{
        @Override
        // has to be public
        public int compare(ListNode a, ListNode b){
            return a.val - b.val;
        }
    }
    
    public ListNode mergeKLists(ListNode[] lists) {
        
        int k = lists.length;
        
        if(0 == k)
            return null;
            
        ListNode resPreHead = new ListNode(0);
        
        ListNode index = resPreHead;
        
        PriorityQueue pq = new PriorityQueue(k, new ListNodeComp());
        
        for(int i = 0; i < k; ++i){
            
            if(null != lists[i]){
                pq.add(lists[i]);
            }
            
        }
        
        while(null != pq.peek()){
            
            index.next = pq.poll();
            index = index.next;
            
            if(null != index.next){
                pq.add(index.next);
                // be safe
                index.next = null;
            }
            
        }
        
        // log(k)*n
        
        // k/2*(n/k)*2 = n
        
        // log(k) times 
        
        return resPreHead.next;
    }
}

[LeetCode] 22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Subscribe to see which companies asked this question

public class Solution {
    
    public void generateParenthesisAux(int n, int k, int i, char[] path, List res){
        if(0 == k){
            // no more left parenthesis
            for( int l = i; l < n*2; ++l){
                path[l] = ')';
            }
            res.add(new String(path));
            
        }else{
            path[i] = '(';
            generateParenthesisAux(n, k-1, i+1, path, res);
            if((n - k) * 2 > i){
                path[i] = ')';
                generateParenthesisAux(n, k, i+1, path, res);
            }
        }
        
        return;
        
    }
    
    public List generateParenthesis(int n) {
        ArrayList res = new ArrayList();
        generateParenthesisAux(n, n, 0, new char[2*n], res);
        return res;
    }
}

[LeetCode] 21. Merge Two Sorted Lists

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.

Subscribe to see which companies asked this question

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode resPreHead = new ListNode(0);
        
        ListNode index = resPreHead;
        
        while(null != l1 && null != l2){
            if(l1.val > l2.val){
                index.next = l2;
                l2 = l2.next;
            }else{
                index.next = l1;
                l1 = l1.next;
            }
            index = index.next;
            // be safe.
            index.next = null;
        }
        
        if (null == l1){
            index.next = l2;
        }else{
            index.next = l1;
        }
        
        return resPreHead.next;
    }
}

[LeetCode] 20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Subscribe to see which companies asked this question

public class Solution {
    public boolean isValid(String s) {
        
        int len = s.length();
        
        if(0 == len)
            return true;
        
        // can not use char in template
        // Use queue instead of stack at first ........, can't find the bug even.
        Stack pq = new Stack();

        /*
        pq.peek() == new Character('[') 
        OK.
        pq.peek() == '['
        '[' == pq.peek()
        null return can not compare with primitive char
        null pointer execption
        */
        

        for(int i = 0; i < len; ++i){
            
            char c = s.charAt(i);
            
            if(c =='(' || c =='{' || c =='['){
                pq.push(c);
            // The peek operation is different from queue to stack. We can peek empty queue, but not for stack. 
            }else if(pq.empty()){
                return false;
            }else{
                if(c == ')')
                    // use poll instead of peek here first, not working for input "]", empty queue, must peek before poll
                    if(pq.peek().charValue() == '(') pq.pop(); else return false;
                if(c == '}')
                    if(pq.peek().charValue() == '{') pq.pop(); else return false;
                if(c == ']')
                    if(pq.peek().charValue() == '[') pq.pop(); else return false;
            }
        }
        
        // shouldn't return true here. pq must be empty
        return pq.empty();
        
    }
}

[Leetcode] 19. Remove Nth Node From End of List

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

For 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.
Try to do this in one pass.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(null == head)
            return null;
        
        int k = n;
        
        ListNode preHead = new ListNode(0);
        
        preHead.next = head;
        
        ListNode i = preHead;
        ListNode j = head;
        
        while(null != j.next){
            j = j.next;
            if(k > 1){
                --k;
            }else{
                i = i.next;
            }
        }
        
        i.next = i.next.next;
        
        return preHead.next;
    }
}

[LeetCode] 18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

1. Call 3 sum.

public class Solution {
    
    public List> threeSum(int[] nums, int startI, int target) {
        int len = nums.length;
        List> ret = new ArrayList>();
        for(int i = startI; i < len; ++i){
            if(i > startI && nums[i-1] == nums[i])
                continue;
            int x = i+1;
            int y = len-1;
            while(x < y){
                int sum = nums[x] + nums[y] + nums[i];
                if(target == sum){
                    Integer[] res = {nums[x], nums[y], nums[i]};
                    ret.add(Arrays.asList(res));
                    --y;
                    while(y >= startI && nums[y+1] == nums[y]){
                        --y;
                    }
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }else if(target < sum){
                    --y;
                    while(y >= startI && nums[y+1] == nums[y]){
                        --y;
                    }
                }else{
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }
            }
        }
        
        return ret;
    }
    
    public List> fourSum(int[] nums, int target) {
        int len = nums.length;
        List> ret = new ArrayList>();
        Arrays.sort(nums);
        
        for( int i = 0; i < len -3; ++i){
            if(i > 0 && nums[i-1] == nums[i])
                continue;
            int j = i+1;
            int threeSumTarget = target - nums[i];
            List> resThree = threeSum(nums, j, threeSumTarget);
            
            for(List l : resThree){
                ArrayList t = new ArrayList(l);
                t.add(nums[i]);
                Collections.sort(t);
                ret.add(t);
            }
        }
        
        return ret;
    }
}

2. Build K Sum

public class Solution {
    
    public List> kSum(int[] nums, int startI, int target, int k) {
        
        int len = nums.length;
        
        List> ret = new ArrayList>();
        
        //        List> ret = null can not pass input [0] in 4 sum. All loop return immedicately, including twoSum. It can be controlled by if(4 > len) in main function.
        
        if(2 == k){
            
            // error : forgot to initialize the ret, List> ret = new ... was removed because line 44, ret = kSum(nums, i+1, target - nums[i], k-1);

            ret = new ArrayList>();
            
            int i = startI;
            int j = len -1;
            
            while(i < j){

                int sum = nums[i] + nums[j];
                if(sum == target){
                    List twoSumItem = new ArrayList();
                    twoSumItem.add(nums[i]);
                    twoSumItem.add(nums[j]);
                    ret.add(twoSumItem);
                    
                    // Here, forgot to increase and decrease index, time limit exceeded. Brain power depleted after 2 hour coding.
                    ++i;
                    while(i < len && nums[i-1] == nums[i]){
                        ++i;
                    }
                    --j;
                    while(j >= startI && nums[j+1] == nums[j]){
                        --j;
                    }
                // get the wrong sign, increasing decreasing index with wrong direction, get no answer or little answer.    
                }else if(sum < target){
                    ++i;
                    while(i < len && nums[i-1] == nums[i]){
                        ++i;
                    }
                }else{
                    --j;
                    while(j >= startI && nums[j+1] == nums[j]){
                        --j;
                    }
                }
            }
            
            return ret;
        }
        
        for(int i = startI; i < len; ++i){
            if(i > startI && nums[i-1] == nums[i])
                continue;
            
            // Tried to optmize code
            // Assigned ret as the return from k-1 sums, while forgot k-1 sums were called multiple times, previuos ret were washed out.
            /*
            ret = kSum(nums, i+1, target - nums[i], k-1);
            
            for(List l : ret){
                l.add(nums[i]);
            }
            */
            List> kMOneRes = kSum(nums, i+1, target - nums[i], k-1);
            for(List l : kMOneRes){
                l.add(nums[i]);
            }
            
            ret.addAll(kMOneRes);
            
        }

        return ret;
    }
    
    public List> fourSum(int[] nums, int target) {
        int len = nums.length;
        
        List> ret = new ArrayList>();
        if(4 > len)
            return ret;
        
        Arrays.sort(nums);
        
        ret = kSum(nums, 0, target, 4);
        
        for(List l : ret){
            Collections.sort(l);
        }

        return ret;
    }
}

3. Pariwise, them two sum. Good solution, reduce complexity to O(N^2), but it is not easy to handle replicated answer. Plus, it can be O(n^4) in worst case. Consider 0 0 0 0 0 1 1 1 1 1, target 1. HashMap : 0: (0, 0) ... , 1: (0, 1) ... , 2 : (1, 1) .... For each key, it contains a list with length O(n^2), Then for target 1 = key 0 + key 1, do pair-wise match between two O(n^2) lists. Could we remove duplicates before hand? It does not sounds possible. Another solution could be divide 4 sum into 0 + 4, 1 + 3, 2 + 2, 3 + 1, 4 + 0 then conquer?

3.

3.

[LeetCode] 17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

public class Solution {
    
    public void letterCombinationsAux(String digits, int i, char[][] dial, StringBuilder sb, List res){
        
        int len = digits.length();
        
        if(i >= len){
            res.add(sb.toString());
            return;
        }
        
        int number = Character.getNumericValue(digits.charAt(i));
        
        for(char c : dial[number]){
            sb.append(c);
            letterCombinationsAux(digits, i+1, dial, sb, res);
            sb.deleteCharAt(sb.length()-1);
        }
        
        return;
        
    }
    
    public List letterCombinations(String digits) {
        char[][] dial = {{}, {}, {'a','b','c'},{'d','e','f'}, {'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
        
        int len = digits.length();
        ArrayList res = new ArrayList();
        
        if(0 == len)
            return res;
            
        letterCombinationsAux(digits, 0, dial, new StringBuilder(), res);
        
        return res;
    }
}

public class Solution {
    
    public void letterCombinationsAux(String digits, int i, char[][] dial, char[] path, List res){
        
        int len = digits.length();
        
        if(i >= len){
            res.add(new String(path));
            return;
        }
        
        int number = Character.getNumericValue(digits.charAt(i));
        
        for(char c : dial[number]){
            path[i] = c;
            letterCombinationsAux(digits, i+1, dial, path, res);
        }
        
        return;
        
    }
    
    public List letterCombinations(String digits) {
        char[][] dial = {{}, {}, {'a','b','c'},{'d','e','f'}, {'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
        
        int len = digits.length();
        List res = new ArrayList();
        
        if(0 == len)
            return res;
            
        letterCombinationsAux(digits, 0, dial, new char[len], res);
        
        return res;
    }
}

[LeetCode] 16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Subscribe to see which companies asked this question

public class Solution {
    
    int keepDec(int i, int[] nums){
        --i;
        while(i>=0 && nums[i]==nums[i + 1]){
            --i;
        }
        return i;
    }
    int keepInc(int i, int[] nums){
        ++i;
        while(i= 0 && y < len){
                int sum = nums[i] + nums[x] + nums[y];
                
                if(Math.abs(sum - target) < Math.abs(res - target)){
                    res = sum;
                }
            
                if(sum == target){
                    return target;
                }
                else if( sum > target){
                    y = keepDec(y, nums);
                }else{
                    x = keepInc(x, nums);
                }
            }
            
            i = keepInc(i, nums);
        }
        
        return res;
        
    }
}

[LeetCode] 15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

public class Solution {
    public List> threeSum(int[] nums) {
        int len = nums.length;
        List> ret = new ArrayList>();
        Arrays.sort(nums);
        for(int i = 0; i < len; ++i){
            if(i > 0 && nums[i-1] == nums[i])
                continue;
            int x = i+1;
            int y = len-1;
            while(x < y){
                int sum = nums[x] + nums[y];
                sum += nums[i];
                if(0 == sum){
                    Integer[] res = {nums[x], nums[y], nums[i]};
                    Arrays.sort(res);
                    ret.add(Arrays.asList(res));
                    --y;
                    while(y >= 0 && nums[y+1] == nums[y]){
                        --y;
                    }
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }else if(0 < sum){
                    --y;
                    while(y >= 0 && nums[y+1] == nums[y]){
                        --y;
                    }
                }else{
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }
            }
        }
        
        return ret;
    }
}

[LeetCode] 14. Longest Common Prefix My Submissions Question

class Solution {
public:
    string longestCommonPrefix(vector &strs) {
        string comPrefix;
        if(strs.empty()) return comPrefix;

        // It is better to compare with the first element instead of previous element.

        for(int i=0; i=strs[j].size() || strs[j][i]!=strs[0][i])
                    return comPrefix;
            }
            comPrefix.push_back(strs[0][i]);
        }
        return comPrefix;
    }
};