CareerCup

You can take assumption that there is no negative value and gems are not 0.
your solution seems to be correct.
But can you do it in O(n) ?

Can you please write your logic?

1. it should be subarray , not subsequence of numbers
2. it should be non-overlapping subarray
3. We have to return sum of largest M such subsets..

i didn't get your M * K largest numbers part, what it is ?

http: //ideone .com/K604Ay

pre & post order to Nary tree.
much cleaner

Generic solution of reversing linklist, set k =2 for this particular problem.
Logic in in comments

static LinkedListNode reverse_k (LinkedListNode head, int k) {
		LinkedListNode prev = null;
		LinkedListNode cur = head;
		LinkedListNode next = head;
		
		while (k > 0 && cur != null) {
			next = cur.next;
			cur.next = prev;
			prev = cur;
			cur = next;
			k--;
		}
		head.next = cur;
		head = prev;
		return head;
	}

	/*
	 * <pre>
	 * 1. Reverse first k nodes, and get new head of list
	 * 2. Get head of remaining list (Size - k) as oldhead.next will now be pointing to start of remaining list
	 * 3. recusrively call this function with this newHead
	 * 4. To build complete list, merge oldhead of old list and newhead of remaining list.
	 * 		oldhead.next was pointing to previous head of newlist, and it should point to newHead of remaining list.
	 * 		So oldhead.next = newHeadOfRemainingList
	 * 		and this makes complete list. This is done recursively for all sub-lists 
	 * </pre>
	 */
	static LinkedListNode rec_reverse_k (LinkedListNode oldhead, int k) {
		if (oldhead == null) {
			return null;
		}
		LinkedListNode newhead = reverse_k (oldhead, k);
		LinkedListNode nextListHead = oldhead.next;
		LinkedListNode nextListNewHead = rec_reverse_k (nextListHead, k);
		oldhead.next = nextListNewHead;
		return newhead;
	}

courtesy : http : // stackoverflow . com/a/4973083/3010355

Just replaced TreeNode structure
static class TreeNode {
	public TreeNode left;
	public int key;
	public TreeNode right;
	
	public TreeNode (int k) {
		this.left = null;
		this.key = k;
		this.right = null;
	}
}
class BTreePrinter {

    public static void printNode(TreeNode root) {
        int maxLevel = BTreePrinter.maxLevel(root);

        printNodeInternal(Collections.singletonList(root), 1, maxLevel);
    }

    private static void printNodeInternal(List<TreeNode> nodes, int level, int maxLevel) {
        if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
            return;

        int floor = maxLevel - level;
        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

        BTreePrinter.printWhitespaces(firstSpaces);

        List<TreeNode> newNodes = new ArrayList<TreeNode>();
        for (TreeNode node : nodes) {
            if (node != null) {
                System.out.print(node.key);
                newNodes.add(node.left);
                newNodes.add(node.right);
            } else {
                newNodes.add(null);
                newNodes.add(null);
                System.out.print(" ");
            }

            BTreePrinter.printWhitespaces(betweenSpaces);
        }
        System.out.println("");

        for (int i = 1; i <= endgeLines; i++) {
            for (int j = 0; j < nodes.size(); j++) {
           		BTreePrinter.printWhitespaces(firstSpaces - i);
                if (nodes.get(j) == null) {
                    BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
                    continue;
                }

                if (nodes.get(j).left != null) {
                	System.out.print("/");                	
                }
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(i + i - 1);

                if (nodes.get(j).right != null)
                	System.out.print("\\");
                else
                    BTreePrinter.printWhitespaces(1);

               	BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
            }

            System.out.println("");
        }
        printNodeInternal(newNodes, level + 1, maxLevel);
    }

    private static void printWhitespaces(int count) {
        for (int i = 0; i < count; i++)
            System.out.print(" ");
    }

    private static int maxLevel(TreeNode node) {
        if (node == null)
            return 0;

        return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
    }

