CareerCup

public class Solution {
  public static String encodeRepeatedChars(String source) {
      StringBuffer result = new StringBuffer();
      for (int idx = 0; idx < source.length(); idx++) {
          int runLength = 1;
          while (idx + 1 < source.length()
                  && source.charAt(idx) == source.charAt(idx + 1)) {
              runLength++;
              idx++;
          }
          result.append(runLength);
          result.append(source.charAt(idx));
      }
      return result.toString();
  }

  public static void main(String[] args) {
      String example = "aaaggbbbbc";
      System.out.println(encodeRepeatedChars(example));
  }
}

Time Complexity: O(N)

Can make use of Observer Design Pattern.
Here is a simple implementation of the Publisher/Subscriber model for StockMarket. As and when interviewer pose with some more questions, we can add on to it.

Publisher Interface:

public interface Publisher {
  public void setStockValue(int value);
  public void registerObserver(Observer observer);
  public void unRegisterObserver(Observer observer);
  public void notifyAllObservers();
}

Subscriber(Observer) Interface:

public interface Observer {
   public void update(int newValue);
   public void display();
   public void unSubscribe();
}

StockMarket Class which implements the Publisher interface:

public class StockMarket : Publisher {
  Set<Observer> observers;
  int newValue;

  public StockMarket() {
	observers = new HashSet<Observer>();
	newValue = 0;
  }  
  
  public void setStockValue(int value){
    newValue = value;
  }
  
  public void registerObserver(Observer observer){
    observers.add(observer);
  }

  public void unRegisterObserver(Observer observer){
    if(observer != null && observer instanceof Observer){
	    observers.remove(observer);
	}
  }

  public void notifyAllObservers(){
	Iterator<Observer> observerIterator = observers.iterator();
	while(observerIterator.hasNext()){
		Observer observer = observerIterator.next();
		observer.update(this, null);
	}
  }
}

As a sample i will implement the PayPalStock which implements the Observer Interface. This inturn maintains a reference to the Publisher.

public class PayPalStock : Observer {
   Publisher stockMarket;
   int latestValue;

   public PayPalStock (Publisher subject){
   	latestValue = 0;
    stockMarket = subject;
    stockMarket.registerObserver(this); // Self-Registering to the Publisher
   }

   public void update(int newValue){
    latestValue = newValue;
    display();
   }

   public void display(){
     System.out.println("Latest Stock Price = " + latestValue);
   }

   public void unSubscribe(){
     stockMarket.unRegisterObserver(this);
   }
}

A more detailed design can be looked up at: http://read.pudn.com/downloads152/doc/663610/Software%20Design.pdf

MineSweeper game rules are briefed here:

The games is played on a M by N grid of `cells', each of which is either empty or contains an explosive mine. Your task (should you choose to accept it) is to locate all of the mines without causing any of them to explode.

Sounds easy? Well, unfortunately for you the location of the mines is a well-kept secret. In fact, at the beginning of the game you have no information as to whether any given cell contains a mine or not. Your only course of action is to `reveal' the contents of a chosen cell. Should you reveal a mine, the game is over and you have lost. If, however, you reveal an empty cell, two useful things will happen:

The program will indicate how many of the revealed cell's eight neighbours do contain mines.
Any neighbouring empty cells will also be revealed in the same way.

Together these should provide you with enough information to determine where the mines are hidden. The game is over (and you have won) when the number of unrevealed cells is equal to the number of mines on the board (since every unrevealed cell must then contain a mine).


Below are high level classes for the game. There are 2 classes: Board class and the MineSweeper Class.

public abstract class Board {

    // Board size
    protected int width, height;

    // Number of mines on the board
    protected int numMines;

    // Number of cells currently marked
    protected int numMarked;

    // Number of cells yet to be revealed
    protected int numUnknown;

    // Indicates where the mines are hidden
    protected boolean[][] mines;

    // The current state of the board
    protected int[][] board;

    // Constants for cell contents.  The MINE value might be returned by
    // reveal(), the others are only used internally but will probably be
    // required in subclasses.
    public static final int UNKNOWN = -1;
    public static final int MARKED = -2;
    public static final int MINE = -3;

    public Board(int width, int height, int numMines) {

        this.width = width;
        this.height = height;
        this.numMines = numMines;
        this.numMarked = 0;
        this.numUnknown = width * height;

        // Allocate storage for game board and mines
        mines = new boolean[width][height];
        board = new int[width][height];

        // Clear the board
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                mines[i][j] = false;
                board[i][j] = UNKNOWN;
            }
        }

        // Randomly allocate mines. 
        int cells = width * height;
        int temp = 0;
        Random rand = new Random();

        while (temp < numMines) {
            int cell = rand.nextInt();
            cell = (cell < 0 ? -cell : cell)%cells;
            if (!mines[cell%width][cell/width]) {
                mines[cell%width][cell/width] = true;
                temp++;
            }
        }
    }

    public void draw() {
        //Draw representation of Board
    }

    public int reveal(int x, int y) {
        //Reveal the contents of the cell at position (x, y) on the board.
    }

    public boolean mark(int x, int y)
        //Mark' the cell (x, y), probably to indicate that a player thinks there may be a mine there.
    }

    public boolean unmark(int x, int y) {
        //Unmark the previously marked cell at (x, y).
    }

    private int closeMines(int x, int y) {
        //Work out how many neighbours of cell (x, y) contain mines.  Return the
        //number of explosive neighbours.
    }
}



public class MineSweeper {
 
   // The game board
   private Board board;
 
   // Tokenizer for commands
   private StreamTokenizer tok;
 
   // Various flags used by play() and doCommand()
   private boolean done, quit, win;
 
   // Contents of last cell revealed
   private int lastCell;

    public MineSweeper(int width, int height, int mines) {
        // Create the game board
        board = new TextBoard(width, height, mines);
     
        // Set up the command tokenizer
        tok = new StreamTokenizer(new InputStreamReader(System.in));
     
        done = win = quit = false;
    }

    public void play() throws IOException {
        //Game play code goes here. On CLick what should happen
    }

    public static void main(String[] args) throws IOException {

     MineSweeper game;

     if (args.length < 3) {
       System.out.println("Usage: java MineSweeper width height mines");
       System.exit(0);
     }
     else {
       int width = Integer.parseInt(args[0]);
       int height = Integer.parseInt(args[1]);
       int mines = Integer.parseInt(args[2]);
       game = new MineSweeper(width, height, mines);
       game.play();
     }
    }
}

Left to Right.
Move variable i from rowStart till columnLength. (Print data from first row till last column.)

Top to Bottom.
Move variable i from (rowStart+1) till rowLength. (Print data in last column till)
We need to start from (rowStart+1) because, we already printed corner element in Left to Right printing and no need to include it again. Same treatment for corner elements in other directions.

Right to Left.
Move variable i from columnLength-1 till columnStart. (Print data in last row)

Bottom to Up.
Move variable i from rowLength-1 till rowStart. (Print data in first column)

After printing all 4 directions, In next iteration,
we need to start from second row and second column, so increment
(rowStart ++) and (columnStart++).
we need to print till second Last column and till second Last row, so decrement
(columnLength --) and (rowLength --).

vector<int> spiralOrder(vector<vector<int>>& matrix) {
	    vector<int> result;
		
		int rowStart = 0, rowLength = matrix.size() - 1, columnStart = 0, columnLength = matrix[0].size() - 1;
		while(rowStart<=rowLength && columnStart<=columnLength) {
		    //Right Sweeping 
		    for(int i=columnStart;i<=columnLength;i++) {
		        result.push_back(matrix[rowStart][i]);
		    }
		    //Downward Sweeping
		    for(int i = rowStart + 1; i <= rowLength; i++) {
		        result.push_back(matrix[i][columnLength]);
		    }
		    //Left Sweeping
		    if(rowStart != rowLength)
		    for(int i = columnLength - 1; i >= columnStart; i--) {
		        result.push_back(matrix[rowLength][i]);
		    }
		    //Upward Sweeping
		    if(columnStart != columnLength)
		    for(int i = rowLength - 1; i > rowStart; i--) {
		        result.push_back(matrix[i][columnStart]);
		    }
		    rowStart++;rowLength--;
		    columnStart++;columnLength--;
		}
		return result;  
    }

