RM

csharptrie project on Google Code

2010-10-06T21:52:21-07:00

Added project csharptrie - a C# implementation of trie data structure to Google Code.

building tree view from given child-parent pairs in hashmap

2010-08-23T15:50:22-07:00

Ex: The child-parent pairs are in a hashmap 'childParentMap' as shown below. The root node is with value 0.
1 -> 0
2 -> 1
3 -> 2
4 -> 2
5 -> 0

The tree node data structure has an int value and list of children tree nodes.



class TreeNode:

    int value

    IList children

    

    //constructor

    TreeNode(int value):

        this.value = value

        children = new List()

The code first traverses through the childParentMap hashmap to build the value->TreeNode hashmap 'valueNodeMap'. It traverses through it again to get child and parent values, their equivalent nodes and adds the child node to the parent node. The root node with value 0 is created separately (root of the tree).



TreeNode createTreeView(Hashmap childParentMap):

    // build value->TreeNode map

    Hashmap valueNodeMap = new Hashmap()

    foreach (KeyValuePair kvPair in childParentMap):

        int value = kvPair.Key

        TreeNode node = new TreeNode(value)

        if !valueNodeMap.ContainsKey(value):

            valueNodeMap.Add(value, node)

    

    // add root value 0 and root node to valueNodeMap

    int rootValue = 0;

    TreeNode rootNode = new TreeNode(rootValue);

    valueNodeMap.Add(rootValue, rootNode);

    

    // for child and parent values, find equivalent nodes and 

    // add child node as child to parent node

    foreach (KeyValuePair kvPair in childParentMap):

        int childValue = kvPair.Key 

        int parentValue = kvPair.Value

        TreeNode childNode = valueNodeMap[childValue]

        TreeNode parentNode = valueNodeMap[parentValue]

        

        parentNode.children.Add(childNode)

    

    // return root

    return rootNode

Time is O(n).

There is a recursive solution too but it takes O(n^2) time.

The code is similar to building a graph from an adjacency list.

[H/T ai, as, sc, jf, se]

bracket matching

2010-08-06T17:54:53-07:00

Check for brackets matching - curly, square, round, {}[]() - and return boolean.
ex: return true for
{}
{[()]}
{()[]}
return false for
{
}



bool bracketMatching(char[] str):

    bool result = true

    Stack stack = new Stack()

    

    //close-open bracket map

    Hashmap bracketMap = new Hashmap()

    bracketMap.Add('}', '{')

    bracketMap.Add(')', '(')

    bracketMap.Add(']', '[')



    foreach (char c in str):

        if (c == '{' || c == '[' || c == '('):

            stack.Push(c)



        if (c == '}' || c == ']' || c == ')'): 

            if (stack.isEmpty

()):

                 result = false

                break

            //tos should be open bracket and c close bracket

            char tos = stack.Pop()

            if (tos != bracketMap[c]):

                result = false

                break

    if (!stack.isEmpty()):

        result = false

    return result

[Hat tip to BR]

codejam 2010 qualifications

2010-05-22T15:31:29-07:00

qualifications problems

A Snapper Chain

The snappers are same as incrementing binary bits. The overflow is discarded. ANDing K with 111...N bits gives the state of the snappers after K snaps. The count of 1 bits of that number if same as N means the state is ON else OFF.

 string snapperChain(int n, int k)

    int nbit = (int) Math.Pow(2, n) - 1;

    int result = nbit & k;

    int count1 = count1bits(result);

    

    if (count1 == n)

        return "ON";

    else

        return "OFF";



int count1bits(int num)

    int n = num;

    int count = 0;

    while (n != 0)

        n = n & (n - 1);

        count++;

    return count;

B Fair Warning

I used this IntX code for 64+ bits data structure. The trick is to subtract the min of the array and find their gcd - which gives Tmax. ymin is calculated then. One way is to sort the array and find the gcd from index 1...N. Another way is to find the min and put checks for 0 in gcd function.



