Brandy
BAN USERFollowing is the minimal DB design required to support the requirement
UserPriceTrackingData
User_id  Item_id  Price limit  expiry_date
ItemPrice
Item_id  Price
User
User_id  User_email
API's exposed:
1) UpdatePrice, params: item_id, price
Prices will be updated using UpdatePrice api and will be stored in ItemPrice table.
2) AddTrackingData, params: user_id, item_id, tracking price
User can enter price tracking data using AddTrackingData will be stored in UserPriceTrackingData with request expiry_date set to, say, 30 days later. If the price is already below the tracking price, a email is sent straightaway.
Worflow:
Whenever UpdatePrice is called to update the price, a background task will try match the UserPriceTrackingData entry for the item with tracking price larger than the new price. If a match is found, an email is sent.To expedite it, we can cache the tracking data for the most frequently updated items.
Sort the numbers and traverse from starting keeping a cumulative sum of numbers found so far(including numbers added). At any point the cumulative sum value denotes the largest number that we can get by adding numbers in the array.
static int NumbersToAdd(int[] elements, int last)
{
int size = elements.length;
int addedNums = 0;
int cum_sum = 0;
int i = 0;
while(i<size  cum_sum < last)
{
if(i>=size  elements[i] > cum_sum + 1)
{
addedNums++;
int number_added = cum_sum + 1;
cum_sum += number_added ;
}
else
{
cum_sum += elements[i];
i++;
}
}
return addedNums;
}

Brandy
August 10, 2015 import java.util.Scanner;
import java.util.Vector;
class SmallerFactorialNumber
{
public static void main(String arg[])
{
int num;
Scanner in = new Scanner(System.in);
num = in.nextInt();
Vector<Integer> vecDigits = new Vector<Integer>();
for (int i = 9; i > 1; i)
{
while (num % i == 0)
{
vecDigits.add(i);
num /= i;
}
}
int size = vecDigits.size();
if (num != 1)
System.out.print(1);
else if (size == 0)
System.out.print(1);
else if (size == 1)
{
System.out.print(1);
System.out.print(vecDigits.get(0));
}
else
{
for (int i = size  1; i >= 0; i)
{
System.out.print(vecDigits.get(i));
}
}
in.close();
}
}

Brandy
June 05, 2014 We need to maintain 1 max heap and 1 min heap. Max heap will contain lower half of the numbers and min the upper half. Whenever, a new number comes:
1) if its less than root of max heap, it is inserted into max heap.
2) if its higher than root of min heap, it is inserted into min heap.
3) after insertion if the size difference of two heaps is greater than 1, the root of the larger heap is transferred to the other heap to balance their size.
At any point, the median will be:
1) (root of max heap + root of min heap) / 2 if size of both heap are equal.
2) root of larger heap otherwise.
Dynamic Programming
C[i] = for all j>[0,i) & ij > Arr[j] min{C[j] + 1}
int MinSteps(vector<int> vecNum)
{
int size = vecNum.size();
vector<int> vecSteps(size);
vecSteps[0] = 0;
for (int i = 1; i < size; i++)
{
int min = i;
for (int j = 0; j < i; j++)
{
if (i  j <= vecNum[j])
{
if (min > vecSteps[j] + 1)
min = vecSteps[j] + 1;
}
}
vecSteps[i] = min;
}
return vecSteps[size  1];
}

Brandy
May 29, 2014 It's a Dynamic Programming problem with recursive function as
CanReach(i,j) = { true if stone[i] is true && (CanReach[ij][j1]  CanReach[ij][j] CanReach[ij][j+1])
where,
i is the stone
j is the velocity when the frog reached i
bool CanCross(vector<bool> vecStones)
{
vecStones.push_back(true); // last true for the land, it makes things simpler
int size = vecStones.size();
vector<vector<bool>> vecCanReach(size, vector<bool>(size, false));
vecCanReach[0][1] = true;
for (int i = 1; i < size; i++)
{
if (vecStones[i] == false)
continue;
for (int j = i  1; j >= 0; j)
{
if (vecStones[j] == false)
continue;
if (vecCanReach[j][i  j]  ((i  j  1 >= 0) && vecCanReach[j][i  j  1])  ((i  j + 1 < size) && vecCanReach[j][i  j + 1]))
vecCanReach[i][i  j] = true;
}
}
for (int i = 0; i < size; i++)
{
if (vecCanReach[size  1][i])
return true;
}
return false;
}

Brandy
May 26, 2014 Easy but tricky question. The key is:
1) save numbers in buffer and print at the end
2) avoid repeat combinations.
void PrintCombo(int num, int* arr, int index )
{
if (num == 0)
{
for (int i = 0; i<index; i++)
{
if (i != 0)
cout << ',';
cout << arr[i];
}
cout << '\n';
return;
}
for (int i = num; i > 0; i)
{
if (index == 0  i <= arr[index  1])
arr[index] = i;
else
continue;
PrintCombo(num  i, arr, index + 1);
}
}
int main()
{
int num;
cout << "Enter the number \n";
cin>>num;
int *arr = new int[num];
PrintCombo(num, arr, 0);
}