    private static <T> boolean isAllElementsNull(List<T> list) {
        for (Object object : list) {
            if (object != null)
                return false;
        }

        return true;
    }

A = 20, 19, 18, 17 ,16
B= 1 , 2 , 3 , 4 ,5

for each i < j, there is a pair
so, there will be O(N^2) possible pair and so complexity.

This will return element which is present different number of times than recurringElementCount i.e. if all elements are present for 5 number of times and there is a single element which is not present 5 number of times (either 1,2,3,4,6,7,8 etc) that element will be returned

static int findUnique (int[] input, int recurringElementCount) {
		int result = 0;
		for (int bit = 0; bit < 32; bit++) {
			int mask = 1 << bit;
			int setCount = 0;
			for (int i = 0; i < input.length; i++) {
				if ((input[i] & mask) != 0) {
					setCount++;
					setCount = setCount % recurringElementCount;
				}
			}
			if (setCount > 0) {
				result = result | mask;
			}
		}
		return result;
	}

This can be done in O (N) time-complexity. But it will take O(log N) space complexity. Space for stack usage

Brief idea of algo: 
1. Iterative inorder
2. two ways: one from increasing order and another decreasing order. For that we need two stacks. This is similar to processing sorted array and finding two elements whose sum is equal to given K.

1. Get left most element (smallest element) and get right most element (biggest element)
2. Also prepare both stacks: Increasing stack and decreasing stack
3. Get sum of both elements and it sum is equal to K then voilla we got answer otherwise check which direction we should move. 
4. If new sum is less than K then we have to move increasing stack otherwise decreasing stack
5. Function nextIncreasingKey, nextDecreasingKey get next required value and also update required stack.
code is 

	static IntPair getPair (Tree root, int K) {
		IntPair result = new IntPair ();
		Stack incr = new Stack ();
		Stack decr = new Stack ();
		int leftkey = nextIncreasing (incr, root);
		int rightkey = nextDecreasing (decr, root);

		while (leftkey < rightkey) {
			int sum = leftkey + rightkey;
			if (sum == K) {
				result.setFirst(leftkey);
				result.setSecond(rightkey);
				break;
			}
			else if (sum < K) {
				leftkey = nextIncreasing (incr, root);
			}
			else {
				rightkey = nextDecreasing (decr, root);
			}
		}
		return result;
	}

	static private int nextDecreasing(Stack decr, Tree root) {
		
		TreeNode node = (TreeNode) decr.pop();
		if (node == null) {
			node = updateDecreasingStack (decr, root.root);
		}
		else {
			node = updateDecreasingStack (decr, node.left);
		}
		return node.key;
	}
	static private TreeNode updateDecreasingStack(Stack decr, TreeNode node) {
		while (node != null) {
			decr.push(node);
			node = node.right;
		}
		return (TreeNode) decr.peek ();
	}
	
	static private int nextIncreasing(Stack incr, Tree root) {
		
		TreeNode node = (TreeNode) incr.pop();
		if (node == null) {
			node = updateIncreasingStack (incr, root.root);
		}
		else {
			node = updateIncreasingStack (incr, node.right);
		}
		return node.key;
	}
	static private TreeNode updateIncreasingStack(Stack incr, TreeNode node) {
		while (node != null) {
			incr.push(node);
			node = node.left;
		}
		return (TreeNode) incr.peek ();
	}

Its a running code, except you have to create your own tree and pair class or you can use min and max separate variable in place of minMax.
Algo:

1. While following inorder traversal, at every node of tree calculate the value formed from root to till that node.
2. compare that value with minMax value till that digit position. If number lies in range then continue, else return false. 
3. If a node gets false from either of its subtree, it updates that subtree to null.

static boolean func (TreeNode root, int M, int num, Pair<Integer,Integer> minMax) {
		if (root == null) {
			return true;
		}
		int newNum = num * 10 + root.key;
		if (checkRange(newNum, minMax, M) == false) {
			return false;
		}
		if (func (root.left, M/10, newNum, minMax) == false)
			root.left = null;
		if (func (root.right, M/10, newNum, minMax) == false)
			root.right = null;
		return true;
	}
	
	static boolean checkRange (int N, Pair<Integer,Integer> minMax, int M) {
		if (M <= 0) {
			return false;
		}
		int min = minMax.getFirst()  / M;
		int max = minMax.getSecond()  / M;
		if (N < min
				|| N > max) {
			return false;
		}
		return true;
	}