string fairWarning(IntX[] input)

    IntX Tmax = -1;

    IntX ymin = -1;



    //Array.Sort(input);

    IntX min = minf(input);

    

    for (int i = 0; i < input.Length; i++)

        input[i] = input[i] - min;

    Tmax = gcdf(input);



    if (Tmax == 0 || (min % Tmax) == 0)

        ymin = 0;

    else

        ymin = Tmax - (min % Tmax);

    

    return ymin.ToString()



//min of array

IntX minf(IntX[] input)

    IntX min = input[0];

    for (int i = 0; i < input.Length; i++)

        if (input[i] < min)

            min = input[i];

    return min;



//gcd of array

IntX gcdf(IntX[] input)

    IntX a = input[0];

    for (int i = 1; i < input.Length; i++)

        IntX b = input[i];

        if (i < input.Length-1 && a == 0)

            i++;

            a = input[i];

        if (i < input.Length-1 && b == 0)

            i++;

            b = input[i];

        a = gcdf(a, b);

    return a;



//gcd of a, b

IntX gcdf(IntX a, IntX b)

    if (a == 0 && b == 0)

        throw new ArgumentException();

    while (b != 0)

        IntX t = a % b;

        a = b;

        b = t;

    return a;

C Theme Park

Limits
1 <= T <= 50
gi <= k

Small dataset
1 <= R <= 1000
1 <= k <= 100
1 <= N <= 10
1 <= gi <= 10

Large dataset
1 <= R <= 10^8
1 <= k <= 10^9
1 <= N <= 1000
1 <= gi <= 10^7

My first solution was of O(R*N) time i.e. 10^8 * 10^3 which does not work for large dataset. The trick is to first calculate and cache the sums and save the next group position which takes O(N*N) time i.e. 10^6 and then add the sums in O(R) time i.e. 10^8 - the sum is calculated for each position i of N in cache[] and the next group index in nextCacheIndex[].



Int64 themePark(Int64 R, Int64 k, Int64[] q)

    Int64 totalMoney = 0;

    Int64 groups = q.Length;



    Int64[] cache = new Int64[q.Length];

    Int64[] nextCacheIndex = new Int64[q.Length];



    for (Int64 i = 0; i < groups; i++)

        Int64 sum = 0;

        Int64 nextIndex = i;



        Int64 groupCount = 0;

        //while sum <= k and not at the end of the *current* queue 

        while ((sum + q[nextIndex] <= k) && (groupCount < groups))

            sum += q[nextIndex];

            nextIndex = (nextIndex + 1) % groups;

            groupCount++;

        cache[i] = sum;

        nextCacheIndex[i] = nextIndex;



    Int64 index = 0;

    for (Int64 r = 0; r < R; r++)

        totalMoney += cache[index];

        index = nextCacheIndex[index];



    return totalMoney;

[codejam]

permutations and combinations of string - derivative

2010-05-14T23:23:26-07:00

This is a derivative of permutations of a string. For digits [1, 2, 3], we want [1, 12, 21, 123, 132, 213, 231, 312, 321]. The permute_wrapper loops through the input array to permute the sub-array with limit marking its end.



def permute_wrapper(digits):

    input = [i for i in range(1, digits+1)]

    print(input)

    output = [0 for x in range(len(input))]

    flags = [False for x in range(len(input))]

    depth = 0

    

    for i in range(len(input)):

        permute_(input, i+1, output, flags, depth, nums)

    

    return nums



def permute_(input, limit, output, flags, depth, nums):

    if depth == limit:

        num = 0

        factor = 1

        for i in range(limit, 0, -1):

            num = num + output[i - 1] * factor

            factor *= 10

        nums.append(num)

        return None

    

    for i in range(limit):

        if flags[i] == True:

            continue

        flags[i] = True

        output[depth] = input[i]

        

        permute_(input, limit, output, flags, depth + 1, nums)

        

        flags[i] = False

For combinations of digits, instead of using a string buffer for output, an int array is used. index is used to keep track of where to insert the digit. The number is between index and 0 of output array.



