2020 | JavaByPatel: Data structures and algorithms interview questions in Java

Home » Archives for 2020

Swagger OpenAPI REST Java Example using Guice and Jersey

in Miscellaneous - on 00:15:00 - No comments

Swagger OpenAPI REST API Java Example using Guice and Jersey

In this post we will see how to integrate Swagger in Guice and Jersey to dynamically generate OpenAPI REST endpoint documentation.

Sample project uses below libraries,
1. Google Guice
2. Jersey
2. Grizzly server
3. Swagger OpenAPI Annotations

Sample project to demonstrate OpenAPI Swagger configuration in Guice grizzly jersey example.

We are going to write a small hello world maven application containing one REST api endpoint and will generate OpenAPI swagger documentation for it.

We will be mostly using Swagger Java Annotations for generating the Resource description.

Sample project generates OpenAPI swagger documentation in both JSON and YAML format.

Download the complete application from here

https://github.com/javabypatel/guice-grizzly-jersey-openapi-swagger-example

Dependencies: pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.javabypatel</groupId>
    <artifactId>guice-grizzly-jersey-openapi-swagger-example</artifactId>
    <version>1.0-SNAPSHOT</version>

    <properties>
        <grizzly.version>2.3.16</grizzly.version>
        <jersey.version>2.30</jersey.version>
        <guice.version>4.2.2</guice.version>
        <guice.bridge>2.5.0-b61</guice.bridge>
        <swagger.version>2.1.5</swagger.version>
        <maven.compiler.source>11</maven.compiler.source>
        <maven.compiler.target>11</maven.compiler.target>
    </properties>

    <dependencies>
        <!-- Guice dependencies -->
        <dependency>
            <groupId>com.google.inject</groupId>
            <artifactId>guice</artifactId>
            <version>${guice.version}</version>
        </dependency>
        <dependency>
            <groupId>org.glassfish.hk2</groupId>
            <artifactId>guice-bridge</artifactId>
            <version>${guice.bridge}</version>
        </dependency>

        <!-- Jersey dependencies -->
        <dependency>
            <groupId>org.glassfish.jersey.bundles</groupId>
            <artifactId>jaxrs-ri</artifactId>
            <version>${jersey.version}</version>
        </dependency>
        <dependency>
            <groupId>org.glassfish.jersey.containers</groupId>
            <artifactId>jersey-container-grizzly2-http</artifactId>
            <version>${jersey.version}</version>
        </dependency>
        <dependency>
            <groupId>org.glassfish.jersey.ext</groupId>
            <artifactId>jersey-bean-validation</artifactId>
            <version>${jersey.version}</version>
        </dependency>
        <dependency>
            <groupId>org.glassfish.jersey.inject</groupId>
            <artifactId>jersey-hk2</artifactId>
            <version>${jersey.version}</version>
        </dependency>

        <!-- swagger dependencies -->
        <dependency>
            <groupId>io.swagger.core.v3</groupId>
            <artifactId>swagger-jaxrs2</artifactId>
            <version>${swagger.version}</version>
        </dependency>
        <dependency>
            <groupId>io.swagger.core.v3</groupId>
            <artifactId>swagger-annotations</artifactId>
            <version>${swagger.version}</version>
        </dependency>
        <dependency>
            <groupId>io.swagger.core.v3</groupId>
            <artifactId>swagger-core</artifactId>
            <version>${swagger.version}</version>
        </dependency>
    </dependencies>

</project>

openapi-configuration.json

This file contains the OpenAPI high-level resource description. you can describe the same using Swagger Annotations.

{
  "resourcePackages": [
    "com.javabypatel.resource"
  ],
  "prettyPrint": true,
  "cacheTTL": 0,
  "openAPI": {
    "info": {
      "version": "1.0.0",
      "title": "Guice Grizzly Jersey Openapi Swagger Example API",
      "description": "OpenAPI swagger configuration example in sample project that uses Guice, Grizzly, Jersey.",
      "contact": {
        "email": "jayeshmaheshpatel@gmail.com"
      },
      "license": {
        "name": "MIT License",
        "url": "https://en.wikipedia.org/wiki/MIT_License"
      }
    },
    "servers": [
      {
        "url": "http://localhost:8080/OpenAPIExample/",
        "description": "Guice Grizzly Jersey Openapi Swagger Example API server"
      }
    ]
  }
}

Sample REST API Endpoint:

package com.javabypatel.resource;

import com.javabypatel.model.GreetResponse;
import io.swagger.v3.oas.annotations.Operation;
import io.swagger.v3.oas.annotations.Parameter;
import io.swagger.v3.oas.annotations.enums.ParameterIn;
import io.swagger.v3.oas.annotations.media.ArraySchema;
import io.swagger.v3.oas.annotations.media.Content;
import io.swagger.v3.oas.annotations.media.Schema;
import io.swagger.v3.oas.annotations.responses.ApiResponse;

import javax.ws.rs.BadRequestException;
import javax.ws.rs.GET;
import javax.ws.rs.Path;
import javax.ws.rs.Produces;
import javax.ws.rs.core.Context;
import javax.ws.rs.core.MediaType;
import javax.ws.rs.core.Response;
import javax.ws.rs.core.UriInfo;