PsuedoCode:

initialization:
    // set semA to 1 so that the call to sem_wait in the
    // even thread will succeed right away
    sem_init(semA, 1)
    sem_init(semB, 0)

even_thread:
   to_print = 0;

   loop:
       sem_wait(semA);

       write(to_print);
       to_print += 2

       sem_post(semB)

odd_thread:
    to_print = 1

    loop:
        sem_wait(semB)

        write(to_print)
        to_print += 2

        sem_post(semA)

C Code:

pthread_mutex_t count_mutex     = PTHREAD_MUTEX_INITIALIZER;
    pthread_cond_t  condition_var   = PTHREAD_COND_INITIALIZER;

    void *functionCount1();
    void *functionCount2();

    int  count = 0;
    #define COUNT_DONE  200

    main()
    {
       pthread_t thread1, thread2;

       pthread_create( &thread1, NULL, &functionCount1, NULL);
       pthread_create( &thread2, NULL, &functionCount2, NULL);

       pthread_join( thread1, NULL);
       pthread_join( thread2, NULL);

       exit(0);
    }

    // Print odd numbers

    void *functionCount1()
    {
       for(;;)
       {

          // Lock mutex and then wait for signal to relase mutex
          pthread_mutex_lock( &count_mutex );


          // Check if the last emitted value was an odd; if so, wait till
          // an even is printed
          if (count % 2 != 0) {
              pthread_cond_wait( &condition_var, &count_mutex );
          }

          count++;
          printf("Counter value functionCount1: %d\n",count);
          pthread_cond_signal( &condition_var );

          if(count >= COUNT_DONE) {
             pthread_mutex_unlock( &count_mutex );
             return(NULL);
          }
          pthread_mutex_unlock( &count_mutex );
        }
    }


    // print even numbers
    void *functionCount2()
    {
       for(;;)
       {

          // Lock mutex and then wait for signal to relase mutex
          pthread_mutex_lock( &count_mutex );

          // Check if the last emitted value was an even; if so, wait till
          // an odd is printed
          if (count % 2 == 0) {
              pthread_cond_wait( &condition_var, &count_mutex );
          }

          count++;
          printf("Counter value functionCount2: %d\n",count);

          pthread_cond_signal( &condition_var );

          if(count >= COUNT_DONE) {
             pthread_mutex_unlock( &count_mutex );
             return(NULL);
          }
          pthread_mutex_unlock( &count_mutex );
        }
    }

    Output::
    ubuntu:~/work$ gcc even_odd.c -lpthread
    ubuntu:~/work$ ./a.out 
    Counter value functionCount1: 1
    Counter value functionCount2: 2
    Counter value functionCount1: 3
    Counter value functionCount2: 4
    Counter value functionCount1: 5
    Counter value functionCount2: 6
    Counter value functionCount1: 7
    Counter value functionCount2: 8
    Counter value functionCount1: 9
    Counter value functionCount2: 10

C++ Version:

Complexity: O(N) - N is the number of elements in the array

The root of a balanced BST should be the middle element from the sorted array.

There are two arrays left — The one on its left and the one on its right. These two arrays are the sub-problems of the original problem, since both of them are sorted. Furthermore, they are subtrees of the current node’s left and right child.

BSTNode* sortedArrayToBST(int sortedArr[], int start, int end) {
  if (start > end) 
  	return NULL;
  int mid = start + (end - start) / 2;
  BSTNode *node = new BSTNode(sortedArr[mid]);
  node->left = sortedArrayToBST(sortedArr, start, mid-1);
  node->right = sortedArrayToBST(sortedArr, mid+1, end);
  return node;
}

Static class is a Java class, which only contains static methods.
Ex: java.lang.Math
which contains lots of utility methods for various maths function e.g. sqrt().

No instance of this class exists. Only fields and methods can be directly accessed as constants or helper methods.

public final class ActionHelper {

    /**
     * private constructor to stop people instantiating it.
     */
    private ActionHelper() {
        // /this is never run
    }

    /**
     * prints hello world and then the users name
     * 
     * @param users
     *            name
     */
    public static void printHelloWorld(final String name) {
        System.out.println("Hello World its " + name);
    }

}

Singleton classes are those, which has only one instance during application life cycle. And usually have
private constructor and one static method to create the instance.
Ex: like java.lang.Runtime

Singleton Class is class of which only single instance can exists per classloader.

public class ClassicSingleton {
    private static ClassicSingleton instance = null;

    private ClassicSingleton() {
        // Exists only to defeat instantiation.
    }

    public static ClassicSingleton getInstance() {
        if (instance == null) {
            instance = new ClassicSingleton();
        }
        return instance;
    }
}

Some important Points:


1) Singleton can extend classes and implement interfaces, while a static class cannot (it can extend classes, but it does not inherit their instance members).
2) A singleton can be initialized lazily or asynchronously while a static class is generally initialized when it is first loaded, leading to potential class loader issues.
Static class provides better performance than Singleton pattern, because static methods are bonded on compile time.
3) One difference between Singleton and static is, ability to override. Since static methods in Java cannot be overridden, they leads to inflexibility. On the other hand, you can override methods defined in Singleton class by extending it.
4) Static classes are hard to mock and consequently hard to test than Singletons, which are pretty easy to mock and thus easy to test. It’s easier to write JUnit test for Singleton than static classes, because you can pass mock object whenever Singleton is expected, e.g. into constructor or as method arguments.
5) If your requirements needs to maintain state than Singleton pattern is better choice than static class, because
maintaining state in later case is nightmare and leads to subtle bugs.
6) Singleton classes can be lazy loaded if its an heavy object, but static class doesn't have such advantages and always eagerly loaded.
7) Many Dependency Injection framework manages Singleton quite well e.g. Spring, which makes using them very easy.
8) Main advantage of Singleton over static is that former is more object oriented than later. With Singleton, you can use Inheritance and Polymorphism to extend a base class, implement an interface and capable of providing different implementations. If we talk about java.lang.Runtime, which is a Singleton in Java, call to getRuntime() method return different implementations based on different JVM, but guarantees only one instance per JVM, had java.lang.Runtime an static class, it’s not possible to return different implementation for different JVM.
9) Singleton object stores in Heap but, static object stores in stack
10) We can clone the object of Singleton but, we can not clone the static class object
11) Singleton class follow the OOP(object oriented principles) but not static class
12) we can implement interface with Singleton class but not with Static class.

Class Cell  {
	---  Responsible Each individual cell of the game board
}
Class Board  {
	--- Class responsible for Drawing Board 
	--- Draw() method with taken NumCol and NumRow as input for 
		Drawing the Board with Cell[][]
}
Class Player  {
	--- Class for mainting Players 
	--- constructor taking Number of players as input for Multi Player support
	--- If no of player is not supplied, then create one player vs Computer
}
Class GameState  {
	--- To keep track of state of the Game
	--- Evaluate() method to check if somebody won the game becasue of a move made 
}

Class Game  {
	--- Responsible for Overrall control of the Game
	--- Keep track the Moves made by Player
	--- GamePlay() method taking care of rotation of players for their respective Turn
}

Putting out these details to the interviewer, you can start discussing what all detaisl are required and
keep evolving the design.

Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]‘) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”


Time Complexity: O(n)
Space: O(n) for stack.

import java.util.*;
class BalancedParenthesis {
    public static void main(String [] args){
        Scanner scan=new Scanner(System.in);
        String exp=scan.next();
        if(isParenthesisBalance(exp))
             System.out.println("Parenthesis is balanced");
        else
            System.out.println("Parenthesis is not balanced");
    }
    public static boolean isParenthesisBalance(String exp){
        Stack<Character> stack=new Stack<Character>();
        int size=exp.length();
        int i=0;
        char popChar;
        while(i<size){
            if(exp.charAt(i)=='{'||exp.charAt(i)=='('||exp.charAt(i)=='['){
                stack.push(exp.charAt(i));
                i++;
            }
            else if(exp.charAt(i)=='}'||exp.charAt(i)==']'||exp.charAt(i)==')'){
                if(stack.isEmpty())
                    return false;
                else
                    popChar=stack.pop();
                if(isSamePairsOfParenthesis(popChar,exp.charAt(i))){
                    i++;
                }
                else
                    return false;
            }
        }
        if(stack.isEmpty())
           return true;
        else
            return false;
    }
    public static boolean isSamePairsOfParenthesis(char left, char right){
        if(left=='(' && right==')' || left=='{' && right=='}'|| left=='[' && right==']')
            return true;
        else
            return false;
    }

TRIE can used for Auto-Complete.

Here is a simple java implementation:

// Trie.java
public class Trie {

