6. Get the positive smallest number that is missing in array

6. Get the positive smallest number that is missing in array

Tool

-Java 8
-CoderPad/sanbox

Solution

import java.io.*;
import java.util.*;
import static java.util.Comparator.*;
/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution
{
  public static void main(String[] args)
  {

//Init array 1
    List <Integer>array = new ArrayList<Integer>();
    array.add(3);
    array.add(4);
    array.add(-1);
    array.add(1);

//Get the smallest num that is missing in array
    int res = getMin(array);

//Print result
    System.out.println("The smallest number that is missing in array is "+res);
    // Init array 2
    List <Integer>array2 = new ArrayList<Integer>();
    array2.add(1);
    array2.add(2);
    array2.add(0);

// Get the smallest num that is missing in array 2
    int res2 = getMin(array2);

//Print result
    System.out.println("Min number that lefts in array 2 is "+res2);
  }
 
  public static int getMin(List<Integer>array)
  {

//Sort the array that identify faster the smallest num
    array.sort(Integer::compareTo);
    int res =0;
    for(int x=0; x<array.size();x++)
    {

//check if next element exists
      if(x+1 < array.size())
      {

//aux is equals to the current element plus one. This will help to identify the missing number
        int aux = array.get(x)+1;

//if aux is less than the next element in array and aux is diferent to 0. Then a element is missing in array
        if(array.get(x+1)> aux && aux >0)
        {

//Res is equeal to the current element in array plus 1 which means that the next number must be the current element plus one
          res =array.get(x)+1;
          break;
        }
      }
    }

//If res is equeal to 0 then the smallest number than is missing in array is the last number in array plus 1
    if(res ==0)
      res = array.get(array.size()-1)+1;
    return res;
  }
 
}

5. Serialize and Deserialize a binary tree

5. Serialize and Deserialize a binary tree

Tools

-Java 8
-CoderPad/SandBox

Solution

class Solution
     {
       public static void main(String[] args)
         {
         // Init a tree level 1
         Node root = new Node("root",null,null);
         root.right= new Node("righta",null,null);
         root.left= new Node("leftb",null,null);
         //Init tree level 2 left part
         root.right.right = new Node("righta.right",null,null);
         root.right.left= new Node("righta.left",null,null);
   
         //Init tree level 2 left part
         root.left.right=new Node("leftb.right",null,null);
   
         //Serialize the tree
         String res = Node.serialize(root);
         //Print the result
         System.out.println("Serialize: "+res);
         //Create a new tree from the Serialized tree
         Node root2 = Node.deSerialize(res);
         //Print the result. it must be similar to the previos tree
         System.out.print("Deserialize:");
         Node.print(root2);
       }
     }
     class Node
     {
       //Node Structure
         String value;
         Node right;
         Node left;
       //Empty construct
         public Node ()
         {
         }
       //Construct of a tree with values
         public Node(String value, Node left,Node right)
         {
           this.value = value;
           this.right=right;
           this.left=left;
         }
       //Serialize the tree
         public static String serialize (Node root)
         {
           //It uses a preorder method to serialize the tree
           return preorder(root,"",";root");
         }
         public static Node deSerialize(String tree)
         {
           /*
           Split the string into and array based on a regular expression. Don't forget to escape the separator, in mi case I used pipeline
           */
           String[] array = tree.split("\\|");
           //In first place, you need to send the method null, cero and the array
           Node root = preorderConstruct(null,0,array);
           return root;
         }
       /*
       Here node is the target node to evaluate
       String is the resulting string. The tree is serialing into it
       sense is the place that ocupes the target node into a previos node
       */
         public static String preorder(Node node, String string,String sense)
         {
           //Concatenate the resulting string to the new incoming values
           string = string + node.value+sense + "|";
           //Verify if there are nodes in tree. If true then move to left and get the string 
           if(node.left!=null)
           {
             string = preorder(node.left,string,";left");
           }
           //Verify if there are nodes in tree. If true then move to right and get the string
           if(node.right!=null)
           {
             string = preorder(node.right,string,";right");
           }
           // return string.
           return string ;
         }
       /*Method that re build the tree
       */
         public static Node preorderConstruct(Node prev,int index,String[]array)
         {
           //If index is less than lenght then do the precedure
           if(index < array.length)
           {
             //Get a node from the serializing string
             String sNode = array[index];
             //Split the node based on a regular expression
             String[] rNode = sNode.split(";");
             //Get the value and sense of the node based on a regular expression
             String value = rNode[0];
             String sense = rNode[1];
             //Create a new node with the values
             Node node = new Node(value,null,null);
             //If sense is equals to root then the previuos node must be the node that we created in the previous line
             if(sense.equals("root"))
             {
               prev = node;
             }
             //If sense is equals to left then we set the new node in the left side of the previous node
             if(sense.equals("left"))
             {
               prev.left= node;
             }
             //If sense is equals to left then we set the new node in the right side of the previous node
             if(sense.equals("right"))
             {
               prev.right= node;
             }
             //we send the new node, the increasing index by one and the array
             preorderConstruct(node,index+1,array);
           }
           return prev ;
         }
         public static void print(Node node)
         {
           System.out.print(node.value+"|");
           if(node.left!=null)
           {
             print(node.left);
           }
           if(node.right!=null)
           {
             print(node.right);
           }
         }
       }