	static int multipier (int num) {
		int orig = num;
		int multipier = 1;
		while (num/10 > 0) {
			multipier = multipier * 10;;
			num = num/10;
		}
		System.out.println("Multiplier for Num: " + orig + " is : " + multipier);
		return multipier;
	}

calling function () {
		Pair<Integer, Integer> minMax = new Pair<Integer, Integer> (125, 136);
		int M = multipier (minMax.getFirst());
		func (t.root, M, 0, minMax);

@Nascent, Yes Please elaborate "don’t compute reverse of string at all" ?

Regarding first part, hashing of words should be one solution.

This can be done with temporary array which reduces number of iteration to number of elements only (Dynamic Programming).
And simply by kind of DFS.

IntPair is class with matrix positions

public class MaxMatrixPath {

	int[][] tempMatrix = null;
	
	MaxMatrixPath () {
		tempMatrix = null;
	}

	MaxMatrixPath (int sizeX, int sizeY) {
		tempMatrix = new int [sizeX][sizeY];
		initialise ();
	}

	private void initialise() {
		for (int i = 0; i < tempMatrix.length; i++) {
			for (int j = 0; j < tempMatrix[0].length; j++) {
				tempMatrix[i][j]=Integer.MIN_VALUE;
			}
		}
	}

	int maxSum_less_expensive (int[][] input, IntPair current) {
		int right_sum = 0;
		int down_sum = 0;
		int x = current.getFirst();
		int y = current.getSecond();

		if (tempMatrix[x][y] != Integer.MIN_VALUE) {
			return tempMatrix[x][y];
		}

		if (isLastNode (input, current)) {
			return input[input.length][input[0].length];
		}
		if (rightPathValid (input, current)) {
			right_sum = maxSum_less_expensive (input, rightNode(input, current));
		}
		if (downPathValid (input, current)) {
			down_sum = maxSum_less_expensive (input, downNode(input, current));
		}
		int max_sum = Math.max(right_sum, down_sum);
		int sumTillNode = max_sum + input[x][y];
		tempMatrix [x][y] = sumTillNode;
		return sumTillNode;
	}

	int maxSum (int[][] input, IntPair current) {
		int right_sum = 0;
		int down_sum = 0;

		if (isLastNode (input, current)) {
			return input[input.length][input[0].length];
		}
		if (rightPathValid (input, current)) {
			right_sum = maxSum (input, rightNode(input, current));
		}
		if (downPathValid (input, current)) {
			down_sum = maxSum (input, downNode(input, current));
		}
		int max_sum = Math.max(right_sum, down_sum);
		return max_sum + input[current.getFirst()][current.getSecond()];
	}

	private IntPair downNode(int[][] input, IntPair current) {
		return new IntPair ((current.getFirst()+1), current.getSecond());
	}

	private IntPair rightNode(int[][] input, IntPair current) {
		return new IntPair (current.getFirst(), (current.getSecond() + 1));
	}

	private boolean downPathValid(int[][] input, IntPair current) {
		if (input.length > (current.getFirst() + 1)){
			return true;
		}
		return false;
	}

	private boolean rightPathValid(int[][] input, IntPair current) {
		if (input[0].length > (current.getSecond() + 1)){
			return true;
		}
		return false;
	}

	private boolean isLastNode(int[][] input, IntPair current) {
		if (current.getFirst() == input.length
				&& current.getSecond() == input[0].length) {
			return true;
		}
		return false;
	}
}

In case all input is in characters only, then we can use array of characters.
Parse one array, and turn on corresponding index in array.
Parse second array, increment corresponding index by one.
Parse updated array, and whichever position has count one, they all r non-common.

good only if input is characters only.

run following file:
8
3 1
4 1
5 2
5 3
6 1
6 2
6 3
6 4

package com.code.saurabh.misc;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

import com.code.saurabh.util.UtilClass;

public class PolygonDiagonal {

	public static void main(String[] args) {
		try {
			readInput ("Inputs/polygon.txt");
		} catch (NumberFormatException | IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	private static void readInput(String filename) throws NumberFormatException, IOException {
		File file = new File (filename);
		if (!file.exists()) {
			return;
		}
		
		FileReader fr = new FileReader (filename);
		BufferedReader br = new BufferedReader (fr);
		int totalTest = Integer.parseInt(br.readLine());
		for (int i = 0; i < totalTest; i++) {
			String[] NK = br.readLine().split("\\s+");
			int N = Integer.parseInt(NK[0]);
			int K = Integer.parseInt(NK[1]);
			System.out.println("N: " + N + ", K: " + K + " -> " + calculateDiag (N, K));
		}
	}

	static int calculateDiag (int N, int K) {
		/*It can create a diagonal with all other vertexes than immediate neighbors and its own vertex (count 3) */
		int maxDiagonal = N-3; //Maximum number of diagonals from a vertex
		int totalDiagonal = 0;
		if (maxDiagonal <= 0) {
			return 0;
		}
		
		if (K > maxDiagonal) {
			return 0;
		}
		
		/*This method calculate how many diagonal can be created from a single vertex given constraint*/
		int pointDiagonal = singleVertexDiagonal (K, maxDiagonal);
		
		totalDiagonal = pointDiagonal * N;
		if (K == 1) {
			totalDiagonal = totalDiagonal/2;
		}
		return totalDiagonal;
	}

	private static int singleVertexDiagonal(int k, int maxDiagonal) {
		return factorial (maxDiagonal) / (factorial (maxDiagonal-k) * factorial (k));
	}

	public static int factorial (int N) {
		if (N == 0 || N == 1) {
			return 1;
		}
		return N * factorial (N-1);
	}
}

can't we store all characters in array of characters and corresponding indexes?
While parsing, updating this array with count & first index.After scanning stream, now scan stored array and find out the characters whose count is 1 and whose index is minimum !!!

We can use hashing + hashing + hashing approach.
First hash will be based on number of characters in line
Second hash will be number of words in the line
third will be hash of words and now we can store line here.

When a new line comes, it will pass all three hashes and if comes into same bucket then we can compare lines.
using these 3 hash (or filters) we can minimize the chances of clashing lines.

Shouldn't it be like:
Each item contain customer list who has purchased this item.
lets say Item X is purchased by Customer A, Customer B, Customer C & Customer D

Now, each customer also contain its itemHistory.
Customer A: X, a, b, c
Customer B: X, b, c, d
Customer C: X, e, f
Customer D: X, d, g

So if customer A buy item X, then it should be suggested a, b, c, d, e, f, g
or should customer be suggested only common items, like: b ,c ,d only ?

For case 2, there will be additional check to filter out common items. Now problem converts to finding common items in the list of list of items (list<listOfItems>).

Putting only classes and interfaces:

typedef long ID;

enum Roll {CASHIER, MANAGER, WAITER};
class Employee
{
	ID empID;
	string name;
	Roll roll;
	public:
	setRoll ();
}

class Waiter: public Employee
{
	public:
	waiter() {	setRoll (WAITOR); }
}

class Cashier: public Employee
{
	public:
	cashier () {	setRoll (CASHIER); }
}

class Table
{
	ID tableId;
	bool isAvailable;
	int capacity;
	int used;

	public:
	Table(ID id) {tableId = id; // set other params also}

	bool isAvailable ();
	void reserveTable ();
	void freeTable ();
}

Class Item
{
	ID itemID;
	double itemCost;
	public:
	getItemCost ();
}

class Order
{
	Table tableID;
	Waiter waiterID;
	Cashier cashierID;

	vector<item, int> request; // item, quantity
	public:
	void placeOrder (itemID, quantity) ;// push_back in request vector
	double getBill (); // call Invoice Class's generateBill()
}

class Menu
{
	map<item, double> itemCostMap; //
	map<item, int> itermQuantityMap; //

	public:
	double getItemCost (Item itemID);
	int getItemQuantity (Item itemID);
	bool isItemAvailable (Item itemID);
}

class invoice
{
	Menu menu;
	public:
	generateBill (vector<itemID, quantity>); // uses Menu class getItemCost () to get cost and generate bill
}


class coffeeShop
{
	List<Table> tables;
	List<Waiter> waiters;
	List<Cashier> cashiers;
	map<Table, Order> orders;

	public:
	coffeeShop ()
	{
		//initialise each table with ID and capacity; and other member also;
	}
	void addWaiter ();
	void removeWaiter ();
	void addCashier();
	void removeCashier ();
	//similar for other employees, like manager 

	void addTable ();
	void removeTable():

	void getOrder (Table tableId, Item itemID, int quantity); // this will order object and place in map

	double getBill (Table tableId)
	{ 
		Order order = orders[tableId]; 
		order.getBill ();
	}
}

a little mess-up is due to considering size changing of sequence at least start.
I have not tested if size changes in between, will it work. Although listed few test case where it is not working.

911 is sequence in a sense
consider sequence, 9,10,11 and if 10 is missing from sequence then it is 911

suffix tree will be good option. Nodes will be allocated only when they are required.

take example of apple, application, aptitude
                 a
                /
              p
             /  \
         pl     titude
        /   \
      e     ication

if user type: ap then output will: aptitude, apple, application
if user type: app then output will be: apple, application

whenever there is new addition of word and that word require to break node at some level, then break it and make two or more nodes.
"Apartment" and "Applied" addition will make tree like this
                             a
     	                    /
                       _    p
                     /    /   \
                 artment pl  titude
                         /   \
                       e     i
                           /  \
                          ed   cation

i have listed few test cases, can you check if they are working.
string str = "960961962964";
string str = "123457891011";
string str = "12345789";
string str = "123412351237";
string str = "123112321234";
string str = "293031323335";
string str = "99101";
string str = "99100101103104";
string str = "911";

Follow code is not working for some test case. specifically where digit size is changing from 9 to 10.
Two identified test cases which are not working are written.
I think with some changes they should work.

idea is:
try to figure out starting number, for that purpose 3 numbers are retrieved from string and checked for increasing order with difference of one.
Started with considering that digit size will be 1 and continue till digit size is (stringsize/2).

bool findMissing (string str, int dsize, int ssize)
{
        int i = 0;
        int missing = 0;
        bool tripped = false;

        while (1)
        {
                if ((i+2*dsize) >= ssize)
                {
                        break;
                }

                if (tripped == true)
                {
                        tripped = false;
                        dsize += 1;
                }
                string A = string(str,i,dsize);
                int a = atoi (A.c_str());

                string B;
                string C;
                if ( ((a+1)%100) == 0)
                {
                        tripped = true;
                        B = string(str,i+dsize, dsize+1);
                        C = string(str,i+(dsize+ dsize+1), dsize+1);
                }
                else
                {
                        B = string(str,i+dsize, dsize);
                        C = string(str,i+2*dsize, dsize);
                }

                int b = atoi (B.c_str());
                int c = atoi (C.c_str());

                cout << "a: " << a << ", b:" << b << ". c:" << c << endl;

                if (c == 0)
                {
                        if ( ((a+2) == b) )
                        {
                                missing = a+1;
                                i += dsize;
                                continue;
                        }
                }

                if ( ((a+1) == b) && ((b+1) ==c) )
                {
                        i += dsize;
                        continue;
                }
                else if ( ((a+1) == b) && ((b+1) !=c) && ((b+2) == c) )
                {
                        missing = b+1;
                        i += dsize;
                        continue;
                }
                else if ( ((a+1) != b) && ((a+2) ==b) && ((a+3) == c) )
                {
                        missing = a+1;
                        i += dsize;
                        continue;
                }
                else
                {
                        missing = 0;
                        break;
                }
        }
        if (missing != 0)
        {
                cout << "Missing is: " << missing << endl;
                return true;
        }
        return false;
}
int main ()
{
        //work
        //string str = "960961962964";

        //doesnot work
        //string str = "123457891011";

        //work
        //string str = "12345789";

        //work
        //string str = "123412351237";

        //work
        //string str = "123112321234";

        //work
        //string str = "293031323335";

        //work
        //string str = "99101";

        //work
        //string str = "99100101103104";

        //does not work
        string str = "911";

        int len = str.length();

        int i = 0;
        int ret = false;
        for (i = 1; i <= len/2; i++)
        {
                ret = findMissing (str, i, len);
                if (ret == true)
                {
                        break;
                }
        }
}

yes, I have not used inheritance.
I had tried to keep objects separate and later on we can remove or merge un-necessary classes during discussion.

Output for your logic giving some wrong results, only for digit[0]
n=199,
output
digits[0]=30

n=209
output
digits[0]=31

clearly, there should be digits[0] = 41 for n=209
anyways, i didn't go through your algo.

thanks buddy,
it should be return 0 in place of return S[i] in breaking condition.
if (S[i] != 0)
return 0;
corrected !!! :)

@Roxanne:
Algo is very much O(nlogn)
For each element starting from index 0 to n, it will search another 2*i element which in case of sorted array, can be done in O(logn).
Now, for your test case,
starting from 0th index, 2*a[0] = 2 * 3 = 6 and <= of 6 is 5 whose index is 10.
yes, i m wrong in writing array size to subtract from. it should be (arraySize -1). In this case it is 11.
subtracting 10 from 11 gives 1 and adding this to current index (which is 0) give 0 +1 = 1. So we need to remove only 1 element to get the desired result.

In your this case, as initial numbers are same, so with each additional index you will get count: 2, then 3 then 4 ... but min will remain same 1.
You can break this loop after finding that there can not be minimum than 1 in this case, and in some case minimum will be 0.

Did I understand you right?
By projecting all edges of rectangle to X & Y-axis, you are getting (X1, X2) and (Y1, Y2) of rect_1.
Similarly for all rectangles.
<X1, X2>, <X3, X4> ... <X2n, X2n+1>
<Y1, Y2>, <Y3, Y4> ... <Y2n, Y2n+1>

Now, sort all (X1, X2) and (Y1, Y2) based on 2nd element of pair.
if there is overlap of any two interval in <X1, X2> <Xk, Xk+1>, then check corresponding <Y1, Y2> <Yk, Yk+1>. if that too overlap then this rectangle do overlap.
M i rite?
If not, then please explain your algo a little bit more.

Also, does it also consider the case mentioned by "srikantaggarwal".
What if rectangles are not parallel to axis?

@Shankar:
Can you please give some example for this question?
I have some doubts regarding this question:
1) Output array will be fully sorted? in that case there will be only one possible position for each element in array, how can that be k from its initial position?
2) Is it possible that there is no solution of some given input?
3) Or output should be just each element should be k distance away from its initial position, but not sorted among themselves ?

Can be done with two traversal:

First traversal:
Find if any in-order successor of any node is equal to that node to find our duplicate
Second traversal:
Do post order traversal, and each traversal get (min, max) from both subtree and then check for BST property.

if duplicates is allowed in BST, then insertion will be with:
i) add new key to left subtree if key is less than or equal to root key
or
ii) add new key to right subtree if key is greater than or equal to root key