def combine_wrapper(digits):

    input = [i for i in range(1, digits+1)]

    print(input)

    output = [0 for x in range(len(input))]

    start = 0

    index = 0

    

    combine_(input, output, start, index, nums)

    

    return nums



def combine_(input, output, start, index, nums):

    if start == len(input):

        return None

    

    for i in range(start, len(input), 1):

        output[index] = input[i]

        

        num = 0

        factor = 1

        for x in range(index, -1, -1):

            num = num + output[x] * factor

            factor *= 10

        nums.append(num)

        

        index+=1

        combine_(input, output, i + 1, index, nums)

        index-=1

nine-digit polydivisible number with 1 to 9 exactly once: 381654729

2010-05-14T22:52:25-07:00

Arrange the digits 1 to 9 in order so that the first two digits form a multiple of 2, the first three digits form a multiple of 3, the first four digits form a multiple of 4 etc. and finally the entire number is a multiple of 9. It contains the digits 1 to 9 exactly once each. [Polydivisible number]

There are 9^9 9-digit numbers; 9^9 = 387420489. There are only 9! numbers with 1-9 appearing only once; 9! = 362880 (1000 times smaller set). So, the trick is to find those 9! first (using permutations or otherwise) and then check for polydivisiblity. 381654729 is the only number.

#checks if a number is polydivisible

#polydivCheck(381654729)

def polydivCheck(n, digts):

    for i in range(digts, 0, -1):

        if (n % i != 0):

            return False

        n = int(n / 10)

    return True



#finds permutation for array 'input' and puts the numbers in list 'nums'

def permute(digits, input, output, flags, depth, nums):

    if depth == len(input):

        num = 0

        factor = 1

        for i in range(digits, 0, -1):

            num = num + output[i - 1] * factor

            factor *= 10

        nums.append(num)

    

    for i in range(len(input)):

        if flags[i] == True:

           continue



        flags[i] = True

        output[depth] = input[i]

        

        permute(digits, input, output, flags, depth + 1, nums)

        

        flags[i] = False



#wrapper function to call the recursive 'permute' function

def permute_wrapper(digits):

    input = [i for i in range(1, digits+1)]

    output = [0 for x in range(len(input))]

    flags = [False for x in range(len(input))]

    depth = 0

    nums = []

    

    permute(digits, input, output, flags, depth, nums);

    

    return nums



#calls 'permute_wrapper' and for each number checks for polydivisibility

def getPolydivNums(digits):

    nums = permute_wrapper(digits)

    numbers=[]

    for num in nums:

        if polydivCheck(num, digits):

            numbers.append(num)

    return numbers



#start(9)

def start(digits):

    nums = getPolydivNums(digits)

    for n in nums:

        print(n)

[Hat tip to JF]

print all word combinations from phone number

2010-05-02T08:01:53-07:00

Print all words combinations from phone number.
ex: 111-1111 -> AAA-AAAA, AAA-AAAB ... CCC-CCCC

char charkeyMap(int digit, int position)
ex:
charkeyMap(1, 0) = 'A'
charkeyMap(1, 1) = 'B'
charkeyMap(1, 2) = 'C'



void printCombinations(int[] in):

    char[] out = new char[in.length]

    

    //first combination ex: 111-1111 -> AAA-AAAA

    for(int i = in.length -1; i >= 0; i--):

        out[i] = charkeyMap(in[i], 0)



    int i

    while (true):

        out.print()

        i = in.length - 1;

        

        while (true):

            //if A then B

            if out[i] == charkeyMap(in[i], 0):

                out[i] = charkeyMap(in[i], 1)

                break

            

            //if B then C

            if out[i] == charkeyMap(in[i], 1):

                out[i] = charkeyMap(in[i], 2)

                break

            

            //if C then A and let it loop for the adjacent digit

            if out[i] == charkeyMap(in[i], 2):

                out[i] = charkeyMap(in[i], 0)

                //let it loop

            

            i--

            if i < 0 break

        

        if i < 0 break

fix duplicates in sorted array

2009-09-26T13:02:01-07:00

