C***U
发帖数: 2406 | 1 #include
#include
#include
#define MAX 10000
int main(int argc, char *argv[]){
std::vector numbers1;
std::vector numbers2;
int k = atoi(argv[3]);
if(argc < 4)
std::cout << "we need 2 files and a number." << std::endl;
std::cout << "we need find " << k << "th number" << std::endl;
std::cout << "reading first array of numbers ..." << std::endl;
std::ifstream f1(argv[1]);
if(!f1){
std::cout << "cannot open... 阅读全帖 |
|
|
w****x
发帖数: 2483 | 3 OVERFLOW的处理相当麻烦, 特别还要注意INT_MIN, INT_MAX的情况, 贴一个我修改了n
遍的代码:
int myatoi(const char* p)
{
assert(p);
//Judge signal
bool bNeg = false;
const char* pCur = p;
if(*pCur == '-' || *pCur == '+')
{
if (*pCur++ == '-')
bNeg = true;
}
//treat the rest as positive numeric number, so for negative number
//it is 2^31, and for positive number it is 2^31
unsigned int uLimit = bNeg ? 0x7FFFFFFF + 1 : 0x7FFFFFFF;
// The reson to use unsigned int rat... 阅读全帖 |
|
|
b******t
发帖数: 965 | 5 其实大家都太挑战自我
要我来implement 内部用long long 然后越界的话转成 INT_MIN INT_MAX
简单很多
n |
|
i**********e
发帖数: 1145 | 6 F:
3Sum
Add Binary
Combination Sum
Count and Say
Divide Two Integers
Edit Distance
Implement strStr()
Letter Combinations of a Phone Number
Longest Palindromic Substring
Merge Intervals
Multiply Strings
Next Permutation
Permutations, Permutations II
Regular Expression Matching
Remove Duplicates
Remove Element
Search in Rotated Sorted Array
String to Integer (atoi)
Sqrt(x)
Substring with Concatenation of All Words
Trapping Rain Water
Unique Paths, Unique Paths II
G:
3Sum
Climbing Stairs
Container... 阅读全帖 |
|
L***Q
发帖数: 508 | 7 你如果是计算两个整数除法，function的参数是int，返回值也是int，内部就用一个更
大，能确保不溢出的变量。leetcode上面atoi的题就是如此，返回值是int，那么就用
long long来计算，返回前判断long long的值是不是已经超过int的范围。 |
|
L***Q
发帖数: 508 | 8 你如果是计算两个整数除法，function的参数是int，返回值也是int，内部就用一个更
大，能确保不溢出的变量。leetcode上面atoi的题就是如此，返回值是int，那么就用
long long来计算，返回前判断long long的值是不是已经超过int的范围。 |
|
w****x
发帖数: 2483 | 9 自己想的解法, 一般不能通过现在的number > 之前的number来判断.
, 如果用int统一处理的话可能不能处理INT_MIN的情况, 因为负数范围比正数大一个.
用unsigned int来处理也不能通过判断现在的比值前的数大来决定是否溢出, 并且
unsigned int自己可能溢出.
溢出判断分两阶段, 一个是在增加新digit前作溢出判断, 这个是判断unsigned int自
己不溢出.
if (uRes > UINT_MAX/10 || (uRes == UINT_MAX/10 && nDigit > (UINT_MAX - (UINT
_MAX/10)*10)))
throw CException("Over flow detected");
在unsigned int自己不溢出的情况下判断是否转换成int后会溢出
//update uRes
uRes = uRes*10 + nDigit;
//uLimit = bNeg ? 0x7FFFFFFF + 1 : 0x7FFFFFFF;
//Overflow situation if uRes... 阅读全帖 |
|
h****e
发帖数: 928 | 10 我的做法是用long long作为中间变量，当溢出int能存放的
最大/小值以后，就提前退出返回。
还有一种办法是溢出以后符号会改变，用那个来判断。 |
|
|
|
c****p
发帖数: 6474 | 13 严格来说会变号
一般情况下是的。。。
唯一比较麻烦的是-2^31，搞成正的话会溢出，但是那个数本身不溢出。 |
|
|
w****x
发帖数: 2483 | 15 不一定会变符号 要是溢出的过头的话. 还有得考虑负数和正数范围不同的问题 |
|
|
n**e
发帖数: 116 | 17 I posted my implementation before. Here is my handling with overflow issue.
//----------------------------------------------------------------
// Compute the cutoff value between legal numbers and illegal
// numbers. That is the largest legal value, divided by the
// base. An input number that is greater than this value, if
// followed by a legal input character, is too big. One that
// is equal to this value may be valid or not; the limit
// between valid and invalid numbers is... 阅读全帖 |
|
U*********y
发帖数: 54 | 18 //如果不爱分享, 至少懂得回报
1.一个整数数组a[], 每个元素的值代表能向前跳1到a[i]格,问最少跳几步刚好到达数
组的末端, 超出数组的index或到不了末端算失败
2.排好序的连续数组只缺一个数,二叉搜索找出来
3.Boggle游戏, 返回牌面上所有有效单词
4.按顺时针打印二叉树边缘, 解法见leetcode
5.zigzag打印二叉树, 解法见leetcode
6.电话号码的regular expression
7.二叉搜索树找相等或最相近某值的节点
8.singleton的多线程
9.股票最佳买入和卖出点
10.Kth分割 (快排序的分割步骤)
11.网络用户的网速慢,如何设计浏览器加速网页的浏览速度
12.浏览器输入URL,发生了什么
13.给电话号码, 打印所有可能字符串
14.写API, 允许用户注册一个程序到ID, 注销一个程序, 运行一个ID下所有的程序
15.找质数
16.atoi
17.讲电话本的trie设计,对比哈希表
3家的电/店的题目放在了一起,大部分都算常见题.
经验总结: 面试的不定因素太多,感觉就像抽奖. 所以不要放弃,感觉准备好了的话(以上... 阅读全帖 |
|
j********e
发帖数: 1192 | 19 写了个使用O(1)memory, O(logN * logN) (N是tree的size)的程序。
类似于binary search的算法，测试代码也在下面，应该没有大bug。
先获得树的高度h，然后比较h和root->right子树的高度+1,如果相同，
说明树最后一个节点在root->right，否则最后一个节点在root->left的子树。
#include
#include
#include
#include
using namespace std;
class Node {
private:
Node *left;
Node *right;
int value;
public:
Node() {
left = right = NULL;
value = 0;
}
Node(int v) {
left = right = NULL;
value = v;
}
int Height(Node *node) {
int h... 阅读全帖
|
|
d****o
发帖数: 1055 | 20 Time average O(lgn) worst O(n)
int findSubInt(string in,int mid,int& subBegin,int& subEnd){
subBegin=mid;
subEnd=mid;
while(in[subBegin]!=' '){
subBegin--;
}
if(in[subBegin]==' ') subBegin++;
while(in[subEnd]!=' '){
subEnd++;
}
if(in[subEnd]==' ') subEnd--;
string subStr = in.substr(subBegin,subEnd-subBegin+1);
return atoi(subStr.c_str());
}
bool findInt(string in, int target){
int begin =0;
int end... 阅读全帖 |
|
p*********7
发帖数: 40 | 21 如果用long去存储最终结果res的话，32位机，long和int的值一样啊。
int myATOI(const char* p){
int flag=1;
if((*p)=='-') {
flag=-1;
p++;
}
long res=0;
while(*p){
res=res*10+(*p)-'0';
if(res>INT_MAX) cout<<"overflow";
p++;
}
return res*flag;
}
请问这个代码怎么改才能支持overflow比较好？ |
|
|
n****n
发帖数: 117 | 23 返回个0算了
The strtol(), strtoll(), strtoimax(), and strtoq() functions return the
result of the conversion, unless the value would underflow or overflow.
If no conversion could be performed, 0 is returned and the global vari-
able errno is set to EINVAL (the last feature is not portable across
all
platforms). If an overflow or underflow occurs, errno is set to ERANGE
and the function return value is clamped according to the following ta-
ble. |
|
p*****2
发帖数: 21240 | 24
long在java里是64位的。你可以改成 if(res< new res) |
|
h****e
发帖数: 928 | 25 C/C++用long long会简化很多。只用int也可以解，但是非常繁琐，因为
你要和-(2^31)/10、(2^31-1)/10之类的边界值做比较。面试的时候除非
被要求用int，不然还是选择long long好。 |
|
w****x
发帖数: 2483 | 26 我使用unsigned int处理INT_MIN绝对值比INT_MAX大的情况,
对于overflow, 我分两步, 一是判断unsigned int有没有overflow,
一个是判断unsigned int没有overflow的情况下int有没有overflow
class CException
{
public:
CException(const char* str) : m_strErr(str) {}
string GetErrInfo() { return m_strErr; }
private:
std::string m_strErr;
};
int myatoi(const char* p)
{
assert(p);
//Judge signal
bool bNeg = false;
const char* pCur = p;
if(*pCur == '-' || *pCur == '+')
{
if (*pCur++ == '-')
bNeg = true... 阅读全帖 |
|
w****x
发帖数: 2483 | 27 long long 处理overflow
int myatoi(const char* p)
{
assert(p);
//Judge signal
bool bNeg = false;
const char* pCur = p;
if(*pCur == '-' || *pCur == '+')
{
if (*pCur++ == '-')
bNeg = true;
}
long long dummy = INT_MIN;
//can't directly use -(INT_MIN) because of precompile treat -(INT_MIN)
//as 32 bit integer which will cause overflow
long long limit = bNeg ? -(dummy) : INT_MAX;
long long res = 0;
do
{
//Deals with ille... 阅读全帖 |
|
t**********h
发帖数: 2273 | 28 北京，java里搞这题，long了后，还要考虑溢出么？那得多大的数阿，
long在java里是64位的。你可以改成 if(res
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
r*****e
发帖数: 792 | 29 一个小建议，*10的时候改成 n<<3+n<<1
另，刚注意到你的注释，对你这种自我批评的精神致敬。
我自己的注释会比较含蓄，以鼓励和表扬为主，呵呵 |
|
l*********8
发帖数: 4642 | 30 that's because it's faster or it's easier to handle overflow? |
|
r*****e
发帖数: 792 | 31 faster and it's a common practice |
|
|
p*****2
发帖数: 21240 | 33
long溢出也不是不可能的。但是这题应该跟面试官交流好。问用long解决overflow行不
行。比赛的时候有时候long也会溢出。 |
|
S******2
发帖数: 7 | 34 刚面试完embedded software engineer，贡献一个面经，顺便求祝福，local small
company, 不过是my Dream Company
1. Why declare/define volatile variables
2. reverse a linked list.
3. socket/Tcp/ip APIs: difference between sendto and send functions.
4. implement the atoi function.
5. bootloader and bootstraper, differences?
6. the first user process spawned in an embedded linux? and its functions?
7. Mutex and Semaphore, differences? how to use them to avoid race
conditions?
本地公司，面了大约2个小时，大概就些，还有一些linked list， BSTcoding什么
的... 阅读全帖 |
|
g*****g
发帖数: 34805 | 35 牛啥呀，两个电面，atoi一堆小错，比较anagram这种题我都没做出来，人
还是让我周一去onsite了，所以着急。 |
|
g*****g
发帖数: 34805 | 36 公司最近一年不太好，想换个工作。正好N家的recruiter来骚扰，
就答应发简历过去。N很快，过了两天就找了个组来电面。
我啥都没准备，感觉很糟糕。问了个放水的atoi，结果
网上写，出了一堆的bug，我后来放进eclipse，自己都觉得
脸红。光compiler error就有5，6处。
本以为肯定挂了，谁知recruiter说反应还不错，但是那个position
filled了，给我换个组。于是换个组重新电面，这次不敢怠慢，
一个周末学习了一下cc150，看了一点精华区，至少还有10道题
不会做，也就那样了，来不及。
电面主要探讨了一下java concurrency和NoSQL，我吹嘘了一下
high scalability，high availablity的一些经验。问了个boggle
的算法，和高用户数得分的排序如何设计。前者整得我又是一头汗，
虽然我知道用trie，一些优化的搜索算法不是很熟悉，对方也没为难
我。高在线用户这些我就比较熟悉，回答得还好。
onsite面了5个人，2个engineer，1个recruiter，2个engineer manager。
前面两个要... 阅读全帖 |
|
W******g
发帖数: 887 | 37 不，不，我说的不是这种字符串处理,你说的这种属于算法
我说的是实现atoi()这样的字符串处理! |
|
|
n*****g
发帖数: 178 | 39 本帖内容来自于：
发信人: segin (segin), 信区: JobHunting
标 题: 明天ONSITE攒人品,发面试知识点总结!!
发信站: BBS 未名空间站 (Thu Feb 4 13:40:29 2010, 美东)
http://www.mitbbs.com/bbsann2/life.faq/JobHunting/17/D128425435
非常好的总结啊！！！！攒人品再转发一次。
C: pointer, call by value/pointer, return the pointer of a local variable,
string manipulations, source code of some important C string subroutines
(strcpy, strtok, etc), itoa, atoi, static variable and fuction, name
mangling,
memory allocation
http://www.eskimo.com/~scs/C-faq/faq.html
C++: name... 阅读全帖 |
|
w****x
发帖数: 2483 | 40 做了两道做过不下5遍的题, 大体逻辑都记得很清楚, 做起来都像默写一下, 最后每道
题还是发现了两个bug, 还是检查了一遍以后的, 这玩艺真是防不胜防啊~~~, 过几天
OnSite估计要悲剧了...
一个是biggest rectangle in histogram, 一个是handle异常的atoi, 大家可以试试. |
|
n*******e
发帖数: 612 | 41 c++ 用strtok在atoi吧
或者sscanf循环 |
|
d*****o
发帖数: 310 | 42 会不会是char，然后用atoi类似的转换排序？ |
|
f********4
发帖数: 988 | 43
这。。。校园面的时候问了道超简单的题。。就是atoi。我还到处都是bug，我也不知
道是为什么，可能对fresh grad的标准比较低 |
|
|
O******i
发帖数: 269 | 45 atoi写的完美可真不容易。自由度也高，比如出错处理是抛出异常还是返回全局的
error code? |
|
l***i
发帖数: 1309 | 46 被人问过atoi，还不止一次，然后怎么处理integer overflow，板上大牛给指点一下贝 |
|
y****n
发帖数: 743 | 47 我对C/C++很初级，关于这个atoi请教大牛们一个问题：
不理解为什么要调用strchr？平均5次循环，10byte的常量空间？
...
static const char digits[] = "0123456789";
...
where = strchr(digits, *s);
...
digit = (where - digits);
...
如果我写成这样，有什么问题没有？
if ((*s >= '0') && (*s <= '9'))
digit = *s - '0'; |
|
|
|
|
