Find Second largest Element in an Array

Find Second largest Element in an Array in Minimum Time Complexity

1. State different ways and the Complexities involved with them

• Keep two pointers, largest, second_largest. Let the first element is largest and second element as second_largest. Compare. After comparison, largest, second_largest will point to right array indices. Move from the third index till the end of array. At each entry to loop, again compare and reset the pointers: largest and second_largest. This solution is of order n, o(n) as there are almost 2n comparisons

A general variation of this problem will be to find out the kth largest in an array of N numbers

• Kth largest logically means that in a set of K elements , find the smallest element. This smallest in the set of K elements is the Kth largest for the set of K. So steps include

Using Min-heap

• Get the first K elements. Construct a min-heap of it. Order of Complexity of constructing this heap = kLog(k)
• Root of this min-heap, which is the smallest of this heap, is the currently the kth largest on this set of k
• a: Iterate over the array from k+1 index. Get the k+1 element of array. If it is less, ignore it
• b: If k+1 th element is greater then root, then insert this element in the min-heap. Order of Complexity for this Log(k)
• c: Remove the smallest , which is the new root. order of Complexity for this is again Log(k)
• d: Now the min-heap again contains K elements, the new root is now the K th largest.
• Do the steps a, b, c, d, for the rest of the elements of array

Order of Complexity in this case:

Order of Complexity to construct the min-heap of K elements = kLog(k)- one time

order of Complexity to insert a new element = kLog(k) - ( n-k) times

order of Complexity to remove the root = kLog(k) - ( n-k) times

Total complexity, order :

kLog(k) + 2*(n-k)*Log(k)

Serialize a Binary Search tree

Jersey Mutipart - Resource that Produces MULTIPART Response and Client code to process it

Handling 'MULTIPART/MIXED'  using Jersery Apis.

Jars required:

a. ) jersey-bundle-1.13.jar
b. ) jersey-multipart-1.13.jar

Jersey Client to GET a Multipart Http Request

______________________________________--

Lets build a client equired to GET a Multipart Response. This Response that has two BodyParts.

1. An xml Input : This is the first body part. It is an Xml representation for a JAXB object  ,MyEntity E
2. Byte[] array : This array of bytes is the second body part. This byte array is the content of the file produced by a REST resource

So the aim is to create a jersery client and GET a MULTIPART request.


                  final long resourceId = 1026l;
final String exportUrl =  "get Export Resource URL"
final String path = "/" + resourceId ;

Client c = Client.create();
WebResource service = c.resource(exportUrl );

MultiPart multipart = service.path(path).type(MediaType.APPLICATION_XML).header( headerKey, headerValue).get(MultiPart.class);

List bodyParts = multipart.getBodyParts();
String xmlResponse = bodyParts.get(0).getEntityAs(String.class);
byte[] exportedContent = bodyParts.get(1).getEntityAs(byte[].class);
System.out.println("XML  = " + xmlResponse);
System.out.println("\n\n");
System.out.println("ExportedContent : \n");
System.out.println(new String(exportedContent ));


/////////////// The FileExport Resource that would Produce this Multipart Request ///////////////////////

       @GET
@Path("{id}")
@Produces("multipart/mixed")
public Response read(@PathParam("id") String resourceId , @Context HttpHeaders headers,
@Context UriInfo uriInfo) // add other @Context arguments if required
{
          // process Request and fetch Xml Response Strinrg
           String responseStr = getResponseStrForResourceId( reesource Id );
         
           // build Multipart Web Response
           MultiPart multipart = buildMultipartResponse(responseStr);
 
            Response response = Response.status(status).header( headerKey, headerValue ) .entity(multipart).type(MultiPartMediaTypes.MULTIPART_MIXED).build();

return response;

       }

  // build Multipart Data
   MultiPart buildMultipartResponse(String xmlResponseStr)
{
MultiPart multiPart = new MultiPart();
multiPart.bodyPart(new BodyPart(xmlResponseStr, MediaType.APPLICATION_XML_TYPE)).bodyPart(
new BodyPart(getAttachmentBytes(), MediaType.APPLICATION_OCTET_STREAM_TYPE));

return multiPart;
}

Jersey Mutipart - Resource that Consumes MULTIPART and Client that POSTs such a request

Handling 'MULTIPART/MIXED'  using Jersery Apis.

Jars required:

a. ) jersey-bundle-1.13.jar
b. ) jersey-multipart-1.13.jar

Jersey Client to POST Multipart Http Request

______________________________________--

Lets build a client that requires to POST to a REST resource a multipart request that has two body parts

1. An xml Input : This is the first body part. Let the JAXB object created for this be Represented by MyEntity E
2. Byte[] array : This array of bytes is the second body part. This byte array is the content of the file that needs to imported , along with the above xml input