Taking (i):
For tree

5
	3
		5
	4
5 is root
3 is left to root(5)
next 5 is right to 3
4 is left to 5 (below)

in this tree, 3 is smaller than 5 so in left subtree to 5.
next 5 is less than or equal to root 5 so in left subtree of root (that is 5) and this new 5 is greater than 3 so in right subtree of 3.
So now, 5 is not immediate children of root (5).

a very naive implementation goes like to iterate from 0 to N.
Parse each digit and add digits to digit array.

#include <iostream>
#include "stdlib.h"
using namespace std;

void updateDigits (int *digits, int num)
{
	if (num == 0)
	{
		digits[0] += 1;
		return;
	}
	int k = 0;
	while (num > 0)
	{
		k = num%10;
		digits[k] += 1;
		num = num/10;
	}
}

void countDigits (int num)
{
	int j = 0;
	int digits[10] = {0};
	for (j = 0; j <= num; j++)
	{
		updateDigits (digits, j);
	}
	for (j = 0; j <= 9; j++)
	{
		cout << "digits[" << j <<"]" << digits[j] << endl;
	}
}
int main(int argc, char* argv[]) {
	countDigits (299);
	return 0;
}

Output:
digits[0]50
digits[1]160
digits[2]160
digits[3]60
digits[4]60
digits[5]60
digits[6]60
digits[7]60
digits[8]60
digits[9]60

