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.

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

The author discusses about how to manage risk and bugs in software development. The author divides risk management in following

1. Risk Assessment: The author suggests to brainstorm a list of things that might go wrong for risk assessment including things that might impact the cost, schedule or quality of the product. The author then asks the reader to order the list of risks based on importance. This is achieved by assigning probability and cost to each risk and multiplying them to get the impact.
   
2. Risk Control: After the risks have been identified and prioritized, the author advises to create a risk management plan where the reader needs to specify what he is going to do to mitigate the risk.
3. Top Five Risks List: The author advises the reader to maintain top five risk list including its previous rank and how long the risk is on the list.
   

The author then discusses about Bug Triage, a term that refers to prioritizing bugs based on their criticality and decide on what to do about them. The author then provides following list of resolutions that can be applied to bugs:

• By design
• Duplicate
• Postponed
• Not reproducible
• Won't fix
• Reassigned
• Fixed

The author then discusses different types of software testing such as:

• Unit Testing - This is done by developers to ensure a function or unit is bug-free.
• Functional Testing - This is is carried out by testers to make sure the application confirms to the requirements and specifications.
  
• Conformance Testing - This ensures the application confirms the industry standards.
• Compatibility Testing - This ensures that the application runs in different environments including hardware, operating systems, browsers etc...
  
• Performance Testing - The goal of this testing is to identify performance issues and creating benchmarks.
• Stress Testing - The goal is to identify how the application fails when it is subjected to excessive stress. It involves simulating large number of users, low RAM, CPU contention etc... to make sure the application failure doesn't result in damage to operating system or data loss.
  
• Regression Testing - This involves making sure that new features didn't break the existing functionality.
• Smoke Testing - This involves running quick tests to verify that major features work.
• Black-box Testing - The testing of components is done based solely on their interfaces.
• White-box Testing - Internal behaviour of the components is tested with full knowledge of the implementation.

The author provides some tips to effectively test the application when there is no separate quality assurance department. The author also suggest to take every bug as a learning experience rather than as a deficiency in coding skills of a developer.

The author then provides following tips to create a test network:

• Buy pre-assembled machines
• Buy name brands
• Buy serious development hardware
• Store data separately
• Keep drive images
• Use virtual machines
• Use KVM switches
• Get your own domain
• Use a firewall
• Set aside test machines
• Set aside a build machine
• Use a mix of machines for testing

The author then discusses about bug-tracking tools. The author then provides a list of issues to consider while deciding on a bug-tracking tool:

• Price
• License Fee structure
• Cross-platform availability
• E-mail notification
• Allow outside access
• Allow custom information
• Differentiation between bugs and feature requests
• Integration with source code control and requirements tool
• Flexible workflow
• Storage Format

The author then provides an example bug-tracking tool and how he used it to track one of the bugs for his own application.

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

The author discusses that code generation is the core activity of any developer and his focus in this chapter will be on code generation tools. The author suggests to spend time on thinking about automating a repetitive task instead of doing it. The author then gives an example of generating stored procedures using a tool. The code generation tools are classified in two categories:

• Passive that dumps the code and forgets
• Active which are then classified in several other categories
• Code munger
• Inline-code expander
• Mixed-code generator
• Partial-class generator
• Tier generator
• Full-domain language

The author clarifies that code-generation is not just restricted to code but a variety of end products can be developed using the technology such as:

• Database access code
• User interface code
• Documentation
• Unit tests
• Web services
• DLL wrappers for legacy code
• Configuration files or initialization files
• Scripting files
• Installation files

The author then discuss a specific example of generating code directly from a database table using MSDataSetGenerator tool in .NET. The author then also provide a list of other tools available and briefly mentions their functionality. The author then provides an example of how he uses one of the code generation tool to help create code for his DownloadTracker application. The author then provides a list of pros and cons of using code generation tools.

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

The author discusses about reusing the code in such a manner as to increase efficiency. The author then talks about following tools:

• Ildasm: This tool is intermediate language disassembler. The author then provides an example of disassembling an assembly.
• Reflector: This tool translates the MSIL code to C# or VB.NET code.
• Nogoop: This tool allows to inspect and use a .NET component or class.
• Snippet compiler: This tool allows you to write code to exercise a new component.

The author then discusses about several sources of reusable code including .NET framework class library, Microsoft application blocks, logidex .NET library and free sources like CodeProject and GetDotNet.

The author then discusses a tool FxCop which can be used to check if a class library confirms to design guidelines suggested by Microsoft.

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

The author discusses the importance of IDE (Integrated Development Environment) in this chapter. It is not possible to create an IDE that suits every developer and that's why customisation is required. The author then provides some of the customisation that can be used in Visual Studio.NET environment. The author then talks about using macros in Visual Studio environment. The author provides examples of visual studio add-ins that analyzes source-code and provides useful information such as lines of code in each module that helps distinguish simple and complex modules, lines of comments that provides information about under-documented or over-documented module, easy reference to different classes/methods in the source code, suggestions to improve performance of the code, etc...

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

