Category Archives: Uncategorized

Nuts & Bolts Problem (Lock & Key problem)

Posted on by

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently.
Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

Other way of asking this problem is, given a box with locks and keys where one lock can be opened by one key in the box. We need to match the pair.

Logic

  • first performs a partition by picking last element of bolts array as pivot,
  • rearrange the array of nuts and returns the partition index ‘i’ such that all nuts smaller than nuts[i] are on the left side and all nuts greater than nuts[i] are on the right side.
  • Next using the nuts[i] we can partition the array of bolts. This operation also makes nuts and bolts array nicely partitioned.
  • Now we apply this partitioning recursively on the left and right sub-array of nuts and bolts.

As we apply partitioning on nuts and bolts both so the total time complexity will be Θ(2*nlogn) = Θ(nlogn) on average.

CODE

    private static void matchPairs(char[] nuts, char[] bolts, int low, int high)
    {
        if (low < high)
        {
            // Choose last character of bolts array for nuts partition.
            int pivot = partition(nuts, low, high, bolts[high]);
            // Now using the partition of nuts choose that for bolts
            partition(bolts, low, high, nuts[pivot]);
            // Recur for [low...pivot-1] & [pivot+1...high] for nuts and bolts array.
            matchPairs(nuts, bolts, low, pivot-1);
            matchPairs(nuts, bolts, pivot+1, high);
        }
    }

HashMap

Posted on by 
If you're only interested in the keys, you can iterate through the keySet() of the map:
Map<String, Object> map = ...;

for (String key : map.keySet()) {
    // ...
}

If you only need the values, use values():
for (Object value : map.values()) {
    // ...
}
Finally, if you want both the key and value, use entrySet():
for (Map.Entry<String, Object> entry : map.entrySet()) {
    String key = entry.getKey();
    Object value = entry.getValue();
    // ...
}

Simple Ajax program

Posted on by 
<!DOCTYPE html>
<html>
<head>
<script>
function loadXMLDoc()
{
var xmlhttp;
if (window.XMLHttpRequest)
  {// code for IE7+, Firefox, Chrome, Opera, Safari
  xmlhttp=new XMLHttpRequest();
  }
else
  {// code for IE6, IE5
  xmlhttp=new ActiveXObject("Microsoft.XMLHTTP");
  }
xmlhttp.onreadystatechange=function()
  {
  if (xmlhttp.readyState==4 && xmlhttp.status==200)
    {
    document.getElementById("myDiv").innerHTML=xmlhttp.responseText;
    }
  }
xmlhttp.open("GET","ajax_info.txt",true);
xmlhttp.send();
}
</script>
</head>
<body>

<div id="myDiv"><h2>Let AJAX change this text</h2></div>
<button type="button" onclick="loadXMLDoc()">Change Content</button>

</body>
</html>

SDLC

Posted on by

Software development life cycle model phases:

  1. Requirement gathering and analysis
  2. Design
  3. Implementation or coding
  4. Testing
  5. Deployment
  6. Maintenance

SDLC models:

  • Waterfall Model
  • Iterative Model
  • Spiral Model
  • V-Model
  • Big Bang Model

Waterfall Model

First Process Model. Each phase must be completed before proceeding to the next phase without any overlapping in the phases.

Some situations where it is most appropriate:

  • Requirements are very well documented, clear and fixed
  • Technology not dynamic
  • Ample resources with required expertise available
  • Short project
  • does not allow for much reflection or revision.
  • No working software is produced until late during the life cycle.
  • Once an application is in the testing stage, it is very difficult to go back and change something

Disadvantage

  • does not allow for much reflection or revision.
  • No working software is produced until late during the life cycle.
  • Once an application is in the testing stage, it is very difficult to go back and change something

Iterative Model

Whole requirement is divided into various builds. During each iteration, the development module goes through the requirements, design, implementation and testing phases. Each subsequent release of the module adds function to the previous release.

Some situations where it is most appropriate:

  • Major requirements must be defined, some functionalities or requested enhancements may evolve with time.
  • A new technology is being used and is being learnt by the development team while working on the project.
  • Resources with needed skill set are not available and are planned to be used on contract basis for specific iterations.
  • There are some high risk features and goals which may change in the future.

