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 $.

IIT Delhi MTech Interview Question: Find formula for coordinates

On a grid, the numbering is done as shown in the image below. Dotted lines go up and solid lines go down.

Find out the formula to describe number on grid given the standard $ (x, y) $ coordinate. Credit goes to my colleague Jignesh Parsana for the problem.

Update: I found that this is Cantor's Pairing Function as given at http://szudzik.com/ElegantPairing.pdf

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.

Google Interview Question : Design a cache replacement policy for a hard-disk if the stream of sector requests is already known

Problem statement: You are given a hard-disk with large number of sectors say $ N $ and that has a facility to store $ k $-sectors in cache such that read time for cache is very less compared to the time to read sector from a hard-disk and $ N >> k $. Assume the seek time is negligible compared to read-time. You are given a stream of requests $ s_i \text{ such that } 0 <= i <= R, k << R << N $.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Chapter 11

The author discusses about working in team and the reasons for doing so such as:

• Large projects with thousands of classes cannot be handled by a single person
• Creating a whole application by a single person may miss the deadline
• Creating a software involves not just developing an application but documentation, help files, installer, graphics, a website and many more things so it is better to have a team with different skills

The author then discusses about team management and the 'soft' issues involved in managing the team such as:

• Choosing a structure: There are two alternatives to deciding a team structure
• Community of equals: Each member on the team is recognised of being equally capable.
• Hierarchy:
• Tracking progress: The author suggests email-notification tool from source code control module or web page refresh from build tools. The author suggests 3 x 3 approach where each member regularly sends a report to other members of the team or just the project manager containing:
• Three accomplishments for the previous week
• Three obstacles to progress from the previous week
• Three plans for the coming week
• Avoiding your incompetence: The author discusses the Peter Principle, i.e. In a hierarchy, every employee tends to rise to his or her level of incompetence. In most organizations, people are promoted when they do their job well but never demoted. The author gives following tips to become a competent manager:
• Start with a small team
• Spend some time on management chores
• Pay attention to everybody's ideas
• Read literature on software project management

The author then discusses tools for distributed teams such as:

• E-mail:
• Use spam protection
• Keep project related emails organized
• Read emails in a batch
• Instead of sharing every email with everyone, try sharing items through public folders or a news server
  
• Instant Messages:
• Read messages in a batch
• Keep everybody on the same service
• Keep an archive of conversations
• Online Workspaces: The author discusses use of online workspaces like GotDotNet or SourceForge and their pros and cons.
  
• Wikis: The author provides several wikis available and what their benefits and disadvantages are.
  
• Microsoft Sharepoint: The author discusses advantages and disadvantages of Microsoft sharepoint and groove.
  
• Programmer's tools: The author discusses CodeWright and CodeReview.
  

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.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Chapter 10

The author discusses importance of logging application activity both during development and after shipping and methods of logging. The logging during development is required since

• Log allows you to understand actions that led to a bug
• Log helps clarify the order of events
• Some bugs only reproduce when running without a debugger
• Some bugs occur after thousands of calls of a function

The author suggests to make it easy for end user to turn logging on or off. The author advises to include following in the logs:

• Error messages and information including stack trace
• The state of internal data structures
• User actions
• The timings of significant actions
• Important environment information
  

The author then discusses about logging tools including:

• The Trace and Debug classes of .Net framework -
• The EventLog class - This is used to log events to Windows Event Log
• Enterprise Instrumentation Framework
• Logging Application Block
• log4net

If there is no logging included in application, the author discusses about diagnostic tools like System Information to collect information from user machine.