logic

  • Sorting

1. Alternating sort

Given a list of pairwise distinct integers, sort it in alternating order: The second number is larger than the first, the third is smaller than the second, the fourth is larger than the third etc. (This order is not unique.) E.g., 5 7 3 4 2 9 1 would be valid output.

Solution 

You can do this in O(n) by placing each element in turn at the end, or at the penultimate position based on a comparison with the current last element.

For example,

1,4,9,2,7,5,3,8,6
Place 1 at end, current list [1]
4>1 true so place 4 at end, current list [1,4]
9<4 false so place 9 at penultimate position [1,9,4]
2>4 false so place 2 at penultimate [1,9,2,4]
7<4 false so place 7 at penultimate [1,9,2,7,4]
5>4 true so place 5 at end [1,9,2,7,4,5]
3<5 true so place 3 at end [1,9,2,7,4,5,3]
8>3 true so place 8 at end [1,9,2,7,4,5,3,8]
6<8 true so place 6 at end [1,9,2,7,4,5,3,8,6] 

Note that the equality tests alternate, and that we place at the end if the equality is true, or at the penultimate position if it is not true.

2. Turning Number in an Array

Turning number is the maximum number in an array which increases and then decreases. This kind of array is also named unimodal array. Please write a function which gets the index of the turning number in such an array.

For example, the turning number in array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 10, so its index 5 is the expected output.

3. Sum Of Three

Given three sets A, B, and C of at most N integers each, determine whether this is a triple a in A, b in B,
and c in C such that a + b + c = 0.

Solution

Sort B in increasing order; sort C in decreasing order; for each a in A, scan B and C for a pair that sums to – a
(when the sum is too small, advance in B, when the sum is too large, advance in C).

4. Expensive exchange

A clerk at a shipping company is charged with the task of rearranging a number of large crates in order of the time they are to be shipped out.
Thus, the cost of compares is very low (just look at the labels) relative to the cost of exchanges (move the crates). The warehouse is nearly full—there is extra space sufficient to hold any one of the crates, but not two. What sorting method should the clerk use?

5. Nuts and bolts(G. J. E. Rawlins) 

You have a mixed pile of N nuts and N bolts and need to quickly find the corresponding pairs of nuts and bolts. Each nut matches exactly one bolt, and each bolt matches exactly one nut. By fitting a nut and bolt together, you can see which is bigger, but it is not possible to directly compare two nuts or two bolts. Give an efficient method for solving the problem.

Solution 

Since we can’t compare a nut with other nuts and a bolt with other bolts, we can’t sort them. So current best possibility seems to pick nuts one-by-one and find matching bolts for them. In this manner, we will match all the pairs in O(n^2) time complexity.
But though we can’t compare a nut with other nuts and so for bolts, we can compare a nut with bolts and vice-versa. Also keep in mind that if a Nut(N) is smaller than a Bolt(B) than N is fit only for bolts smaller than B. Similarly if a Bolt(B’) is smaller than a Nut(N’) than N is fit only for bolts smaller than B’. So we can go like following in solving this problem.
  • Take a nut from the nuts pile
  • Divide bolts around it in 2 parts, which are smaller and larger than this.
  • Find a matching bolt to this nut.
  • Divide nuts in 2 parts, which are smaller and larger than matching bolt.
Now we have 2 subsets of Nuts and Bolts. If we pick a nut from small size nuts pile, we will get a corresponding bolt in smaller size bolts pile and similarly for large size piles. At every step, we will be able to divide these piles in 2 halves and reduce complexity by a factor of 2 in average case. In this case time complexity will be O(nlogn).

In worst case we might have choose the smallest/largest nut/bolt as reference and our one pile will have zero nut/bolt and another pile will have all the remaining. In this case time complexity will be O(n^2).
Algorithm:
Take a nut; partition the bolts with respect to this nut. We will find the matching bolt for this nut. Now take the bolt; partition the nuts.
In this manner, we have divided the Original problems into 2 sub-problems.
T(n) = T( i ) + T(n-i ) + O(n)
Where we have chosen the ith largest nut from a particular pile.
Average time complexity = O(nlogn).
Worst time complexity = O(n^2).
6. The way a card game player arranges his card as he pick them up 1 by 1 is an example of :
Solution
insertion sort
7. Which sorting algorithm should not be used in below case :
    1) data is already sorted in same order.
    2) data is already sorted in reverse order.
    3) All elements are same (special case of case 1 and 2)