12233344445 -> 12345

 
//using 3 pointers
fixDuplicatesInSortedArray(Integer[] a):
    start = 0
    end = 0
    destination = 0

    while(start < a.length):
        while(end < a.length && a[end] == a[start]):
            end++
        end--
        
        //copy the distinct element
        a[destination] = a[start]
        destination++
        
        start = end + 1
        end = start

    //null out the rest
    while destination < a.length:
        a[destination] = null

    return

//using 2 pointers
fixDuplicatesInSortedArray(Integer[] a):
    prev = 0
    curr = 1
    
    while curr < a.length():
        while curr < a.length && a[curr] == c[prev]:
            curr++
        if curr == a.length() break
        
        prev++
        a[prev] = a[curr]
        curr++
    
    //null out the rest
    prev++
    while prev < a.length:
        a[prev] = null
    
    return

[Hat tip to MG]

topical arguments

2009-09-17T08:23:49-07:00

[Hats off to xkcd - images from Time Travel, Voynich Manuscript]

induction too

2009-07-26T00:05:52-07:00

My lame attempt at this.

[Hats off to xkcd - images from Fetishes, No Pun Intended, Voynich Manuscript, Designated Drivers]

Head First Design Patterns book

2009-07-12T22:03:00-07:00

Head First Design Patterns (link) book: It is such a nice read. A must read for Software Engineers. It is, although, a preface to the GoF book.

It is very visual, simple to read, easy to understand, highly exemplified. And it is fun to read.

dfs, bfs without recurssion

2009-06-15T17:31:51-07:00

BFS (Breath First Search) without recurssion:

BFS is a first in first out search. So, a non-recursive version of BFS can be done using a queue.

void bfs_nonrecursive(Node root) : 

    Queue queue = new Queue()

    while (true): 

        curr = queue.pop()

        if curr == null:

            break

            

        queue.push(curr.left)

        queue.push(curr.right)

        curr.printValue()

Time: Since each node is visited once, O(n) time is required.

Space: We save the nodes at each level. We have to save a maximum of n/2 nodes for the last level. i.e. O(n) space is needed.

DFS (Depth First Search) without recurssion:

DFS is a first in last out search. It is a recursive process. Recursion uses a stack implicitly. So, a non-recursive version of DFS can be done using a stack. Since we want to hold off visiting a particular node until all of its children are visited, we have to push the node again on the stack. We need to differentiate when we revisit the node ("backtracking" in recursion) so that we do not push its children again on the stack. For that we use a Hashmap data structure which serves as a flag to denote if a node is already visited and its children are added to the stack.

void dfs_nonrecursive(Node root) :

     Stack stack = new Stack()

    stack.push(root)

    

    Hashmap visited = new Hashmap()

    while true :

        curr = stack.pop()

        if curr == null:

            break

        

        //if curr has children and curr not in visited

        if (curr.left != null || curr.right != null) && visited.get(curr) == null :

            stack.push(curr)

            stack.push(right)

            stack.push(left)

            

            visited.put(curr)

            continue

        

        curr.printValue()

Time: We visit the non-leaf nodes (n/2) twice and the leaf nodes (n/2) once. So, 2*(n/2) + n/2 = O(3n/2) i.e. still O(n) time.

Space: Hashmap visited saves references to the non-leaf nodes only. For tree of n nodes, visited would saves 2^logn-1 = n/2 still O(n) space. The stack would save only O(logn) nodes.

Induction

2009-06-15T13:35:25-07:00

PS: For information, read Josephine's problem (Cheating Husbands Puzzle) over here.

[Hats off to xkcd - images from Hobby and Numerical Sex Positions]

Windows 7

2009-05-06T00:17:12-07:00

A few days back, I posted about installing Ubuntu on my laptop instead of going with Vista. After some really onerous trials at installing XP went in vain AGAIN, I decided to go with Windows 7 beta (fingers crossed).

That said I can safely say from my experience is - Lenovo's ThinkPad support is a farce and ridiculously incompetent (I heard previously that ThinkPads' support made it a ThinkPad).

