Design a stack that supports getMinimum() in O(1) time

Problem statement:

Find the minimum element in a stack in O(1) time complexity and O(n) space complexity

Solution:

Maintain another stack and keep pushing the minimum element on the stack as in when found.

Before each push on stack 1, just check if the current element is less than the top element of the second stack if yes then push it on to stack 2.

While popping an element from stack1 check if the top of stack2 is same as the element in that case pop both the elements so that next minimum would show up on stack 2 for next min operation.

Inserts an element e1 to Stack.

push(int e1)

1) push e1 to the stack 1.

2) compare e1 with the top element(=e2) of the stack 2 (the auxiliary stack).

   a) If e1<e2, then push e1 to the auxiliary stack.

   b) If e1>e2, then push e2 to the auxiliary stack.

Removes an element from Stack and return the removed element.

int pop()

1) pop the top element from the auxiliary stack.

2) pop the top element from the actual stack and return it.

The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.

Returns the minimum element from Stack.

int getMinimum()

1) Return the top element of the auxiliary stack.

This would ensure that we pop out the minimum element in O(1) time.

Naïve String Matching Algorithm

It employs a Brute Force technique to identify the presence of a pattern in the given text.

It is not efficient algorithm because it takes the time complexity of the algorithm to check for a substring is O((m-n)n) where m is the length of the text and n is the length of the pattern (substring) to be searched.

There is no preprocessing is required for this algorithm, unlike KMP algorithm.

Preprocessing time: 0 (no preprocessing)

Matching time: O((n-m)m).

Pseudo Code:

NaiveStringMatcher(text, pattern)

tLen ← length [text]

pLen ← length [pattern]

for i ← 0 to tLen - pLen do

     mCount = 0;

for j ← 0 to pLen do

    if text[i] != pattern[j+i]

        break;

    mCount++;

     if(mCount == pLen)

           return Valid match found at position: + i!!

Implementation:

public class NaiveStringMatch {

      public static void main(String[] args) {

            String text = "I love to work on the algorithms!";

            String pattern = "the algorithms";

            naiveStringMatcher(text, pattern);

      }

      /**

       * Implementation of Naive String matching algorithm.

       * @param text

       * @param pattern

       */

      private static void naiveStringMatcher(String text, String pattern) {

            char[] txtArr = text.toCharArray();

            char[] patArr = pattern.toCharArray();

            int tLen = txtArr.length;

            int pLen = patArr.length;

            for (int i = 0; i < tLen - pLen; i++) {

               int charMatchCount = 0;

               for (int j = 0; j < pLen; j++) {

                    /**

                     * If pattern mismatch, break next searching point.

                     **/

                     if (patArr[j] != txtArr[i + j]) {

                          break;

                     }

                     charMatchCount++;

               }

               if (charMatchCount == pLen) {

                     print("String found at "+(i+1)+" position!!");

                     break;

               }

            }

      }

      private static void print(String string) {

            System.out.println(string);

      }

}

Output:

String found at 19 position!!

volatile is not always enough?

Even if the volatile keyword guarantees that all reads of a volatile variable are read directly from main memory, and all writes to a volatile variable are written directly to main memory, there are still situations where it is not enough to declare a variable volatile.

In fact, multiple threads could even be writing to a shared volatile variable, and still have the correct value stored in main memory, if the new value written to the variable does not depend on its previous value. In other words, if a thread writing a value to the shared volatile variable does not first need to read its value to figure out its next value.

As soon as a thread needs to first read the value of a volatile variable, and based on that value generate a new value for the shared volatile variable, a volatile variable is no longer enough to guarantee correct visibility. The short time gap in between the reading of the volatile variable and the writing of its new value creates a race condition where multiple threads might read the same value of the volatile variable, generate a new value for the variable, and when writing the value back to main memory - overwrite each other's values.

The situation where multiple threads are incrementing the same counter is exactly such a situation where a volatile variable is not enough.

Explain with an example:

Imagine if Thread 1 reads a shared counter variable with the value 0 into its CPU cache, increment it to 1 and not write the changed value back into main memory. Thread 2 could then read the same counter variable from main memory where the value of the variable is still 0, into its own CPU cache. Thread 2 could then also increment the counter to 1, and also not write it back to main memory.

                   

Thread 1 and Thread 2 are now practically out of sync. The real value of the shared counter variable should have been 2, but each of the threads has the value 1 for the variable in their CPU caches, and in main memory, the value is still 0. Even if the threads eventually write their value for the shared counter variable back to main memory, the value will be wrong.

When is volatile enough?

As I have mentioned earlier, if two threads are both reading and writing to a shared variable, then using the volatile keyword for that is not enough. You need to use a synchronized in that case to guarantee that the reading and writing of the variable is atomic. Reading or writing a volatile variable does not block threads reading or writing. For this to happen you must use the synchronized keyword around critical sections.

As an alternative to a synchronized block, we can use one of the many atomic data types found in the java.util.concurrent package (=AtomicLong, AtomicReference or one of the others).

In case only one thread reads and writes the value of a volatile variable and other threads only read the variable, then the reading threads are guaranteed to see the latest value written to the volatile variable. Without making the variable volatile, this would not be guaranteed.

The volatile keyword is guaranteed to work on 32 bit and 64 variables.

Java Serialization with Aggregation (HAS-A Relationship)

If a class has a reference to another class, all the references must be Serializable otherwise serialization process will not be performed. In such case, NotSerializableException is thrown at runtime.

Address.java

class Address { 

     String hNo,city,state; 

     public Address(String hNo, String city) { 

           this.hNo=hNo; 

           this.city=city; 

     } 

}

Employee.java

import java.io.Serializable; 

public class Employee implements Serializable { 

     int id; 

     String name; 

     Address address;//HAS-A 

     public Student(int id, String name) { 

           this.id = id; 

           this.name = name; 

     } 

} 

Since Address is not Serializable, we are getting NotSerializableException while serializing the instance of Employee class.

How to fix the Serialization in the case of Association?

Using the transient keyword:

In case the class refers to non-serializable objects and these objects should not be serialized, then, you can declare these objects as transient. Once a field of a class is declared as transient, then, it is ignored by the serializable runtime.

Using the static keyword:

In serialization, static variables are not serialized, so during deserialization, static variable value will load the class.

Make it a Serializable object:

All the objects within an object must be Serializable.