@booley.
yes, u r right.
Well, it can be modified a bit. Instead of multiplying digits from front, we can do it from backward and then print digits in sorted order.
changing it.

Ajeet, quite sufficient and detailed interfaces. But some can be merged i think. like:

Class Input, Class KeyPad, Class Key and Class display can be merged into like: UserInterface
Class MoneyValidator can be merged with Class Money itself (this class will have enough info regarding the value of currency and cost should be passed as parameter to validate function)

1) Divide number in multiple of 2,3,5,7 of number. For given number: 2 * 2 * 5 *5
2) Backward, keep on multiplying adjacent number as long as multiple is a single digit (< 10) and create new digit and put new digit in place of that number. for given number: 4 * 5* 5
3) repeat step 2, u wont have to do it much.concatenate digits in sorted order. Result it: 455
4) if number can not be divided into multiple of 2, 3, 5, 7 only, then return -1

Example: 40 =>  2 * 2 * 2 * 5 = 8 * 5 =  5 * 8 = 40
Example: 1260 => 2 * 2 * 3 * 3 * 5 * 7 = 4 * 9 * 5 *  7 = 4 * 5 * 7 * 9 = 4579
Example: 12 => 2 * 2 * 3 = 2 * 6 = 26

i think it should very much depend on the server itself whether it support to push its info to other who has registered itself.
in case of push model, there must be some kind of event module running on newAggregator which will receive notification from server and update its database.