@Path("greet")
public class GreetResource {

    private static final String GREET_MESSAGE = "Hello";

    @GET
    @Produces(MediaType.APPLICATION_JSON)
    @Operation(
            summary = "This is a sample test API to greet user.",
            parameters = {
                    @Parameter(in = ParameterIn.QUERY, name = "name")
            },
            responses = {
                    @ApiResponse(
                            responseCode = "200",
                            description = "Greeted successfully.",
                            content = @Content(
                                    mediaType = MediaType.APPLICATION_JSON,
                                    array = @ArraySchema(schema = @Schema(implementation = GreetResponse.class))
                            )
                    ),
                    @ApiResponse(
                            responseCode = "400",
                            description = "Bad request. Request is not well formed."
                    )
            }
    )
    public Response greet(@Context UriInfo uriInfo) {
        if (!uriInfo.getQueryParameters().containsKey("name")) {
            throw new BadRequestException("'name' query parameter is missing.");
        }
        return Response
                .ok()
                .entity(new GreetResponse(GREET_MESSAGE + " " + uriInfo.getQueryParameters().getFirst("name")))
                .build();
    }
}

Generated OpenAPI documentation - JSON

{
  "openapi" : "3.0.1",
  "info" : {
    "title" : "Guice Grizzly Jersey Openapi Swagger Example API",
    "description" : "OpenAPI swagger configuration example in sample project that uses Guice, Grizzly, Jersey.",
    "contact" : {
      "email" : "jayeshmaheshpatel@gmail.com"
    },
    "license" : {
      "name" : "MIT License",
      "url" : "https://en.wikipedia.org/wiki/MIT_License"
    },
    "version" : "1.0.0"
  },
  "servers" : [ {
    "url" : "http://localhost:8080/OpenAPIExample/",
    "description" : "Guice Grizzly Jersey Openapi Swagger Example API server"
  } ],
  "paths" : {
    "/greet" : {
      "get" : {
        "summary" : "This is a sample test API to greet user.",
        "operationId" : "greet",
        "parameters" : [ {
          "name" : "name",
          "in" : "query",
          "schema" : {
            "type" : "string"
          }
        } ],
        "responses" : {
          "200" : {
            "description" : "Greeted successfully.",
            "content" : {
              "application/json" : {
                "schema" : {
                  "type" : "array",
                  "items" : {
                    "$ref" : "#/components/schemas/GreetResponse"
                  }
                }
              }
            }
          },
          "400" : {
            "description" : "Bad request. Request is not well formed."
          }
        }
      }
    }
  },
  "components" : {
    "schemas" : {
      "GreetResponse" : {
        "type" : "object",
        "properties" : {
          "message" : {
            "type" : "string"
          }
        }
      }
    }
  }
}

Generated OpenAPI documentation - YAML

openapi: 3.0.1
info:
  title: Guice Grizzly Jersey Openapi Swagger Example API
  description: "OpenAPI swagger configuration example in sample project that uses\
    \ Guice, Grizzly, Jersey."
  contact:
    email: jayeshmaheshpatel@gmail.com
  license:
    name: MIT License
    url: https://en.wikipedia.org/wiki/MIT_License
  version: 1.0.0
servers:
  - url: http://localhost:8080/OpenAPIExample/
    description: Guice Grizzly Jersey Openapi Swagger Example API server
paths:
  /greet:
    get:
      summary: This is a sample test API to greet user.
      operationId: greet
      parameters:
        - name: name
          in: query
          schema:
            type: string
      responses:
        "200":
          description: Greeted successfully.
          content:
            application/json:
              schema:
                type: array
                items:
                  $ref: '#/components/schemas/GreetResponse'
        "400":
          description: Bad request. Request is not well formed.
components:
  schemas:
    GreetResponse:
      type: object
      properties:
        message:
          type: string

You can download the full application here:

https://github.com/javabypatel/guice-grizzly-jersey-openapi-swagger-example

Create Docker Image of Spring Boot Microservices using Fabric8 maven plugin.

in Docker - on 01:29:00 - No comments

Create Docker Image of Spring Boot Microservices using Fabric8 maven plugin.

In this post we will see how to create a Docker image of Spring Boot Microservice using Fabric8 maven plugin.

Steps,

1. First we will create a Spring Boot Microservice with some REST endpoints
2. Run the Spring Boot Microservice and access the endpoints to see if it works.
3. Create the docker image of a Microservice created above.
4. Run the Spring Boot Microservice Docker image to see if we can access the REST endpoints.

Spring Boot Microservices Hello World Example

Download the Spring Boot Microservices Hello World Example from GitHub:
spring-boot-docker-hello-world

Layout of the application is as shown below,

spring-boot-docker-fabric8-maven-plugin-example

It is a Spring Boot Microservice exposing only one endpoint "/"

resources/application.properties

Microservice contains application.properties file through which we can define the application context, change the default post on which application is going to deploy.

In this example we changed the default application port to 8085

Dockerfile

Microservice also contains Dockerfile which contains instructions for the Docker as how to create the image of this Microservice.