  private TrieNode rootNode;

  public Trie() {
    super();
    rootNode = new TrieNode(' ');
  }

  public void load(String phrase) {
    loadRecursive(rootNode, phrase + "$");
  }

  private void loadRecursive(TrieNode node, String phrase) {
    if (StringUtils.isBlank(phrase)) {
      return;
    }
    char firstChar = phrase.charAt(0);
    node.add(firstChar);
    TrieNode childNode = node.getChildNode(firstChar);
    if (childNode != null) {
      loadRecursive(childNode, phrase.substring(1));
    }
  }

  public boolean matchPrefix(String prefix) {
    TrieNode matchedNode = matchPrefixRecursive(rootNode, prefix);
    return (matchedNode != null);
  }

  private TrieNode matchPrefixRecursive(TrieNode node, String prefix) {
    if (StringUtils.isBlank(prefix)) {
      return node;
    }
    char firstChar = prefix.charAt(0);
    TrieNode childNode = node.getChildNode(firstChar);
    if (childNode == null) {
      // no match at this char, exit
      return null;
    } else {
      // go deeper
      return matchPrefixRecursive(childNode, prefix.substring(1));
    }
  }

  public List<String> findCompletions(String prefix) {
    TrieNode matchedNode = matchPrefixRecursive(rootNode, prefix);
    List<String> completions = new ArrayList<String>();
    findCompletionsRecursive(matchedNode, prefix, completions);
    return completions;
  }

  private void findCompletionsRecursive(TrieNode node, String prefix, List<String> completions) {
    if (node == null) {
      // our prefix did not match anything, just return
      return;
    }
    if (node.getNodeValue() == '$') {
      // end reached, append prefix into completions list. Do not append
      // the trailing $, that is only to distinguish words like ann and anne
      // into separate branches of the tree.
      completions.add(prefix.substring(0, prefix.length() - 1));
      return;
    }
    Collection<TrieNode> childNodes = node.getChildren();
    for (TrieNode childNode : childNodes) {
      char childChar = childNode.getNodeValue();
      findCompletionsRecursive(childNode, prefix + childChar, completions);
    }
  }

  public String toString() {
    return "Trie:" + rootNode.toString();
  }
}

// TrieNode.java
public class TrieNode {

  private Character character;
  private HashMap<Character,TrieNode> children;

  public TrieNode(char c) {
    super();
    this.character = new Character(c);
    children = new HashMap<Character,TrieNode>();
  }

  public char getNodeValue() {
    return character.charValue();
  }

  public Collection<TrieNode> getChildren() {
    return children.values();
  }

  public Set<Character> getChildrenNodeValues() {
    return children.keySet();
  }

  public void add(char c) {
    if (children.get(new Character(c)) == null) {
      // children does not contain c, add a TrieNode
      children.put(new Character(c), new TrieNode(c));
    }
  }

  public TrieNode getChildNode(char c) {
    return children.get(new Character(c));
  }

  public boolean contains(char c) {
    return (children.get(new Character(c)) != null);
  }

  public int hashCode() {
    return character.hashCode();
  }

  public boolean equals(Object obj) {
    if (!(obj instanceof TrieNode)) {
      return false;
    }
    TrieNode that = (TrieNode) obj;
    return (this.getNodeValue() == that.getNodeValue());
  }

  public String toString() {
    return ReflectionToStringBuilder.reflectionToString(this, ToStringStyle.DEFAULT_STYLE);
  }
}

A Re-EntrantLock is owned by the thread last successfully locking, but not yet unlocking it. A thread invoking lock will return, successfully acquiring the lock, when the lock is not owned by another thread. The method will return immediately if the current thread already owns the lock.

public class ReEntrantLock {
    private int count = 0;
    private boolean isLocked = false;
    private Thread lockedByThread = null;
    

    public synchronized void lock() throws InterruptedException{
        while(isLocked && Thread.currentThread() != lockedBy){
            this.wait();
        }
        isLocked = true;
        lockedByThread = Thread.currentThread();
        count++;
    }

   public synchronized void unlock(){
        if (!isLocked || lockedByThread != Thread.currentThread()) {
            return;
        }
        count--;
        if(count == 0){
            isLocked = false;
            this.notify();
        }
    }
}

We can make use of method known as "Content Filtering"

Intro:

> Google news is a large multi-user streaming news application
> The data set has very high churn due to the abundance of new news stories
> There are too many stories to rely on the user’s discretion to filter interesting and uninteresting news
> There are thousands of users with known usage histories in the form of “click data”
> Because this is an online system with streaming data (users don’t want old news) an offline method will not work.


Make Decisions for Users:


> The method is called content filtering
> The goal is to use any data at your disposal about a user and about incoming articles to predict the user’s interest.
> More specifically you would need a function that would take a user and an article and generate a prediction for interest (0,1).
> Then order the list such that articles with a high interest prediction are presented to the user.


Available Data:


> We have a limited variety of data, however we have an abundance of a certain type of data from which we can compute metadata about users and news stories.
> Click Histories
>> Record the stories that a user has clicked on in the past
>> Store this along with all other users click histories in a large table
>> The table consists simply of news articles for columns and users for rows.


MAP REDUCE - a large cluster data processing framework can be used. In simple words this framework will do:

> User Program executes the framework.
> The framework assigns a master computer
> And partitions the data set over the available workers
> The workers map the data
> Once all mapping is complete the workers are reassigned reducing tasks.
> The result of the reducing tasks are returned to the User Program 


Map Reduce Example of Word Counts

Map - scan words from documents
	Map(String key, String value)‏
		//key: document name
		//value: document contents
		for each word w in value
			EmitIntermediate(w,”1”)‏
Reduce – add all word’s counts together
	Reduce(String key, Iterator value)‏
		//key: a word
		//value: a list of counts
		int result = 0
		for each v in value:
			result+= ParseInt(v)‏
		Emit(AsString(result))‏	

Memroy Based Method:

> Makes predictions based on a user’s past selections
> For each story generate a vector of users that clicked on the story.
> Then use a similarity measurement (dot product) in the user-vector space to compute a users’s similarity with all other users.
> Unfortunately this is not scalable
	O(n^2) to compare all stories with all other stories
	So we will borrow a previously mentioned comparison technique – Min-wise Hashing


Can look at Min-Hash Clustering, Map-Reduced Min-Hash Clustering.

Please refer the presented paper at the below:
Google News Personalization paper at www2007.org papers paper570.pdf

Take 2 arrays, isReq[256] and isFound[256] which tells the frequency of each character in S and while parsing the string S, the frequency of each character that has found yet.
Also, keep a counter which tells when a valid window is found.
Once a valid window is found, we can shift the window (towards right) maintaining the given invariant of the question.

Complexity: O(N)

Program in C++:

void findMinWindow(const char *S, const char *T, int &start, int &end){
        int SLen = strlen(S);
        int TLen = strlen(T);

        // Declare 2 arrays which keep tab of required & found frequency of each char in T
        int isReq[256] ;
        int isFound[256];
        int count = 0; //For valid window

        int minWindow = INT_MAX;

        //Prepare the isReq[] array by parsing the T
        for(int i=0;i<TLen;i++){
            isReq[T[i]]++;
        }

        //Let's start parsing the S now; Take 2 pointers: i and j - both starting at 0
        int i=0, j=0;
        
        //Keep moving j forward, keep i fixed till we get a valid window
        for(c=j;c<SLen;c++){
           //Check if the character read appears in T or not
           if(isReq[S[c]] == 0){
              //This character does not appear in the T; skip this
              continue;
           }
           //We have this character in the T, lets increment isFound for this char
           isFound[S[c]]++;

           //increment the count if this character satisfies the invariant
           if(isFound[S[c]] <= isReq[S[c]]){
              count++;
           }

           //Did we find a valid window yet?
           if(count == TLen){
              //A valid window is found..lets see if we can do better from here on
              //better means: increasing i to reduce window length while maintaining invariant
              while(isReq[s[i]] == 0 || isFound[s[i]] > isReq[s[i]]){
                   //Either of the above 2 conditions means we should increment i; however we 
                   // must decrease isFound for this char as well.
                   //Hence do a check again
                   if(isFound[s[i]] > isReq[s[i]]){
                      isFound[s[i]]--;
                   }
                   i++;
              }

               // Note that after the while loop, the invariant is still maintained
               // Lets check if we did better
               int winLength = j-i+1;
               if(winLength < minWindow){
                  //update the references we got
                  begin = i;
                  end = j;
                  //Update new minimum window lenght
                  minWindow = winLength;
               }
          } //End of if(count == TLen)
     } //End of for loop 
}

Complexity: O(n)

class PushZeroToLast
{
        public static void main (String[] args)
        {
                //int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
                int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9,0};
                int n = arr.length;
                pushZerosToLast(arr, n);
                System.out.println("Output: ");
                for (int i=0; i<n; i++)
                        System.out.print(arr[i]+" ");
        }

