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;
}
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();
}
}
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) & i-j > 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];
}
It's a Dynamic Programming problem with recursive function as
CanReach(i,j) = { true if stone[i] is true && (CanReach[i-j][j-1] || CanReach[i-j][j] ||CanReach[i-j][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;
}
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);
}
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(i-1, k-1) }
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;
}
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;
}
My bad... I dont think a O(n) solution is possible inplace. Here is O(n2) insertion sort kind-of 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;
}
}
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;
}
}
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;
}
Divide the number recursively with the largest digit possible (9,8,...,2). Save the digit at each step.
- Brandy June 24, 2018