FROM adoptopenjdk/openjdk11-openj9:alpine
ADD target/${project.build.finalName}.jar /myapp/${project.build.finalName}.jar
EXPOSE 8080
ENTRYPOINT java -jar /myapp/${project.build.finalName}.jar

Get the base image adoptopenjdk/openjdk11-openj9:alpine,

Add our microservice jar inside docker image file directory at location "/myapp",

Expose the container port 8080 (this means Docker image container will listen on port 8080)

Start our Microservice jar

Run the Spring Boot Microservices Hello World Example

Run the SpringBootDockerHelloWorldApp file as Java application.

When you see below logs in console,

[main] o.s.b.w.embedded.tomcat.TomcatWebServer : Tomcat started on port(s): 8085 (http)

[main] c.j.SpringBootDockerHelloWorldApp : Started SpringBootDockerHelloWorldApp

Go to browser and hit url http://localhost:8085/, you will see response as "Hello JavaByPatel"

Create the Docker image of Spring Boot Microservices using Fabric8 maven plugin
Run the command,

1. mvn clean install
This will create the target directory and place the generated jar of our Microservice inside directory with name "spring-boot-docker-hello-world-0.0.1-SNAPSHOT.jar"

2. mvn fabric8:build
This will create the docker image of the Microservice inside the running Docker.
run the command below to see existing "docker images"

Inside the target directory, you would see a new folder name Docker containing image tar file.

Running the Docker image

Run the command,

docker run -p 8085:8085 spring-boot-docker-hello-world:0.0.1-SNAPSHOT.dev

Here we are saying, map the container port 8085 to Tomcat port 8085 running inside container.

Go to browser and hit "http://localhost:8085/", it should give the response as "Hello JavaByPatel"

In case if the URL is not reachable, check the IP of docker by issuing the command(I was running Docker toolbox on windows and has to provide IP instead of localhost),

$ docker-machine ip

192.168.98.112

Go to browser and hit, "http://192.168.98.112:8085/", It should work now.

Write your own Integer to String (itoa) implementation in Java

in Interviews, Miscellaneous - on 00:28:00 - No comments

Write your own Integer to String (itoa) converter.

Implement your own Integer to ASCII (itoa) method which converts an Integer to String.

Input 1: 123
Output: "123" (as String)

Input 2: 0
Output: "0" (as String)

Input 3: 8
Output: "8" (as String)

Algorithm

Before we look into the algorithm, lets understand the ASCII ranges for 0-9.

ASCII Char

---------------

48 0

49 1

50 2

51 3

52 4

53 5

54 6

55 7

56 8

57 9

so if we have integer 4 and we want to get the char representation of 4, we can get by

char number = '0' + 4 which would be 48 + 4 = 52 and when we do ((char) 52) we get '4'.

similarly, if we have integer 7 and we want to get the char representation of 7, we can get by

char number = '0' + 7 which would be 48 + 7 = 55 and when we do ((char) 55) we get '7'.

Lets jump to original problem, if given the number 123

Mod and Divide the number by 10 to read each digits from end, once we have the digit convert it in the way shown below and put in StringBuilder.

Java Program to convert Integer To Ascii.

package javabypatel;

public class IntegerToASCII {
    public static void main(String[] args) {
        System.out.println(integerToAscii(10));
    }

    private static String integerToAscii(int num) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            int lastDigit = num % 10;
            char ch = (char) ('0' + lastDigit);

            // since we are processing the last digit first(reverse order),
            // inserting at 0th position so that output is not in reverse order.
            sb.insert(0, ch);
            num /= 10;
        }
        return sb.toString();
    }
}

Write your own String to Integer (atoi) implementation in Java

in Interviews, Miscellaneous - on 00:07:00 - No comments

Write your own String to Integer (atoi) converter.

Implement your own ASCII to Integer (atoi) method which converts a string to an integer.

Input 1: "123"
Output: 123 (as int)

Input 2: "0"
Output: 0 (as int)

Input 3: "8"
Output: 8 (as int)

Algorithm

Before we look into the algorithm, lets understand the ASCII ranges for 0-9.

ASCII Char

---------------

48 0

49 1

50 2

51 3

52 4

53 5

54 6

55 7

56 8

57 9

so if we have char '4' and we want to get the Integer representation of '4', we can get by

int number = '4' - '0' which would be 52 - 48 = 4 (an integer 4),

similarly, if we want to get the integer representation of char '7', just subtract it by '0'.

int number = '7' - '0' which would be 55 - 48 = 7 (an integer 7), similarly

Lets jump to original problem, if given the String "123"

Iterate the String, get the first character '1', convert it to Integer as shown above.

Similarly for all the characters of the String.

For getting the integer number, we will use the technique,

sum = 0 initially.

sum = (sum * 10) + (str.charAt(i) - '0')

Java Program to convert Ascii To Integer.

    

package javabypatel;

public class ASCIIToInteger {
    public static void main(String[] args) {
        System.out.println(asciiToInt("10"));
    }

    private static int asciiToInt(String num) {
        int result = 0;
        for (int i = 0; i < num.length(); i++) {
            char ch = num.charAt(i);
            result = (result * 10) + (ch - '0');
        }
        return result;
    }
}

Merge all overlapping intervals in Java

in Interviews - on 17:22:00 - No comments

