SK
BAN USER
- 1of 1 vote
AnswersGiven row on N house, each is marked either R or B. And each house having some gems. You have to collect gems from these house with some constraint:
- SK in India
You can choose gems from any blue house but you have to choose even number of red house ( either from 2 Red houses or from 4 red houses)
each time you take gem from one house, you will multiply gems received with gems currently, you have.
You have to choose continuous houses.
You have to return start point and end point of house (remember this should be continuous )| Report Duplicate | Flag | PURGE
Directi Senior Software Development Engineer Algorithm - 5of 5 votes
Answersyou have given array of Size N and two numbers M, K. K is size of subarray and M is count of subarray.
- SK in India
You have to return sum of max M subarray of size K (non-overlapping)
N = 7, M = 3 , K = 1
A={2 10 7 18 5 33 0} = 61 — subsets are: 33, 18, 10 (top M of size K)
M=2,K=2
{3,2,100,1} = 106 - subsets are: (3,2), (100,1) 2 subsets of size 2| Report Duplicate | Flag | PURGE
Directi Senior Software Development Engineer Algorithm Dynamic Programming - 0of 0 votes
AnswerDesign a notification framework which notifies for birthdays, movie release, book release whenever one occurs.
- SK in India
Things kept on adding based on user subscription?
How all object, classes related/talk to each other?
There on, move on how to store them in tables?| Report Duplicate | Flag | PURGE
iLabs Senior Software Development Engineer Object Oriented Design - 0of 0 votes
AnswersGiven a Binary tree find out if it a BST or not?
- SK in India| Report Duplicate | Flag | PURGE
iLabs Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersGiven a N * M matrix, you have to rotate it by 90 degree.
- SK in India for Bing
I gave him solution with transpose matrix & then reverse each row.
He was satisfied but after asked that this required each element to be touched twice. Can you do it like all elements will be touched once only.| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersYou given an array:
- SK in India
3, 2, 1, 6, 5, 4, 9, 8, 7
you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array.
Answer can have multiple tuples, you have to find any one.
In this array, answer will be 3, 6, 9| Report Duplicate | Flag | PURGE
Flipkart Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersFollowing sequence is given:
- SK in India
1,2,3,4,5,6,8,9,10,12,15,16,18,20,24
In this sequence, each number is multiple of 2,3 or 5 only.
This sequence does not contain 7 & 14 as these number has sequence 7 as multiple.
So, if you are given N find the Nth number of this sequence.| Report Duplicate | Flag | PURGE
Flipkart Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersThere is a server when a user can login.
- SK in India
A used can login multiple times.
you have to return number of unique users in last 10 minutes.
Retrieve unique user count operation should be as fast as possible.
Note:
A user who has done login in last 10 minutes more than once should be counted only 1.
It is possible that in a particular duration no user has logged in.| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 5of 5 votes
AnswersGiven a binary tree.
Print nodes of extreme corners of each level but in alternate order.10 5 11 9 20 - 15 14 - - - 25 30
then output should be 10,11,9,25,30
- SK in India
left most of 0th level
right most of 1st level
left most of 2nd level
& like this| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm Trees and Graphs
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;
}
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);
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.
- SK August 26, 2014package 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);
}
}
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 ();
}
}
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;
}
}
}
@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 ?
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
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.
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
};
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;
You can take assumption that there is no negative value and gems are not 0.
- SK January 22, 2015your solution seems to be correct.
But can you do it in O(n) ?