        static void pushZerosToLast(int arr[], int n)
        {
                int count = 0;

                for (int i = 0; i < n; i++)
                        if (arr[i] != 0)
                                arr[count++] = arr[i];

                while (count < n)
                        arr[count++] = 0;
        }
}

To solve this problem efficiently in O(N), you would need to track the minimum value’s index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).

void getMaxProfit(int stocks[], int sz, int &profit) {
	if (sz == 1) {
		profit = 0;
		return;
	}
	profit = 0;
	for (int i = 1; i < sz; i++) {
		while (i < sz && stocks[i] <= stocks[i-1]) {
			i++;
		}
		int buy = i-1;
		while (i = stocks[i-1]) {
			i++;
		}
		int sell = i-1;
		profit += stocks[sell]-stocks[buy];
	}
}

One of the easiest yet efficient methods to generate a list of prime numbers if the Sieve of Eratosthenes.

Here’s the basic idea:

>Create a list with all positive integers (starting from 2 as 1 is not considered prime).
>Start at the first valid number (at this point all are valid) and eliminate all its multiples from the list. So start with 2, and eliminate 4, 6, 8, 10, 12 and so on.
>Once all the multiples are eliminated advance to the next valid number (one that has not been eliminated) and repeat the process, until there are no more valid numbers to advance to.

Sieve of Eratosthenese algo

public class PrimeSieve {
    public static void main(String[] args) {
        final int N = 500000;

        // initially assume all integers are prime
        boolean[] isPrime = new boolean[N + 1];
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i*i <= N; i++) {

            // if i is prime, then mark multiples of i as nonprime
            // suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[i]) {
                for (int j = i; i*j <= N; j++) {
                    isPrime[i*j] = false;
                }
            }
        }

        // count primes
        int kPrime = Integer.parseInt(args[0]);
	// for N=500000 we can only have 41538 primes
        if ( kPrime <= 0 || kPrime > 41538 ) {
                System.out.println("Invalid Input.Please try again!!!");
                return ;
        }
        int i = 2;
        for (int primes = 0; primes < kPrime; i++) {
            if (isPrime[i]) primes++;
        }
        System.out.println("The " + kPrime + "th number of prime = " + (i-1) );
    }
}

Output:
$ java PrimeSieve 234
The 234th number of prime = 1481

$ java PrimeSieve 0
Invalid Input.Please try again!!!

Max Heap can be used in this scenario.

Basic tending system works based on #tag and its count e.g. how many times it has been shared in particular geography,You can go with Heap data structure when designing such system, say for example you wanna find out the top N trending keywords in you application/website,you can create heap of N #tag based on count (its should be max-heap).

Algorithm:

> Create max heap of size N. Time complexity to build the heap is O(N).
> For every new #tag compare its count with existing root (#tag) count if its greater then root count , replace root with this node (#tag, count) and call heapify to maintain the max-heap property. Heapify will take O(log N) time.
> Sort the heap if you're interested in ordering, it will take O(N log N) to sort the heap.
> At any time T heap will only contain the top N trending keywords.

int isBST(struct node* node) { 
  return(checkIsBST(node, INT_MIN, INT_MAX)); 
}

int checkIsBST(struct node* node, int min, int max) { 
  if (node==NULL) 
	return true;

  if (node->data<min || node->data>max) 
	return false;

  return 
     ( checkIsBST(node->left, min, node->data) && 
       checkIsBST(node->right, node->data+1, max) ); 
}

Redirect Part:

When you click on a link of any tiny url, an HTTP Request is sent to their server with the full URL, like http // bit.ly / b9 (not a real one).

They read the path part (here b9), which maps to their Database.

In the Database, they find the real URL. Then they issue a redirect, which is a HTTP 302 response and the target URL in the header.

Encoding Part:

One of the most popular URL shortening services simply take the ID in the database of the URL and then convert it to Base 62[a-zA-Z0-9].

import static org.testing.AssertJUnit.assertEquals ;

public class TinyURL {
	private static final String ALPHABET_MAP = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" ;
	private static final int BASE = ALPHABET_MAP.length() ;

	public static String encode ( int IndexNum ) {
		StringBuilder sb = new StringBuilder() ;
		
		while ( IndexNum > 0 ) {
			sb.append ( ALPHABET_MAP.charAt ( IndexNum % BASE ) ) ;
			IndexNum /= BASE ;
		}
		return sb.reverse().toString() ;
	}

	public static int decode ( String str ) {
		int Num = 0 ;

		for ( int i = 0, len = str.length(); i < len; i++ ) {
			Num = Num * BASE + ALPHABET_MAP.indexOf ( str.charAt(i) ) ;
		}
		return Num ;
	}

	public static void main ( String[] args ) {
		//System.out.println ( "Encoding for 123 is " + encode(123) ) ;
		//System.out.println ( "Decoding for b9 is " + decode ("b9" ) ) ;

		assertEquals ( "b9", encode(123) ) ;
		assertEquals ( 123, decode("b9") ) ; 
	}
}

Dependency injection/ IoC (inversion of control) – Is the main principle behind decoupling process that Spring does

Factory – Spring uses factory pattern to create objects of beans using Application Context reference

// Spring uses factory pattern to create instances of the objects
BeanFactory factory = new XmlBeanFactory(new FileSystemResource("application-config.xml"));
Triangle triangle = (Triangle) factory.getBean("triangle");
triangle.draw();

Proxy – used heavily in AOP, and also in remoting.

Singleton – by default, beans defined in spring config file (xml) are only created once. No matter how many calls were made using getBean() method, it will always have only one bean. This is because, by default all beans in spring are singletons.
This can be overridden by using Prototype bean scope.Then spring will create a new bean object for every request.

Model View Controller – The advantage with Spring MVC is that your controllers are POJOs as opposed to being servlets. This makes for easier testing of controllers. One thing to note is that the controller is only required to return a logical view name, and the view selection is left to a separate ViewResolver. This makes it easier to reuse controllers for different view technologies.

Front Controller – Spring provides DispatcherServlet to ensure an incoming request gets dispatched to your controllers.

View Helper – Spring has a number of custom JSP tags, and velocity macros, to assist in separating code from presentation in views.

Template method – used extensively to deal with boilerplate repeated code (such as closing connections cleanly, etc..). For example JdbcTemplate, JmsTemplate, JpaTemplate.

> Traverse the linked list and for each node , create a new node.
> Insert the new node in the original linked list right after the original node.
> Once the entire linked list is traversed , we would be having a linked list with each node followed by its duplicate node.

> Now Traversal again, this time only by iterating over the original nodes.
> For each originalNode , we set its duplicate's random pointer to its randomPointer's next.
> Then traverse the link list again & remove all the duplicate nodes from the link list and return the head pointer of the linked list.