Disadvantage

  • Applicable only to large and bulky software development projects.

Spiral model

Combination of iterative development process model and sequential linear development model i.e. waterfall model with very high emphasis on risk analysis.

The spiral model has four phases.

  • Identification
  • Design
  • Construct or Build
  • Evaluation and Risk Analysis

Uses of Spiral model:

  • budget constraint and risk evaluation
  • Long-term project commitment
  • Complex
  • Significant changes are expected in the product during the development cycle.

Disadvantage

Complex management as there is a risk of running the spiral in indefinite loop. Not suitable for small or low risk projects as its expensive.

V-Model

Extension of the waterfall model and is based on association of a testing phase for each corresponding development stage. There are Verification phases on one side and Validation phases on the other side with Coding phase in between.

Verification phases are:

  • Business Requirement Analysis
  • System Design
  • Architectural Design
  • Module Design

Validation phases in V-Model:

  • Unit Testing – Testing at code level and helps eliminate bugs at an early stage
  • Integration Testing – Testing the coexistence and communication of the internal modules within the system.
  • System Testing – Testing entire system functionality and the communication of the system under development with external systems. Most of the software and hardware compatibility issues are covered.
  • Acceptance Testing – Testing the product in user environment to check the non-functional issues such as load and performance defects.

Uses:

  • Requirements are well defined, clearly documented and fixed.
  • Product definition is stable and short.
  • Technology is not dynamic.

Disadvantage

Not a good model for long and complex and object-oriented projects. No working software is produced until late during the life cycle.

Big Bang Model

Focusing all the possible resources in software development and coding, with very little or no planning. Ideal for small projects

Advantages

  • Easy to manage
  • Very few resources required
  • Gives flexibility to developers
  • Good learning aid for new comers or students

Disadvantages

  • Very High risk and uncertainty.
  • Not a good model for long and complex and object-oriented projects.
  • Can turn out to be very expensive if requirements are misunderstood.

Agile Model

Breaks the product into small incremental builds which are provided in iterations. Each iteration lasts about 1-3 weeks and involves cross functional teams working simultaneously on various areas like planning, requirements analysis, design, coding, unit testing and acceptance testing.

Iterative approach is taken and working software build is delivered after each iteration. Each build is incremental in terms of features; the final build holds all the features required by the customer.

The most popular agile methods include Rational Unified Process (1994), Scrum (1995), Extreme Programming (1996), Adaptive Software Development and Dynamic Systems Development Method (DSDM) (1995).

  • Agile uses adaptive approach where there is no detailed planning and there is clarity on future tasks only in respect of what features need to be developed.
  • Team adapts to the changing product requirements dynamically.
  • The product is tested very frequently, through the release iterations, minimizing the risk of any major failures in future.
  • Customer interaction is the backbone of Agile methodology, and open communication with minimum documentation are the typical features of Agile development environment.
  • The agile teams work in close collaboration with each other and are most often located in the same geographical location.

Disadvantages

  • Not suitable for handling complex dependencies.
  • An agile leader and agile PM practice is a must.
  • Depends heavily on customer interaction.
  • High individual dependency and transfer of technology to new team members quite challenging, since there is minimum documentation generated.

Different types of software prototypes:

  • Throwaway/Rapid Prototyping
  • Evolutionary Prototyping
  • Incremental Prototyping
  • Extreme Prototyping

What happens when you open a website in a browser

Posted on by
  1. browser checks cache; if requested object is in cache and is fresh, skip to #9
  2. browser asks OS for server’s IP address
  3. OS makes a DNS lookup and replies the IP address to the browser
  4. browser opens a TCP connection to server (this step is much more complex with HTTPS)
  5. browser sends the HTTP request through TCP connection
  6. browser receives HTTP response and may close the TCP connection, or reuse it for another request
  7. browser checks if the response is a redirect (3xx result status codes), authorization request (401), error (4xx and 5xx), etc.; these are handled differently from normal responses (2xx)
  8. if cacheable, response is stored in cache
  9. browser decodes response (e.g. if it’s gzipped)
  10. browser determines what to do with response (e.g. is it a HTML page, is it an image, is it a sound clip?)
  11. browser renders response, or offers a download dialog for unrecognized types