Merge overlapping intervals in Java.

Given a N pairs of intervals. merge all overlapping intervals..

You are given a pair of intervals in a format (start time, end time), Merge intervals that overlaps with each other.

Consider this problem as asking someone availability in their calendar, and if the person calendar is like below,
Meeting from [[1,2],[2,3],[3,4],[10,12]] what the person will say?
I am busy from [1-4] and [10-12], it is like merging intervals that overlaps.

Example of Merging overlapping intervals

Let see some more input and output:

Example 1: Input: intervals = [[1,2],[2,3],[3,4],[10,15]]
Output: [[1,4],[10,15]]

Example 2: Input: intervals = [[1,5],[3,5],[2,6],[10,15]]
Output: [[1,6],[10,15]]

Example 3: Input: intervals = [[1,4],[2,6]]
Output: [[1,6]]

Algorithm

Lets say we are given below time intervals

(1, 4), (7, 9), (3, 6), (8, 10)

If we sort the time intervals based on start time,

(1, 4), (3, 6), (7, 9), (8, 10)

If we see the first two interval, end time of first interval is greater than start time of second interval which means there is overlap of (end time - start time).

Our task is to Iterate all the intervals and compare, if there is overlap, just Merge the both intervals into one and expand the endInterval window by comparing endTime of both intervals and consider the one which is highest.

(1, 4), (3, 6),

Merged Interval = (1, 6)

(7, 9)

totally new range, doesn't overlap with the Merged Interval till now (1, 6)

Put it in our Merged Interval list [(1, 6), (7, 9)]

(8, 10)

Compare the top interval from merged interval list that is compare (7, 9) with (8, 10)

there is overlap, update the window (7, 10), update the merged interval list (1, 6) (7, 10).

Java Program to Merge overlapping intervals.

    
package javabypatel

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class MergeOverlappingIntervals {

    public static void main(String[] args) {
        List<Interval> intervals = Arrays.asList(
                new Interval(1, 2),
                new Interval(2, 3),
                new Interval(3, 4),
                new Interval(10, 15));

        Stack<Interval> mergedIntervals = new MergeOverlappingIntervals().mergeOverlappingIntervals(intervals);
        System.out.println(mergedIntervals);
    }

    public Stack<Interval> mergeOverlappingIntervals(List<Interval> intervals) {
        if (intervals == null) {
            return null;
        }

        Stack<Interval> stack = new Stack<>();
        if (intervals.size() < 2) {
            stack.addAll(intervals);
            return stack;
        }

        Collections.sort(intervals);

        //We can take any data structure which can help us compare the top element.
        stack.add(intervals.get(0));

        for (int i = 1; i < intervals.size(); i++) {
            Interval nextInterval = intervals.get(i);
            Interval resultInterval = stack.peek();

            //Check if Interval overlaps? If yes, increase the end time
            //example (1, 3) (2, 6) -> Intervals overlaps,
            //end time will be max of both end time = 6
            //since the array is sorted by startTime, no need to update the startTime as smallest will be at top.
            if (resultInterval.endTime >= nextInterval.startTime) {
                //update the peek endTime
                resultInterval.endTime = Math.max(resultInterval.endTime, nextInterval.endTime);
            } else {
                //if no overlaps then this is the new range, add it in stack.
                stack.add(nextInterval);
            }
        }

        return stack;
    }
}

Interval.java

package javabypatel;

public class Interval implements Comparable<Interval>{
    public int startTime;
    public int endTime;

    public Interval(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Interval interval) {
        if (startTime < interval.startTime) {
            return -1;
        } else if (startTime == endTime) {
            return 0;
        } else {
            return 1;
        }
    }

    @Override
    public String toString() {
        return "Interval{" +
                "startTime=" + startTime +
                ", endTime=" + endTime +
                '}';
    }
}

Find overlapping interval among a given set of intervals.

in Interviews - on 22:44:00 - No comments

Find overlapping interval among a given set of intervals.

Given a N pairs of intervals. Identify interval that overlap with other interval.

You are given a pair of intervals in a format (start time, end time), find interval that overlaps with other interval.

Example of overlapping intervals

Let see some more input and output:

Example 1:
Input: (1, 3) (3, 5) (5, 7)
Output: No overlapping Intervals.

Example 2: (2, 3) (3, 5) (1, 6)
Output: (1, 6) overlaps with (2, 3)
Though (3, 5) also overlaps with (1, 6) we are mainly looking for one of them. Given solution below find one of them.

Algorithm

Lets say we are given below time intervals

(1, 4), (7, 9), (3, 6), (8, 10)

If we sort the time intervals based on start time,

(1, 4), (3, 6), (7, 9), (8, 10)

If we see the first two interval, end time of first interval is greater than start time of second interval which means there is overlap of (end time - start time) in this case it is (4 - 3) = overlap of 1 unit.

Our task is to just find the overlapping intervals.

Java Program to find overlapping intervals among a given set of intervals.

