Data Structures

Question: Design a data structure that can push, pop, and getmin in O(1), on given set of data.


Question: Design a data structure that allow insert, delete, max in O(1)

Question: Design a special stack that support these operation pop(), push(), isFull and getMin() or getMax(), in O(1).
Answer:
Maintain two stack, Main stack and other stack. Other stack will maintain the current max or min in Main stack. If you want minimum element then other stack will maintain minimum element, otherwise if you want maximum element then other stack will maintain current max element.
The answer is, you use two stacks: the main stack, and a min (or max) stack.
So for example, after pushing 1,2,3,4,5 onto the stack, your stacks would look like this:

MAIN   MIN
+---+  +---+
| 5 |  | 1 |
| 4 |  | 1 |
| 3 |  | 1 |
| 2 |  | 1 |
| 1 |  | 1 |
+---+  +---+

However, if you were to push 5,4,3,2,1, the stacks would look like this:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 2 |  | 2 |
| 3 |  | 3 |
| 4 |  | 4 |
| 5 |  | 5 |
+---+  +---+

For 5,2,4,3,1 you would have:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 3 |  | 2 |
| 4 |  | 2 |
| 2 |  | 2 |
| 5 |  | 5 |
+---+  +---+

and so on.
You can also save some space by pushing to the min stack only when the minimum element changes, iff the items are known to be distinct.

Strings

Question: For a given string, find its first non-repeating character?

Algorithm1: 
Step1: Make an array of 256,
Step2: Count frequency of all character and store in array. Here characters ASCII value is used as index.
Step3: Now again scan the string character by character, and check the frequency of current character. If it is one just break loop and return the first non-repeating character.

Time Complexity is O(n)+O(n)=O(n), but required two scan of given strings. Please remember here we required to scan string two times.

Algorithm2: 

Step1: Declare Data Structure which takes two fields 1. count, 2. index. count will be the frequency of characters and index is the index of character which occurs first time.  

class countCharAndIndex{
      int count;
      int index;
}

Step2: First make an array of countCharAndIndex. And  scan the string and count the frequency of each character and store the index, when any character occurs first time.

    a. countCharAndIndex [] array=new countCharAndIndex[256];
    b. For i=0 to length of countCharAndIndex-1.
           array[str.charAt(i)].count++;
           if(array[str.charAt(i)].count==1)// char str.charAt(i) occur first time
                 array[str.charAt(i)].index=i;
        return array;
  
   Here we need one scan of string.

Step3: Here we need only scan of array, whose length is 256.
   a. result=MAX
   b. for i=0 to 255
           if((array[i].count==1) && (array[i].index<result))
                    result=array[i].index;
       return result.

Time complexity is only O(n)+256=O(n), only one almost one scan.