Round1
Q1: Sort an array of Strings based on ASCENDING Order of the length of element.
Input: [“ABCDE”, “ABCD”, “Z”, “A”, “AB”, “AA”, “ABC”]
Output: [“A”, “Z”, “AA”, “AB”, “ABC”, “ABCD”, “ABCDE”]
#include <bits/stdc++.h>
using namespace std;
bool comp(const string &a, const string &b) {
if (a.length() != b.length()) return a.length() < b.length();
int N = a.length();
int M = b.length();
int i = 0, j = 0;
while(i < N && j < M) {
if (a[i] == b[j]) {
++i;
++j;
} else {
return a[i] < b[j];
}
}
return true;
}
class Solution {
public:
static vector<string> sortStringArray(vector<string> &arr) {
sort(arr.begin(), arr.end(), comp);
return arr;
}
void print(vector<string> &arr) {
for (auto x: arr) {
cout << x << " ";
}
cout << endl;
}
};
int main() {
Solution solution;
vector<string> vec;
vec.push_back("ABCDE");
vec.push_back("ABCD");
vec.push_back("Z");
vec.push_back("A");
vec.push_back("AB");
vec.push_back("AA");
vec.push_back("ABC");
cout << "Input array: ";
solution.print(vec);
vec = solution.sortStringArray(vec);
cout << "output array: ";
solution.print(vec);
cout << endl;
return 0;
}Q2: Write a function that takes a sentence and reverse only alphanumeric word but other characters remain unchanged.
For Example -
-
**Input:**This is test!!!
Output: sihT si tset!!! -
Input: Hello, Bangkok:)
Output: olleH, kokgnaB:) -
Input: Hurray! Easy Questions
Output: yarruH! ysaE snoitseuQ -
Input: Bangkok12:)Has
Output: 21kokgnaB:)saH -
Input: Bangkok
Output: kokgnaB
#include <bits/stdc++.h>
using namespace std;
class ReverseTheString {
public:
string reversedString;
//This would return true when the character is part of the set which we can reverse
bool isAllowedChar(char ch) {
if (ch >= 'a' && ch <= 'z') return true;
if (ch >= 'A' && ch <= 'Z') return true;
if (ch >= '0' && ch <= '9') return true;
return false;
}
string reverseString(string &s) {
string result = "";
for (int i = s.length() - 1; i >= 0; --i) {
result += s[i];
}
return result;
}
void addChar(char ch) {
reversedString = ch + reversedString;
}
string getStringFromStack() {
return reversedString;
}
void resetReversedString() {
reversedString = "";
}
string reverse(string &s) {
string tmp = "", result = "";
for (int i = 0; i < s.length(); ++i) {
bool isAllowed = isAllowedChar(s[i]);
if (isAllowed) {
addChar(s[i]);
} else {
result += getStringFromStack();
result += s[i];
resetReversedString();
}
}
if (getStringFromStack().size() > 0) {
result += getStringFromStack();
resetReversedString();
}
return result;
}
bool test(vector<string> &input, vector<string> &output) {
bool isAllTestsPassed = true;
for (int i = 0; i < input.size(); ++i) {
string result = reverse(input[i]);
if ( result != output[i]) {
cout << "Given Input: " << input[i] << "\nExpected Output: " << output[i] << "\nReceived Output: " << result << endl;
isAllTestsPassed = false;
}
}
return isAllTestsPassed;
}
};
int main() {
ReverseTheString reverseTheString;
vector<string> input{"This is test!!!", "Hello, Bangkok:)", "Hurray! Easy Questions", "Bangkok12:)Has", "Bangkok"};
vector<string> output({"sihT si tset!!!", "olleH, kokgnaB:)", "yarruH! ysaE snoitseuQ", "21kokgnaB:)saH", "kokgnaB"});
if (reverseTheString.test(input, output)) {
cout << "All tests passed\n";
} else {
cout << "some of the tests failed\n";
}
return 0;
}They were kind of focusing on the optimized code And the Test Driven classes.
Round 2:
Q1: Evaluate the given expression.
Input: 31+/3-5/6
Output: 1
I disscussed that we can transform the given string into the postfix expression first and then do the evaluation of the expression. He was more interested in evaluating the result while traversal, without converting the string to any other form.
We discussed the approach and then He gave me 10 minutes to code.
#include <bits/stdc++.h>
#include <features.h>
// 31+/3-5/6
// curr +=1
using namespace std;
class Solution{
public:
int evaluate(string &s) {
int curr = 0;
int acc = 0;
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= '0' || - && s[i] <= '9') {
curr = 10 * curr + s[i] - '0';
} else if (s[i] == '+' || s[i] == '-') {
//here current is previously parsed value
if (s[i] == '+') {
acc = acc + curr;
} else {
acc = acc - curr;
}
curr = 0;
} else if (s[i] == '/' || s[i] == '*') {
int nextNumber = 0;
char ch = s[i];
++i;
int p = i;
while(p < s.length() && s[p] >= '0' && s[p] <= '9') {
nextNumber = nextNumber * 10 + (s[p] - '0');
++p;
}
if (ch == '/') {
curr = curr/nextNumber;
} else {
curr = curr*nextNumber;
}
i = p - 1;
}
}
return (curr + acc);
}
};
int main( ) {
Solution solution;
string expr = "1+3/3+5/6";
int eval = solution.evaluate(expr);
cout << "Evaluated value = " << eval << endl;
return 0;
}Note: Above code has some flaws, basically it was not working for the cases where the negative operator was present in the string. But he seemed fine since we discussed the approach to resolve this bug as well.