package javabypatel;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class OverlappingIntervals {
    public static void main(String[] args) {
        List<Interval> intervals = Arrays.asList(
                new Interval(1, 3),
                new Interval(6, 8),
                new Interval(2, 4),
                new Interval(5, 6));
        List<Interval> interval = new OverlappingIntervals().findOverlappingIntervalApproach1(intervals);
        System.out.println("Overlapping intervals :" + interval);

        boolean isOverlappingIntervals = findOverlappingIntervalApproach2(intervals);
        System.out.println("Is overlapping intervals :" + isOverlappingIntervals);
    }

    //Sort the intervals by start time and compare the endtime of first interval with the start time of next interval.
    //If the endTime of first interval is > then startTime of next interval means there is overlap
    //Example: [(1, 3) (2, 4)]
    //time complexity: (n log n) + n = (n log n)
    public List<Interval> findOverlappingIntervalApproach1(List<Interval> intervals) {
        Collections.sort(intervals); //(n log n)
        List<Interval> overlappingInterval = new ArrayList<>();

        for (int i = 0; i < intervals.size()-1; i++) { //n
            if (intervals.get(i).endTime > intervals.get(i+1).startTime) {
                overlappingInterval.add(intervals.get(i));
                overlappingInterval.add(intervals.get(i+1));
            }
        }
        return overlappingInterval;
    }

    //Another approach which just says there is overlap or not.
    //time complexity:
    // O(n) = to find the max element in array
    // O(m) = where m is the max element in array
    // Total = O(m + n)
    // this approach works well when the range is small
    public static boolean findOverlappingIntervalApproach2(List<Interval> intervals){
        //find the highest end time within list of all intervals
        int highestTime = intervals.get(0).endTime;
        for (int i = 1; i<intervals.size(); i++) {
            int endTime = intervals.get(i).endTime;
            if(highestTime < endTime)
                highestTime = endTime;
        }

        int[] count = new int[highestTime + 1];
        //Mark the count[startTime] to +1 and count[endTime] to -1
        for (int i = 0; i<intervals.size(); i++) {
            Interval current = intervals.get(i);
            count[current.startTime]++;
            count[current.endTime]--;
        }

        //Iterate count array and sum the values
        //if at any point sum is > 1 that means interval overlaps.
        boolean isOverlappingIntervals = false;

        int sum = 0;
        for (int i = 0; i <count.length; i++) {
            sum += count[i];
            if(sum > 1){
                isOverlappingIntervals = true;
                break;
            }
        }

        return isOverlappingIntervals;
    }
}

Interval.java

package javabypatel;

public class Interval implements Comparable<Interval>{
    public int startTime;
    public int endTime;

    public Interval(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Interval interval) {
        if (startTime < interval.startTime) {
            return -1;
        } else if (startTime == endTime) {
            return 0;
        } else {
            return 1;
        }
    }

    @Override
    public String toString() {
        return "Interval{" +
                "startTime=" + startTime +
                ", endTime=" + endTime +
                '}';
    }
}

Approach 2

In this approach, we are going to take a count array and for each given interval start time we will do count[startTime]++ and for end time, do count[endTime]--.

After filling the count array, iterate count array and do the sum of counts, If at any given index we find

sum > 2 it means there is overlapping intervals.

How this approach is working? say if we have intervals as (1, 3) and (2, 5), and count array for this will be. array size will be 5(highest end time in given intervals)

(1, 3) = [0, 1, 0, -1, 0, 0]

(2, 5) = [0, 1, 1, -1, 0, -1]

Whenever we see adjacent one's, it means there is y interval(in this case (2,5)) which has starting time before the end of x interval(1,3).

Serialize and Deserialize N-ary tree in Java

in Datastructure, Interviews, N-ary-tree - on 16:17:00 - No comments

Serialize and Deserialize N-ary tree in java

This is a popular interview question asked in Tier-1 companies.

Given an n-ary tree, serialize and deserialize it.

Example of N-ary tree Serialization-Deserialization.

Algorithm

Serialization and Deserialization of N-ary tree is very similar to Serialization and Deserialization of Binary tree.

I would recommend to visit the Serialization/Deserialization post if not visited before: Serialize and Deserialize a Binary Tree

In Binary tree since there are only 2 child, we can get where is the start and end of the child of a particular Node from the serailized key, but in N-ary tree a Node can have n children, so we need some method to identify the start and end of a child nodes.

In this approach we will do a preorder traversal of N-ary tree and place the length of child nodes next to Node value as shown in example below,

In Deserialization process, it is exactly reverse now, we know first key in the String is the actual node and next key is the length of child nodes of a key.

Java Program to Serialize Deserialize N-ary tree