It is about 120 days after that I am able to get Windows on my laptop. The laptop is about 120 days old. I refuse to pay for recovery DVDs. I refuse to install Vista.

Update: The only issue I have had so far with Windows 7 is the sound did not work as default (Volume Control Options - Sound Devices - check Speakers).

Update 5/6: Updated to RC (build 7100) from beta build 7077 from here and here.

+c

2009-05-01T11:15:23-07:00

I bit the bullet. Took the leap. Faced the music. Peed in the wind.

I switched to Chrome (Dev Channel) as default browser.

Update:

I made my Chrome's launch icon --incognito.

I made my default browser registry setting as --incognito for http and https.

I made all the above changes on all the machines I use.

Some people do not like history. Some people do not like thumbnails. Some people do not like autocomplete for the URL bar. Some people like to type.

Chrome developers, please provide a simple way to always open in incognito - and get a nice spot in heaven. Remember karma. Remember - 'Don't do evil'. ;)

Is this an original or copy?

2009-03-12T21:30:52-07:00

I created a copy for you and I want to keep the original. But I got it mixed up and now I do not know which one is the copy and which one is the original.

(silence)

It is the same paper quality. And, I did not mark on the originals with a red/blue pen or highlighter or pencil. They both are same in every aspect.

(silence)

Damn! I will just make another copy and give that to you!

(silence)

PS: There have been numerous occasions where I can relate to this event (like how one should know if the current problem relates to an NP-complete problem :D).

sudoku evil

2009-03-03T20:23:32-08:00

[web sudoku]

Sometime back, I had solved this sudoku. After filling in the few blanks in blue, it did not budge. So I had assumed the positions of the 1-3 pair in the top right square.

With any sudoku, you should not have to assume. I tried it again and found it to be true.

I was stuck again at the same state. In the bottom right square, 3 and 5, even though possible in different blocks, paired. After that, it fell apart.

Nice Video on Credit Crisis

2009-02-22T19:30:57-08:00

The Crisis of Credit Visualized from Jonathan Jarvis on Vimeo.

This is a nice work by Jonathan Jarvis who provides a simple and logical explanation of the current Credit Crisis.

Key points the video focuses on are:

Terms involved in credit crisis: Sub-prime Mortgages, Collatarized Debt Obligation, Credit Default Swaps and Frozen Credit Market.
How Home Owners (Main Street) and Investors (Wall Street) were connected through the Investment Banks.
How credit and leverage normally works and how Investment Banks abused it.
The entities involved in Housing market: Home Owners, Broker, Lender, Investment Banks, Investors.
What is Collaterized Debt Obligation (a bunch of Safe, OK and Risky mortgages).
How Investment Banks sold the so-called safe investments (mortgages with AAA ratings provided by Rating Agencies) to the Investors interested only in safe investments.
How the Lenders sold the defaulted Prime Mortgages to "less responsible" Home Owners (the turning point) as Sub-prime Mortgages which were later bought by Investment Banks. (The "less responsible" Home Owners eventually defaulted too leading to the vicious cycle.)
Why the Housing prices went down (due to more supply of houses in the market than demand) and how it led to the crash of the Housing Market (either Home Owners defaulted or forsake the depreciating asset).
How Investment Banks (and even Investors) are left with such currently risky Housing assets that no one else (Investors, others Banks, etc.) wants to buy. This led to the Frozen Credit Market.

List

2009-04-08T20:53:05-07:00

The List with basic APIs:

boolean add(Object)
void add(Object, index)
Object remove(index)
int size()