Brandy
May 25, 2014 Let the horses are numbered from 1 to n with total k stables. We will calculate C(i,j) which is the minimum sum of products for i stables and j horses.
The recursive relation would be:
C(i, j) = min { P(k,j) + C(i1, k1) }
where,
i ranges from 1 to k
j ranges from 1 to n
k ranges from j to i
P(k,j) is the product of black and white horses in range k to j, when put in one stable.
Node* Copy(Node* head)
{
if (head)
return;
node* curr = head;
//create a copy of each node and insert it after the node in the original list
while (curr)
{
node* temp = new node();
temp>Data = curr>Data;
temp>Next = curr>Next;
curr>Next = temp;
curr = temp>Next;
}
//Polpulate this>Other and separate out the copy LL
curr = head;
node* duplicate = head>next;
while (curr)
{
node* copy = curr>next;
copy>other = curr>other>next;
curr>next = copy>next;
curr = curr>next;
copy>next = curr>next;
}
return dulticate;
}

Brandy
May 23, 2014 The code will take a binary search approach with few checks in between. Complexity = O(logn)
int FindPivotIndex(vector<int> arr)
{
int size = arr.size();
int first = 0, last = size  1;
while (first <= last)
{
if (arr[first] <= arr[last])
return first;
int mid = (first + last) / 2;
if (arr[mid] < arr[first] && arr[mid] <= arr[last])
{
if (arr[mid  1] > arr[mid])
return mid;
// pivot in first half
last = mid  1;
}
else if (arr[mid] >= arr[first] && arr[mid] > arr[last])
{
//pivot in second half
first = mid + 1;
}
}
return 1;
}

Brandy
May 23, 2014 My bad... I dont think a O(n) solution is possible inplace. Here is O(n2) insertion sort kindof solution
void Rearrange(highNode* head)
{
highNode* highList = head;
highNode* curr = head;
while(curr)
{
if(curr>data < highList>data)
{
curr>high = highList;
highList = curr;
}
highNode* highIter = highList;
while(highIter>high && highIter>high>data < curr>data)
{
highIter = highIter>high;
}
highNode* temp = highIter>high;
highIter>high = curr;
curr>high = temp;
curr = curr>next;
}
}

Brandy
May 13, 2014 First we need to find the lowest number in O(n) and then starting from there rearrange high pointers.
Code:
void Rearrange(highNode* head)
{
if(head == NULL)
return;
int min = head>data;
highNode* curr = head;
highNode* minNode = head;
while(curr)
{
if(curr>data < min)
{
min = curr>data;
minNode = curr;
}
curr = curr>next;
}
while(minNode>high)
{
highNode* temp = minNode>high;
minNode>high = minNode>high>high;
minNode = temp;
}
}

Brandy
May 13, 2014 bool DuplicateBraces(const char * exp, int len)
{
stack<int> braceIndices;
int lastPop = 0;
int prevIndex = 1;
for (int i = 0; i < len; i++)
{
if (exp[i] == ' ')
continue;
if (exp[i] == '(')
{
braceIndices.push(i);
lastPop = 0;
}
else if (exp[i] == ')')
{
int topIndex = braceIndices.top();
if (((prevIndex  topIndex) == 1) && lastPop == 1)
return true;
braceIndices.pop();
prevIndex = topIndex;
lastPop = 1;
}
else
{
lastPop = 0;
}
}
return false;
}

Brandy
May 04, 2014
Divide the number recursively with the largest digit possible (9,8,...,2). Save the digit at each step.
 Brandy June 24, 2018