package javabypatel;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class SerializeDeserializeNAryTree {

    public static void main(String[] args) {
        NAryNode root = new NAryNode(1,
                Arrays.asList(
                        new NAryNode(2, Arrays.asList(
                                new NAryNode(5),
                                new NAryNode(6),
                                new NAryNode(7, Arrays.asList(
                                        new NAryNode(11),
                                        new NAryNode(12))))),
                        new NAryNode(3),
                        new NAryNode(4, Arrays.asList(
                                new NAryNode(8),
                                new NAryNode(9),
                                new NAryNode(10)))
                ));

        String str = serializeTree(root, new StringBuilder());
        System.out.println(str);
        NAryNode deserializeRoot1 = deserializeApproach1(str == null? null : str.split(","), new int[1]);
        NAryNode deserializeRoot2 = deserializeApproach2(str);

        System.out.println(deserializeRoot1);
        System.out.println(deserializeRoot2);
    }

    //In this approach, we need to take a separate index array of size 1 to remember the next element in array to pick
    //or we can take a static integer to remember the state.
    private static NAryNode deserializeApproach1(String[] arr, int[] index) {
        if (arr == null || index[0] >= arr.length || arr[index[0]] == null) {
            return null;
        }

        NAryNode n = new NAryNode(Integer.parseInt(arr[index[0]++]));
        int size = Integer.parseInt(arr[index[0]++]);
        n.child = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            n.child.add(deserializeApproach1(arr, index));
        }
        return n;
    }

    //In this approach, we are converting serialized tree to Queue, so that when we do
    //queue.poll it will remove the element and we don't need to keep track of the next element to process.
    private static NAryNode deserializeApproach2(String str) {
        if (str == null) {
            return null;
        }
        return deserializeHelper(new LinkedList<String>(Arrays.asList(str.split(","))));
    }

    private static NAryNode deserializeHelper(Queue<String> queue) {
        if (queue.isEmpty()) {
            return null;
        }

        NAryNode n = new NAryNode(Integer.parseInt(queue.poll()));
        int size = Integer.parseInt(queue.poll());
        n.child = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            n.child.add(deserializeHelper(queue));
        }
        return n;
    }

    private static String serializeTree(NAryNode root, StringBuilder sb) {
        if (root == null) {
            return null;
        }

        sb.append(root.data);
        sb.append(",");

        if (root.child != null) {
            sb.append(root.child.size());
            sb.append(",");
            for (int i = 0; i<root.child.size(); i++) {
                serializeTree(root.child.get(i), sb);
            }
        } else {
            sb.append(0);
            sb.append(",");
        }
        return sb.toString();
    }
}

NAryNode.java

package javabypatel;

import java.util.List;

public class NAryNode {
    public int data;
    public List<NAryNode> child;

    public NAryNode(int data, List<NAryNode> child) {
        this.data = data;
        this.child = child;
    }
    public NAryNode(int data) {
        this.data = data;
    }
}

N-ary tree preorder traversal in java

in Datastructure, Interviews, N-ary-tree - on 14:52:00 - No comments

N-ary tree preorder traversal in java

This is a popular interview question asked in Tier-1 companies.

Given an n-ary tree, print preorder traversal of its nodes values.

Example of N-ary tree preorder traversal below:

Algorithm

Preorder traversal: To traverse a Binary Tree in Preorder, following operations are carried-out
Visit the root node and print data of that node.
Traverse the left subtree, and
Traverse the right subtree.

Preorder traversal of N-ary tree is very similar to that of Binary tree preorder traversal, only difference is instead of two children in Binary tree here we have N children.

Preorder traversal of Binary tree: Binary Tree Preorder Traversal

Considering the example above,
we will first visit the root Node 1, then instead of directly going Left and then Right that is what we do in Binary tree preorder traversal because there is only 2 children, here we don't know the number of child, so what we are going to do is loop for all the child and then do a Preorder traversal for each child.

Visit Root Node 1,
loop for all the children [Node 2, Node 3, Node 4] (i = 0, i<3; i++) i=0

Visit Node 2,
Iterate all its children [Node 5, Node 6, Node 7] (i = 0, i<3; i++) i=0

Visit Node 5,
Iterate all its children []

Node 5 has no children so we came back to Node 2, now i = 1

Came back to Node 2,
Iterate all its children [Node 5, Node 6, Node 7], (i = 0, i<3; i++), i =2 do for Node 6.

and it continues.

Java Program to print N-ary tree preorder traversal

package javabypatel;

import java.util.Arrays;

public class NAryTreeTraversal {
    public static void main(String[] args) {
        NAryNode root = new NAryNode(1,
                Arrays.asList(
                        new NAryNode(2, Arrays.asList(
                                    new NAryNode(5),
                                    new NAryNode(6),
                                    new NAryNode(7, Arrays.asList(
                                                new NAryNode(11),
                                                new NAryNode(12))))),
                        new NAryNode(3),
                        new NAryNode(4, Arrays.asList(
                                    new NAryNode(8),
                                    new NAryNode(9),
                                    new NAryNode(10)))
                ));

        preOrderTraversal(root);
    }

    private static void preOrderTraversal(NAryNode start) {
        if (start == null) {
            return;
        }

        System.out.print(start.data + ",");
        if (start.child != null) {
            for (int i = 0; i < start.child.size(); i++) {
                preOrderTraversal(start.child.get(i));
            }
        }
    }
}

NAryNode.java

package javabypatel;

import java.util.List;

public class NAryNode {
    public int data;
    public List<NAryNode> child;

    public NAryNode(int data, List<NAryNode> child) {
        this.data = data;
        this.child = child;
    }
    public NAryNode(int data) {
        this.data = data;
    }
}

Minimum deletions required to make frequency of each letter unique in a String in Java

in Array, PriorityQueue - on 20:10:00 - No comments

Minimum deletions to make frequency of each character unique

This is a popular interview question asked in Tier-1 companies.