So the aim is to create a jersery client and post a multipart request.

        String fileImporUrl = "URl to the resource that would handle this request"

   Client c = Client.create();
   WebResource service = c.resource(fileImporUrl );

   // Construct a MultiPart with two body parts

    // Construct the JAXB object for the Input Xml 
   MyEntity E = new MyEntity ();
          // E.setname( "anbc" );
          //E.setId(123 );
          .............
         ..... Build the Entity
 
            // read the file and get bytes to import
   byte[] bytesToImport = getBytesToImport();
 
               // Construct Multipart Request. Content-type of the first part is 'application/xml '
              // and second part is 'appication/octet-stream'
   MultiPart multiPart = new MultiPart().
    bodyPart(new BodyPart(E, MediaType.APPLICATION_XML_TYPE)).
     bodyPart(new BodyPart(bytesToImport, MediaType.APPLICATION_OCTET_STREAM_TYPE));

   // POST the request
   ClientResponse response = service.path("/import").
     type("multipart/mixed").header( headerKey, headerValue).post(ClientResponse.class, multiPart);

   System.out.println( "Import Response status = " + response.getStatus() );


/////////////// A FileImport Resource that would consume this Multipart Request ///////////////////////

    @POST
@Consumes("multipart/mixed")
@Produces({ MediaType.APPLICATION_XML, MediaType.TEXT_XML })
public Response importFile(MultiPart multipart, @Context HttpHeaders headers, @Context UriInfo uriInfo) // add other context if required
{

final int INDEX_XML = 0; final int INDEX_FILE_CONTENT = 1; MultipartBodyEntityContent bodyEntityContent = new MultipartBodyEntityContent(); MyEntity E = null; BodyPartEntity fileContentAsBodyPart = null; try { E = multipart.getBodyParts().get(INDEX_XML).getEntityAs(MyEntity.class); fileContentAsBodyPart = (BodyPartEntity) multipart.getBodyParts().get(INDEX_FILE_CONTENT).getEntity(); byte[] byteContent = getByteArrayFromInputStream( fileContentAsBodyPart .getInputStream() );

// Process the MyEntity E and byteContent and return Response }

}

// get byte[] from Input Stream byte[] getByteArrayFromInputStream(InputStream in) { ByteArrayOutputStream buffer = new ByteArrayOutputStream(); int nRead; byte[] data = new byte[4096]; while ((nRead = in.read(data, 0, data.length)) != -1) buffer.write(data, 0, nRead); buffer.flush(); buffer.close(); return buffer.toByteArray(); }

Simple Java Program to Write to a Zip File.

This Program takes a Zip file Directory and a Zip file name as Input.
'writeAsZip()' method writes an Array of Bytes as a Zip Entry to the Zip file.
Suppose a zip file 'D:\\test\\cb-1-zip.zip' is has two constituents, namely : 'a.txt' and 'b.png'
This zip File is read and contents stored in a hashMap by 'ZipFileReader'.The size of hashmap is now 2, containing bytes[] of a.txt and b.png

'write()' method takes bytes[] array and name of the file entry to be written to t he Zip file.

Each entry is closed by calling ZipOutputStream#closeEntry() method. Once closeEntry() is called , ZipOutputStream is ready for addition of a new Zip Entry.

Finally ZipOutpurStream#close() method is called. This method finally closes the stream
If the program misses to call 'close()' then a fautly zip file is written to the file system, that is corrupt and perhaps cannot be used. ZipOutpurStream#close() adds the required stream terminating characters.


import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.zip.ZipEntry;
import java.util.zip.ZipOutputStream;


public class ZipFileWriter {

    private String zipDir;
   
    private String zipFilename; // ends in .zip
   
    private static String FS = System.getProperty("file.separator" );
   
    public ZipFileWriter( String zipDir, String zipFilename ) {
        this.zipDir = zipDir;
        this.zipFilename = zipFilename;
    }
   
    /**
    }
     *
     * @return
     * @throws IOException
     */
    public void writeAsZip( byte[] bytesRead, String fileEntry ) throws IOException {

        String absoluteZipFIleName = zipDir + FS + zipFilename;
        ZipOutputStream zos = new ZipOutputStream(new FileOutputStream(absoluteZipFIleName));
   
        ZipEntry entry = new ZipEntry( fileEntry );
        zos.putNextEntry( entry );
       
        zos.write(bytesRead);
       
        zos.closeEntry();       
        zos.close();
    }
   
    public void writeAsText( String filename, byte[] bytesRead ) throws IOException{
        FileOutputStream fos = new FileOutputStream( new File( zipDir +  FS + filename ));
        fos.write( bytesRead );
        fos.close();
    }


 public static void main(String[] args) throws Exception {
     String FS = System.getProperty("file.separator" );
      String zipDirRead = "D:\\test";
      String zipDirWrite = "D:\\test\\out";
      String zipFilename = "cb-1-zip.zip";
     
      
      File zipFile = new File ( zipDirRead + FS + zipFilename );
     
      ZipFileReader reader = new ZipFileReader( zipFile );
      Map map = reader.read();
   
      ZipFileWriter writer = new ZipFileWriter(zipDirWrite, zipFilename);
      Set set = map.keySet();
      Iterator iter = set.iterator();
      while ( iter.hasNext() ) {
         
         String key = iter.next();
          System.out.println("Writing file Entry :" + key );
          byte[] bytesread = map.get(key);
       
          writer.writeAsZip( bytesread, key );
          writer.writeAsText( key, bytesread );
      }
   
}