public RandomList DuplicateRandomList(RandomList root) {
 
	if (!root)
		return null;
 
	RandomList ptr = root;
 
	//copy each node and insert to list adjacent to original
	while (ptr != null) {
		RandomList copy = new RandomList(ptr.label);
		copy.next = ptr.next;
		ptr.next = copy;
		ptr = copy.next;
	}
 
	//copying random pointer for each new node
	ptr = root;
	while (ptr != null) {
		if (ptr.random != null)
			ptr.next.random = ptr.random.next;
		ptr = ptr.next.next;
	}
 
	// generate two list by breaking
	ptr = root;
	RandomList newHead = root.next;
	while (ptr != null) {
		RandomList temp = ptr.next;
		ptr.next = temp.next;
		if (temp.next != null)
			temp.next = temp.next.next;
		ptr = ptr.next;
	}
 
	return newHead;
}

Complexity: O(n)

Evaluating without precedence is straight forward.

With Precedence:
Can make use of the following approaches:

1.Recursive-descent recognition
2.The shunting yard algorithm
3.The classic solution
4.Precedence climbing

The Shunting Yard Algo Approach:
The idea of the shunting yard algorithm is to keep operators on a stack until both their operands have been parsed. The operands are kept on a second stack.
The key to the algorithm is to keep the operators on the operator stack ordered by precedence (lowest at bottom and highest at top), at least in the absence of parentheses. Before pushing an operator onto the operator stack, all higher precedence operators are cleared from the stack.
Ex:

To evaluate 3 + 4 * 2 + 8. 

Intuitively, you "know" you have to do the 4 * 2  first, but how do you get this result? 

The key is to realize that when you're scanning the string from left to right, you will evaluate an operator when the operator that follows it has a lower (or equal to) precedence. 

In the context of the example, here's what you want to do:

Look at: 3 + 4, don't do anything.
Now look at 3 + 4 * 2, still don't do anything.
Now look at 3 + 4 * 2 + 8, now you know that 4 * 2 has to to be evaluated because the next operator has lower precedence.

Implementation:

> Have two stacks, one for numbers, and another for operators. 
> You push numbers onto the stack all the time. 
> You compare each new operator with the one at the top of the stack, if the one on top of the stack has higher priority, you pop it off the operator stack, pop the operands off the number stack, apply the operator and push the result onto the number stack. 
> Now you repeat the comparison with the top of stack operator.

C Implementation:

void minprintf(char *fmt, ...)
{
    va_list ap;   /* points to each unnamed arg in turn */
    char *p, *sval;
    int ival;
    double dval;
    
    va_start(ap, fmt); /* make ap point to 1st unnamed arg */
    for (p = fmt; *p; p++) {
        if (*p != '%') {
            putchar(*p);
            continue;
        }
        switch (*++p) {
            case 'd':
            case 'i':
                ival = va_arg(ap, int);
                printf("%d", ival);
                break;
            case 'o':
                ival = va_arg(ap, int);
                printf("%o", ival);
                break;
            case 'x':
                ival = va_arg(ap, int);
                printf("%x", ival);
                break;
            case 'X':
                ival = va_arg(ap, int);
                printf("%X", ival);
                break;
            case 'u':
                ival = va_arg(ap, int);
                printf("%u", ival);
                break;
            case 'c':
                ival = va_arg(ap, int);
                printf("%c", ival);
                break;
            case 'f':
                dval = va_arg(ap, double);
                printf("%f", dval);
                break;
            case 'e':
                dval = va_arg(ap, double);
                printf("%e", dval);
                break;
            case 'E':
                dval = va_arg(ap, double);
                printf("%E", dval);
                break;
            case 's':
                for (sval = va_arg(ap, char *); *sval; sval++)
                    putchar(*sval);
                break;
            default:
                putchar(*p);
                break;
        }
    }
    va_end(ap);
}

Sample parsing in Java:

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

public class EmployeeParse {
	
	private Integer empID ;
	private String empName ;
	private String empCity ;
	
	
	public Integer getEmpID() {
		return empID;
	}

	public void setEmpID(Integer empID) {
		this.empID = empID;
	}

	public String getEmpName() {
		return empName;
	}

	public void setEmpName(String empName) {
		this.empName = empName;
	}

	public String getEmpCity() {
		return empCity;
	}

	public void setEmpCity(String empCity) {
		this.empCity = empCity;
	}

	
	public EmployeeParse() {
	}

	public static void main(String[] args) {
		try {
			ArrayList<EmployeeParse> empList = new ArrayList<EmployeeParse>() ;
		    File file = new File ( "/Users/ramesh/Documents/workspace/Programs/src/employee.rtf") ;
		    
		    if ( file.exists() )   
		    {  
		    	Scanner inFile = new Scanner( file );
		    	inFile.useDelimiter("[;]");
		        while ( inFile.hasNext() )
		        {
		        	String line = inFile.next() ;
		            line = line.trim().replaceAll("\n", "");
		            line = line.trim().replaceAll("\t", "");
		            line = line.trim().replaceAll(" ", "");
		            if ( line.length() > 0 ) {
		            	String delims = "[,]+";
		            	String[] tokens = line.split(delims);
		            	EmployeeParse emp = new EmployeeParse() ;
		            	emp.setEmpID(Integer.parseInt(tokens[0]));		            	
		            	emp.setEmpName(tokens[1]);
		            	emp.setEmpCity(tokens[2]);
		            	
		            	empList.add(emp) ;
		            }
		        }

		        inFile.close(); 
		        
		    }
			else {
				System.out.println( "File Not Found");
			}
		    Integer rec = 0 ;
		    for (EmployeeParse employee : empList) {
		    	System.out.println( "Employee-"+ ++rec +":");
				System.out.println( "ID = " + employee.getEmpID());
				System.out.println( "Name = " + employee.getEmpName());
				System.out.println( "City = " + employee.getEmpCity());
			}
		}
		catch ( FileNotFoundException e) {
			System.out.println( "File Not Found Exception");
		}
	
	}

}

Output:

Employee-1:
ID = 101
Name = emp1
City = city1
Employee-2:
ID = 2
Name = emp2
City = city2
Employee-3:
ID = 3
Name = emp3
City = city3
Employee-4:
ID = 4
Name = emp4
City = city4
Employee-5:
ID = 5
Name = emp5
City = city5
Employee-6:
ID = 6
Name = emp6
City = city6

TRIE Java Implementation:

import java.util.*;
import java.util.Map.Entry;

public class AutoCompleteTrie {

    protected final Map<Character, AutoCompleteTrie> children;
    protected String value;
    protected boolean isWord = false;

    public AutoCompleteTrie() {
        this(null);
    }

    private AutoCompleteTrie(String value) {
        this.value = value;
        children = new HashMap<Character, AutoCompleteTrie>();
    }
    
    public void insert(String word) {
        if (word == null) {
            throw new IllegalArgumentException("Can't Add NULL.");
        }
        AutoCompleteTrie node = this;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) {
                node.add(c);
            }
            node = node.children.get(c);
        }
        node.isWord = true;
    }

    protected void add(char c) {
        String val;
        if (this.value == null) {
            val = Character.toString(c);
        } else {
            val = this.value + c;
        }
        children.put(c, new AutoCompleteTrie(val));
    }

    public String find(String word) {
        AutoCompleteTrie node = this;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return "";
            }
            node = node.children.get(c);
        }
        return node.value;
    }

    public Collection<String> autoComplete(String prefix) {
        AutoCompleteTrie node = this;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return Collections.emptyList();
            }
            node = node.children.get(c);
        }
        return node.allPrefixes();
    }

    protected Collection<String> allPrefixes() {
        List<String> results = new ArrayList<String>();
        if (this.isWord) {
            results.add(this.value);
        }
        for (Entry<Character, AutoCompleteTrie> entry : children.entrySet()) {
            AutoCompleteTrie child = entry.getValue();
            Collection<String> childPrefixes = child.allPrefixes();
            results.addAll(childPrefixes);
        }
        return results;
    }
    
    public static void main(String[] args) {
		AutoCompleteTrie root = new AutoCompleteTrie();
		root.insert("team.com");
		root.insert("tea.in");
		root.insert("teamwork.org");
		root.insert("teams.com");
		root.insert("pot.uk");
		root.insert("potter.in");
		root.insert("post.com");
		
		Collection<String> results = root.autoComplete("te") ;
		for (String string : results) {
			System.out.println(" "+ string);
		}
	}
}

