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();
         }
     }
}

Sockets in C

Socket function creates an endpoint for communication and returns a descriptor. It has three arguments.

a. Protocol Family : AF_INET,(IPv4 internet protocols), AF_INET6(IPv6 internet protocols),                                              AF_UNIX, AF_LOCAL(Local Communication)
b. Communication Semantics :  SOCK_STREAM(tcp), SOCK_DGRAM(udp)
c. Protocol Type: ip(0), icmp(1),  ospf(89), isis(124)

Information regarding (a) and (b) can be found in man pages (man socket) in Linux.
Information regarding (c) can be found in protocols file in Linux (cat /etc/protocols).

Definition:

int socket(int domain, int type, int protocol);

This method returns a file descriptor on success and -1 on failure. It does not specify where data will be coming from nor where it will be coming, it just provides the interface.

 #include <sys/types.h>
 #include <sys/socket.h>
 #include <stdio.h>
 #include <errno.h>  // for error macros
 
int main(){

        int sock = socket(AF_INET, SOCK_STREAM, 0);
        if(sock != -1){
            printf("Socket created successfully\n");
            close(sock);
        }else if(sock == ENFILE){
            printf("The system limit on total number of open files has been reached\n");
       }
 
}

Generics in C++

C++ provides templates to define short, simple code and avoid code duplication.With templates programmers can define a family of functions or classes that can perform operations on multiple types of data. Through templates, C++ provides generic programming.

Entities such as functions or classes created using generic programming are called generics.

Uses of templates:

1. Templates are widely used to implement the Standard Template Library (STL).
2. Templates are used to create Abstract Data Types (ADTs) and classify algorithms and data                    structures.
3. Class templates are generally used to implement containers.

Function Templates

A function template enables a programmer to write generic code without specifying specific type of data. Template keyword tells the compiler that what follows is a template. Here class is keyword and T is generic argument. You can also use 'typename' instead of 'class'

template<class T> return-type function-name(T a,...){
     //body of template
}

Consider the c++ code below:

#include <iostream>
using namespace std;

//template definition
template<class T> void sum(T x, T y)
{
    cout << "Sum is:" << (x+y) ;
}

int main()
{
int a = 10, b = 20;
sum(a, b);
float p = 1.5, q = 2.4;
sum(p, q);
return 0;
}

Output for the above program is as follows:
Sum is: 30
Sum is: 3.9

Here, in first call to sum, integers are passed and float on the second call to sum.


Class object can also be passed as an argument as follows:

#include <iostream>
using namespace std;

class Student
{
    public:
        int age;
        string name;
 
    Student(int age, string name)
    {
        this->age = age;
        this->name = name;
    }
};

template<class T>void display(T &obj)
{
    cout << "Name is: " << obj.name << endl;
    cout << "Age is: " << obj.age << endl;
}

int main()
{
    Student s(25, "hey");
    display(s);  // object s of class Student passed as an argument.
    return 0;
}

Output for the above program is as follows:
Name is: hey
Age is: 25

Test if a given number is power of two in one line in C

In binary representation, a number is power of two if it has only one on bit and others bits as off.
For ex: binary representation of 8 is 1000 (contains only one on bit) whereas, that of 5 is 0101(contains two on bits).

If a number is power of two, for example 8, bitwise and of 8 and 7 is 0

Code:

#include <stdio.h>

int main(){
     int n = 8;
     if((!(n & (n-1)))){  // & is bitwise and whereas ! is logical not
          printf("The number is power of two\n");
     }else{
           printf("Not a power of two\n");
     }
     return 0;
}

However, this does not give correct result for n = 0. For n = 0, the above expression would be 1, thus printing, "the number is power of two". To accommodate, the case for n = 0, use the following code.

 #include <stdio.h>

int main(){
     int n = 8;
     if((n && !(n & (n-1)))){     // && is logical and, ! is logical not and & is bitwise and
          printf("The number is power of two\n");
     }else{
           printf("Not a power of two\n");
     }
     return 0;
}