class List:

    

    //data members

    int end//end element, zero-based

    Object[] list//array

    

    //constructors

    List():

        list = new Object[10] //default = 10

        end = -1

       

    List(int size):

        list = new Object[size]

        end = -1

    

    //methods

    boolean add(element):

        //return false if element does not satisfy certain conditions

        

        //increase array size if maxed out

        if list.length() = end+1 :

            //create new array and copy elements from current array

            sizeNew = getNewSize() //determine the new size

            listNew = new Object[sizeNew]

            for i = 0 to end :

                listNew[i] = list[i]

            list = listNew

            

        end++

        list[end] = element

        return true

        

    void add(element, index):

        if index > end :

            throw exception('out of bounds')

  

        //increase array size if maxed out

        if list.length() = end+1 :

            //create new array and copy elements from current array

            sizeNew = getNewSize() //determine the new size

            listNew = new Object[sizeNew]

            for i = 0 to end :

                listNew[i] = list[i]

            list = listNew

            

        //shift elements

        for int i = end down to index :

            list[i+1] = list[i] 

        

        end++

        list[index] = element

       

    Object remove(index):

        if end < 0 :

            throw exception('list empty')

        if index > end :

            throw exception('out of bounds')

        

        removedObject = list[index]

        //shift elements

        for int i = index to end-1 :

            list[i] = list[i+1]

        

        list[end] = null

        end--

        

        return removedObject

    

    int size():

        return end+1

[Hat tip to TL]

typing

2009-04-08T20:53:31-07:00

[from wikipedia]

Recently, I read too many good articles on this topic and I thought I should write on it too due to its importance. :D

The keyboard is the most used input interface with the computer (even more than the mouse). So typing speed does matter.

Touch typing is typing without the sight of the keys. Above is the layout of the zones for each finger (QWERTY). Some people can correctly touch-type fast without sticking to these zones. They have invented their own typing technique and would not want to change zones now. However, if they do, it would certainly boost their speed in the long run.

I always recommend touch typing to others. And sticking to the zones.

There should be enough sites to learn touch-typing and speed testing. And there is Typing of the Dead :D. For programmers, 70 rpm (as per Steve Yegge) should be achievable.

Recently, I found that I was using the wrong fingers for two keys and I am trying hard to switch - and it is turning out to be hard. The more you are used to, the harder it is to correct. So correct early. Use both hands for combination keys (ex: Shift key for caps). I think Typing 101 is a really good investment.

A difference of keys throws me off and for that reason I always dread the keyboard design in laptops (not to mention the difference from vendor to vendor).

I read about ergonomic keyboards which increase typing to some extent (and reduce muscle strain). I might look into one. But I would need to carry it around then. :D

I read about Dvorak Simplified Keyboard and I think it would have been a great experience to have used it. I would have been able to compare my speeds on both layouts. However, the inability to use the Ctrl X, C, V keys is a con. Which leads me to speculate that Dvorak keyboard is more for typists than programmers.

Again to reiterate. We are typists first, programmers second.

[Hat tip to Jeff Atwood, Steve Yegge]

heapsort

2009-02-07T14:53:51-08:00

In heapsort,
- First put the elements of the array in a heap property (max-heap has the greater elements as parents) so that the first element is the max.
- The first element (root of heap) is swapped with the last element of the array (last leaf node of the heap) and the array is again put in heap property by sifting up or sifting down.



heapSort(array) :

    //get max at root

    maxheapify(array)

    

    end = array.length() -1

    

    while end > 0 :

        // put max at the end

        swap(0, end)

        end--

        // put heap in max-heap order again

        siftDown(0, end) // or

siftUp(0, end)

Sift-Down version: The sift-down version sifts the root or start down the heap. It takes O(n) time.

The sift-down version takes O(n) time.



maxHeapify(array) :

    start = (length-2) /2 //last parent node

    while start >= 0 :

        siftDown(start, length-1)

        start--



siftDown(start, end) :

    root = start

    lastLeaf = end

    

    while root*2 +1 <= lastLeaf :

        child = root*2 +1

        if (child+1 <= lastLeaf) and (a[child+1] > a[child]) : 

            child = child+1

        if a[root] < a[child] : 

            swap(a[root], a[child])

            root = child

        else :

            return

Sift-Up version: The sift-up version builds the heap top-down as if starting with an empty heap and inserting new nodes. The child or end is sifted up to the root.

The sift-up version is slower and takes O(nlogn) time.



maxHeapify(array) :

    end = 1

    while end < length :

        siftUp(0, end)

        end++



