h*******0 发帖数: 270 | 1 一个小公司的面试题
第一题就是让写一个stack machine。 就是计算一个类似于“13*6+”这样的string。
读到数就把数字push到stack里面。 如果读到operator, 就pop出来2个数字。 然后计
算,再把计算结果push到stack。 重复直到计算出最终结果。
第二题找array的magnitude pole. 就是找一个点,所有左边的数字均小于等于它,所
有右边的数字都大于等于它。要求O(n)。
第一题,我写的code,大数据的case时候很慢。大家看看有什么能提高的?
int calculator(int op1, int op2, const char opt){
if(opt == '+'){
return op1+op2;
}else if(opt == '/'){
if(op2 == 0) return -1;
return op1/op2;
}else if(opt == '*'){
return op1*op2;
}else if(opt == '-'){
return op1-op2;
}
}
int checkoverflow(int num){
int mask = 0x11111000;
if((num&mask )== 0){
return 0;
}else{
return 1;
}
}
int stack_machine_emulator ( const string &S ) {
stack machine;
int i =0;
int operand1;
int operand2;
while(i
if(S[i]>='0'&&S[i]<'9'){
string temp = "1";
temp[0] = S[i];
machine.push(temp);
}else{
if(!machine.empty())
{
operand1 = atoi((machine.top()).c_str());
machine.pop();
}else{
cerr<<"error input"<
return -1;
}
if(!machine.empty()){
operand2 = atoi((machine.top()).c_str());
machine.pop();
}else{
cerr<<"error input"<
return -1;
}
int tempresult = calculator(operand1, operand2, S[i]);
cout<
if(tempresult==-1){
cerr<<"underflow happened"<
return -1;
}
if(checkoverflow(tempresult)){
cerr<<"overflow happened"<
return -1;
}
std::string s;
std::stringstream out;
out << tempresult;
s = out.str();
machine.push(s);
}
i++;
}
return atoi((machine.top()).c_str());
}
第二题, 大家有什么好的方法没? 我自己想到一个,但是不知道对不对。 就是设两
个pointer从头和尾开始,头pointer找到第一个大于等于它的点停下,尾pointer找到
第一个小于等于它的点停下。 然后头和尾比较大小:如果头小于尾,尾继续往前走找
第一个小于它的点。 如果start和end的index相同,那么这个index就是magnitude
pole。 |
l****i 发帖数: 2772 | 2 第2题,不在乎空间的话,可以创建2个boolean array。一个是比所有左边大的位置。
另一个是比所有右边小的位置。最后同时走一遍2个boolean array,都是true的位置就
是结果。 |
f*******t 发帖数: 7549 | 3 第二题:
int magnitutePole(int[] array) {
if(array == null || array.length == 0)
return -1;
int[] status = new int[array.length];
int smaller = Integer.MIN_VALUE, larger = Integer.MAX_VALUE;
for(int i = 0; i < array.length; i++) {
if (array[i] >= smaller) {
smaller = array[i];
status[i]++;
}
}
for(int i = array.length - 1; i >= 0; i--) {
if(array[i] <= larger) {
larger = array[i];
if(status[i] > 0)
return i;
}
}
return -1;
} |
h*******0 发帖数: 270 | 4 能详细说说如何创建这两个boolean array吗?怎么感觉创建这2个array的时间复杂度
是(n^2)呢?
【在 l****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第2题,不在乎空间的话,可以创建2个boolean array。一个是比所有左边大的位置。 : 另一个是比所有右边小的位置。最后同时走一遍2个boolean array,都是true的位置就 : 是结果。
|
l****i 发帖数: 2772 | 5 楼上那位大牛给了答案了,基本思路是一样的。一个辅助array也够了。从左向右扫一
遍,找到所有比左边都大的index。再从右向左扫一遍,如果比右边都小,而且这个
index是第一轮扫到的index,就是结果。
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能详细说说如何创建这两个boolean array吗?怎么感觉创建这2个array的时间复杂度 : 是(n^2)呢?
|
d**********x 发帖数: 4083 | 6 要记录到当前的最大值,不要只记录bool
置。
置就
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能详细说说如何创建这两个boolean array吗?怎么感觉创建这2个array的时间复杂度 : 是(n^2)呢?
|
p****e 发帖数: 3548 | 7 the initial values of smaller and larger should be switched?
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题: : int magnitutePole(int[] array) { : if(array == null || array.length == 0) : return -1; : int[] status = new int[array.length]; : int smaller = Integer.MIN_VALUE, larger = Integer.MAX_VALUE; : for(int i = 0; i < array.length; i++) { : if (array[i] >= smaller) { : smaller = array[i]; : status[i]++;
|
M********5 发帖数: 715 | 8 我觉得第一题的代码有问题,像你举的例子,13*6这样的,13就是两个字母,所以你
push的时候应该push 13而不是push 1再push 3;另外一点,如果你support + - * /的
话(如果没有括号),那么就应该先算整个表达式里面的* /把结果推入number stack
里面,然后第二次再把number stack和operator stack按照你说的pop一个operator,
pop两个number做计算;如果support括号的话,那就更麻烦了,得先算所有括号里面的
内容,再算括号外面的内容。。。
btw,用string表达expression是一个很麻烦和expensive的方法。。。
。
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个小公司的面试题 : 第一题就是让写一个stack machine。 就是计算一个类似于“13*6+”这样的string。 : 读到数就把数字push到stack里面。 如果读到operator, 就pop出来2个数字。 然后计 : 算,再把计算结果push到stack。 重复直到计算出最终结果。 : 第二题找array的magnitude pole. 就是找一个点,所有左边的数字均小于等于它,所 : 有右边的数字都大于等于它。要求O(n)。 : 第一题,我写的code,大数据的case时候很慢。大家看看有什么能提高的? : int calculator(int op1, int op2, const char opt){ : if(opt == '+'){ : return op1+op2;
|
l*********8 发帖数: 4642 | 9 第二题,从左向右找max, 从右向左找min.
。
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个小公司的面试题 : 第一题就是让写一个stack machine。 就是计算一个类似于“13*6+”这样的string。 : 读到数就把数字push到stack里面。 如果读到operator, 就pop出来2个数字。 然后计 : 算,再把计算结果push到stack。 重复直到计算出最终结果。 : 第二题找array的magnitude pole. 就是找一个点,所有左边的数字均小于等于它,所 : 有右边的数字都大于等于它。要求O(n)。 : 第一题,我写的code,大数据的case时候很慢。大家看看有什么能提高的? : int calculator(int op1, int op2, const char opt){ : if(opt == '+'){ : return op1+op2;
|
f*******t 发帖数: 7549 | 10 yes, fixed
【在 p****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : the initial values of smaller and larger should be switched?
|
|
|
h*******0 发帖数: 270 | 11 忘了说条件了。。 string里面的数字只含有0-9, 所以你就push 1和3就行
stack
【在 M********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得第一题的代码有问题,像你举的例子,13*6这样的,13就是两个字母,所以你 : push的时候应该push 13而不是push 1再push 3;另外一点,如果你support + - * /的 : 话(如果没有括号),那么就应该先算整个表达式里面的* /把结果推入number stack : 里面,然后第二次再把number stack和operator stack按照你说的pop一个operator, : pop两个number做计算;如果support括号的话,那就更麻烦了,得先算所有括号里面的 : 内容,再算括号外面的内容。。。 : btw,用string表达expression是一个很麻烦和expensive的方法。。。 : : 。
|
h*******0 发帖数: 270 | 12 大牛! 非常感谢帖code!
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题: : int magnitutePole(int[] array) { : if(array == null || array.length == 0) : return -1; : int[] status = new int[array.length]; : int smaller = Integer.MIN_VALUE, larger = Integer.MAX_VALUE; : for(int i = 0; i < array.length; i++) { : if (array[i] >= smaller) { : smaller = array[i]; : status[i]++;
|
w****a 发帖数: 710 | 13 第二题我觉得同时扫应该也可以吧。O(n)的space |
l***i 发帖数: 1309 | 14 problem 2:
for each a[i], find max value among a[0..i-1] and min value among a[i+1..n-1
]. This can be done by a left to right scan and a right to left scan.
Then a[i] is pole iff max[i] <= a[i] <= min[i]
max[0] = -inf; v = a[0];
for (int i=1; i
max[i] = v;
if (a[i] > v) v = a[i];
}
min[n-1] = inf; v = a[n-1];
for (int i=n-2; i>=0; --i) {
min[i] = v;
if (a[i] < v) v = a[i];
}
for (int i=0; i
if (max[i] <= a[i] && a[i] <= min[i])
return i;
}
return -1; // no pole, for example a[] = {2, 1} |
M********5 发帖数: 715 | 15 你的意思是只可能出现6*9,不可能出现19*16这种情况吗?
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 忘了说条件了。。 string里面的数字只含有0-9, 所以你就push 1和3就行 : : stack
|
p*****p 发帖数: 379 | 16 第一个题其实可以把string parse以后转成int,stack里就存int就行,不然你每次拿
出来算完还得构造string放回去比较浪费时间,不过要是题目要求那样就只能你那样弄了
。
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个小公司的面试题 : 第一题就是让写一个stack machine。 就是计算一个类似于“13*6+”这样的string。 : 读到数就把数字push到stack里面。 如果读到operator, 就pop出来2个数字。 然后计 : 算,再把计算结果push到stack。 重复直到计算出最终结果。 : 第二题找array的magnitude pole. 就是找一个点,所有左边的数字均小于等于它,所 : 有右边的数字都大于等于它。要求O(n)。 : 第一题,我写的code,大数据的case时候很慢。大家看看有什么能提高的? : int calculator(int op1, int op2, const char opt){ : if(opt == '+'){ : return op1+op2;
|
s****n 发帖数: 48 | 17 第二题写了个javascript的。不用编译可以直接Chrome/FF/IE js console里跑就好了。
思路是:先假定第一个元素就是pole,然后从位置1开始往后扫描。
如果后面的值都大于它,那正好,它就是了。
如果后面有值小于它,说明迄今为止的值都不可能为pole,下一个可能的pole是第一个
比迄今为止最大值还大(或相等)的值。
偷懒了一下假定原数组值都是正的。
function partition(a) {
if (!a || a.length == 0) return -1; // -1 means impossible, assume the
orignal array only contains positive values.
var possible = a[0];
var max = a[0];
for(var i = 1; i < a.length; i++){
if (possible >= 0) {
if (a[i] >= possible) {
max = a[i];
} else {
possible = -1;
}
} else {
if (a[i] >= max) {
possible = a[i];
max = a[i];
}
}
}
return possible;
}
// test cases
console.log(partition([])); // -1
console.log(partition([1])); // 1
console.log(partition([1,2,3])); // 1
console.log(partition([2,1,3])); // 3
console.log(partition([3,2,1])); // -1
console.log(partition([6,10,7,9,19,33])); // 6
console.log(partition([6,10,5,7,9,19,33,20])); // 19 |
f*******t 发帖数: 7549 | 18 找出了一年多前写的逆波兰处理算数表达式的代码,强烈建议有兴趣的自己实现一下:
#include
#include
#include
#include
#define BUFFSIZE 1024
using namespace std;
struct Token {
bool isNum;
int num;
char op;
Token();
Token(const Token& t);
};
Token::Token()
{
isNum = false;
num = 0;
op = 0;
}
Token::Token(const Token& t)
{
isNum = t.isNum;
num = t.num;
op = t.op;
}
Token *getToken(const char expr[], int& idx)
{
Token *res = NULL;
while(expr[idx] == ' ')
idx++;
if(expr[idx] == '-' || expr[idx] == '+' || expr[idx] == '*' || expr[idx]
== '/'
|| expr[idx] == '(' || expr[idx] == ')') {
res = new Token;
res->isNum = false;
res->op = expr[idx];
idx++;
}
else if(expr[idx] >= '0' && expr[idx] <= '9') {
res = new Token;
res->isNum = true;
res->num = 0;
while(expr[idx] >= '0' && expr[idx] <= '9') {
res->num *= 10;
res->num += (int)(expr[idx] - '0');
idx++;
}
}
return res;
}
bool getPosixExpr(const char expr[], char result[])
{
stack operators;
queue > output;
int idx = 0;
Token *cur = NULL;
while((cur = getToken(expr, idx)) != NULL) {
if(cur->isNum) {
cout << "number " << cur->num << endl;
output.push(*cur);
delete cur;
}
else {
cout << "operator " << cur->op << endl;
if(cur->op == '(' || cur->op == '+' || cur->op == '-') {
operators.push(*cur);
}
else if(cur->op == ')') {
while(!operators.empty()) {
Token t = operators.top();
operators.pop();
if(t.op == '(')
break;
output.push(t);
}
}
else {
if(operators.empty() ||
(operators.top().op != '+' && operators.top().op != '-'))
operators.push(*cur);
else {
if(operators.top().op == '*' || operators.top().op == '/
') {
output.push(operators.top());
operators.pop();
operators.push(*cur);
}
else
operators.push(*cur);
}
}
delete cur;
}
}
while(!operators.empty()) {
output.push(operators.top());
operators.pop();
}
int resIdx = 0;
while(!output.empty()) {
Token t = output.front();
output.pop();
if(t.isNum) {
resIdx += sprintf(&result[resIdx], "%d", t.num);
}
else {
result[resIdx] = t.op;
resIdx++;
}
result[resIdx] = ' ';
resIdx++;
}
result[resIdx] = 0;
return true;
}
int calculate(const char revpol[])
{
int ans = 0;
stack nums;
Token *cur = NULL;
int idx = 0;
while((cur = getToken(revpol, idx)) != NULL) {
if(cur->isNum)
nums.push(*cur);
else {
if(nums.size() < 2) {
cout << "Invalid expression" << endl;
break;
}
Token num1 = nums.top();
nums.pop();
Token num2 = nums.top();
nums.pop();
cout << num1.num << " " << cur->op << " " << num2.num << " = ";
switch(cur->op) {
case '+':
num1.num += num2.num;
break;
case '-':
num1.num -= num2.num;
break;
case '*':
num1.num *= num2.num;
break;
case '/':
num1.num /= num2.num;
break;
default:
cout << "Unsupported operand " << cur->op << endl;
break;
}
cout << num1.num << endl;
nums.push(num1);
}
}
if(nums.size() != 1)
cout << "Invalid expression!" << endl;
return nums.top().num;
}
int main()
{
const char expr[] = "3 +2 *5 / (2 + 1)";
char buff[BUFFSIZE];
if(getPosixExpr(expr, buff))
cout << buff << endl;
else
cout << "The expression is invalid" << endl;
int ans = calculate(buff);
cout << "Final value is " << ans << endl;
return 0;
}
|
l*********u 发帖数: 19053 | 19 第二题,用binary search应该更快吧。
对折array。取array中间,向左移pointer,过掉等值,找到小值,pole在右半段,找到
大值,pole在左半段。再取array中间。。。
。
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个小公司的面试题 : 第一题就是让写一个stack machine。 就是计算一个类似于“13*6+”这样的string。 : 读到数就把数字push到stack里面。 如果读到operator, 就pop出来2个数字。 然后计 : 算,再把计算结果push到stack。 重复直到计算出最终结果。 : 第二题找array的magnitude pole. 就是找一个点,所有左边的数字均小于等于它,所 : 有右边的数字都大于等于它。要求O(n)。 : 第一题,我写的code,大数据的case时候很慢。大家看看有什么能提高的? : int calculator(int op1, int op2, const char opt){ : if(opt == '+'){ : return op1+op2;
|