Output:

teams.com
teamwork.org
team.com
tea.in

The below line should be

string[] numbers = inputString.split("\\.");

Else can use the:

StringTokenizer stringTokenizer = new StringTokenizer( ip, "." ); 
	while ( stringTokenizer.hasMoreTokens() ) { 
		byte byteValue = Byte.parseByte(stringTokenizer.nextToken()) ;
	}

Using the inet_pton - which returns -1 on failure, and supports both the IPv4 and future IPv6 addresses

#include <arpa/inet.h>
bool isValidIP(char * ipAddr)
{
    struct sockaddr_in socAddr;
    return ( inet_pton(AF_INET, ipAddr, &(socAddr.sin_addr)) != 0 ) ;
}

Using Regular Expressions for IPV4:

package sample;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class IPAddrValidator {
	
	public boolean validate(final String ip){		  
		  matcher = pattern.matcher(ip);
		  return matcher.matches();	    	    
	    }

	public IPAddrValidator() {
		pattern = Pattern.compile(IP_ADDRESS_PATTERN);
	}

	private Pattern pattern;
    private Matcher matcher;
 
    private static final String IP_ADDRESS_PATTERN = 
		"^([01]?\\d\\d?|2[0-4]\\d|25[0-5])\\." +
		"([01]?\\d\\d?|2[0-4]\\d|25[0-5])\\." +
		"([01]?\\d\\d?|2[0-4]\\d|25[0-5])\\." +
		"([01]?\\d\\d?|2[0-4]\\d|25[0-5])$";
 
    
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String ip = new String ("1.1.1.1") ;
		IPAddrValidator ipValidator = new IPAddrValidator();
		System.out.println("IP Address = "+ ip + " is " + ipValidator.validate(ip) );
		System.out.println("IP Address = "+ "127.0.0.1" + " is " + ipValidator.validate("127.0.0.1") );
		System.out.println("IP Address = "+ "10.10" + " is " + ipValidator.validate("10.10") );
	}
}

@akiremi - Agree... Missed that part.

Use the FlyWeight Design Pattern.

Have a look at Source Code, which is part of JDK:

java.lang.String

For each Stack, start from the two extremes of the array and move towards the center of the array as elements are being added to them.

Full = When the stacks meet.

import java.lang.Integer; 

public class TwoStacksInOneArray {
	
	private Integer[] array ;
	private Integer top1 ;
	private Integer top2 ;
	private Integer size ;

	public TwoStacksInOneArray ( Integer size ) {
		this.array = new Integer[size] ;
		this.top1 = -1 ;
		this.top2 = size ;
		this.size = size ;
	}

	public void push1 ( Integer item ) {
		if ( top1 < (top2 - 1) ) {
			array[++top1] = item ;
		}
		else {
			System.out.println( "Stack OverFlow. Unable to Push " + item );
		}
	}
	
	public void push2 ( Integer item ) {
		if ( top1 < (top2 - 1) ) {
			array[--top2] = item ;
		}
		else {
			System.out.println( "Stack OverFlow. Unable to Push " + item );
		}
	}
	
	public Integer pop1 ( ) {
		if ( top1 > -1 ) {
			Integer item = array[top1--] ;
			return item ;
		}
		else {
			System.out.println( "Stack UnderFlow" );
			return Integer.MIN_VALUE ;
		}
	}
	
	public Integer pop2 ( ) {
		if ( top2 < size ) {
			Integer item = array[top2++] ;
			return item ;
		}
		else {
			System.out.println( "Stack UnderFlow" );
			return Integer.MIN_VALUE ;
		}
	}
	
	public String toString() {
		String arr = new String() ;
		arr = "[ " ;
		for (int j = 0; j < array.length; j++) {
			arr = arr + this.array[j] + " " ;
		}
		return arr + " ]";
	}
	
	public static void main(String[] args) {
		TwoStacksInOneArray stack = new TwoStacksInOneArray(5) ;
		stack.push1(1);
		stack.push2(5);
		stack.push1(2);
		stack.push1(3);
		stack.push1(4);
		System.out.println( "Stack = " + stack.toString() );
		stack.push2(6);
		
		System.out.println( "Pop1 = " + stack.pop1() );
		System.out.println( "Pop1 = " + stack.pop1() );
		System.out.println( "Pop1 = " + stack.pop1() );
		System.out.println( "Pop1 = " + stack.pop1() );
		System.out.println( "Pop1 = " + stack.pop1() );
		System.out.println( "Pop2 = " + stack.pop2() );
		System.out.println( "Pop2 = " + stack.pop2() );
	}
}

Output:

Stack = [ 1 2 3 4 5  ]
Stack OverFlow. Unable to Push 6
Pop1 = 4
Pop1 = 3
Pop1 = 2
Pop1 = 1
Stack UnderFlow
Pop1 = -2147483648
Pop2 = 5
Stack UnderFlow
Pop2 = -2147483648

SOLUTION-1:
Time Complexity = O(n)
Space Complexity = O(n)

Steps:

> Use 2 Pointers 'slow' and 'fast' 
> As you traverse to the middle of List PUSH the 'slow' pointer's 'value' on to Stack.
> Once in Middle of List, then from there till the end of list, POP value from Stack and compare with 'slow' pointer 'value'.
> If everything matches then its Palindrome, else return false.

Code:

public boolean isPalindrome(ListNode root) {
    Stack<Integer> stack = new Stack<Integer>();
    ListNode slow = root;
    ListNode fast = root;

    while (fast != null && fast.next != null) {
      stack.push(slow.val);
      slow = slow.next;
      fast = fast.next.next;
    }
 
   // odd number of elements
    if (fast != null) {
      slow = slow.next;
    }

    while (slow != null) {
      int top = stack.pop();
      if (slow.val != top) {
        return false;
      }
      slow = slow.next;
    }
    return true;
  }

SOLUTION-2:
Time Complexity = O(n)
Space Complexity = O(1)

Steps:

> Get the middle of the linked list by using the ‘slow’ and ‘fast’ pointers.
> Reverse the second half of the linked list.
> Check if the first half and second half are identical. Else return false.

Code:

public boolean isPalindrome(ListNode root) {
    ListNode slow = root;
    ListNode fast = root;

    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
 
   // odd number of elements
    if (fast != null) {
      slow = slow.next;
    }

    //Reverse the Second half of list
    slow.next = Reverse(slow.next) ;
    slow = slow.next ;

    fast = root ;
    while (slow != null) {
      if (slow.val != fast.val) {
        return false;
      }
      slow = slow.next;
      fast = fast.next ;
    }
    return true;
  }

#!/usr/bin/env bash

counter=0
for i in *; do
    mv "${i}" file${count}.`echo "${i}" | awk -F. '{print $2}'`
    ((++counter))
done

for-loop:
iterating over the output of the command 'ls' command, which is alphabetically sorted.
Rest of the code is self explanatory...

TCP and UDP are Transport layer protocols, which are extensively used in internet for transmitting data between one host to another.

TCP:
> Connection based
> Guaranteed reliable and ordered
> Automatically breaks up your data into packets for you
> Makes sure it doesn’t send data too fast for the internet connection to handle (flow control)
> Easy to use, you just read and write data like its a file

UDP:
> No concept of connection, you have to code this yourself
> No guarantee of reliability or ordering of packets, they may arrive out of order, be duplicated, or not arrive at all!
> You have to manually break your data up into packets and send them
> You have to make sure you don’t send data too fast for your internet connection to handle
> If a packet is lost, you need to devise some way to detect this, and resend that data if necessary

Code is wrong. It outputs:
{12, 12, 10, 10, 10, 10, 10, 10, 3, 2}

It is Next Larger Element not the Largest...
O/p: {12,12,10,10,10,2,10,10,3,2}

Redirect Part:

