pavelkushtia
BAN USERwrong code in terminating condition.
- pavelkushtia June 20, 2015#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
std::unordered_set<std::string> operatorSet;
std::stack<std::string> runningStack;
void initOperatorSet() {
operatorSet.insert("+");
operatorSet.insert("-");
operatorSet.insert("/");
operatorSet.insert("*");
}
bool isOperator(std::string op) {
return (operatorSet.find(op) != operatorSet.end());
}
string getCalculatedValue(std::string num1, std::string num2, std::string op) {
float val1 = std::stof(num1);
float val2 = std::stof(num2);
char opChar = op[0];
switch(opChar) {
case '+':
return std::to_string(val1+val2);
case '-':
return std::to_string(val1-val2);
case '*':
return std::to_string(val1*val2);
case '/':
if (val2 == 0) {
printf("ArithmeticException\n");
return "";
}
return std::to_string(val1/val2);
default:
printf("IllegalArgumentException\n");
break;
}
printf("ArithmeticException\n");
return "";
}
bool pushNumber(std::string num) {
if(runningStack.empty()) {
runningStack.push(num);
return true;
}
if(isOperator(runningStack.top())) {
runningStack.push(num);
return true;
}
std::string num2 = runningStack.top(); runningStack.pop();
if (runningStack.empty()) {
printf("IllegalArgumentException\n");
return false;
}
if(!isOperator(runningStack.top())) {
printf("IllegalArgumentException\n");
return false;
}
std::string str = getCalculatedValue(num, num2, runningStack.top());
runningStack.pop();
runningStack.push(str);
return true;
}
std::string calculateReversePolish(std::vector<std::string> seqArray) {
initOperatorSet();
int len = seqArray.size();
for (int i=0; i< len; i++) {
if(isOperator(seqArray[i])) {
runningStack.push(seqArray[i]);
}
else {
if (!pushNumber(seqArray[i])) {
return "Invalid";
}
}
}
if (runningStack.size() != 1) {
printf("IllegalArgumentException\n");
return "Invalid";
}
return runningStack.top();
}
int main() {
/** Compute the value of an expression in Reverse Polish Notation. Supported operators are "+", "-", "*" and "/".
* Reverse Polish is a postfix mathematical notation in which each operator immediately follows its operands.
* Each operand may be a number or another expression.
* For example, 3 + 4 in Reverse Polish is 3 4 + and 2 * (4 + 1) would be written as 4 1 + 2 * or 2 4 1 + *
*
* @param ops a sequence of numbers and operators, in Reverse Polish Notation
* @return the result of the computation
* @throws IllegalArgumentException ops don't represent a well-formed RPN expression
* @throws ArithmeticException the computation generates an arithmetic error, such as dividing by zero
*
* <p>Some sample ops and their results:
* ["4", "1", "+", "2.5", "*"] -> ((4 + 1) * 2.5) -> 12.5
* ["5", "80", "40", "/", "+"] -> (5 + (80 / 40)) -> 7
*/
std::vector<std::string> strVec;
strVec.push_back("*");
strVec.push_back("2.5");
strVec.push_back("+");
strVec.push_back("1");
strVec.push_back("4");
std::string res = calculateReversePolish(strVec);
printf("%s\n", res.c_str());
return 0;
}
Simple logic:
====================
Maintain a stack S
For each item
if operator then inert in S
if number then call pushNumber function with the number
inside pushNumber function:
check top of S => if number then insert
else just pop a number and a operator and calculate,
push the calculated number to S using pushNumber function
Here is the c++ implementation:
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
std::unordered_set<std::string> operatorSet;
std::stack<std::string> runningStack;
void initOperatorSet() {
operatorSet.insert("+");
operatorSet.insert("-");
operatorSet.insert("/");
operatorSet.insert("*");
}
bool isOperator(std::string op) {
return (operatorSet.find(op) != operatorSet.end());
}
string getCalculatedValue(std::string num1, std::string num2, std::string op) {
float val1 = std::stof(num1);
float val2 = std::stof(num2);
char opChar = op[0];
switch(opChar) {
case '+':
return std::to_string(val1+val2);
case '-':
return std::to_string(val1-val2);
case '*':
return std::to_string(val1*val2);
case '/':
if (val2 == 0) {
printf("ArithmeticException\n");
return "";
}
return std::to_string(val1/val2);
default:
printf("1->IllegalArgumentException\n");
break;
}
printf("ArithmeticException\n");
return "";
}
bool pushNumber(std::string num) {
if(runningStack.empty()) {
runningStack.push(num);
return true;
}
if(isOperator(runningStack.top())) {
runningStack.push(num);
return true;
}
std::string num2 = runningStack.top(); runningStack.pop();
if (runningStack.empty()) {
printf("2->IllegalArgumentException\n");
return false;
}
if(!isOperator(runningStack.top())) {
printf("3->IllegalArgumentException\n");
return false;
}
std::string str = getCalculatedValue(num, num2, runningStack.top());
runningStack.pop();
pushNumber(str);
return true;
}
std::string calculateReversePolish(std::vector<std::string> seqArray) {
initOperatorSet();
int len = seqArray.size();
for (int i=0; i< len; i++) {
if(isOperator(seqArray[i])) {
runningStack.push(seqArray[i]);
}
else {
if (!pushNumber(seqArray[i])) {
return "Invalid";
}
}
}
if (runningStack.size() != 1) {
printf("4->IllegalArgumentException - stack size(%d)\n", runningStack.size());
return "Invalid";
}
return runningStack.top();
}
int main() {
/** Compute the value of an expression in Reverse Polish Notation. Supported operators are "+", "-", "*" and "/".
* Reverse Polish is a postfix mathematical notation in which each operator immediately follows its operands.
* Each operand may be a number or another expression.
* For example, 3 + 4 in Reverse Polish is 3 4 + and 2 * (4 + 1) would be written as 4 1 + 2 * or 2 4 1 + *
*
* @param ops a sequence of numbers and operators, in Reverse Polish Notation
* @return the result of the computation
* @throws IllegalArgumentException ops don't represent a well-formed RPN expression
* @throws ArithmeticException the computation generates an arithmetic error, such as dividing by zero
*
* <p>Some sample ops and their results:
* ["4", "1", "+", "2.5", "*"] -> ((4 + 1) * 2.5) -> 12.5
* ["5", "80", "40", "/", "+"] -> (5 + (80 / 40)) -> 7
*/
std::vector<std::string> strVec;
strVec.push_back("+");
strVec.push_back("/");
strVec.push_back("40");
strVec.push_back("80");
strVec.push_back("5");
std::string res = calculateReversePolish(strVec);
printf("%s\n", res.c_str());
return 0;
}
Binary Search:
#include <iostream>
using namespace std;
int getIndex(int* array, int val, int start, int end) {
if (start >= end) {
if (array[start] == val) return start;
else return -1;
}
int mid = (start+end)/2;
if (array[mid] == val)
return mid;
if (array[mid] > val)
return getIndex(array, val, start, mid);
return getIndex(array, val, mid+1, end);
}
int findNum(int* array, int len, int val) {
return getIndex(array, val, 0, len-1);
}
int main()
{
int array[] = {1, 2, 3, 4, 5, 6};
int val = 3;
printf("index of %d = %d\n", val, findNum(array, 6, val));
val = 1;
printf("index of %d = %d\n", val, findNum(array, 6, val));
val = 7;
printf("index of %d = %d\n", val, findNum(array, 6, val));
return 0;
}
followup:
#include <iostream>
using namespace std;
int getIndex(int* array, int val, int start, int end) {
if (start >= end) {
if (array[start] == val) return start;
else return -1;
}
int mid = (start+end)/2;
if (array[mid] == val)
return mid;
if (array[mid] > val) {
if (array[start] > val)
return getIndex(array, val, mid+1, end);
return getIndex(array, val, start, mid);
}
else {
if (array[start] > val)
return getIndex(array, val, start, mid);
return getIndex(array, val, mid+1, end);
}
return -1;
}
int findNum(int* array, int len, int val) {
return getIndex(array, val, 0, len-1);
}
int main()
{
int array[] = {4, 5, 6, 1, 2, 3};
int val = 2;
printf("index of %d = %d\n", val, findNum(array, 6, val));
val = 6;
printf("index of %d = %d\n", val, findNum(array, 6, val));
val = 5;
printf("index of %d = %d\n", val, findNum(array, 6, val));
return 0;
}
This is what i did exactly but in c++. Plain and simple.
- pavelkushtia February 06, 2015Here is the recursive solution:
#include <iostream>
using namespace std;
class FoundInfo {
public:
bool found;
int value;
FoundInfo(bool fnd, int val) {
this->found = fnd;
this->value = val;
}
};
class Node {
public:
int value;
Node* left;
Node* right;
Node(int val) {
this->value = val;
left = NULL;
right = NULL;
}
FoundInfo findKth(int &k) {
FoundInfo Found(false, 0);
if (this->left) {
Found = this->left->findKth(k);
if (Found.found) {
return Found;
}
}
--k;
if ( k == 0 ) {
Found.value = this->value;
Found.found = true;
return Found;
}
if (this->right) {
Found = this->right->findKth(k);
}
return Found;
}
};
int main() {
Node* root = new Node(4);
Node* child1 = new Node(2);
Node* child2 = new Node(6);
Node* gchild11 = new Node(1);
Node* gchild12 = new Node(3);
Node* gchild21 = new Node(5);
Node* gchild22 = new Node(7);
root->left = child1;
root->right = child2;
child1->left = gchild11;
child1->right = gchild12;
child2->left = gchild21;
child2->right = gchild22;
int k=4;
printf("value(%d)\n", root->findKth(k).value);
return 0;
}
Here is the C++ Implementation:
#include <iostream>
#include <string>
#include <list>
#include <unordered_map>
using namespace std;
class Node {
public:
bool isLeaf;
std::unordered_map<char, Node*> childMap;
std::string value;
Node() {
isLeaf = false;
value = "";
}
void insertUrl(std::string toInsert, std::string value) {
int len = toInsert.length();
if (len == 0 ) {
this->isLeaf = true;
return;
}
char firstChar = toInsert[0];
if (childMap[firstChar] == NULL) {
Node* child = new Node();
child->value = value + firstChar;
childMap[firstChar] = child;
}
Node* child = childMap[firstChar];
child->insertUrl(toInsert.substr(1, len-1), value + firstChar);
}
void findMatch(std::string toFind, std::list<std::string>& matchedString){
if (this->isLeaf) {
matchedString.push_back(this->value);
}
int len = toFind.length();
// empty string all children are eligible
if (len == 0) {
for (std::unordered_map<char, Node*>::iterator it = childMap.begin();
it != childMap.end(); it++) {
Node* node = it->second;
node->findMatch(toFind, matchedString);
}
return;
}
if (childMap[toFind[0]] != NULL) {
Node* node = childMap[toFind[0]];
node->findMatch(toFind.substr(1, len-1), matchedString);
}
}
};
int main() {
Node* root = new Node();
root->insertUrl("team.com", "");
root->insertUrl("tea.in", "");
root->insertUrl("teamwork.org", "");
root->insertUrl("teams.com", "");
root->insertUrl("pot.uk", "");
root->insertUrl("potter.in", "");
root->insertUrl("post.com", "");
std::list<std::string> myList;
root->findMatch("te", myList);
for (list<std::string>::iterator it = myList.begin(); it != myList.end(); it++) {
cout << *it << endl;
}
return 0;
}
Just tried with {11, 5} and your code is returning 11. I think you need to modify the recursion termination condition (m==0 doesn't return the correct result in this case).
- pavelkushtia February 01, 2015Your logic has a worst case O(n^2) complexity. For example if the list contains all odd numbers. Also, have you tested the implementation? inserting the left and right as neighbors doesn't seems right to me.
- pavelkushtia February 01, 2015Can you explain your code? how does it solve the problem? what is your return value? It doesn't clear to me exactly what are you trying to achieve here.
- pavelkushtia February 01, 2015This is really easy and nice approach with small flaw in it. Better to keep the granularity to 2 while dividing, the merging works perfect. Here is the updated code:
public class HelloWorld {
public static void main(String[] args) {
int[] array = {7, 8, 2, 3, 4, 5 };
System.out.println(getMaxQAZ(array));
}
public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length-1).qaz;
}
private static QAZResult getMaxQAZ(int[] array, int start, int end) {
if (end <= start) {
return new QAZResult(array[end], 0);
}
if (end == start+1) {
if (array[start] < array[end]) {
return new QAZResult(array[start], 1);
}
return new QAZResult(array[end], 0);
}
int middle = (end + start) / 2;
QAZResult leftResult = getMaxQAZ(array, start, middle);
QAZResult rightResult = getMaxQAZ(array, middle+1, end);
if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}
for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}
return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
}
}
class QAZResult {
int minVal;
int qaz;
public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}
None of the tree solution can guarantee an O(nlogn) in worst case.
- pavelkushtia February 01, 2015You can check my explanation and the O(1) space solution below.
- pavelkushtia January 21, 2015Shouldn't it be 6, how it is 7?
- pavelkushtia January 16, 2015Solution with Fibonacci Terms:
Sequences for continuous two digit matching numbers can be broken down as Fibonacci term, and the final result is the multiplication of each such terms.
Example:
11 -> 2 F(3)
111 -> 3 F(4)
1111 -> 5 F(5)
11111 -> 8 F(6)
.....
......
n consecutive -> F(n-1)
so, 110511 -> F(4)*F(3) = 3*2 = 6
Here are the 6 variations:
BBAFBB
LAFBB
BKFBB
BBAFL
LAFL
BKFL
Here is the O(n) time and O(1) space solution
int getVariation(char* array)
{
int retVal = 1;
int len = strlen(array);
int prevSum=1, currSum=1;
for (int i=0; i< len; i++)
{
int twoDigitNum = -1;
if( i>0 && array[i-1] > '0')
{
twoDigitNum = (array[i-1]-'0')*10 + array[i] - '0';
}
if (twoDigitNum >=10 && twoDigitNum <=25)
{
int tmp = currSum;
currSum += prevSum;
prevSum = tmp;
}
else
{
retVal *= currSum;
currSum = 1;
prevSum = 1;
}
}
retVal *= currSum;
return retVal;
}
When the array is sorted then we can find a solution in O(logN) time. Here is the C++ solution:
- pavelkushtia June 20, 2015