CareerCup

// TC: O(logn) the log is based on 10.
public class AMZ_NumOfNums {
    // n>0
    int getNum(Integer n)
    {
        return helper(n-1);
    }

    int helper(Integer n)
    {
        if(n<=1)
            return 0;
        if(2<=n && n<=11)
            return 1;

        String s = n.toString();
        if(s.charAt(0) == '2')
        {
            int low = (int)(n%Math.pow(10, s.length()-1));
            return (low + 1) + helper(n- low - 1);
        }
        else if(s.charAt(0) < '2') {
            int low = (int) (n % Math.pow(10, s.length() - 1));
            return helper(low) + helper(n - low - 1);
        }
        else
        {
            int high = Integer.parseInt("" + s.charAt(0));
            int tens = (int)Math.pow(10, s.length() - 1);
            int low = (int)(n%tens);
            return helper(low+1) + helper(tens-1)*(high-3) + helper(3*tens - 1);
            // this splits n (e.g. 456) into three parts
            // 1. 57 -> this covers 400 to 456
            // 2. helper(99)*1 -> this covers from 300 to 399
            // 3. 299  -> this covers 1 to 299. It uses if(=='2') branch to avoid looping on 99.
        }
    }
}

- jiangok2006 November 28, 2015 | Flag Reply

binary search?

- jiangok2006 November 15, 2015 | Flag Reply

Some brain storm. The challenge is to support multi-threading. Besides lock, I am thinking about a lock free design.

1. use below data structure:

a. a hashmap (let's call it image map) whose key is the image name and the value is the double linked list node. Assumption: each image has different name so names can be used as hash key.
b. a double linked list (let's call it position list) stores the image name and the image index in the online image array.
c. two image arrays. Any time one array is online serving the requests and the other is offline processing the write operations (e.g. image adding/deletion).
d. an image write operation buffer. Just like a queue. All image write operation is put in this buffer.
e. an image write thread responsible for handling the write request in the buffer and update the offline image array. After updating, this thread put the original online array offline and the original offline array online. This design ensures the high availability - the cache always responds the image read request.

The image map and position list is immutable. Each request thread will clone and maintain its own copy of image map and position list. These two pieces of data are small so it is ok to clone repeatedly.

The image array could be big so it is shared. But there is no lock for it because: (1) we use two rotating image array for writing. One thread is handling these requests in a serialized way. (2) there could be chances that a thread tries to read an image which has been replaced/deleted in the online image array. This is a cache miss. It is ok to return "not found" by comparing the image name from the position list node with that from the image array. It should never return a wrong image. In this case, the request thread should be able to look up the online image array to check if the wanted image is in the cache but just in a different slot. If not, send an image adding request to the write buffer and return.

For all image write operations, the request threads just fire and forget.

This is a start and a lot of more details to add. For example, how the request thread update the hash table and position list if the image is deleted or changing the image array slot. How to reduce cache miss.

- jiangok2006 November 11, 2015 | Flag Reply

// not a good solution, but still a solution.
try {
            int tmp = 1/x;
            y = a;
        } catch(IllegalArgumentException exception) {
            y = b;
        }

- jiangok2006 November 10, 2015 | Flag Reply

IMHO, this is the only viable solution I have seen for 1 hour interview in terms of code size, logic complexity. BST (too much coding), binary indexed tree (un-intuitive logic and still fair amount of coding) are not appropriate for an interview.

- jiangok2006 November 10, 2015 | Flag Reply

The sample code on SO is overly simplified. The actually implementation is much more complicated if you need to implement index sort, consider duplicate numbers. However, BIT is still a great idea and may possibly still easier to code compared with other solutions.

- jiangok2006 November 10, 2015 | Flag Reply

Just think loud.

boolean isEqual(int a, int b) {
    try { 
         double a = 1/(a-b);
         return false;
    }  catch (InvalidOperationException) {
        return true;
    }
}

- jiangok2006 November 09, 2015 | Flag Reply

This is another DP algo in Java. I think TC is O(n*n!) and SC O(n!). It is not better than the brutal force algo of exhausting the combinations satisfying the length constraint.

public class GG_SubsetSum {
    class Comb {
        ArrayList<Integer> left; // keep left.size()>=right.size()
        ArrayList<Integer> right;

        Comb(ArrayList<Integer> left, ArrayList<Integer> right)
        {
            this.left = left;
            this.right = right;
        }
    }

    ArrayList<ArrayList<Integer>> partition(int[] nums)
    {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(nums == null || nums.length == 0)
            return ret;

        ArrayList<Comb> d = new ArrayList<>();
        ArrayList<Integer> d0 = new ArrayList<>();
        d0.add(nums[0]);
        d.add(new Comb(d0, new ArrayList<>()));

        for(int i=1; i< nums.length; ++i) {
            ArrayList<Comb> newCombs = new ArrayList<>();
            for(int j=0; j<d.size(); ++j) {
                Comb c = d.get(j);
                int lengthDiff = c.left.size() - c.right.size();

                if(lengthDiff == 0) {
                    Comb c1 = new Comb((ArrayList<Integer>)c.left.clone(), (ArrayList<Integer>)c.right.clone());
                    c1.right.add(nums[i]); // right will be longer
                    newCombs.add(new Comb(c1.right, c1.left)); // create a new Comb to keep left longer.
                    c.left.add(nums[i]);
                } else if(lengthDiff == 1) {
                    Comb c1 = new Comb((ArrayList<Integer>)c.left.clone(), (ArrayList<Integer>)c.right.clone());
                    c1.right.add(nums[i]);
                    newCombs.add(c1);
                    c.left.add(nums[i]);
                }
                else { // lengthDiff == 2
                    c.right.add(nums[i]);
                }
            }

            for(int j=0; j<newCombs.size(); ++j)
                d.add(newCombs.get(j));
        }

        double min = Double.MAX_VALUE;
        int minIndex = -1;
        for(int i=0; i<d.size(); ++i) {
            Comb c = d.get(i);
            int lengthDiff = c.left.size() - c.right.size();
            if(lengthDiff <= 1) {
                int leftSum = 0;
                for(int j=0; j<c.left.size(); ++j) {
                    leftSum += c.left.get(j);
                }

                int rightSum = 0;
                for(int j=0; j<c.right.size(); ++j) {
                    rightSum += c.right.get(j);
                }

                int lmin = Math.abs(leftSum - rightSum);
                if(lmin < min) {
                    min = lmin;
                    minIndex = i;
                }
            }
        }

        ret.add(d.get(minIndex).left);
        ret.add(d.get(minIndex).right);
        return ret;
    }
}

- jiangok2006 November 07, 2015 | Flag Reply

does not work for cdabc. expect: cdab, actual: dabc

- jiangok2006 November 05, 2015 | Flag Reply

not work for cbacdbced. expect abced, actual output: acbed

- jiangok2006 November 04, 2015 | Flag Reply

public class GG_SubArraySumInRange {
    // This java code uses segment tree. TC: O(n*lgn*lgn)
    
    // O(n*lgn*lgn)
    int getSubArr(int[] nums, int low, int high)
    {
        if(nums==null || nums.length==0)
            return 0;

        //get the sum array. O(n)
        Sum[] sums = new Sum[nums.length];
        for(int i=0; i<nums.length;++i) {
            if(i==0) {
                sums[i] = new Sum(nums[i], 0);
            }
            else {
                sums[i] = new Sum(sums[i-1].val + nums[i], i);
            }
        }

        //O(nlgn)
        Arrays.sort(sums);

        //build segment tree on the sorted sum array. O(nlgn)
        TreeNode segTree = buildSegTree(sums, 0, sums.length-1, null);

        TreeNode[] map = new TreeNode[nums.length];
        //create a map of original index to its corresponding segment tree node. O(n)
        populateMap(segTree, map);

        int count = 0;
        int prevSum = 0;
        //O(n*lgn*lgn)
        for(int i=0; i<nums.length; ++i)
        {
            // get updated range for searching in segment tree.
            int low2 = low + prevSum;
            int high2 = high + prevSum;

            // search the segment for each updated range. O(lgn*lgn)
            count += searchRange(sums, segTree, low2, high2);
            prevSum += nums[i];

            // After handling this num, excluding it from the segment tree. O(lgn)
            excludeNode(map[i]);
        }

        return count;
    }

    // data structure for sum sorting.
    class Sum implements Comparable<Sum> {
        int val;
        int ind; // the index in the original nums array.
        Sum(int val, int ind)
        {
            this.val = val;
            this.ind = ind;
        }

        public int compareTo(Sum s)
        {
            return this.val - s.val;
        }
    }

    class TreeNode {
        ArrayList<Integer> sumInd = new ArrayList<>();
        int ind;  // the original index in nums array.
        boolean excluded; // indicate if current node is excluded.
        TreeNode parent; // for segment tree update in O(lgn)
        TreeNode left;
        TreeNode right;
        public TreeNode(TreeNode parent, int ind)
        {
            this.parent = parent;
            this.ind = ind;
            this.excluded = false;
            this.left = this.right = null;
        }
    }

    boolean isValid(int n, int low, int high) {
        return low<=n && n<=high;
    }

    void excludeNode(TreeNode node)
    {
        node.excluded = true;
        int st = node.sumInd.get(0);
        int end = node.sumInd.get(node.sumInd.size()-1);

        while(true)
        {
            node = node.parent;
            if(node == null)
                break;
            int st1 = bs(node.sumInd, 0, node.sumInd.size()-1, st);
            int end1;
            if(st == end)
                end1 = st1;
            else
                end1 = bs(node.sumInd, 0, node.sumInd.size()-1, end);
            
            for(int i=end1; i>st1-1; --i)
                node.sumInd.remove(i);
            
            // if all children have been excluded, then current node is excluded also.
            if(node.sumInd.size()==0)
                node.excluded = true;
        }
    }

    // regular binary search
    int bs(ArrayList<Integer> sumInd, int st, int end, int target)
    {
        if(st>end)
            return -1;
        int mid = st + (end-st)/2;
        if(target == sumInd.get(mid))
            return mid;

        if(target < sumInd.get(mid))
        {
            return bs(sumInd, st, mid-1, target);
        }

        return bs(sumInd, mid+1, end, target);
    }

    // populate the map for original indexes in nums to TreeNodes.
    void populateMap(TreeNode segTree, TreeNode[] map)
    {
        //preorder dfs
        if(segTree == null)
            return;

        if(segTree.ind != -1)
            map[segTree.ind] = segTree;

        populateMap(segTree.left, map);
        populateMap(segTree.right, map);
    }

    TreeNode buildSegTree(Sum[] sums, int st, int end, TreeNode parent)
    {
        if(st > end)
            return null;

        if(st == end) {
            TreeNode root = new TreeNode(parent, sums[st].ind);
            root.sumInd.add(st);
            return root;
        }

        int mid = st + (end-st)/2;
        TreeNode root = new TreeNode(parent, -1);
        root.left = buildSegTree(sums, st, mid, root);
        root.right = buildSegTree(sums, mid+1, end, root);
        for(int i=st; i<end+1; ++i) // this loop does not change tree build complexity O(nlgn)
            root.sumInd.add(i);

        return root;
    }

    int searchRange(Sum[] sums, TreeNode segTree, int low, int high) {
        if(segTree == null)
            return 0;

        int lowSum = sums[segTree.sumInd.get(0)].val;
        int highSum = sums[segTree.sumInd.get(segTree.sumInd.size()-1)].val;

        if(high < lowSum || highSum < low)
            return 0;

        if(low <= lowSum && highSum <= high)
            return segTree.sumInd.get(segTree.sumInd.size()-1) - segTree.sumInd.get(0) + 1;

        int count = 0;
        count += searchRange(sums, segTree.left, low, high);
        count += searchRange(sums, segTree.right, low, high);
        if(segTree.ind!=-1 && isValid(sums[segTree.ind].val, low, high))
        {
            count+=1;
        }

        return count;
    }
}

- jiangok2006 November 03, 2015 | Flag Reply

The time and space complexity are both O(n) where n is the number of characters of all words in the array. Due to ambiguous search, we have to search all paths in the worst case to get the final match. So trie does not improve the worst case time complexity compared with the brutal force word by word comparing.

Like above trie algo, the brutal force algo can also use string length and char difference count to early terminate the comparison. So I am a little confused how trie is useful at all. :( Any insight will be highly appreciated.

- jiangok2006 November 03, 2015 | Flag Reply

/* To my understanding:
1. the interviewer actually asked for the same array, how to make queries fast - each using different word.
    If for only one time query, brutal force word by word comparison should work.

 2. two words one char different means:
   a. they are the same length but one char is different. OR
   b. one is one char shorter or longer than the other.

Below is java code using trie and dfs.
 */
public class GG_OneOffCompare {
    class DepMinMax {
        int max;
        int min;
        DepMinMax(int max, int min)
        {
            this.max = max;
            this.min = min;
        }
    }
    class Node {
        char ch;
        ArrayList<Node> children;
        int minDep;
        int maxDep;
        Node(char ch)
        {
            this.ch = ch;
            children = new ArrayList<>();
            this.minDep = this.maxDep = 1;
        }

        boolean isSentinel()
        {
            return children.size() == 0;
        }

        boolean isBeforeSentinel()
        {
            for(int i=0; i<children.size(); ++i)
            {
                if(children.get(i).isSentinel())
                    return true;
            }
            return false;
        }
    }

    boolean query(String[] arr, String word) {
        Node trie = buildTrie(arr);
        getDepth(trie);
        print(trie, "");

        for(int i=0; i<trie.children.size(); ++i) {
            if(queryEqualLength(trie.children.get(i), word, false))
                return true;

            if(queryShorterLength(trie.children.get(i), word, false))
                return true;

            if(queryLongerLength(trie.children.get(i), word, false))
                return true;
        }

        return false;
    }

    boolean queryShorterLength(Node trie, String word, boolean alreadyOneOff) {
        // check if there is a word in the trie that is one char shorter
        if (trie.isSentinel())
            return (alreadyOneOff && word.length() == 0) ||
                    (!alreadyOneOff && word.length() == 1);

        if (alreadyOneOff) {
            if (word.length() < trie.minDep - 1 || trie.maxDep - 1 < word.length())
                return false;
        } else {
            if (word.length() - 1 < trie.minDep - 1 || trie.maxDep - 1 < word.length() - 1)
                return false;
        }

        if (trie.ch == word.charAt(0)) {
            for (int i = 0; i < trie.children.size(); ++i) {
                if (alreadyOneOff) {
                    if (queryShorterLength(trie.children.get(i), word.substring(1), true))
                        return true;
                } else {
                    if (queryShorterLength(trie.children.get(i), word.substring(1), false) ||
                            queryShorterLength(trie, word.substring(1), true))
                        return true;
                }
            }
        } else {
            if (alreadyOneOff) return false;
            for (int i = 0; i < trie.children.size(); ++i) {
                if (queryShorterLength(trie, word.substring(1), true))
                    return true;
            }
        }

        return false;
    }

    boolean queryLongerLength(Node trie, String word, boolean alreadyOneOff) {
        // check if there is a word in the trie that is one char longer than the parameter word
        if (word.length() == 0)
            return (alreadyOneOff && trie.isSentinel()) ||
                    (!alreadyOneOff && trie.isBeforeSentinel());

        if (alreadyOneOff) {
            if (word.length() < trie.minDep - 1 || trie.maxDep - 1 < word.length())
                return false;
        } else {
            if (word.length() + 1 < trie.minDep - 1 || trie.maxDep - 1 < word.length() + 1)
                return false;
        }

        if (trie.ch == word.charAt(0)) {
            for (int i = 0; i < trie.children.size(); ++i) {
                if (alreadyOneOff) {
                    if (queryShorterLength(trie.children.get(i), word.substring(1), true))
                        return true;
                } else {
                    if (queryLongerLength(trie.children.get(i), word.substring(1), false) ||
                            queryLongerLength(trie.children.get(i), word, true))
                        return true;
                }
            }
        } else {
            if (alreadyOneOff) return false;
            for (int i = 0; i < trie.children.size(); ++i) {
                if (queryLongerLength(trie.children.get(i), word, true))
                    return true;
            }
        }

        return false;
    }

    boolean queryEqualLength(Node trie, String word, boolean alreadyOneOff)
    {
        // check if there is a word in trie that have the
        // same length as the parameter word but one char different.

        if(trie.isSentinel())
            return (alreadyOneOff && word.length() == 0);

        if(word.length() < trie.minDep-1  || trie.maxDep-1 < word.length())
            return false;

        // pre-order dfs
        if(trie.ch == word.charAt(0))
        {
            for(int i=0; i<trie.children.size(); ++i) {
                if (queryEqualLength(trie.children.get(i), word.substring(1), alreadyOneOff))
                    return true;
            }
        }
        else
        {
            if (alreadyOneOff) return false;
            for(int i=0; i<trie.children.size(); ++i) {
                if (queryEqualLength(trie.children.get(i), word.substring(1), true))
                    return true;
            }
        }

        return false;
    }

    void print(Node trie, String buf) {
        if(trie.isSentinel()) {
            System.out.println(buf + trie.ch);
            return;
        }

        buf = buf + trie.ch + ",";
        for(int i=0; i<trie.children.size();++i)
        {
            print(trie.children.get(i), buf);
        }
    }

    // get min and max depths for each node.
    DepMinMax getDepth(Node trie)
    {
        // postorder DFS
        if(trie.isSentinel())
            return new DepMinMax(1, 1);

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i=0; i<trie.children.size(); ++i)
        {
            DepMinMax dep = getDepth(trie.children.get(i));
            min = Math.min(min, dep.min);
            max = Math.max(max, dep.max);
        }

        trie.maxDep = max + 1;
        trie.minDep = min + 1;
        return new DepMinMax(trie.maxDep, trie.minDep);
    }

    Node buildTrie(String[] arr) {
        Node root = new Node('#');
        for(int i=0; i<arr.length; ++i)
        {
            buildTreeHelper(root, arr[i]);
        }
        return root;
    }

    void buildTreeHelper(Node root, String s)
    {
        if(s.length() == 0) {
            root.children.add(new Node('$')); //important: add sentinel node - required.
            return;
        }

        Node child = null;
        for(int i=0; i<root.children.size(); ++i)
        {
            if(root.children.get(i).ch == s.charAt(0))
            {
                child = root.children.get(i);
                break;
            }
        }

        if(child == null)
        {
            Node s0Node = new Node(s.charAt(0));
            root.children.add(s0Node);
            child = s0Node;
        }

        buildTreeHelper(child, s.substring(1));
    }
}

- jiangok2006 November 03, 2015 | Flag Reply

This problem can be solved using BFS (the worst case O(n^2)). Below is the java code which has been tested with above inputs.

import java.util.*;
import java.util.concurrent.atomic.AtomicReference;

public class GG_SwapSeats {
    int swapSeats(String s)
    {
        Queue<String> queue = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();

        ArrayList<Character> singles = new ArrayList<>();
        ArrayList<Character> couples = new ArrayList<>();

        for(int i=0; i<s.length(); ++i)
        {
            if(singles.contains(s.charAt(i)))
            {
                couples.add(s.charAt(i));
                singles.remove(new Character(s.charAt(i)));
            }
            else singles.add(new Character(s.charAt(i)));
        }

        if(couples.size()==0) return 0;

        queue.add(s);
        visited.add(s);
        int level = 0;
        Integer c1;
        c1=1;
        AtomicReference<Integer> c2 = new AtomicReference<>(0);
        while(queue.size()>0)
        {
            String s1 = queue.poll();

            boolean isValid = true;
            HashMap<Character, ArrayList<Integer>> charMap = new HashMap<>();
            ArrayList<Character> separatedCouples = new ArrayList<>();
            for(int i=0; i<s1.length(); ++i)
            {
                if(charMap.containsKey(s1.charAt(i))) {
                    ArrayList<Integer> list = charMap.get(s1.charAt(i));
                    list.add(i);
                    if(Math.abs(list.get(0)-list.get(1))>1) {
                        isValid = false;
                        separatedCouples.add(s1.charAt(i));
                    }
                }
                else {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(i);
                    charMap.put(s1.charAt(i), list);
                }
            }

            if(isValid)
                break;

            for(int i=0; i<separatedCouples.size(); ++i) {
                ArrayList<Integer> list = charMap.get(separatedCouples.get(i));

                if (list.get(0) > 0)
                    addToQueue(s1, list.get(0) - 1, list.get(1), c2, visited, queue);

                if (list.get(0) < s1.length() - 1)
                    addToQueue(s1, list.get(0) + 1, list.get(1), c2, visited, queue);

                if (list.get(1) > 0)
                    addToQueue(s1, list.get(1) - 1, list.get(0), c2, visited, queue);

                if (list.get(1) < s1.length() - 1)
                    addToQueue(s1, list.get(1) + 1, list.get(0), c2, visited, queue);

                // must consider the singles
                for (int j = 0; j < singles.size(); ++j) {
                    addToQueue(s1, charMap.get(singles.get(j)).get(0), list.get(0), c2, visited, queue);
                    addToQueue(s1, charMap.get(singles.get(j)).get(0), list.get(1), c2, visited, queue);
                }

                if (--c1 == 0) {
                    c1 = c2.get();
                    c2.set(0);
                    level++;
                }

            }
        }

        return level;
    }

    void addToQueue(String s,
                    int x,
                    int y,
                    AtomicReference<Integer> childCount,
                    HashSet<String> visited,
                    Queue<String> queue)
    {
        char[] arr = s.toCharArray();
        Util.exchange(arr, x, y);
        String child = new String(arr);
        if (!visited.contains(child)) {
            queue.add(child);
            visited.add(child);
            childCount.set(childCount.get() + 1);
        }
    }
}

- jiangok2006 November 03, 2015 | Flag Reply

Seems not work for "aabcdaafaaaabrrrtaaaeecccccaaddaaa".
It should output "acacacadacaraeabacaradabadataearcf" but your code will output "".

I have not seen any working O(n) algo so far.

- jiangok2006 November 02, 2015 | Flag Reply

isn't this property already used in kyduke's O(nlgn) solution? Can anybody clarify how this observation be used for a O(n) solution?

- jiangok2006 October 28, 2015 | Flag Reply

Sorry, it is not O(n*k) since there are three nested loops. It should be O((n^2)*k).

- jiangok2006 October 11, 2015 | Flag Reply

Below is the C# code. Time: O(n*k).

public int split(int[] arr, int k)
        {
            if (arr == null || arr.Length < k)
                throw new Exception();

            int len = arr.Length;

            int[,] dp = new int[k, len]; // arr storing the min sum for x cuts where x=1..k

            dp[0, 0] = arr[0];
            for(int i=1; i< len; i++)
            {
                dp[0, i] = dp[0,i-1]+arr[i];
            }

            for(int i=1; i< k; i++)
                for(int j=i; j< len; ++j)
                {
                    int minSum = int.MaxValue;

                    for(int t=i; t<j+1; t++)
                    {
                        int lmax = Math.Max(dp[i - 1, t - 1], dp[0, j] - dp[0, t - 1]);
                        if (minSum > lmax)
                            minSum = lmax;
                    }

                    dp[i, j] = minSum;
                }

            return dp[k-1, len-1];
        }

- jiangok2006 October 11, 2015 | Flag Reply

It runs in O(k) where is the range length. If preprocessing cannot improve time complexity (e.g. O(lgk)), I don't see why we need it.

- jiangok2006 October 07, 2015 | Flag Reply

sorry for the duplication, the website made me think my previous post did not go through.

- jiangok2006 September 27, 2015 | Flag Reply

How about this:
1. find the min of the whole array. If min <= 0, go to 2. otherwise, go to 3.
2. add abs(min) + 1 to each element and (a, b) so that all element > 0 and the range becomes (a+abs(min)+1, b+abs(min)+1).
3. use naive algorithm with early termination. If the sum of a sub array > b+abs(min)+1, then stop scanning longer sub array.

The complexity is O(nk) where k is the number of subarray whose sum < b+abs(min)+1. It can be O(n^2) in worst case but is output sensitive.

- jiangok2006 September 27, 2015 | Flag Reply

case class NaryNode(v: Int, var children: Vector[NaryNode])

  def Traverse(root: NaryNode) = {
    def recurse(prev: NaryNode, current: NaryNode): Unit = {
      if (current == null) return
      if (prev == null) current.children = current.children :+ null

      if (current.children.filter(_ == prev).length != 0 ||
        current.children.length == 1) { 
        // if the prev node is one of the child of current, then
        // it means all children have been visited. Now visit current node.
        
        // if current node has no children, then visit current node
        
        // ==1 because we add one pointer to the children Vector 
        // for pointing to the current node's sibling.
        println(current.v)
        
        // visit the current node's sibling
        recurse(current, current.children(current.children.length - 1))
      } else {
        // connect the children into a singular link list.
        for (i <- 0 to current.children.length - 2) {
          current.children(i).children = current.children(i).children :+ current.children(i + 1)
        }
        
        // connect the last child back to the current node.
        current.children(current.children.length - 1).children =
          current.children(current.children.length - 1).children :+ current
        
        // now visit the current node's first child.
        recurse(current, current.children(0))
      }
    }

    recurse(null, root)
  }

- jiangok2006 September 14, 2015 | Flag Reply

nice idea. The complexity is O(m(n^2)) since you need to repeat Min for O(mn) instead of O(m). This complexity is worse than merge algo O(mn*lgn).

- jiangok2006 September 12, 2015 | Flag Reply

public static void MainFunc()
        {       
            string str = "1";
            while (str!=null)
            {
                Console.Write(str+", ");
                str = GetNext(str); 
            }

        }

        static string GetNext(string cur)
        {
            if(cur == "999") return null;

            if (cur.Length < 3)
            {
                cur += "0";
                return cur;
            }

            int tmp = int.Parse(cur);
            if(tmp==100)
            {
                return "1000";
            }

            if (tmp == 1000)
            {
                return "101";
            }

            tmp += 1;
            if (tmp % 100 == 0)
            {
                return ((int)(tmp / 100)).ToString();
            }
            else if (tmp % 10 == 0)
            {
                return ((int)(tmp / 10)).ToString();
            }
            else
            {
                return tmp.ToString();
            }
        }

- jiangok2006 July 16, 2014 | Flag Reply

The information of "complete" tree seems to be unnecessary.

- jiangok2006 June 18, 2014 | Flag Reply

The second solution is wrong. The example misses the return (1, 3, 9)

- jiangok2006 June 15, 2014 | Flag Reply

// C#
int mainfunc(Node r, Node t1, Node t2)
{
   // sum is the minimum distance
   // dt1 is the distance from r to t1
   // dt2 is the distance from r to t2   
   int sum=0, dt1, dt2;
   sum=dt1=dt2=0;

   f(r, t1, t2, ref sum, ref dt1, ref dt2);
   return sum;  
}


void f(Node r, Node t1, Node t2, ref int sum, ref int dt1, ref int dt2)
{
   if(r==null || sum>0) return;

   if(dt1>0)
   {
      if(r==t2) { dt2=1; return;}
      f(r.left, t1, t2, ref sum, ref dt1, ref dt2);
      if(dt2>0) { dt2++; return;}
      f(r.right, t1, t2, ref sum, ref dt1, ref dt2);
      if(dt2>0) { dt2++; return; }
   }

   if(dt2>0)
   {
      if(r==t1) { dt1=1; return;}
      f(r.left, t1, t2, ref sum, ref dt1, ref dt2);
      if(dt1>0) { dt1++; return;}
      f(r.right, t1, t2, ref sum, ref dt1, ref dt2);
      if(dt1>0) { dt1++; return;}
   }

   if(r==t1)
   {
      f(r.left, t1, t2, ref sum, ref dt1, ref dt2);
      if(dt2>0) { sum=dt2; return;}
      f(r.right, t1, t2, ref sum, ref dt1, ref dt2);
      if(dt2>0) { sum=dt2; return;}
      dt1=1; return;
   }

   if(r==t2)
   {
      f(r.left, t1, t2, ref sum, ref dt1, ref dt2);
      if(dt1>0) { sum=dt1; return;}
      f(r.right, t1, t2, ref sum, ref dt1, ref dt2);
      if(dt1>0) { sum=dt1; return;}
      dt2=1; return;
   }

   f(r.right, t1, t2, ref sum, ref dt1, ref dt2);  
   if(sum>0) return;
   if(dt1>0 && dt2>0) { sum=dt1+dt2-1; return;}
   if(dt1>0) { dt1++; return; }
   if(dt2>0) { dt2++; return; }
}

- jiangok2006 June 08, 2014 | Flag Reply

// change the question to return the length of the longest sequence
// Pnt is a class having two int members v and h. v means vertical sequence length starting 
// from this point, h means horizontal sequence length starting from this point.

int f(int[,] mat, Pnt[,] pnt)
{
    int max = INT_MIN;
    for(int i=0;i<mat.length;++i)
	  for(int j=0;j<mat[i].length;++j)
	  {
	      if(mat[i,j]==0)
		  {
		     pnt[i,j]= new Pnt(0, 0);
		  }
		  else
		  {
		         int h = i==0 ? 1 : pnt[i-1,j].v+1;
			 int v = j==0 ? 1 : pnt[i,j-1].h+1;
                         pnt[i,j]= new Pnt(h, v);
			 if(h>max) max=h;
			 if(v>max) max=v;
		  }
	  }
	  
	return max;
}

- jiangok2006 May 24, 2014 | Flag Reply

can be optimized using DP.

- jiangok2006 May 13, 2014 | Flag Reply

int[] coins = {25,10,6,1};

int mainFunction(int change)
{
   return MinCoin(change, 0);
}

int MinCoin(int change, int count)
{
   if(change<=0) return count;
   int min = INT_MAX;
   for(int i=0;i<coins.length;++i)
   {
          if(change>=coins[i])
	  {
	      int c = MinCoin(change-coins[i], count+1);
	      min = Min(c, min);
      }
   }
   
   return min;
}

- jiangok2006 May 13, 2014 | Flag Reply

int MinProd(List<Tuple<int,int>> mats)
{
   int s1, s2, s3;
   s1 = 0;
   if(mats.Count() < 2) return s1;
   
   int s2 = mats[0].First * mats[1].First * mats[2].Second;
   if(mats.Count() < 3) return s2;
   
   for(int i=2; i<mats.Count();++i)
   {
      s3 = Min ( s2 + mats[0].First * mats[i].First * mats[i].Second,
	             s1 + mats[i-1].First * mats[i].First * mats[i].Second + 
				      mats[0].First * mats[i-1].First * mats[i].Second );
	  s1 = s2;
	  s2 = s3;
   }
   
   return s3;
}

- jiangok2006 May 13, 2014 | Flag Reply

good solution. Thanks.

- jiangok2006 May 13, 2014 | Flag Reply

int GetLongestSequence(int[] arr, int max, int min)
{
   int countArrLen = max-min+1;
   if(countArrLen<2) return -1;

   int[] counts = new int[countArrLen];
   for(int i=0;i<counts.length;++i)
   {
      counts[i]=0;
   }

   for(int i=0;i<arr.length;++i)
   {
      counts[arr[i]-min]++;   
   }

   int maxLen = INT_MIN;
   for(int i=0;i<counts.length-1;++i)
   {
      if(counts[i]==0 || counts[i+1]==0) continue;
      int seqLen = counts[i]+counts[i+1];
      if(seqLen>maxLen)
      {
         maxLen=seqLen;
      }
   }

   return maxLen;
}

O(n) time complexity.

- jiangok2006 May 07, 2014 | Flag Reply

{{{ {{{ class ZeroSum { static int[] arr = { 2, 1, -1, 0, 2, -1, -1 }; static List<int> buf = new List<int>(); // store the indexes static Dictionary<string, int> sumDict = new Dictionary<string, int>(); // get all combinations. public static void mainFunc() { for (int i = 1; i < arr.Length+1; ++i) { getCombRec(i, 0); } } static void getCombRec(int len, int start) { if (len == 0) { if (getSum() == 0) { PrintBuffer(); } return; } if (start > arr.Length - 1) return; for (int i = start; i < arr.Length; ++i) { buf.Add(i); getCombRec(len - 1, i + 1); buf.RemoveAt(buf.Count - 1); } } // get sum for the buffered list by table looking up. static int getSum() { int sum; if (buf.Count() == 1) { sum = arr[buf[0]]; sumDict.Add(ConvertBufferToString(0), arr[buf[0]]); return sum; } else { sum = arr[buf[0]] + sumDict[ConvertBufferToString(1)]; sumDict.Add(ConvertBufferToString(0), sum); return sum; } } // construct hash key using the list. static string ConvertBufferToString(int start) { StringBuilder s = new StringBuilder(); for (int i = start; i < buf.Count; ++i) { s.Append(buf[i] + "-"); } return s.ToString(); } static void PrintBuffer() { for (int i = 0; i < buf.Count; ++i) { Console.Write(arr[buf[i]]+", "); } Console.WriteLine(); } } }}} }}} - jiangok2006 March 30, 2014 | Flag Reply

class Hops
    {
        static int[] arr = { 1, 3, 5, 2, 4 };

        public static void mainFunc()
        {
            int i=0;

            while (i < arr.Length)
            {
                Console.WriteLine(i);

                if (i + arr[i] > arr.Length - 1)
                {
                    return;
                }

                int max, maxInd;
                max = maxInd = -1;
                for (int j = 1; j < Math.Min(arr.Length-i, arr[i]+1) ; ++j)
                {
                    int step = j + arr[i + j];
                    if (step > max)
                    {
                        max = step;
                        maxInd = j;
                    }
                }

                i += maxInd;
            }
        }
    }

- jiangok2006 March 27, 2014 | Flag Reply

// 1 f(0)
        // 2 min(2*f(0), 3*f(0), 5*f(0))
        // 3 min(2*f(1), 3*f(0), 5*f(0))
        // 4 min(2*f(1), 3*f(1), 5*f(0))
        // 5 min(2*f(2), 3*f(1), 5*f(0))
        // 6 min(2*f(2), 3*f(1), 5*f(1))
        // 8 min(2*f(2), 3*f(2), 5*f(1))
        public static void mainFunc(int n)
        {
            List<int> f = new List<int>();
            f.Add(1);
            int i1, i2, i3;
            i1 = i2 = i3 = 0;

            for (int i = 1; i < n + 1; ++i)
            {
                int min = Math.Min(Math.Min(2 * f[i1], 3 * f[i2]), 5 * f[i3]);
                f.Add(min);
                if(min == 2*f[i1]) i1++;
                if (min == 3 * f[i2]) i2++;
                if (min == 5 * f[i3]) i3++;
            }

            Console.WriteLine(f[n]);
        }

- jiangok2006 March 27, 2014 | Flag Reply

// C# implementation
public static void mainFunc()
        {
            //"12+5*4+26", more function needed to parse the input into lists.
            List<int> nums = new List<int>();
            nums.Add(12);
            nums.Add(5);
            nums.Add(4);
            nums.Add(26);

            List<char> ops = new List<char>();
            ops.Add('+');
            ops.Add('*');
            ops.Add('+');

            Stack<int> numStack = new Stack<int>();
            Stack<char> charStack = new Stack<char>();

            numStack.Push(nums[0]);

            for (int i = 0; i < nums.Count-1; ++i)
            {
                if (ops[i] == '*')
                {
                    int a = numStack.Pop();
                    numStack.Push(a * nums[i+1]);
                }
                else
                {
                    numStack.Push(nums[i+1]);
                    charStack.Push(ops[i]);
                }
            }

            while (charStack.Count > 0)
            {
                char c = charStack.Pop();
                int a = numStack.Pop();
                int b = numStack.Pop();
                numStack.Push(a + b);
            }

            Console.WriteLine(numStack.Pop());
        }

- jiangok2006 March 26, 2014 | Flag Reply

class Combination
    {
        static string input = "0a123b4525c";
        static char[] arr = input.ToArray();

        public static void mainFunc()
        {
            Rec(input.Length-1);
        }

        private static bool isNum(char c)
        {
            return c <= '9' && c >= '0';
        }

        private static void Rec(int ind)
        {
            if (ind == 0)
            {
                Console.WriteLine(arr);

                if (!isNum(arr[0]))
                {
                    arr[0] = char.ToUpper(arr[0]);
                    Console.WriteLine(arr);
                    arr[0] = char.ToLower(arr[0]);
                }

                return;
            }

            Rec(ind - 1);

            if (!isNum(arr[ind]))
            {
                arr[ind] = char.ToUpper(arr[ind]);
                Rec(ind - 1);
                arr[ind] = char.ToLower(arr[ind]);
            }
        }
    }

- jiangok2006 March 25, 2014 | Flag Reply

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Node
    {
        public int val;
        public Node next;
        public Node(int val)
        {
            this.val = val;
        }
    }

    class MultipleTwoLists
    {
        static int digitsPerNode = 2;
        static Node result = null;
        static Node resultp = result;
        static Node resultp2 = result;

        public static void mainFunc()
        {
            Node n1 = new Node(23);
            Node n2 = new Node(65);
            Node n3 = new Node(12);
            n1.next = n2;
            n2.next = n3;

            Node n4 = new Node(34);
            Node n5 = new Node(55);
            n4.next = n5;

            Multiply(n1, n4);

            PrintResult(result);
        }

        static void Multiply(Node n1, Node n2)
        {
            if (n2.next != null)
            {
                Multiply(n1, n2.next);
            }

            Multiply2(n1, n2);
            resultp2 = resultp = resultp.next;
        }

        static void Multiply2(Node n1, Node n2)
        {
            if (n1.next != null)
            {
                Multiply2(n1.next, n2);
            }

            if (resultp2 == null)
            {
                resultp2 = new Node(0);
                result = resultp = resultp2;
            }

            int m = n1.val * n2.val + resultp2.val;
            
            int carryon = (int)(m / Math.Pow(10, digitsPerNode));
            resultp2.val = m % (int)Math.Pow(10, digitsPerNode);
            if (carryon > 0)
            {
                if (resultp2.next == null)
                {
                    resultp2.next = new Node(carryon);
                }
                else
                {
                    resultp2.next.val += carryon;
                }
            }

            resultp2 = resultp2.next;
        }

        static void PrintResult(Node p)
        {
            if (p == null)
                return;

            if (p.next != null)
            {
                PrintResult(p.next);
            }

            Console.Write(p.val);
        }
    }
}

- jiangok2006 March 19, 2014 | Flag Reply

This question is ambigous and can be understood in two different ways:

1. return true if at least a pair of numbers satisfies the requirement.

2. return true if all pairs of numbers satisfy the requirement.

Both are O(n)

- jiangok2006 January 16, 2014 | Flag Reply

This question is ambigous and can be understood in two different ways:

1. return true if at least a pair of numbers satisfies the requirement.

2. return true if all pairs of numbers satisfy the requirement.

Both are O(n)

- jiangok2006 January 16, 2014 | Flag Reply

Should * be handled by:

isMatching(i,j) = isMatching(i+1,j) or isMatching(i+1,j+1) or isMatching(i,j+1)

So it covers the case string is empty and pattern has only "*".

- jiangok2006 September 01, 2013 | Flag Reply

How can the 3rd step be done in place with O(m+n) time?

- jiangok2006 August 12, 2013 | Flag Reply

good coding question.

- jiangok2006 August 05, 2013 | Flag Reply

Backtrack.

Let's say the first array is height array and the second is count array. Sort the count array from low to high (say [0,1,1]). Start from the first height 3 (corresponding to count 0), the root node of the backtrack tree is (3), then insert the second height 2, generating one child node (3,2). Then insert the third height 1, generating one child node (3,1,2). If a node does not generate any child node, then it is an dead end. In this case, backtrack to the upper level node to visit its next child node.

This way you can find all possible sequences satisfying the two arrays. And you can confidently know if there is no such sequence at all.

- jiangok2006 August 05, 2013 | Flag Reply

Another solution:

int ReadChar4096(char *buf);
char g_buf[4096]; //global buffer to save the data read by ReadChar4096.

int ReadChar(char *buf, int n)
{
        int n1,n2;
	bool isEnd=false;
	
	n1=(int)n/4096;
	n2=n%4096;
	
	int pos = 0;
	for(int i=0;i<n1;++i)
	{
	   int cRead = ReadChar4096(g_buf);	   
	   copy(buf, g_buf, pos, cRead);
	   pos+=cRead;
	   if(cRead<4096)
	   {
                  isEnd = true;		  
		  break;
	   }
	}
	
	if(!isEnd && n2)
	{
	   int cRead = ReadChar4096(g_buf);
	   int cNeeded = cRead < n2 ? cRead : n2;
	   copy(buf, g_buf, pos, cNeeded);
	   pos+=cNeeded;
	}
	
	return pos;
}

- jiangok2006 May 28, 2013 | Flag Reply

tag

- jiangok2006 September 22, 2012 | Flag Reply

void f(int* arr, int* buf, int k, int arr_cur, int buf_cur)
{
   if(k==0)
   {
      printf(buf);
      return;
   }

   for(int i=arr_cur;i<len(arr)-k+1;++i) 
   {
      buf[buf_cur]=arr[i];
      f(arr, buf, k-1, i+1, buf_cur+1);
   }
}

void mainfunc(int* arr, int k)
{
   int* buf = new int[k];
   f(arr, buf, k, 0, 0);
}

- jiangok2006 September 22, 2012 | Flag Reply

Like

- jiangok2006 September 11, 2012 | Flag Reply

Like

- jiangok2006 September 10, 2012 | Flag Reply