mithya
BAN USER- 0of 2 votes
AnswersAn array of integer represents a bar graph, where index of array is X axis (width = 1) and Y axis represents height of the bar graph at X, find out how much water will retain if it rains infinite on the structure. Only portion of graph that retains water is enclosed area due to height difference of bar graph. You need to assume that each bar itself doesn't store any water.
- mithya in United States
e.g. {1,2,3} then no water is stored
{6,4,1} then no water is stored
{3,2,1, 5} then 3 unit water is stored between 3 & 5 (1 unit on 2 and 2 unit on 1)| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a dictionary of words, return words that can be formed by using only symbols from Chemistry Periodic Table.
- mithya in United States
e.g. ARK (Ar-K)
SICK (Si-C-K) etc.
(All the time while writing the code, I was just thinking about Br-Ba :) )| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Algorithm
The optimal solution for this would be to solve by dynamics programming. I will solve it in a non-optimal way - by recursion. You can convert it to dynamic programming.
Start with a given number, split it by first char and rest and apply operator (+/- or none) between numbers and previously calculate sum and store output if wall prime
Helper Functions:
bool IsWallPrime(int num) // checks if given number os wall prime
int CoverToInt(char* str, int len=strlen(str)) // converts len numbers of str into integer. Default value is whole strlen(str) i.e. whole string
To Invoke:
int ans = 0;
CheckPrime("12345", ans, 0);
print ans;
void CheckWallPrime(char* str, int& ans, int prevSum)
{
if(*str == '\0')
{
return ;
}
// For original "123", think that we are here with prevSum = 1 & str = "23"
int sum = prevSum + ConvertToInt(str); // convert whole str to int (case 1 +23)
if(IsWallPrime(sum))
ans += 1;
sum = prevSum- ConvertToInt(str); // convert whole str to int : (case 1 - 23)
if(IsWallPrime(sum))
ans += 1;
int firstNumber = ConvertToInt(str, 1); // split by first char and rest of string
// Apply +ve operator
CheckWallPrime(str+1, ans, prevSum + firstNumber); // (case 1+2 + rest of string "3")
// Apply -ve operator
CheckWallPrime(str+1, ans, prevSum - firstNumber); // (case 1-2 + rest of string "3")
// Apply no operator:
CheckWallPrime(str+1, ans, prevSum*10 + firstNumber); // (case 12 + rest of string "3")
}
I am not handling the case for the first character of string. This code applies operator to it which it shouldn't. e.g. for "123", it will consider +123, -123 and 123 (no operator) which is not correct. I am not handling that to avoid code looking obscure
- mithya October 26, 2013A typo correction in the original question: There are 3 ^ (n-1) i.e. 3 raise to (n-1) such combinations (instead of 3n-1). Why? For n digits, you have n-1 'empty' spaces between consecutive numbers. Where you can decide to put 3 of possible options (+/- or none). So total combinations are 3*3*... (n-1) times
- mithya October 26, 2013
Repnancysimms14, Backend Developer at ASAPInfosystemsPvtLtd
I am Nancy from California,Handling project development and documentation is my job. Passionate determined.Looking for an open project ...
@urik: I appreciate your reply. However, I see a lot of 'could' / 'should' in your reply without providing anything concrete. It would be nice to replace your 'could'/'should' with some code to benefit everyone(especially me) here.
- mithya October 27, 2013