it was a very naive or initial thoughts which can be more specific with discussion in interviews. For your answers:

1) Just like in google news, we have authentication. User preferences are saved for future interaction. Just like in google news, whenever we login it aggregates news according to our preferences. In newsaggregator class, we have provided the interface only for external users. This interface will then call user class for saving preferences and call Source class to add new source if it doesn't exist already. As Source class will also update its database (or you should call more technically, Source class will learn from its users) with new inputs which it has not added initially. So newAggregator is kind of single instance per user.

2) For scaling to multiple machines, we can use Distributed hash table (consistent hashing). So whenever there is request to fetch from source S1, then corresponding hashed server will be requested for source S1.

@Srigopal Chitrapu:
I am not talking about his code. I am talking about his extended version where he is saying to use queue1, queue2 and tempQueue
extracting his sentence:
"use the second queue and the tempQueue to process elements for Queue1"

it was not complete code.
Now it is complete. I have not run many test cases, let me know the ones which fails ...

we can start from 0th index?

what test case it did not pass?

1) Sort the array
2) Scan array from 0 to n/2
3) for each element i in array:
a) find index of a number which is <= 2*a[i]. Take diff of array size - index of the number.  add this diff with index i (away from 0th index). make it min
b) repeat step 3.a and take min

As per question, input array will have numbers from 0 to n-1 only for array size n with probability of duplicates.
Based on that
1) Initialise array S of size n with 0
2) iterate through array and increment S[i] by 1 each time a[i] is accessed.
3) recursively call index a[i] and add return value to S[i] and do as step 2.
4) breakpoint: if i and a[i] is equal return 0, else if S[i] is non-zero then return S[i];
Complexity : O(n) as each index will be accessed once only

