Implement pop(), push(), min(), max() of Stack in O(1)

package algos;

public class SpecialStack {

int stack_size = 256;
int position;
int minPosition;;
int maxPosition;

int[] minStack;
int[] maxStack;
int[] stack;

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

public boolean isEmpty(){
if(stack.length == 0){
return true;
}
return false;
}

public SpecialStack(){
stack = new int[stack_size];
minStack = new int[stack_size];
maxStack = new int[stack_size];
position = 0;
minPosition = 0;
maxPosition = 0;
}

public boolean isFull(){
if(stack.length == stack_size){
return true;
}
return false;
}

public int pop(){
position -= 1;
if(position < 0){
System.out.println("Stack is empty");;
}
if(stack[position] == minStack[minPosition-1]){
minPosition--;
}
if(stack[position] == maxStack[maxPosition-1]){
maxPosition--;
}
return stack[position];
}

public void push(int data){
if(position >= stack_size){
System.out.println("Stack Overflow");
}
stack[position] = data;
position++;
if(data < min){
minStack[minPosition] = data;
minPosition++;
min = data;
}
if(data > max){
maxStack[maxPosition] = data;
maxPosition++;
max = data;
}
}

public int min(){
return minStack[minPosition-1];
}

public int max(){
return maxStack[maxPosition-1];
}

public static void main(String[] args){
SpecialStack s = new SpecialStack();
s.push(10);
s.push(9);
s.push(100);
s.push(12);
s.push(13);
s.push(8);
s.push(7);
s.push(6);
s.push(5);
s.pop();
s.pop();
s.push(1);
s.push(-1);
s.push(5);
s.push(15);
s.push(20);

System.out.println(s.min());
System.out.println(s.max());


}
}

Find the element that appears once

Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space.
Examples:

Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2

We can use sorting to do it in O(nLogn) time. We can also use hashing, it has the worst case time complexity of O(n), but requires extra space.

The idea is to use bitwise operators for a solution that is O(n) time and uses O(1) extra space. The solution is not easy like other XOR based solutions, because all elements appear odd number of times here.

       public static void main(String[] args){
int[] a = {12,12,23,34,45,23,34,45,444,555,444,555,2,2,3,333,333};
int[] result = new int[16];

               //although there are two for loops, time complexity if O(n) as inner loop runs a fixed                              number of times

for(int i = 0;i <= a.length - 1;i++){
for(int j = 15;j > 0;j--){
result[j] += (a[i] & 1);
a[i]  = a[i] >> 1;

}
}
               The result array contains number of set bits for all numbers in array. Since, the numbers are                repeated twice, we take modulus of 2 of every bit of result. If they were repeated thrice, we                  would have to take modulus of 3.

int r = 0;
for(int j = 15;j >= 0;j--){
r += (Math.pow(2, 15-j) * (result[j]%2));
}
System.out.println(r);
}

Appending file to Existing Zip File

A Zip file contains other files inside it. A docx file is essentially a zip file with a custom extension. Whenever you insert an image or other file to it is saves that file inside the zip file and a path to the new file is added in its document.xml file which is the main file that makes docx file.

Let's see how we can achieve the functionality of adding a file to an existing zip file.

If zipFileName is path to existing zip file and fileName, the File object to be added, we can use the following method to add fileName to zipFileName


import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.net.URL;
import java.net.URLConnection;
import java.util.List;
import java.util.zip.ZipEntry;
import java.util.zip.ZipOutputStream;

public class AddFileToZip {
     public static void appendFileToExistingZip(String zipFileName,File fileName) throws                                                                        IOException{
    if(!file.isFile()){
    return;
    }
    URLConnection conn = new URL("zip:" + zipFileName + "\\" +                                                             file.getName()).openConnection();
    byte[] buf = new byte[1024];
    // Compress the files
         InputStream in = new FileInputStream(file);
         // Add file to output stream.
         OutputStream os = conn.getOutputStream();
         // Transfer bytes from the stream to the ZIP file
         int len;
         while ((len = in.read(buf)) > 0) {
                 os.write(buf, 0, len);
         }
     
          in.close();
          os.close();
     }
}

Implement Stack Using Two Queues

import java.util.*;

public class Stack{

/*java.util.Queue is an interface. You can't instantiate interfaces. 
You need to create an instance of a class implementing that interface. In this case a LinkedList is such a class*/
Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();

     public static void main(String []args){
        Stack a = new Stack();
     
        try{
            a.push(10);
             a.push(20);
             a.push(30);
             a.push(40);
             Integer x = a.pop();
             System.out.println(x.toString());
             x = a.pop();
             System.out.println(x.toString());
             x = a.pop();
            System.out.println(x.toString());
             x = a.pop();
             System.out.println(x.toString());
             x = a.pop();
             System.out.println(x.toString());
        }catch(NullPointerException e){
        System.out.println(e.getMessage());
        }catch(Exception e){
        System.out.println(e.getMessage());
        }
     }
   
     public Stack(){
   
     }
   
/*start with checking for empty queue. It can be any of the two. Add new entry to empty queue.
 Then, enque all the entries in previoulsy non-empty queue to queue with newly added entry */
     public boolean push(Integer i) throws Exception{
         if(!q1.isEmpty() && !q2.isEmpty()){
        throw new Exception("Somethig went wrong");
         }
     
         if(q1.isEmpty()){
             q1.add(i);
             while(!q2.isEmpty()){
                 q1.add(q2.remove());
             }
         }else if(q2.isEmpty()){
             q2.add(i);
             while(!q1.isEmpty()){
                 q2.add(q1.remove());
             }
         }
         return true;
     }
   
     /* Since, one queue is always empty at the end of push operation, check for non-empty queue and return first element
which is always the latest addition to the stack class.*/
     public Integer pop() throws NullPointerException{
         if(!q1.isEmpty()){
             return q1.remove();
         }else if(!q2.isEmpty()){
             return q2.remove();
         }else{
        throw new NullPointerException("Stack is empty");
         }
     }
   
     //returns size of stack
     public Integer size(){
        if(!q1.isEmpty()){
             return q1.size();
         }else if(!q2.isEmpty()){
             return q2.size();
         }else{
        return 0;
         }
     }
   
     //checks if stack is empty
     public boolean isEmpty(){
    if(q1.isEmpty() && q2.isEmpty()){
    return true;
    }else{
    return false;
    }
     }
   
     /* returns head element without removing it*/
     public Integer peek(){
    if(!q1.isEmpty()){
             return q1.peek();
         }else{
             return q2.peek();
         }
     }
}