Create a word cloud from source code of an application

I am currently working at Druva Software. I wanted to create word-cloud from the source of the application I was working on. Here is the command I used:

find ./ -type f -print0 | xargs -0 cat | tr '[:space:]' '\n' | tr -c '[:alnum:]' '\n' | sort | uniq -c

This will generate a text file in a format " 'occurence count' 'word' " on each line. The top word would be empty space or new line which you can simply ignore. Since the command searches in binary files too, I got some non-relevant words too which I removed. I converted the file in comma-separated values and uploaded it to wordle and below is what I got. The application seem to be very 'self'ish.

Find formula for coordinates : Solution

The problem statement is here. Observe that the $ (x, y) $ coordinate appears in the $ (x + y) ^{th} $ solid line. The $ n^{th} $ diagonal has $ 1 + 2 + 3 + ... + n $ elements before it, i.e. $ (x + y) ^{th} $ diagonal has $ \frac{(x+y)(x+y+1)}{2} $ elements before it. Add the $ x $ elements to it to get the point at coordinate $ (x+y) $. So the answer is $ \frac{(x+y)(x+y+1)}{2} + x $.

Design a cache replacement policy for a hard-disk if the stream of sector requests is already known : Solution 1

Problem statement is here.

For the first $ k $ requests, all the sectors are cached. For every request $ s_i, k < i <= R $, we have $ k + 1 $ sectors to put in $ k $ cache location. To discard one of the sectors, we can give weight to every sector which is equal to the difference between the index of next request for that sector and the index of the current request. So if the next request for sector $ m $ is appearing at index $ j $ then the weight of that sector is $ j - i $. Choose the $ k $ sectors with the minimum weight.

Find depth of a k-ary tree given a parent array : Solution 3

The problem statement is mentioned here. The first solution is here. The second solution is here.

While traversing up the tree from a leaf node, we can avoid the whole path till root if we can utilize the depth already found for nodes that were traversed earlier. This will reduce the problem to $ O(N) $ as below with extra space of $ O(N) $.

Let DEPTH be an array of length N
Initialize all elements of DEPTH to -1
FINDDEPTH(i)
    if DEPTH[i] == -1
        if P[i] == -1
            DEPTH[i] = 0
        else
            pDepth = FINDDEPTH(P[i])
           DEPTH[i] = pDepth + 1
    return DEPTH[i]

Let L be an array of length N
Initialize all elements of L to true
for each node i from 0 to N-1
   if P[i] is not -1
       set L[P[i]] to false
   end if
end for
initialize maxDepth to 0
for each node i from 0 to N-1
    if L[i] is false, continue next node
    depth = FINDDEPTH(i)
    if maxDepth < depth
       set maxDepth = depth
    end if
end for

As can be seen, the time complexity of the algorithm is $O(N)$ where $N$ is the number of nodes. The space complexity is $O(N)$. Thanks to my colleague Jignesh Parsana to help point to this solution.

Find depth of a k-ary tree given a parent array : Solution 2

The problem statement is mentioned here. The first solution is here.

We can reduce some processing by observation that we only need to find the depth of leaf nodes. Any node whose index appears in the parent array $P$ is an internal node and do not need to be processed. The modified solution is as below:

Let L be an array of length N
Initialize all elements of L to true
for each node i from 0 to N-1
   if P[i] is not -1
       set L[P[i]] to false
   end if
end for
initialize maxDepth to 0
for each node i from 0 to N-1
    if L[i] is false, continue next node
    set parent to P[i]
    set depth to 1
    while parent is not -1
       set parent to P[parent]
       increment depth
    end while
    if maxDepth < depth
       set maxDepth = depth
    end if
end for

As can be seen, the time complexity of the algorithm is $O(N^2)$ where $N$ is the number of nodes. Thus the worst case is still not improved. The space complexity is $O(N)$.

Find depth of a k-ary tree given a parent array : Solution 1

The problem statement is mentioned here.

Following is the first solution.