#include <iostream>
using namespace std;
int update (int *a, int *S, int i, int size)
{
    if (S[i] != 0)
        return 0;
    S[i] += 1;
    if (i == a[i])
        return 0;
    else
        S[i] += update (a, S, a[i], size);
    return S[i];
}
void updateArray (int a[], int size)
{
    int *S = new int[size];
    int i = 0;
    //initialise S with 0;
    for (i = 0; i < size; i++)
    {
        S[i] = 0;
    }
    for (i = 0; i < size; i++)
    {
        update(a, S, i, size);
    }
    int max = 0;
    for (i = 0; i < size; i++)
    {
        if (max < S[i])
        {
            max = S[i];
        }
    }
    cout << "max size: " << max << endl;
}

int main ()
{
    int a[] = {3,1,2,0,4};
    updateArray (a, 5);

    int b[] = {5, 4, 0, 3, 1, 6, 2};
    updateArray (b, 7);
}

with some assumptions, like pull model:

class newsaggregator
{
	User user;
	public:
	bool login (string userId, string password);

	//This will hold timers and update result after timer expiry. will fetch from server based on user credentials
	void aggregateResult ();
	void addSource (string sourcename);
	void addCategory (string category, int freq = 5 min);
};

class User
{
	list<Source> sources;
	public:
	bool validateUser (string userId, string password);
	void addSource(string sourcename);
	void addCategory (string category, int freq);
};

class Source
{
	list<string> sources;
	double frequency; // 1 min
	map<string, list<string> > news;

	public:
	void daemon (); // after timer expiry, query each source and update news
	list<string> retrieveNews (string source, string category); // Interface for newsaggregator
	addNewSource (string source); // if source new, then add
};

How can we get information if we are not allowed to pull or push (page crawl is kind of pull) ??

I can think of only this: catching broadcast information should be aggregated ..

Further lights?

Can you please give some more inputs, like: what kind of job scheduler, in what area?
Printer Job scheduler,
OS job scheduler
or any other type job scheduler, there must be little more follow up inputs, please share in brief ?

typedef long ID;


Class Client
{
	ID clientId;
	string Name; //This can be struct will details
	string location;  //This can be struct will details
	ID zipcode; //Again this can be part of location
	list<Transaction> transactionIDs; 

	public:
	list< Transaction > getTransactions () { return transactionIDs; }
	int getPincode () { return zipcode;}
	string getClientDetails() {return Name;} //Like: first name, last name, age, gender etc
};

class Product
{
	ID productId;
	double productCost;
	string productName;
	public:
	ID getProductID () {return productId};
	string getProductName () {return productName; }
	double getProductCost () {return productCost; }
};

class Service 
{
		ID serviceId;
	double serviceCost;
	string serviceName;
	public:
	ID getServiceID ();
	string getServiceName ();
	double getServiceCost ();
};
struct trxDetail
{
	enum typeOfTransaction;
	ID itemId;
	int itemQuatity;
};
class Transaction
{
	client clientName;
	timestamp purchaseDate;
	timestamp dueDate;
	ID transactionID;
	trxDetail purchasedItem;
public:
	client getClient ();
	ID getTransactionID ();
	date getTransactionDate ();
	date getTransactionDueDate ();
	trxDetails getTransactionDetail ();
	//long transactionCost (); // can be calculated using serviceCost/ProductCost & quantity. tax can be added at time of invoice generation
	//addTransaction (client, transactiontime, duedata, <type, id, quantity>);
};