4. Get a new array from another one by multiplying all the elements except the i element and store the result of each i place

 4. Get a new array from another one by multiplying all the elements except the i element and store the result of each i place

 Tools

-java 8
-CoderPad/Sandbox

Solution

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args)
  {
//Init array
    List <Integer> array = new ArrayList<Integer>();
    array.add(1);
    array.add(2);
    array.add(3);
    array.add(4);
    array.add(5);
    List<Integer> result = new ArrayList<Integer>();
//create an auxiliar to store the result of multiplying all elements of initial array
    int aux = 1;
//Get the result by multiplying all elements of initial array
    for(Integer in: array)
      aux = aux*in;
//Divide the auxiliar by the i element of the initial array and store in result array
    for(Integer in: array )
      result.add(aux / in);
//Print result
    System.out.println(result); // out: [120, 60, 40, 30, 24]
  }
}

Useful tools in java

Index

• 1. Grouping elements of a List -Java 8
• 2. Sorting a map by values - Java 8
• 3. Get first element in a map

1. Grouping elements of a List -Java 8

import java.io.*;
import java.util.*;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.function.Function;
...

List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(3);
list.add(1);
list.add(3);
list.add(2);
list.add(1);

Map<Integer,Long> group = list
                          .stream()
                          .collect
                           (
                             Collectors
                             .groupingBy
                              (
                                 Function.identity()
                                ,Collectors.counting()
                              )
                           )
  ;
System.out.println(group); // out: {1=3, 2=1, 3=2} 

2. Sorting a map by values - Java 8

 import java.io.*;
 import java.util.*;
...
 Map<Integer,Long> list = new HashMap<Integer,Long>();
list.put(3,0L);
list.put(2,5L);
list.put(1,3L);
list.put(4,2L);
 Map<Integer, Long> finalMap = new LinkedHashMap<>();
//This method does not mutate the original map
list
.entrySet()
.stream()
.sorted
(
  Map
  .Entry
  .<Integer,Long>comparingByValue()
  .reversed()
)
.forEachOrdered(e -> finalMap.put(e.getKey(),e.getValue()));

System.out.println(finalMap); //out: {2=5, 1=3, 4=2, 3=0}

3. Get first element in a map 

import java.io.*;
import java.util.*;
...
Map<Integer,Long> map = new HashMap<Integer,Long>();
map.put(3,0L);
map.put(2,5L);
map.put(1,3L);
map.put(4,2L);

System.out.println("Key:"+map.entrySet().stream().findFirst().get().getKey()); //out: Key:1
System.out.print("Value:"+map.entrySet().stream().findFirst().get().getValue());//out: Value:3

Solution to common problems in java

Solution to common problems in java

Index