Solution
Quicksort
7. Minimum Difference between Two Arrays
Given two arrays x[1], …, x[m] and y[1], …, y[n], design an algorithm to find two elements x[i] and y[j] such that the absolute value |x[i] – y[j]| is minimized over all posibble pairs of x and yelements. A brute force algorithm needs O(n^2) time. Your algorithm should be far more efficient than that. Analyze the time complexity of your algorithm.

Solution

First, sort array x. Then, for each element in y, use Binary Search method to find the element with the closest value in array x. In this way, we can find the pair with the minimum absolute value of the difference. Sorting the array takes O(m lg m) time and binary search takes O(n lg m) time.

8. Pancake Sorting

Jeremy is a waiter working in a restaurant. The chef there is sloppy; when he prepares a stack of pancakes, they come out all different sizes. When Jeremy delivers the pancakes to the customer, he wants to rearrange them by grabbing several from the top and flipping them over on the way. After repeating this for several times, the smallest pancake is on top, and so on, down to the largest at the bottom. If there are n pancakes, how many flips are required? Design an algorithm to help Jeremy, and analyze its time complexity.

Solution

This problem is called pancake sorting. For a stack of pancakes, we first locate the largest pancakes. Then we flip the largest pancakes to the top by using one flip and use another flip to move the largest pancaked to the bottom. Then, we recursively sort the top n-1 pancakes. Since every pancake except the smallest one needs at most two flips to move to the correct position, the number of flips is 2(n – 1).


Arrays 


2. Jolly Jumpers

A sequence of n integers is called a jolly jumper if the absolute values of the differences between successive elements take on all possible values 1 through n − 1.Where n > 0.

For instance, 1 4 2 3 is a jolly jumper, because the absolute differences are 3, 2, and 1, respectively. The definition implies that any sequence of a single integer is a jolly jumper. Write a program to determine whether each of a number of sequences is a jolly jumper.

3. Given an array of n integers, where one element appears more than n/2 times, find that element in linear time and constant extra space. 

Solution

There is a beautiful algorithm for solving this that works in two passes (total time O(N)) using only constant external space (O(1)).

The intuition behind the algorithm is actually quite beautiful. Suppose that you were to have a roomful of people each holding one element of the array. Whenever two people find each other where neither is holding the same array element as the other, the two of them sit down. Eventually, at the very end, if anyone is left standing, there’s a chance that they’re in the majority, and you can just check that element. As long as one element occurs with frequency at least N/2, you can guarantee that this approach will always find the majority element.

To actually implement the algorithm, you make a linear scan over the array and keep track of your current guess as to what the majority element is, along with the number of times that you’ve seen it so far. Initially, this guess is undefined and the number of repeats is zero. As you walk across the array, if the current element matches your guess, you increment the counter. If the current element doesn’t match your guess, you decrement the counter. If the counter ever hits zero, then you reset it to the next element you encounter. You can think about this implementation as a concrete realization of the above “standing around in a room” algorithm. Whenever two people meet with different elements, they cancel out (dropping the counter). Whenever two people have the same element, then they don’t interact with each other.

items = [1, 2, 3, 4, 5, 5, 5, 5, 5 ]

# shuffle the items

random.shuffle(items)

print(“shuffled items: “, items)

majority_elem = items[0]

count = 1

for i in range(1,len(items)):

if items[i] == majority_elem:

count += 1

else:

count -= 1

if count == 0:

majority_elem = items[i]

count = 1

print(“majority element : %d” % majority_elem )

4. Given an array of size N that contains values between 1 and N-1, find the duplicate element (assuming there is only one). If it contains values between 1 and N+1, how would you find the missing element (again assuming there is only one missing)? Do each in O(N).

Solution

For the first partcompute the sum of the numbers from 1 to N-1. Then sum the values in the array. The duplicate number is the difference between these sums.

For the second part, compute the sum of the numbers from 1 to N+1. Then sum the values in the array. The missing number is again the difference between these sums.

Advertisements