siftUp(start, end) :

    root = start

    child = end

    

    while child > root :

        parent = child-1 /2

        

        if a[parent] < a[child] :

            swap (a[parent], a[child])

            child = parent

        else :

            return

The heap-sort with either version has O(nlogn) time efficiency.

Gmail with new ways to label mail

2009-02-05T06:49:35-08:00

Gmail has heard me and have rolled out faster ways to label conversation. However, applying multiple labels to a conversation is still tedious.

I have mixed thoughts of the new look that comes with the buttons. It is an irony to Gmail's clean interface.

The simulation of 'folders with the move to' - I do not use it, so it does not matter to me. It is a little noise on screen. But it seems like a lot of people desire it for Gmail to have come up with a compromise. Update: On another note, if Inbox Zero is a great deal for you, this would be really helpful.

Find the distinct words from a text file

2009-02-01T20:23:05-08:00

I'm repeating this post from here, but I think it deserves it because of its elegance.

--

The data structure of the trie and its addWord() method remains the same.



class trieNode:

    trieNode[26] children

    char c

    int countPrefix // words with prefix from root to current node

    int countWord // complete words for this current node 



void addWord(trieNode node, string word): 

        //end of the word

        if (word = ""):

            node.countWord = node.countWord +1

            return



        //do stuff with current node

        node.countPrefix = node.countPrefix + 1

        

        //go to next node 

        char first = firstChar(word)

        if (node.children[first] == null):

            node.children[first] = new trieNode()

       

        addWord(node.children[first], firstCharRemoved(word))

Another example is to find the distinct words from a text file. At first, I thought of a Hashmap which acts like a boolean array for the words as index. In which case, the time required is O(n) and space required is that of the distinct words. With Trie, the solution is better and elegant in terms of space required, time required is O(length). In case of words 'anon', 'an', 'a', the Trie formed (''-a-n-o-n) would just need space for a-n-o-n. Thus, the advantages of Trie would show over a Hashmap when many words have overlapping prefixes. Once the Trie is formed, a DFS would print the distinct words as follows.



//do DFS on the trie

StringBuilder sb = new StringBuilder()

dfs(root, sb)





void dfs(trieNode node, StringBuilder sb):

    sb.append(node.c)

    

    if (node.countWord > 0):

        print(sb)

    

    for (trieNode child : node.children)

        if (child != null):

            dfs(child, sb)

    

    sb.length = sb.length -1

[Hat tip to B.]

Google's and gmail's malware and spam issues for today

2009-01-31T19:41:13-08:00

Though this is not as scary, there is a lot of "hubbub" about it - Google marked my site as malware. It is obvious that it must have been a human error.

"We work with a non-profit called StopBadware.org to come up with criteria for maintaining this list, and to provide simple processes for webmasters to remove their site from the list.

We periodically update that list and released one such update to the site this morning. Unfortunately (and here's the human error), the URL of '/' was mistakenly checked in as a value to the file and '/' expands to all URLs.

...

We will carefully investigate this incident and put more robust file checks in place to prevent it from happening again."

- Marissa Mayer

The original post from Google was updated (updated text in blue) and it looks like Google is trying (though it might not be intentional) to shift blame on StopBadware.org.

It's not human error to include even junk input to a program. It's a human error NOT to check it though - URL '/' is a valid input in this case.

Almost 6 hours later, Gmail issues a statement saying that it uses Google's malware filters and mail might have went to spam.

Now this is scary because it happened to me (nobody searches my blog :P). Below is a cool thing though. I have a soft corner for Gmail's spam team - I think it is quite under-appreciated.

"We're working to roll out an automated fix to put these legitimate messages back into your inboxes, and we expect this to happen within a day. In the meantime, if you were expecting a critical message this morning, please check your spam folder. (We tune our spam filters well enough that ordinarily you should never have to check your spam folder.)"

- Gmail Blog

1.10 MBps

2009-02-03T21:05:08-08:00

The ~$50 spent on internet is the best money spent ever.

- Net Neutrality Proponent.

I was finally able to run the Glasnost test (m-labs) and everything seems to be good.