amazon 面经3

The problem clearly say that we need to flatten level by level. The idea of solution is, we start from first level, process all nodes one by one, if a node has a child, then we append the child at the end of list, otherwise we don’t do anything. After the first level is processed, all next level nodes will be appended after first level. Same process is followed for the appended nodes.

1) Take "cur" pointer, which will point to head of the fist level of the list
2) Take "tail" pointer, which will point to end of the first level of the list
3) Repeat the below procedure while "curr" is not NULL.
    I) if current node has a child then
    a) append this new child list to the "tail"
        tail->next = cur->child
    b) find the last node of new child list and update "tail"
        tmp = cur->child;
        while (tmp->next != NULL)
            tmp = tmp->next;
        tail = tmp;
    II) move to the next node. i.e. cur = cur->next 

what is it the maximum number of the elements 

combination  array and hashtable 

public class Solution {
    public int longestConsecutive(int[] num) {

        Set<Integer> set = new HashSet<Integer>();
        
        for (int i : num) {
            set.add(i);
        }
        int max = 0;
        
        for(int i=0; i<num.length; i++){
            if(set.contains(num[i])){
                int next = num[i] - 1;        // 找比num[i]小一个的值
                int count = 1;
                set.remove(num[i]);            // 及时的移除，减少之后的查找时间
                while(set.contains(next)){
                    set.remove(next);
                    next--;
                    count++;
                }
                next = num[i] + 1;        // 找比num[i]大一个的值
                while(set.contains(next)){
                    set.remove(next);
                    next++;
                    count++;
                }
                max = Math.max(max, count);
            }
        }
        
        return max;
    }

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode sentinel = new ListNode(0);
        ListNode d = sentinel;
        int sum = 0;
        while (c1 != null || c2 != null) {
            sum /= 10;
            if (c1 != null) {
                sum += c1.val;
                c1 = c1.next;
            }
            if (c2 != null) {
                sum += c2.val;
                c2 = c2.next;
            }
            d.next = new ListNode(sum % 10);
            d = d.next;
        }
        if (sum / 10 == 1)
            d.next = new ListNode(1);
        return sentinel.next;
    }
}

divide and conquer

Put each item of the file into map1<key:user_id, list<pageID> >.
When list.size() == 3, create a new struct three_hits to hold the three pageID.
Put it in into map2<struct three_hits, int counter>.
Then, find the item in map2 with largest counter value.

If you want to quickly get an approximate result, use hash tables, as you intended, but add a limited-size queue to each hash table to drop least recently used entries.

If you want exact result, use external sort procedure to sort logs by userid, then combine every 3 consecutive entries and sort again, this time - by page IDs.

Why not just cut the log file into slices that are each big enough to hold in memory