initialize maxDepth to 0
for each node i from 0 to N-1
    set parent to P[i]
    set depth to 1
    while parent is not -1
       set parent to P[parent]
       increment depth
    end while
    if maxDepth < depth
       set maxDepth = depth
    end if
end for

As can be seen, the time complexity of the algorithm is $O(N^2)$ where $N$ is the number of nodes. The space complexity is $O(1)$.

Find Top N : Solution 3

The problem is described here. Solution 1 is here. Solution 2 is here. In both the earlier solution, we used some in-built function offered by IBM Lotus Domino XPages Server side Javascript. In this solution, I will just try to find the optimal solution theoretically without using any in-built functions.

In my MTech thesis, I had worked on multi-pattern matching algorithm, Aho-Corasick. The algorithm basically creates a finite state machine from a list of patterns that are to be searched in a document. A sample FSM created for input strings {he, him, his, she, her} is shown in the image to the left. If we modify the state machine in such a manner that it also keeps the count for a particular string in the end state, the machine can actually work for finding top-N strings from a list of strings.

Now about the time and space complexity, you can clearly see here that the time to create the state machine is $O(|S|)$ where $|S|$ is nothing but the cumulative length of all the strings together. In the second pass, we can keep a list of Top $N$ strings with their occurrence count and then go through each end state and insert/replace the string represented by that end state in the Top N strings list if the occurrence count is higher than any of the string inside the list. This second pass can take $O(|S| \times N)$. This makes it the optimal algorithm in terms of time complexity but space required is quite huge, to the tune of $O(|S|)$.

I thought there might be already some work in this area and found burstsort. This is the fastest sorting algorithm found till 2007 and uses trie. It was discovered by Ranjan Sinha. I found that the space requirement reduces a lot by using the technique mentioned in this algorithm. This is the optimal algorithm in terms of both time and space complexity.

Find Top N : Solution 2

The problem is described here. Solution 1 is here. Server-side Javascript in XPages in IBM Lotus Domino offers a function sort on an array.

Let S strings be stored in an Array names. Calling names.sort() returns sortedNames. Let topNames stores the top N strings with highest occurrence count found so far in descending order of occurrence and topCount keeps track of respective occurrence count. Following is the rest of the algorithm.

For each string s in sortedNames
Begin
   Let start,end store index of s in sortedNames
   Advance end till sortedNames[end] becomes different from s
   Set uniqueCount = end - start
   For each count c in topCount
      if uniqueCount is greater than c
         Begin
            move all the elements in topNames and topCount back by one
            insert uniqueCount in topCount and s in topNames
         End
   Advance sortedNames by uniqueCount
End

Since I don't have complexity numbers for Array.sort, I take the worst case and assume it to be of $O(S^2)$. After that the above algorithm is executed which, if all the strings are unique, take $O(S \times N)$ time. So the time complexity of this algorithm is $O(S^2)$. Space complexity is $O(S + N)$. Just remember that in both the solutions, the comparison of strings are counted. So the algorithms depend on not just the number of strings but on their length too.

Find Top N : Solution 1

The problem is described here. Server-side Javascript in XPages in IBM Lotus Domino offers a function @Unique.

Let S strings be stored in an Array names. Passing this to @Unique returns uniqueNames. Let topNames stores the top N strings with highest occurrence count found so far in descending order of occurrence and topCount keeps track of respective occurrence count. Following is the rest of the algorithm.

For each string u in uniqueNames
Begin
   Initialize uniqueCount to 0
   For each string n in names
      if n matches u, increase uniqueCount
   For each count c in topCount
      if uniqueCount is greater than c
      Begin
         move all the elements in topNames and topCount back by one
         insert uniqueCount in topCount and u in topNames
      End
End

Since I don't have complexity numbers for @Unique, I take the worst case and assume it to be of $ O(S^2) $. After that the above algorithm is executed which, if all the strings are unique, take $O(S \times (S+N))$ time. So the time complexity of this algorithm is $ O(S \times (S+N)) $. In most of the practical scenarios, $S >> N$, so the time complexity can be assumed to be $O(S^2)$. Space complexity is $O(S + N)$.