Given a string, find the minimum number of characters to be deleted in a string so that the frequency of each character in the string is unique.

Question 1:
String s = 'aaaabbbcccdddd'
Frequency of characters : { a=4, b=3, c=3, d=4 }

a nd d both have same frequency 4, similarly b and c have same frequency 3. so frequency is repeated and we need to make it unique.
we need to delete three character from a, one characters from b to make their frequency different.
s = 'abbcccdddd'

Frequency of characters : { a=1, b=2, c=3, d=4 }

Detailed Description:
we need to make the frequency unique,
Either we need to delete one character from a or d so that we break the same frequency.
so we delete a, now string is "aaabbbcccdddd"

Now the frequency of a is 3, b is 3, c is 3 and d is 4
the frequency of a, b and c is repeating, we need to delete one character from a,
s = 'aabbbcccdddd'

Now the frequency of a is 2, b is 3, c is 3 and d is 4
the frequency of b and c is repeating, we need to delete one character from b, but this will make b count to 2 which will be same as a count, so we will delete 2 characters from b so the frequency will be 1.
s = 'aabcccdddd'

Now the frequency of a is 2, b is 1, c is 3 and d is 4, so is unique now.

Answer is 4 because we delete 4 characters to make the frequency unique.

Java Program to find minimum deletions in a String to make the frequency of each character unique

package javabypatel;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class MinimumDeletionUsingPriorityQueue {
    public static void main(String[] args) {
        System.out.println(countFrequency("aaaabbbcccdddd"));
    }

    private static int countFrequency(String str) {

        if (str == null || str.length() < 2) {
            return 0;
        }

        //Taking a map to find unique occurrence of each character in a string.
        Map<Character, Integer> frequencyCount = new HashMap<>();
        for (char ch: str.toCharArray()) {
            int count = frequencyCount.getOrDefault(ch, 0);
            frequencyCount.put(ch, count + 1);
        }

        //Taking a PriorityQueue for processing the count of each occurrence of a character
        //Putting the values in reverse order so that higher counts are at head
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

        //dumping the frequency of each characters in a Priority queue.
        for (Map.Entry<Character, Integer> entry : frequencyCount.entrySet()) {
            priorityQueue.add(entry.getValue());
        }

        int deletionCount = 0;

        while (!priorityQueue.isEmpty()) {
            int frequency = priorityQueue.poll();

            //If there is no element left after poll, It means we are done, return deletionCount.
            if (priorityQueue.size() == 0 ) {
                return deletionCount;
            }

            //Here we are comparing the polled count with the count at the head. since our PriorityQueue is in reverse order
            //Counts that are same will be grouped together. So idea is to check polled and peek and if they are same it means we
            //need to delete one occurrence of a character to make it unique, but the catch is after deletion, the count which we encountered
            //may also be the occurrence count of other character present in a queue, so we have to repeat this process.
            //number of time we delete the occurrence, we add that in our deletionCount.
            if (frequency == priorityQueue.peek()) {
                //it means we have to delete one character to make the frequency unique
                priorityQueue.add(frequency-1);

                //Number of time we delete the character to make frequency unique, we have to increase the deletionCount.
                deletionCount ++;
            }
        }
        return deletionCount;
    }
}

JavaByPatel

In this post we will see how to integrate Swagger in Guice and Jersey to dynamically generate OpenAPI REST endpoint documentation.Sample project uses below libraries,1. Google Guice2. Jersey2. Grizzly server3. Swagger OpenAPI Annotations

openapi-configuration.json

This file contains the OpenAPI high-level resource description. you can describe the same using Swagger Annotations.

You may also like to see

In this post we will see how to create a Docker image of Spring Boot Microservice using Fabric8 maven plugin.Steps,

Download the Spring Boot Microservices Hello World Example from GitHub:spring-boot-docker-hello-world

Inside the target directory, you would see a new folder name Docker containing image tar file.

Run the command,docker run -p 8085:8085 spring-boot-docker-hello-world:0.0.1-SNAPSHOT.dev

You may also like to see

Implement your own Integer to ASCII (itoa) method which converts an Integer to String.Input 1: 123Output: "123" (as String)

Input 2: 0Output: "0" (as String)Input 3: 8Output: "8" (as String)

Before we look into the algorithm, lets understand the ASCII ranges for 0-9.

Java Program to convert Integer To Ascii.

You may also like to see

Implement your own ASCII to Integer (atoi) method which converts a string to an integer.Input 1: "123"Output: 123 (as int)

Input 2: "0"Output: 0 (as int)Input 3: "8"Output: 8 (as int)

Before we look into the algorithm, lets understand the ASCII ranges for 0-9.

Java Program to convert Ascii To Integer.

You may also like to see

Let see some more input and output:Example 1: Input: intervals = [[1,2],[2,3],[3,4],[10,15]]Output: [[1,4],[10,15]] Example 2: Input: intervals = [[1,5],[3,5],[2,6],[10,15]] Output: [[1,6],[10,15]] Example 3: Input: intervals = [[1,4],[2,6]] Output: [[1,6]]

Lets say we are given below time intervals

(1, 4), (7, 9), (3, 6), (8, 10)