When you click on a link of any tiny url, an HTTP Request is sent to their server with the full URL, like http // bit.ly / b9 (not a real one).

They read the path part (here b9), which maps to their Database.

In the Database, they find the real URL. Then they issue a redirect, which is a HTTP 302 response and the target URL in the header.

Encoding Part:

One of the most popular URL shortening services simply take the ID in the database of the URL and then convert it to Base 62[a-zA-Z0-9].

import static org.testing.AssertJUnit.assertEquals ;

public class TinyURL {
	private static final String ALPHABET_MAP = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" ;
	private static final int BASE = ALPHABET_MAP.length() ;

	public static String encode ( int IndexNum ) {
		StringBuilder sb = new StringBuilder() ;
		
		while ( IndexNum > 0 ) {
			sb.append ( ALPHABET_MAP.charAt ( IndexNum % BASE ) ) ;
			IndexNum /= BASE ;
		}
		return sb.reverse().toString() ;
	}

	public static int decode ( String str ) {
		int Num = 0 ;

		for ( int i = 0, len = str.length(); i < len; i++ ) {
			Num = Num * BASE + ALPHABET_MAP.indexOf ( str.charAt(i) ) ;
		}
		return Num ;
	}

	public static void main ( String[] args ) {
		//System.out.println ( "Encoding for 123 is " + encode(123) ) ;
		//System.out.println ( "Decoding for b9 is " + decode ("b9" ) ) ;

		assertEquals ( "b9", encode(123) ) ;
		assertEquals ( 123, decode("b9") ) ; 
	}
}

The recursion will go down the tree, recursively changing the small and large sub-trees into lists, and then append those lists together with the parent node to make larger lists.
Separate out a utility function append(Node a, Node b) that takes two circular doubly linked lists and appends them together to make one list which is returned.
Writing a separate utility function helps move some of the complexity out of the recursive function.

/* The node type from which both the tree and list are built */
struct node {
    int data;
    struct node* small;
    struct node* large;
};
typedef struct node* Node;



/*
 helper function -- given two list nodes, join them
 together so the second immediately follow the first.
 Sets the .next of the first and the .previous of the second.
*/
static void join(Node a, Node b) {
    a->large = b;
    b->small = a;
}


/*
 helper function -- given two circular doubly linked
 lists, append them and return the new list.
*/
static Node append(Node a, Node b) {
    Node aLast, bLast;
    
    if (a==NULL) return(b);
    if (b==NULL) return(a);
    
    aLast = a->small;
    bLast = b->small;
    
    join(aLast, b);
    join(bLast, a);
    
    return(a);
}


/*
 --Recursion--
 Given an ordered binary tree, recursively change it into
 a circular doubly linked list which is returned.
*/
static Node treeToList(Node root) {
    Node aList, bList;
    
    if (root==NULL) return(NULL);

    /* recursively solve subtrees -- leap of faith! */
    aList = treeToList(root->small);
    bList = treeToList(root->large);
    
    /* Make a length-1 list ouf of the root */
    root->small = root;
    root->large = root;

    /* Append everything together in sorted order */
    aList = append(aList, root);
    aList = append(aList, bList);
    
    return(aList);



/* Create a new node */
static Node newNode(int data) {
    Node node = (Node) malloc(sizeof(struct node));
    node->data = data;
    node->small = NULL;
    node->large = NULL;
    return(node);
}


/* Add a new node into a tree */
static void treeInsert(Node* rootRef, int data) {
    Node root = *rootRef;
    if (root == NULL) *rootRef = newNode(data);
    else {
        if (data <= root->data) treeInsert(&(root->small), data);
        else treeInsert(&(root->large), data);
    }
}


static void printList(Node head) {
    Node current = head;
    
    while(current != NULL) {
        printf("%d ", current->data);
        current = current->large;
        if (current == head) break;
    }
    printf("\n");
}


/* Demo that the code works */
int main() {
    Node root = NULL;
    Node head;
    
    treeInsert(&root, 4);
    treeInsert(&root, 2);
    treeInsert(&root, 1);
    treeInsert(&root, 3);
    treeInsert(&root, 5);
    
    head = treeToList(root);
    
    printList(head);    /* prints: 1 2 3 4 5  */
    
    return(0);
}

Redirect Part:

When you click on a link of any tiny url, an HTTP Request is sent to their server with the full URL, like http // bit.ly / b9 (not a real one).

They read the path part (here b9), which maps to their Database.

In the Database, they find the real URL. Then they issue a redirect, which is a HTTP 302 response and the target URL in the header.

Encoding Part:

One of the most popular URL shortening services simply take the ID in the database of the URL and then convert it to Base 62[a-zA-Z0-9].

import static org.testing.AssertJUnit.assertEquals ;

public class TinyURL {
	private static final String ALPHABET_MAP = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" ;
	private static final int BASE = ALPHABET_MAP.length() ;

	public static String encode ( int IndexNum ) {
		StringBuilder sb = new StringBuilder() ;
		
		while ( IndexNum > 0 ) {
			sb.append ( ALPHABET_MAP.charAt ( IndexNum % BASE ) ) ;
			IndexNum /= BASE ;
		}
		return sb.reverse().toString() ;
	}

	public static int decode ( String str ) {
		int Num = 0 ;

		for ( int i = 0, len = str.length(); i < len; i++ ) {
			Num = Num * BASE + ALPHABET_MAP.indexOf ( str.charAt(i) ) ;
		}
		return Num ;
	}

	public static void main ( String[] args ) {
		//System.out.println ( "Encoding for 123 is " + encode(123) ) ;
		//System.out.println ( "Decoding for b9 is " + decode ("b9" ) ) ;

		assertEquals ( "b9", encode(123) ) ;
		assertEquals ( 123, decode("b9") ) ; 
	}
}

Dynamic Programming Approach:

Avoid the repeated work done (By recursion method) by storing the Fibonacci numbers calculated so far.
This can even further optimized the space by storing the previous 2 numbers only because that is all we need to get the next Fibonnaci number in series.

int fibo ( int Num ) {
  	int prev1 = 0, prev2 = 1, next ;

  	if( 0 == Num )
    		return prev1 ;

  	for (int i = 2; i <= num;  i++ )  {
     		next = prev1 + prev2 ;
     		prev1 = prev2 ;
     		prev2 = next ;
  	}
  	return prev2;
}

Time Complexity: O(N)
Space Complexity: O(1)

As we know members of struct are public by default, lets implement the private access specifier behavior into the struct.

In the below samplestruct example, If you provide a samplestruct* create_struct() method as an interface to client and a series of methods that operate on samplestruct*, hiding the actual definition of samplestruct from the client, then a similar effect is achieved.

// File "samplestruct_private.h"

struct samplestruct {
    int priv_int;
    char priv_char;
};

// File "samplestruct.h"

typedef struct samplestruct samplestruct;
samplestruct * create_struct(int a, char b);
int mangle_struct(samplestruct *);

// file "samplestruct.c"

#include <stdlib.h>
#include "samplestruct.h
#include "samplestruct_private.h"

samplestruct * create_struct(int a, char b) {
    samplestruct * s = (samplestruct *) calloc(1, sizeof(samplestruct));
    s->priv_int = a ;
    s->priv_char = b ;
}    

int mangle_struct(samplestruct *s) {
    return s->priv_int + s->priv_char;
}

Distribute samplestruct.c compiled into a library, along with samplestruct.h.

The functions declared in samplestruct.h form the public interface of a type, but the internal structure of that type is opaque.
In effect, the clients who call create_struct() can't access the private members of the samplestruct object.

Assuming:-

Suit:
Club = 0
Diamond = 1
Heart = 2
Spade = 3

Color:
Black = 0
Red = 1

class Cards {
private:
	int m_suit ;
	int m_rank ;

public:
	Cards ( int r, int s ) {
		m_rank = r ;
		m_suit = s ;
	}

	int getRank ( ) { 
		return m_rank ;
	}

	int getSuit() {
		return m_suit ;
	}

	int getColor ( int suit ) {
		return ((1 == suit) || (2 == suit))? 1 : 0 ;
	}

	string toString (int rank) {
		string val ;
		switch (rank) {
			case 1 :
					val = "Ace" ;
					break ;
			.....
			.....
			case 10:
					val = "Jack" ;
					break ;
			case 11:
					val = "Queen" ;
					break ;
			case 12:
					val = "King" ;
					break ;
			default:
					break ;
		}
		return val ;
	}
}

class CardDeck{
private:
	Card[] m_deck ;
	int m_numCards ;
public:
	CardDeck() {
		m_deck = new Card[52] ;
		initCards() ;
	}

	void initCards() {
		int idx = 0 ;
		for ( int rank = 1; rank <= 13; rank++ ) {
			for ( int suit = 0; suit < 4; suit++ ) {
				m_deck[index] = new Card(rank,suit) ;
				index++ ;
			}
		}
		m_numCards = 52 ;
	}

	int getSizeOfDeck () {
		return m_numCards ;
	}

	Card deal () {
		if ( 0 == m_numCards )
			return NULL;
	
		m_numCards-- ;
		return m_deck[m_numCards] ;
	}

	void shuffle() {
		for ( int next = 0; next < m_numCards-1; next++ ) {
			int rdm = myRandom(i, m_numCards-1) ;
			Card temp = m_deck[next] ;
			m_deck[next] = m_deck[rdm] ;
			m_deck[rdm] = temp ;
		}
	}

	static int myRandom ( int low, int high ) {
		return (int) ( (high+1-low) * Math.random() + low ) ;
	}
}

By using these classes, implement for the card games like BlackJack,...

@SKD - Edited...

Its an Longest Increasing Sub-Sequence Dynamic programming Problem with O(N log N) solution.

Above Bank >> 7 4 3 6 2 1 5
Below Bank >> 5 3 2 4 6 1 7
Pairs >> (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)

Sort the pairs based on Lower Bank Cities as Below:
Above Bank >> 1 3 4 6 7 2 5
Below Bank >> 1 2 3 4 5 6 7

Now the Problem reduces to finding the LIS from the Cities in Above Bank >> 1 3 4 6 7 2 5
which is 1 3 4 6 7

So, the Output with corresponding Lower Bank Cities will be
(1,1) (3,2) (4,3) (6,4) (7,5)

EDIT:
If we have the elements sorted by their Below Bank, then we can tell if two pairs are orderable by <=, by just looking at their positions in the Above Bank.
If the first pair(1,1) is to the left of the second pair(3,2), we immediately know that the second elements of the first pair(1) is less than the second element of the second pair(2), since we've sorted them by the second coordinate.
We then have this pair of elements can have Bridge built together if and only if the first element of the first pair(1) is less than the first element of the second pair(3).

Consequently, if we want to find a set of Bridges that can be built together, we're looking for an Increasing Sub-Sequence of the Cities in Above Bank, since in that case both the first and second elements of the pairs are increasing as we move from the left to the right.

Finding the longest increasing subsequence then solves this problem.

Complexity:
Sort the pairs by their Below Bank = O(N log N)
Find the LIS in O(N log N)
So, this is an O(N log N) solution.

One of the Better way of writing a Singleton is using the Static Inner Helper Class (Bill Pugh Method).

public class Singleton {
 
    private Singleton(){}
     
    private static class SingletonHelper{
        private static final Singleton m_instance = new Singleton();
    }
     
    public static Singleton getInstance(){
        return SingletonHelper.m_instance;
    }
}

When the singleton class is loaded, SingletonHelper class is not loaded into memory and only when someone calls the getInstance method, this class gets loaded and creates the Singleton class instance.
This is the most widely used approach for Singleton class as it doesn’t require synchronization.

int my_strcmp ( char *s, char *t ) {

	while ( *s == *t ) {
		if (*s == '\0')
			return 0 ;
		s++ ;
		t++ ;
	}

	return (*s - *t) ;
}

Make use of BFS.
Find all neighbors of U1, then find all neighbors of all neighbors of U1, etc. Once U2 is found, not only do you have a path from U1 to U2, but will also have a shortest path.

Dijkstra's Algo with searching from both ends can speed up the search.

This approach in social n/w sites will be inefficient.

Can use A* search. From wikipedia : "A* uses a best-first search and finds the least-cost path from a given initial node to one goal node (out of one or more possible goals)."

Algorithm:
a) Pick the first character from source string.
b) Append the picked character to the destination string.
c) Count the number of subsequent occurrences of the picked character and append the count to destination string.
d) Pick the next character and repeat steps b) c) and d) if end of string is NOT reached.