Here are some solutions about common problems that you might get by applying to technical interviews. You can find the solutions that I developed for these problems. Feel free to share a better solution in the comments. Most of the code problems I solved were taken from https://www.dailycodingproblem.com/ by subscribing to the page and https://www.udemy.com/11-essential-coding-interview-questions/.

• 1. Get the most frequent element in a list - java 8
• 2. Get the elements in common between two lists - java 8
• 3. Find two numbers within an array that their sum be K - java 8
• 4. Get a new array from another one by multiplying all the elements except the i element and store the result of each i place
• 5. Serialize and Deserialize a binary tree
• 6. Get the positive smallest number that is missing in array

3. Find two numbers within an array that their sum be K - java 8

3. Find two numbers within an array that their sum be K - java 8

 

Tools:

-JDK 8
-CoderPad/Sanbox

Solution:

import java.io.*;
 import java.util.*;
 import java.util.Map;
 import java.util.stream.Collectors;

 class Solution
 {
   public static void main(String[] args)
   {
     //Init array
     ArrayList<Integer> array = new ArrayList<Integer>();
     array.add(10);
     array.add(15);
     array.add(3);
     array.add(7);
     int k=17;
     List<Integer> result=getNumbers(k,array);
     /*Verify result. If result size is higher than 2 then the method found the       numbers */
     if(result.size()==2)
       System.out.println(result.get(0)+" + "+result.get(1)+" = "+ k);
     else
       System.out.println("No numbers found");

   }
   //Method which seach two numbers that get K by adding each other

   public static List<Integer> getNumbers(int k, List<Integer>array)
   {
     /*Get a sorted map of the array. This help to find numbers faster than prove one by one*/
     Map<Integer,Integer> map = array
                               .stream()
                               .sorted()
                               .collect(Collectors
                                         .toMap(Integer::intValue,Integer::intValue));
    
     List <Integer> result= new ArrayList<Integer>();
     //check the results
     for (Map.Entry<Integer, Integer> entry : map.entrySet())
     {
       //get the resudue between key and k
       int reo = k - entry.getKey();
      /*If resudue is equal to itself and resudue is higher than k then it is impossible to get k by adding other number in array*/
       if((reo == entry.getKey() && reo + entry.getKey()> k) )
       {
         break;
       }
       /*if resudue is lower than key + 1 then it is impossible to get k by adding */
       else if(reo < (1+entry.getKey()))
       {
         break;
       }
       /*search resudue in map if the residue is found then the solution is gotten*/
       else
       {
         if(map.containsKey(reo))
         {
           result.add(reo);
           result.add(entry.getKey());
           break;
         }
       }
     }
     return result;
   }
 }

Comment: Leave a comment if you have a doubt or you have a better solution, also if you have any suggestion

2. Get the elements in common between two lists - java 8

2. Get the elements in common between two lists - java 8

 

Tools:

-JDK 8
-CoderPad/Sanbox

Solution:

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.function.Function;
class Solution
 {
   public static void main(String[] args)
   {
     //Init a
     List<Integer> a = new ArrayList<Integer>();
     a.add(1);
     a.add(3);
     a.add(4);
     a.add(6);
     a.add(8);
     a.add(9);

     //Init b
     List<Integer> b= new ArrayList<Integer>();
     b.add(1);
     b.add(2);
     b.add(3);
     b.add(5);
     b.add(6);
     b.add(8);

     List<Integer> commons = commonElements(a,b);
     //Print Result
     System.out.print("The elements in common between a and b are :"+ commons);
   }
  
   //method that find common elements between two lists
   public static List<Integer> commonElements(List<Integer> a,List<Integer>b)
   {
     List<Integer> result = new ArrayList<Integer>();
     //Maybe you would need to override equals and hash method for complex objects
     //This method find an element of a in b
     //This can be work in java 7 and less by replacing forEach to for block
     a.forEach(item->
                    {
                      if(b.contains(item))
                         result.add(item);
                    });
     return result;
   }
 }

Comment:

Leave a comment if you have a doubt or you have a better solution, also if you have any suggestion