class taxDetails
{
	ID zipcode;
	double taxAmount;
public:
	double getTax ();
};

class invoiceManagement
{
	map<ID, Client> clientMap;
	map<ID, Service> serviceMap;
	map<ID, Product> productMap;
	map<ID, Transaction> transactionMap;
	map<ID, taxDetails> taxMap;
	static invoiceManagement *instance;

public:
	static invoiceManagement  *getInstance ()
	{
		if (instance == NULL)
		{ 
			instance = new invoiceManagement;
		}
		return instance;
	}
	Client getClient ( ID clientId ) {  return clientMap[clientID]; }
	Service getService (ID serviceId ) { return serviceMap[serviceID];  }
	Product getProduct (ID productId ) { return productMap[productID];  }
	Transaction getTransaction (ID transactionId ) { return transactionMap[transactionID];  }
	taxDetails getTaxDetails (ID zipcode ) { return taxMap[zipcode];  }

};

class invoice
{
	invoiceManagement *IM;
public:
	invoice () { IM = invoiceManagement::getInstance(); }

	void generateInvoice (ID clientID)
	{
		Client *client = IM->getClient (clientID);
		list<Transaction> trxList= client-> getTransactions ();

		//print: customer details, address
		for (trx: trxList)
		{
			trxDetail td = trx. getTransactionDetail ();
			ID zipcode =  client->getzipcode();
			string clientname = client->getClientDetails ();
			timestamp duedate = trx.getDueDate ();
			timestamp trxdate = trx.getTransactionDate ();
			double unitcost = 0;
			double tax = 0;
			string name = "";
			int quantity = 0;
			if (td.type == PRODUCT)
			{
				quantity = td.quantity;
				Product product = IM->getProduct (td.itemID);
				unitcost = product.getCost ();
				name = product.getName ();
				tax = IM.->getTaxDetails (zipcode);
			}
			else if (td.type == SERVICE)
			{
				quantity = td.quantity;
				Service service = IM->getProduct (td.itemID);
				unitcost = service.getCost ();
				name = service.getName ();
			}

			int totalCost = unitcost * quantity + tax;
			//print: name, unit cost, quantity, totalcost, due date, transaction date
		}
	}
};

It can be done by keeping following type of map:
map<int, pair<tree*, tree*> >
Key: node's key
pair.first = Tree node of Parent of Key
pair.second = Tree Node of Key

parsing each input line, if key exist then update its parent and child else add key to map.

pair<int, int> input[]; // Input data
tree *root = NULL;
tree* binaryTree::constructBinaryTree ()
{
        map<int, pair<tree*, tree*> > keyParentNode;    //Interger: key, pair.second: treenode of key, pair.first: parent of pair.second

        tree *node = NULL;
        pair<tree*, tree*> P(NULL,NULL);
        pair<tree*, tree*> C(NULL,NULL);
        int i = 0;
        int size = input.size();
        map<int, pair<tree*, tree*> >::iterator mapIt;
        for (i = 0; i < size; i++)
        {
                mapIt = keyParentNode.find(input[i].first);//First value of input pair
                if (mapIt == keyParentNode.end())
                {
                        node = new tree;
                        node->key = input[i].first;
                        node->left = NULL;
                        node->right = NULL;
                        keyParentNode[input[i].first] = pair<tree*, tree*>(NULL, node);
                }
                P = keyParentNode[input[i].first];

                mapIt = keyParentNode.find(input[i].second);//Second value of input pair
                if (mapIt == keyParentNode.end())
                {
                        node = new tree;
                        node->key = input[i].second;
                        node->left = NULL;
                        node->right = NULL;
                        keyParentNode[input[i].second] = pair<tree*, tree*>(NULL, node);
                }
                C = keyParentNode[input[i].second];

                if (P.second->left == NULL)
                {
                        P.second->left = C.second;
                }
                else
                {
                        P.second->right = C.second;
                }
                C.first = P.second; //Storing Parent Node
        }

        for (mapIt = keyParentNode.begin(); mapIt != keyParentNode.end(); mapIt++)
        {
                if ((mapIt->second).first == NULL)
                {
                        root = (mapIt->second).second; // return root of tree
                        break;
                }
        }
        return root;