knockoutjs : Computed Observables

  • COMPUTED OBSERVABLES – FUNCTIONS DEPENDENT ON ONE OR MORE OTHER OBSERVABLES.
  • What if you’ve got an observable for firstName, and another for lastName, and you want to display the full
    name? That’s where computed observables come in – these are functions that are dependent on one or
    more other observables, and will automatically update whenever any of these dependencies change.
    Your evaluator function will be called once each time any of its dependencies change, and whatever value you return will be passed on to the observers such as UI elements or other computed observables.

    
    <!DOCTYPE html>
    <html>
    <head>
    <meta charset="utf-8" />
    <title>Home Page</title>
    <script src="../lib/knockout-3.2.0.debug.js" type="text/javascript"></script>
    </head>
    <body>
    	<label>Hello </label>
    	<input type="text" data-bind="value: fullName" />
    	<script type="text/javascript">
    		// Here's my data model
    		var viewModel = {
                firstName: ko.observable("Shiv"),
                lastName: ko.observable("Yadav")
            };
            viewModel.fullName = ko.dependentObservable(function () {
                // Knockout tracks dependencies automatically. It knows that fullName depends on firstName and lastName, because these get called when evaluating fullName.
                return viewModel.firstName() + " " + viewModel.lastName();
            });
    		ko.applyBindings(viewModel); // This makes Knockout get to work
    		
    		setTimeout(function(){ viewModel.firstName("Shivanshu"); }, 3000);// change data after 3 seconds
    		
    	</script>
    </body>
    </html>
    

    ang4

    After 3 seconds….

    ang5

    knockoutjs : Simple data binding

  • Simple binding with “applyBindings” method.
  • Bind data to template by calling “applyBindings” method.
    Note that it is only one time binding.After that data and template are detached.
    Any change in template or data will not affect each other.
    it’s not really a data binding. Works like template parsing.

    <!DOCTYPE html>
    <html>
    <head>
    <meta charset="utf-8" />
    <title>Home Page</title>
    <script src="../lib/knockout-3.2.0.debug.js" type="text/javascript"></script>
    </head>
    <body>
    	<label>Hello </label>
    	<input type="text" data-bind="value: name" />
    	<script type="text/javascript">
    		// Here's my data model
    		var viewModel = {
    			name : "Shiv"
    		};
    		ko.applyBindings(viewModel); // This makes Knockout get to work
    	</script>
    </body>
    </html>
    

    ang1

    JAX-WS Attachment – Enable MTOM

    It all begins with the fact that SOAP is XML. And when you send anything other than text, for instance, an image – it has to be converted into a datatype that an XML processor can understand.

    Without MTOM, your image will be converted to base64Binary and placed smack in the middle of your SOAP envelope. This conversion process makes the data fat.

    <tns:data>A very looooooooooooooooooooooong base64Binary string</tns:data>
    

    Here’s a simple illustration:

    lXWep

    With MTOM, the image will be transmitted outside the envelope as a MIME attachment – in short, it’s sent according to its original datatype: a jpg, png, or gif. Of course it’s still transmitted as binary data, but this time, there’s no XML-related conversion, avoiding the unnecessary overhead. XOP comes into the picture as it’s the one that gives the location of the externalized image.

    <soap:Body><soap:Envelope>
    
    <tns:data><xop:include href="SomeUniqueID-ThatLeadsToTheImage"/></tns:data>
    
    </soap:Body></soap:Envelope>
    
    Content-id: "SomeUniqueID"
    
    Content-Type: image/png
    
    image binary data here
    

    What is MTOM?
    MTOM (Message Transmission Optimization Mechanism) provides an efficient mechanism for transmitting binary data to and from web services over internet. MTOM uses XML binary Optimized Packaging or XOP to serialize and de-serialize binary part of an XML infoset.
    MTOM is a standard that is developed by the World Wide Web Consortium (W3C) and it is a SOAP Version 1.2 feature (based on the Infoset). Even though SwA (SOAP with Attachments) and MTOM are theoretically similar, and both encode binary data as a MIME attachment in a MIME document, SwA could be replaced by the more powerful MTOM and XOP mechanisms because it solves some of the interoperability issues of SwA. MTOM uses XOP in the context of SOAP and MIME over HTTP to achieve performance improvement.

    How Does XOP works?
    As we know, the serialization of XML infoset is text based and uses BASE64 binary-to-text encoding scheme, where the binary data represented in an ASCII string format. This increases the size of the XML payload.
    An MTOM-enabled web services engine detects the presence of Base64Binary data. XOP packaging process extracts the binary data out of the XML Infoset and the binary data serialized differently. XOP process extracts the binary part of the XML info-set and leaves the XML Infoset with the binary parts replaced by external references. This is called XOP infoset and the external reference is added as “xop:Include” element in XML. This makes MTOM actually a “by reference” method.
    The raw bytes are appended to the SOAP Message and are separated by a MIME boundary.
    The XOP package is created by serializing the XOP infoset and the binary data as a MIME attachment. Once the data is received at the other end, the XOP Package is de-serialized into the XOP Infoset plus the extracted content and the extracted content is placed back in the XML infoset where the corresponding external reference is present.
    See and example SOAP response below which uses MTOM. We will see the complete working example as we move on.

    <S:Envelope xmlns:S="http://schemas.xmlsoap.org/soap/envelope/"> <S:Body> <ns2:retrieveImageResponse xmlns:ns2="http://globinch.com"> <return> <xop:Include href="cid:40128994-d019-4c2c-a293-49c448772ea7@example.jaxws.sun.com" xmlns:xop="http://www.w3.org/2004/08/xop/include"/> </return> </ns2:retrieveImageResponse> </S:Body> </S:Envelope>
    

    You can see the reference to the MIME attachment as

    <xop:Include href="cid:40128994-d019-4c2c-a293-49c448772ea7@example.jaxws.sun.com" xmlns:xop="http://www.w3.org/2004/08/xop/include"/>
    

    If you examine the SOAP header you will something like the below

    	
    Transfer-encoding  : chunked
    Content-type            : multipart/related;start="&lt;rootpart*75292b03-7617-4261-a44f-ac8d9df23382@example.jaxws.sun.com&gt;";type="application/xop+xml";boundary="uuid:75292b03-7617-4261-a44f-ac8d9df23382";start-info="text/xml"
    #status# : HTTP/1.1 200 OK
    

    The attachment details are as below

    Name: 40128994-d019-4c2c-a293-49c448772ea7@example.jaxws.sun.com	
    Content type: image/png	
    Size:431731	
    Part: 40128994-d019-4c2c-a293-49c448772ea7@example.jaxws.sun.com	
    Type: XOP	
    ContentId: 40128994-d019-4c2c-a293-49c448772ea7@example.jaxws.sun.com
    

    The contentId is same as the reference.

    Enabling MTOM in JAX-WS :
    In JAX-WS, it’s easy to enable MTOM for a web service endpoint by using either the @MTOM or @BindingType annotations. At the client side, MTOM can be enabled either by passing a new instance of MTOMFeature class when getting a reference to the web service endpoint (port), or by calling the SOAPBinding.setMTOMEnabled(true) method on the binding provider object. Here are the usages and examples in details.

  • Enabling MTOM for the web service endpoint
  • @MTOM annotation :

    The following example illustrates a web service endpoint is annotated with the @MTOM annotation:

    import javax.jws.WebMethod;
    import javax.jws.WebService;
    import javax.xml.ws.soap.MTOM;
    
    
    @WebService
    @MTOM
    public class MyWebService {
      
      @WebMethod
      public void upload(byte[] data) {
        // implementation details...	
      }
    }
    

    The @MTOM annotation has two optional parameters, enabled and threshold. The enabled parameter has a boolean value and indicates if MTOM is enabled for the JAX-WS endpoint. If an attachment is smaller than the size specified in threshold parameter, the runtime will inline the binary data as base64 binary instead of creating an attachment.

    @WebService
    @MTOM(threshold = 10240)
    public class MyWebService {
    }
    

    An alternative way is using the @BindingType annotation with an appropriate value for the SOAP version used. For example:

    Enabling MTOM with SOAP version 1.1:

    import javax.xml.ws.BindingType;
    import javax.xml.ws.soap.SOAPBinding;
    
    @WebService
    @BindingType(value = SOAPBinding.SOAP11HTTP_MTOM_BINDING)
    public class MyWebService {
    }
    

    Enabling MTOM with SOAP version 1.2:

    import javax.xml.ws.BindingType;
    import javax.xml.ws.soap.SOAPBinding;
    
    @WebService
    @BindingType(value = SOAPBinding.SOAP12HTTP_MTOM_BINDING)
    public class MyWebService {
    }
    

    From the above examples, we can see that using the @MTOM annotation is preferred as its succinct and flexibility (enabled/disabled and threshold).

    Enabling MTOM for the client :

    The following example shows how to enable MTOM at the client by passing a new instance of the MTOMFeature class when getting a proxy reference the web service endpoint:

    import javax.xml.ws.soap.MTOMFeature;
    
    MyWebServiceService service = new MyWebServiceService();
    MyWebService port = service.getMyWebServicePort(new MTOMFeature());
    

    Suppose that the MyWebServiceService and MyWebService classes are generated by the wsimport tool. And similar to the @MTOM annotation, we can also specify the enabled and threshold parameters in the MTOMFeature class’ constructor like this:

    boolean enabled = true;
    int threshold = 10240;
    MyWebService port = service.getMyWebServicePort(new MTOMFeature(enabled, threshold));
    

    And here’s an alternative way, calling the SOAPBinding.setMTOMEnabled(true) method:

    MyWebServiceService service = new MyWebServiceService();
    MyWebService port = service.getMyWebServicePort();
    
    BindingProvider provider = (BindingProvider) port;
    SOAPBinding soapBinding = (SOAPBinding) provider.getBinding();
    soapBinding.setMTOMEnabled(true);
    

    For more info :

    http://stackoverflow.com/questions/215741/how-does-mtom-work

    http://java.globinch.com/enterprise-java/web-services/jax-ws/jax-ws-attachment-enable-mtom-jax-ws-web-services/

    http://www.tuicool.com/articles/I3yEbu

    OCWSD

    RESTful web service :

    @Path :

  • Paths are relative
  • Paths are relative. For an annotated class the base URI is the application path. For an annotated method the base URI is the effective URI of the containing class. For the purposes of absolutizing a path against the base URI , a leading ‘/’ in a path is ignored and base URIs are treated as if they ended in ‘/’. E.g.:

    @Path("widgets")
    public class WidgetsResource {
    
        @GET
        String getList() {...}
    
        @GET @Path("{id}")
        String getWidget(@PathParam("id") String id) {...}
    
    }
    

    In the above, if the application path is catalogue and the application is deployed at http://example.com/, then GET requests for http://example.com/catalogue/widgets will be handled by the getList() method while requests for http://example.com/catalogue/widgets/nnn (where nnn is some value) will be handled by the getWidget() method. The same would apply if the value of either @Path annotation started with ‘/’.

    A @Path value may or may not begin with a ‘/’, it makes no difference. Likewise, by default, a @Path value may or may not end in a ‘/’, it makes no difference, and thus request URLs that end or do not end in a ‘/’ will both be matched.

  • Regular expression in @Path
  • If it is required that a user name must only consist of lower and upper case alpha-numeric characters then it is possible to declare a particular regular expression, which overrides the default regular expression, “[^/]+?”, for example:

    @Path("users/{username: [a-zA-Z][a-zA-Z_0-9]*}")
    

    In this type of example the username variable will only match user names that begin with one upper or lower case letter and zero or more alpha numeric characters and the underscore character. If a user name does not match that a 404 (Not Found) response will occur.

    @Produces

    The @Produces annotation is used to specify the MIME media types of representations a resource can produce and send back to the client. In this example, the Java method will produce representations identified by the MIME media type “text/plain”.

    @Produces can be applied at both the class and method levels. Here’s an example:

    @Path("/myResource")
    @Produces("text/plain")
    public class SomeResource {
        @GET
        public String doGetAsPlainText() {
            ...
        }
    
        @GET
        @Produces("text/html")
        public String doGetAsHtml() {
            ...
        }
    }
    

    The doGetAsPlainText method defaults to the MIME type of the @Produces annotation at the class level. The doGetAsHtml method’s @Produces annotation overrides the class-level @Produces setting, and specifies that the method can produce HTML rather than plain text.

    If a resource class is capable of producing more that one MIME media type then the resource method chosen will correspond to the most acceptable media type as declared by the client. More specifically the Accept header of the HTTP request declared what is most acceptable. For example if the Accept header is:

    Accept: text/plain
    

    then the doGetAsPlainText method will be invoked.

    Alternatively if the Accept header is:

    Accept: text/plain; q=0.9, text/html
    

    which declares that the client can accept media types of “text/plain” and “text/html” but prefers the latter, then the doGetAsHtml method will be invoked.

    More than one media type may be declared in the same @Produces declaration, for example:

    @GET
    @Produces({"application/xml", "application/json"})
    public String doGetAsXmlOrJson() {
        ...
    }
    

    The doGetAsXmlOrJson method will get invoked if either of the media types “application/xml” and “application/json” are acceptable. If both are equally acceptable then the former will be chosen because it occurs first.

    The examples above refer explicitly to MIME media types for clarity. It is possible to refer to constant values, which may reduce typographical errors, see the constant field values of MediaType:

    APPLICATION_ATOM_XML          "application/atom+xml"
    APPLICATION_FORM_URLENCODED   "application/x-www-form-urlencoded"
    APPLICATION_JSON              "application/json"
    APPLICATION_OCTET_STREAM      "application/octet-stream"
    APPLICATION_SVG_XML           "application/svg+xml"
    APPLICATION_XHTML_XML         "application/xhtml+xml"
    APPLICATION_XML               "application/xml"
    MULTIPART_FORM_DATA           "multipart/form-data"
    TEXT_HTML                     "text/html"
    TEXT_PLAIN                    "text/plain"
    TEXT_XML                      "text/xml"
    WILDCARD                      "*/*"
    

    Hello!

     

     

     

     

     

    Everyone has his version of truth. His own way of seeing the world. Everyone has his own Shades of Gray.

    I try to see things without any prenotion, things as they are, good or bad,beautiful or ugly.

    So this my blog and these are my Shades of Gray.