char *encode(char *src) {
  int rLen;
  char count[MAX_RLEN];
  int len = strlen(src);

  /* If all characters in the source string are different, 
    then size of destination string would be twice of input string.
    For example if the src is "abcd", then dest would be "a1b1c1d1"
    For other inputs, size would be less than twice.  */
  char *dest = new char [sizeof(char)*(len*2 + 1)];

  int i, j = 0, k;

  /* traverse the input string one by one */
  for(i = 0; i < len; i++) {

    /* Copy the first occurrence of the new character */
    dest[j++] = src[i];

    /* Count the number of occurrences of the new character */
    rLen = 1;
    while(i + 1 < len && src[i] == src[i+1])  {
      rLen++;
      i++;
    }
    /* Store rLen in a character array count[] */
    sprintf(count, "%d", rLen);

    /* Copy the count[] to destination */
    for(k = 0; *(count+k); k++, j++)  {
        dest[j] = count[k];
    }
  }

  /*terminate the destination string */
  dest[j] = '';
  return dest;
}

O(N)

For simplicity i will consider the following, later can be extended for all:

* --- Matches 0 or more of the preceding char
. --- Matches any single char.

bool matchFirst(const char *str, const char *ptrn){
	return ( (*ptrn == *str) || 
			 (*ptrn == '.' && *str != '\0')
			);
}

bool isRegex(const char *str, const char *ptrn) {
	//If the Pattern reaches end
	if (*ptrn == '\0') 
		return *str == '\0';

	//Case-1: If the Pattern's second char is not *
	if (*(ptrn + 1) != '*') {
		//If the first char of pattern is "." or first char of pattern == the first i char 
		//of string, continue to match the left part
		if(!matchFirst(str,ptrn)) 
			return false;
		return isRegex(str + 1, ptrn + 1);
	} 
	//Case-2: If the Pattern second char is *
	else {
		//If the first char of pattern is not ".", the first char of pattern and string 
		//should be the same.
		//Else continue to match the rest
		if(isRegex(str, ptrn + 2)) 
			return true;   
		while ( matchFirst(str,ptrn) )  
			if (isRegex(++str, ptrn + 2))
				return true;
	}
}

Scan from Right for the O(N) Solution.
Scan all the elements from right to left in array and keep track of maximum till now. When maximum changes it’s value, print the same as Leader.

void FindLeader ( int Arr[], int ArrSize ) {
	int max = Arr[ArrSize-1] ;
	for ( int i = ArrSize-1; i >= 0; i– ) {
		if ( Arr[i] >= max ) {
			cout << Arr[i] << ” ” ;
			max = Arr[i] ;
		}
	}
	cout << endl ;
}

Time Complexity: O(N)

When a child process exits and if parent process is not waiting to receive exit status of it, the child process is termed as Zombie process. This process continues to exist in process table, its PID is not freed even though it has terminated.

If parent process exits before child process, the child process is called as orphan process. This process is put directly under the INIT process and its parent process ID becomes 1. There is slight difference between zombie and orphan that is zombie process's parent may not have exited while orphan process's parent has terminated.

Yes, its not DP{My Bad}. Its recursive(backtracking) solution.
For Non-recursive solution can refer to Donald Knuth approach.
Please refer below link:
stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string

def nextPermutation(perm):
    k0 = None
    for i in range(len(perm)-1):
        if perm[i]<perm[i+1]:
            k0=i
    if k0 == None:
        return None

    l0 = k0+1
    for i in range(k0+1, len(perm)):
        if perm[k0] < perm[i]:
            l0 = i

    perm[k0], perm[l0] = perm[l0], perm[k0]
    perm[k0+1:] = reversed(perm[k0+1:])
    return perm

perm=list("12345")
while perm:
    print perm
    perm = nextPermutation(perm)