If we see the first two interval, end time of first interval is greater than start time of second interval which means there is overlap of (end time - start time).

Java Program to Merge overlapping intervals.

You may also like to see

Given a N pairs of intervals. Identify interval that overlap with other interval.You are given a pair of intervals in a format (start time, end time), find interval that overlaps with other interval.Example of overlapping intervals

Let see some more input and output:Example 1:Input: (1, 3) (3, 5) (5, 7)Output: No overlapping Intervals.Example 2: (2, 3) (3, 5) (1, 6)Output: (1, 6) overlaps with (2, 3)Though (3, 5) also overlaps with (1, 6) we are mainly looking for one of them. Given solution below find one of them.

Lets say we are given below time intervals

(1, 4), (7, 9), (3, 6), (8, 10)

If we see the first two interval, end time of first interval is greater than start time of second interval which means there is overlap of (end time - start time) in this case it is (4 - 3) = overlap of 1 unit.

Java Program to find overlapping intervals among a given set of intervals.

You may also like to see

This is a popular interview question asked in Tier-1 companies.Given an n-ary tree, serialize and deserialize it.Example of N-ary tree Serialization-Deserialization.

Algorithm

Serialization and Deserialization of N-ary tree is very similar to Serialization and Deserialization of Binary tree.

I would recommend to visit the Serialization/Deserialization post if not visited before: Serialize and Deserialize a Binary Tree

You may also like to see

This is a popular interview question asked in Tier-1 companies.Given an n-ary tree, print preorder traversal of its nodes values.Example of N-ary tree preorder traversal below:

Algorithm

Preorder traversal: To traverse a Binary Tree in Preorder, following operations are carried-out Visit the root node and print data of that node. Traverse the left subtree, and Traverse the right subtree.

Visit Node 2, Iterate all its children [Node 5, Node 6, Node 7] (i = 0, i<3; i++) i=0Visit Node 5,Iterate all its children []Node 5 has no children so we came back to Node 2, now i = 1

Came back to Node 2, Iterate all its children [Node 5, Node 6, Node 7], (i = 0, i<3; i++), i =2 do for Node 6. and it continues.

Java Program to print N-ary tree preorder traversal

You may also like to see

Java Program to find minimum deletions in a String to make the frequency of each character unique

You may also like to see

Categories

Blog Archive

Search This Blog

Stay in touch -:)

Popular Posts

In this post we will see how to integrate Swagger in Guice and Jersey to dynamically generate OpenAPI REST endpoint documentation.

Sample project uses below libraries,
1. Google Guice
2. Jersey
2. Grizzly server
3. Swagger OpenAPI Annotations

In this post we will see how to create a Docker image of Spring Boot Microservice using Fabric8 maven plugin.

Steps,

Download the Spring Boot Microservices Hello World Example from GitHub:
spring-boot-docker-hello-world

Run the command,

docker run -p 8085:8085 spring-boot-docker-hello-world:0.0.1-SNAPSHOT.dev

Implement your own Integer to ASCII (itoa) method which converts an Integer to String.

Input 1: 123
Output: "123" (as String)

Input 2: 0
Output: "0" (as String)

Input 3: 8
Output: "8" (as String)

Implement your own ASCII to Integer (atoi) method which converts a string to an integer.

Input 1: "123"
Output: 123 (as int)

Input 2: "0"
Output: 0 (as int)

Input 3: "8"
Output: 8 (as int)

Let see some more input and output:

Example 1: Input: intervals = [[1,2],[2,3],[3,4],[10,15]]
Output: [[1,4],[10,15]]

Example 2: Input: intervals = [[1,5],[3,5],[2,6],[10,15]]
Output: [[1,6],[10,15]]

Example 3: Input: intervals = [[1,4],[2,6]]
Output: [[1,6]]

Given a N pairs of intervals. Identify interval that overlap with other interval.

You are given a pair of intervals in a format (start time, end time), find interval that overlaps with other interval.

Example of overlapping intervals

Let see some more input and output:

Example 1:
Input: (1, 3) (3, 5) (5, 7)
Output: No overlapping Intervals.

Example 2: (2, 3) (3, 5) (1, 6)
Output: (1, 6) overlaps with (2, 3)
Though (3, 5) also overlaps with (1, 6) we are mainly looking for one of them. Given solution below find one of them.

This is a popular interview question asked in Tier-1 companies.

Given an n-ary tree, serialize and deserialize it.

Example of N-ary tree Serialization-Deserialization.

This is a popular interview question asked in Tier-1 companies.

Given an n-ary tree, print preorder traversal of its nodes values.

Example of N-ary tree preorder traversal below:

Preorder traversal: To traverse a Binary Tree in Preorder, following operations are carried-out
Visit the root node and print data of that node.
Traverse the left subtree, and
Traverse the right subtree.

Visit Node 2,
Iterate all its children [Node 5, Node 6, Node 7] (i = 0, i<3; i++) i=0

Visit Node 5,
Iterate all its children []

Node 5 has no children so we came back to Node 2, now i = 1

Came back to Node 2,
Iterate all its children [Node 5, Node 6, Node 7], (i = 0, i<3; i++), i =2 do for Node 6.

and it continues.