The author talks about integrating testing into development process using the techniques of test-driven-development and refactoring. The author discusses different kinds of testing such as:

• Unit Testing
• Integration Testing
• System Testing
• Stress Testing
• Beta Testing
• Acceptance Testing

The author then provides a typical set of steps followed by developers in a team and suggests to have system testing done by somebody other than the one who has written the code.

The author provides a list of unit testing tools available. The author then uses one of the tools and write unit test cases for his Download Tracker application. The author then discusses Test Driven Development and provides two easy steps followed in the process:

• Write a failing automated test before any code
• Remove duplication

The author then applies the methodology to his own Download Tracker application to provide example.

The author then introduces the concept of refactoring, the process of changing a software system in such a way that it does not alter the external behaviour of the code yet improves its internal structure. The author then provides a list of tools that can be used for automated refactoring.

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

The author talks about defensive coding in this chapter whose goal is to write code that makes it easy to find problems and make modifications.

The author discuss about usage of assertions to detect errors in code. The author provides following two guidelines:

• Assertions should not have side effects.
• Avoid assertions to test compiler/language issues

The author then talks about exceptions, the exception mechanism in C#, the reason for creating custom exceptions and the guidelines for creating custom exceptions in C#. The author then implements his own custom exception for Download Tracker application. The author then provides following guidelines for good exceptions:

• Exceptions are for exceptional situations
• Don't create unnecessary custom exceptions
• Constructors with a string value should be used
• Pass exception from low level routine to higher level routine with enough information

The author then examines the debate of whether to use comments or have self-documenting code. The author likes the first approach better and classifies comments in following different categories:

1. Noise comments: They just repeat what the code says and does not increase the readability and should be avoided.
2. Placeholder comments: They are note to your future self.
3. Summary and Intent comments: Summary comments summarize a lot of code in short English statements. Intent comments do not explain what the code does, it explains why it does it in a particular manner.

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

In this chapter the author talks about how to use source code control tool effectively. The author provides following list of commands for a novice user to learn:

• Create Project
• Add
• Get
• Checkout
• Revert
• Check In

The author then enlists following commands for level 2 user:

• Label
• Merge
• Branch
• Share

The author then specifies following commands to be used by an expert user:

• Cloak
• Delete
• Move
• Rename
• Pin
• Rollback

The author then specifies a list of source code control tools and their pros and cons. The author provides following list of characteristics to look at when deciding on a source-code control system:

• Price
• Concurrent Development Style (checkout-edit-checkin vs edit-merge-commit).
• Repository
• Internet Friendliness
• IDE Integration
• Cross-platform support

The author then talks about best practices that needs to be followed including:

• What to put under source code control
• Checking out as less files as possible
• Putting comments at the time of check-in
• Proper use of labels
• Maintaining discipline in branching
• Integrate bug-tracking tool with source code control tool

The author then provides the source code control created for his Download Tracker tool.

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

The author talks about how to organize project in three different ways:

• Architectural perspective addresses the overall shape of the application
• Project perspective addresses the construction of the application
• The staged delivery perspective addresses the release of the application

The author then provides definition of architecture with two common elements:

1. Highest level breakdown of a system into parts
2. Decisions that are hard to change

The author then provides three stages of software construction:

1. Architectural stage involves important decisions
2. Design stage involves detailed plans for writing the application
3. Implementation stage involves writing code

The author then draws architecture of its Download Tracker application. The author then talks about UML and tools that can be used to model architecture in form of UML.

The author talks about design patterns and how they help at architecture level. The author then talks about three methods of coding a large project:

1. Breadth-First: In this method, the entire skeleton of the application is built without any details. The author enlists following advantages and disadvantages of the approach:
• This method ensures that everything in architecture is covered.
• It demonstrates overall flow of application early in coding cycle.
• Looking at the skeleton, customer's expectation for schedule may become unrealistic.
• A team of developers are difficult to manage in this approach.
2. Depth-First: In this approach, one part of the application is completely developed before moving on to anything else. The author enlists following advantages and disadvantages for the approach:
• The developer can focus on just one piece of code for its issues.
• A team of developers can work on separate components.
• Architecture will not be tested till late in the development cycle.
• The complete application flow cannot be determined till the end of the development.
  
3. Mixed Models: The author suggests to take a mixed approach since most products have some UI component which can be developed using breadth-first approach and the rest of the components can be developed using depth-first approach.
   

The author then talks about three cornered trade-off representing product, cost and time. The author then discusses several approaches such as:

• The Beta-Test approach: This is used by Microsoft where there are several targets like
  
• Alpha
• Beta 1
• Beta 2
• Release Candidate
• Release
• The XP approach: This involves making a series of small releases with high quality bar. Releases are spaced close to one another with very small functionality added above the previous release.

The author emphasizes the fact that product in three cornered trade-off represents not just features but quality too. Releasing a product full of bugs is a sure-shot way to lose customers.