f*****y
发帖数: 444 | 1 phone interview with hiring manager & hw engineer - 1 hour
1. brief introduction of company
2. resume questions
3. Difference between i2C and SPI bus? CAN bus?
4. what is size of char, char*, void*, int?
5. What debugger tools do you use? Are you familiar with ICE?
6. Node a and b has resistor r1 and node b has resistor r2 to ground.
Node a have Va, what is Vb? why use this circuit? if exchange r2 to a
capacitor, what circuit is this? can this circuit be implemented by software
and how?
7. how d... 阅读全帖 |
|
r********g
发帖数: 1351 | 2 我面的是实习，其他的都是老题，就不说了。
关于FP数的加法，就是给定32bit的unsigned int，当成FP运算，给出结果，结果也是
32bit int形势
的，不考虑溢出的情况。后来他觉得这个题好像太复杂了，改成都是positive的情况（
不考虑负数）。
这个题目其实没做好，忘记了一个重要情况，就是小数位其实省略了那个最高位的1，
比如小数部分是：
1.1011，其实实际中表示成：1011。如果算加法的话，得把这个最高位的1加上去，然
后还好考虑carry进
位的情况，同时还要考虑是不是修改指数部分。我答得很乱，不过还好，他估计也觉得
题目太难了，解释FP
数字在register里的表示就解释了好久，然后就没怎么编程。我觉得思路和表达很重要
，就是让他知道在给
定充分的解释和介绍之后你会做就行了。。。
bless大家都有好运! |
|
l****e
发帖数: 32 | 3 老题都有些啥。。。
我面的是实习，其他的都是老题，就不说了。
关于FP数的加法，就是给定32bit的unsigned int，当成FP运算，给出结果，结果也是
32bit int形势
的，不考虑溢出的情况。后来他觉得这个题好像太复杂了，改成都是positive的情况（
不考虑负数）。
这个题目其实没做好，忘记了一个重要情况，就是小数位其实省略了那个最高位的1，
比如小数部分是：
1.1011，其实实际中表示成：1011。如果算加法的话，得把这个最高位的1加上去，然
后还好考虑carry进
位的情况，同时还要考虑是不是修改指数部分。我答得很乱，不过还好，他估计也觉得
题目太难了，解释FP
数字在register里的表示就解释了好久，然后就没怎么编程。我觉得思路和表达很重要
，就是让他知道在给
定充分的解释和介绍之后你会做就行了。。。
bless大家都有好运! |
|
s********x
发帖数: 914 | 4 Thanks! 原来是unsigned int啊！ 本人用java的，呵呵
偶在做 http://www.facebook.com/careers/puzzles.php?puzzle_id=8 这题。
不知道这个input file是不是就直接放在root of project 下了呢。还有要生成
executable，是不是直接就用eclipse生成jar file就可以了？
另外system.out.println()的输出貌似在executable file看不到啊。
build.xml是不是用eclipse直接生成就可以了？
谢谢诶！ |
|
k*******t
发帖数: 202 | 5 class SyncBuf {
public:
void Thread1();
void Thread2();
private:
typedef vector BufT;
volatile BufT buffer_;
Mutex mtx_; // controls access to buffer_
};
Inside a thread function, you simply use a LockingPtr to get
controlled access to the buffer_ member variable:
void SyncBuf::Thread1() {
LockingPtr lpBuf(buffer_, mtx_);
BufT::iterator i = lpBuf->begin();
for (; i != lpBuf->end(); ++i) {
... use *i ...
}
}
The code is very easy to wr... 阅读全帖 |
|
w*******s
发帖数: 138 | 6 书上说的是对的
EOF 是 (int)-1
unsigned char c = EOF;
c是0xff
c == EOF // false
(int)c == 255 // 不管是不是sign-extension都一样
char |
|
b*****n
发帖数: 760 | 7 1. You have a class that supports to input sample records and to compute the
average of the samples. The class has two members: total and count. How
would you make the class thread-safe? If 99% of the time average() is called
, how to optimize for that?
2. Talk about your recent interesting project/bug.
3. You have 100 files, each containing 10G sorted integers. How to merge all
integers into one sorted file?
4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
--> -98.
5.... 阅读全帖 |
|
i*******w
发帖数: 15 | 8 45分钟三个题目，鬼扯完了之后第一个设计一个数据结构，判断一个电话号码是否被占
用。简单地说就是两个集合: available和used。这个数据结构要能支持 1) use 操作
，就是一个号码从available 变成used；2) 判断一个号码是否已被占用；3)
getUnusedNumber(）。反正不难，讨论一下为什么。讨论一下怎么优化。注意一下加锁
。其他看不出来还能考什么了。
第二个题目，已知f: unsigned-> int是一个单调（升）函数。试写出f的逆函数。讨论
了内存有没有限制，没有限制直接把表造出来查。然后他说有限制，那么就二分法查找
。问能不能优化。说弄个static cache记住前面几次f的结果，可以省几次比较。不知
道还能怎么优化。写了code.
第三个题目，两个排序集合，求第k大的元素。说合并排序那样，用O(k)，幸亏我谦虚
地留了个活路：你等会我看看能不能改进。果然是可以改进的，要是话说满了就被动了
。类似二分法改进出来，没有时间写code了。
不知道结果。 |
|
i**********e
发帖数: 1145 | 9 Good observation.
You are correct, my previous post has bugs and did not address the overflow
issue properly.
Two methods to address:
i) find the upper bound of SQRT(INT_MAX) once and pass it into that function
. The upper bound can be found using a helper function that tests for
overflow. (ie, as soon as the condition when x > x*x is met, we knew x-1 is
the upper bound).
ii) declare the parameter x as unsigned int. Then initialize the upper bound
,
hi = min(n/2, (1<<16) - 1);
Hope this helps. |
|
i**********e
发帖数: 1145 | 10 关于第一题，突然想到一个方法：
既然区间里只有7天，那为何不用一个 byte (8 bits）来表示一个区间呢？
这样判断两个区间是否相交，只要两个区间做一个 and operation，0 就代表不相交，
否则相交。
typedef unsigned char u8;
u8 setBits(int i, int j) {
if (i > j) return 0;
assert(j >= 0 && j <= 6);
assert(i >= 0 && i <= j);
u8 x = (1U << (j+1)) - 1;
u8 y = (1U << i ) - 1;
return x ^ y;
}
u8 createInterval(int start, int end) {
if (start <= end)
return setBits(start, end);
else
return ~setBits(end+1, start-1);
}
bool isIntersect(int a, int b, int c, int d) {... 阅读全帖 |
|
c*******n
发帖数: 63 | 11 写个简单的第二题
void OR(Bits *out, const Bits &in1, const Bits &in2)
{
unsigned int sntnl = 1;
assert(out);
out->known = 0;
out->value = 0;
while(sntnl >0)
{
if( (in1.known&sntnl && in1.value&sntnl)
|| (in2.known&sntnl && in2.value&sntnl) )
{
out->value |= sntnl;
out->known |= sntnl;
}
else if(in1.known&sntnl && in2.known&sntnl)
{
out->known |= sntnl;
}
sntnl <<= 1;
}
} |
|
c****p
发帖数: 6474 | 12 没理解错的话，如果A conform to A'，那么A'中为1的位，A对应地必须为1；A'中为0的
位，A对应地可以为1或者0。
如果令ones(A)=A中1的位数（对于30-bit unsigned有O(1)算法），
则A'的可能数为2^(30-ones(A))。
令f(A) = A'的可能数，
那么答案应该是：
f(A) + f(B) + f(C) -f(A&B) - f(A&C) - f(B&C) + f(A&B&C)
=====
囧，，，，和例子验证了一下，好像不对。。。。
=====
上式改成
f(A) + f(B) + f(C) -f(A|B) - f(A|C) - f(B|C) + f(A|B|C)
one |
|
c**********e
发帖数: 2007 | 13 In my computer, the size of a pointer is always 4. But why?
Because the address is essentially a long integer?
I see the following:
size of unsigned integer is 4
size of integer is 4
size of long is 4
size of float is 4 |
|
c*******g
发帖数: 1996 | 14 g++中的
00062 inline size_t __stl_hash_string(const char* __s)
00063 {
00064 unsigned long __h = 0;
00065 for ( ; *__s; ++__s)
00066 __h = 5*__h + *__s;
00067
00068 return size_t(__h);
00069 } |
|
w*******e
发帖数: 1588 | 15 double power(double x, unsigned int n)
{
if (n == 0) return 1;
if (n == 1) return x;
int xsquare = x * x;
if (n % 2 == 1) // n is odd
{
return (x * power(xsquare, n / 2));
}
else // n is even
{
return power(xsquare, n / 2);
}
}
We can also write an iterative version, I think. |
|
|
w*******e
发帖数: 1588 | 17 double power(double x, unsigned int n)
{
if (n == 0) return 1;
if (n == 1) return x;
int xsquare = x * x;
if (n % 2 == 1) // n is odd
{
return (x * power(xsquare, n / 2));
}
else // n is even
{
return power(xsquare, n / 2);
}
}
We can also write an iterative version, I think. |
|
|
h*******s
发帖数: 8454 | 19 用vector of vector不是挺好么，为啥非要用数组
可以试试
template
void foo(int m[][width], int height); |
|
s*******f
发帖数: 1114 | 20 u are goddamn right
template
void foo(int m[][width], int height){
for (int i = 0; i < height; ++i){
for (int j = 0; j < width; ++j)
printf("%d ", m[i][j]);
printf("\n");
}
return;
}
int main(){
int a[3][2] = {{1,2},{3,4},{5,6}};
foo<2>(a,3);
} |
|
x*******5
发帖数: 152 | 21 凑热闹，给个runable的code
/*Descriptoin: given a dictionary of words, find the longest word in the
dictionary such that it can be built from successively adding a single
character to an existing word in the dictionary in any location
Input: Dict& dict, vector v, vector & result
Output: void
K.O.: back tracking
*/
vector String::generate_next_string(string& s, String::Dict& dict){
string t;
vector v;
set temp;
for(int i=0;i<26;i++){
... 阅读全帖 |
|
B*******1
发帖数: 2454 | 22 bool isLittleEndian() {
unsigned int temp = 1;
return *(char *)&temp;
} |
|
f*******t
发帖数: 7549 | 23 应该是把内存空间当作多项式来计算，我写过一个C++ version:
int hash(const Object &o) {
int len = sizeof(Object);
int result = 0;
int i = 0;
while(i < len) {
result *= 256;
result += (int)(((unsigned char*)&o)[i]);
if(result > largeprime)
result %= largeprime;
i++;
}
return result;
} |
|
d********t
发帖数: 9628 | 24 result是hash value?哪个是key啊？
还有((unsigned char*)&o)是啥意思？我c语言好久没看了。 |
|
g*********8
发帖数: 64 | 25 int str2int(string s){
assert(s.length()>0);
bool isNeg=false;
unsigned int num=0,i=0,d=0;
if(s[0]=='-'){
isNeg=true;
i=1;
}
while(i
d=s[i]-'0';
num=num*10+d;
assert(d>=0&&d<=9);
assert(num<=INT_MAX);
i++;
}
if(isNeg) num=-1*num;
return num;
}
我写的代码，望指正，处理了溢出，负数，非数值，还有什么异常没有处理？ |
|
n**e
发帖数: 116 | 26 看到版上太多关于atoi的讨论，我贴一个我的实现，希望对有所帮助。如发现bugs，请
指正。
//--------------------------------------------------------------------
// Convert a string to an integer
// How to handle 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... 阅读全帖 |
|
g*********8
发帖数: 64 | 27 跟风写一个C++版本的
void string_permute_noduplicate(string str, int d){
if(d==str.length()){
cout<
return;
}
else{
char lastswap=' ';
for(unsigned int i=d;i
if(str[i]==lastswap) continue;
else{
lastswap=str[i];
swap(str[i],str[d]);
string_permute_noduplicate(str,d+1);
swap(str[i],str[d]);
}
}
}
} |
|
k***t
发帖数: 276 | 28 来自主题: JobHunting版 - 问个算法题 也来凑个热闹。主要是练练trie。
花了些时间才调通:( 谁帮忙给Review一下？谢了。
运行结果：
ad: 5
bc: 3
bb: 2
aaa: 1
aa: 1
源码：
#include
#include
using namespace std;
struct Node {
int cnt;
char c;
struct Node *n[26];
char *p; // to the 1st occurrence in the original input string
};
#define idx(x) (x-'a')
void add2trie (Node *r, char *p1, char *p2) {
char *p; Node *cur=r; Node *n;
p=p1;
cur=r;
while (p!=p2 && cur->n[idx(*p)]) {cur=cur->n[idx(*p)]; ++p;}
if (p==p2) { cur->cnt++;... 阅读全帖 |
|
w****x
发帖数: 2483 | 29 const char* myitoa(int num, char str[])
{
assert(a);
char* pIterBeg = str;
if (num < 0)
{
num = -num;
*pIterBeg++ = '-';
}
//use long not short to avoid INT_MIN overflow
unsigned int numshort = num;
char* pIter = pIterBeg;
while (true)
{
*pIter++ = numshort%10 + '0';
numshort = numshort/10;
if (numshort == 0) break;
}
*pIter = 0;
int nLen = strlen(pIterBeg);
assert(nLen > 0);
char* pIterEnd = ... 阅读全帖 |
|
w****x
发帖数: 2483 | 30
const char* myitoa(int num, char str[])
{
char* pIterBeg = str;
if (num < 0)
{
num = -num;
*pIterBeg++ = '-';
}
unsigned int numshort = num; //avoid INT_MIN overflow
char* pIter = pIterBeg;
do
{
*pIter++ = numshort%10 + '0';
numshort = numshort/10;
}while (numshort != 0);
*pIter = 0;
char* pIterEnd = pIter - 1;
while (pIterEnd > pIterBeg)
swap(*pIterBeg++, *pIterEnd--);
return str;
}
谢谢提醒, 修改版本 |
|
i******r
发帖数: 793 | 31 擦。。。犯了一个巨二的错误
第三题没有用unsigned int而是用int
估计挂了 |
|
b***u
发帖数: 12010 | 32 我会弄个bitmap，四位digit有10k，用10k/32+1个unsigned int。每读一个digit把后
四位查下出现没。第几位出现就需要多少时间。 |
|
b******t
发帖数: 965 | 33 调用putchar打印一个unsigned int |
|
r****t
发帖数: 10904 | 34 真的是 c++ library 的 atoi 么？libc 里面是用 unsigned 来处理溢出，并且有两个
不同的 cutoff 才对阿。 |
|
p*i
发帖数: 411 | 35 int myatoi(const string& str) {
const int n = str.size();
int curr = 0; // current index
while ((curr < n) && (isspace(str[curr]))) curr++; // skip leading
spaces
int sign = 1; // positive
if (str[curr] == '-') {
sign = -1; curr++;
}
if (curr == n)
throw runtime_error("Invalid input");
// prepare overflow check
int base, extra;
if (sign == 1) {
base = numeric_limits::max() / 10;
extra = numeric_limits::max() % 10;
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 36 没有考虑 overflow，思路跟楼上的一样。
我首先想到的是 binary search 的思路，这个用 bit 的思路还是没那么直接和容易想
到。
typedef unsigned int uint;
uint divide(uint a, uint b) {
uint x = 0, ret = 0;
int numBits = sizeof(uint) * 8;
for (int i = numBits - 1; i >= 0; i--) {
x |= ((a >> i) & 1);
if (x >= b) {
ret |= 1;
x -= b;
}
if (i > 0)
ret <<= 1;
x <<= 1;
}
return ret;
}
int divide(int a, int b) {
assert(b != 0);
int sign = 1;
if ((a... 阅读全帖 |
|
i**********e
发帖数: 1145 | 37 Just tried running your code here:
http://www.leetcode.com/onlinejudge
it seemed it failed for some test cases when a or b == -2147483648.
This is because if (a < 0) a = -a; cause it to overflow for negative
integers. Since Java doesn't have unsigned int, you may have to use long
long to avoid overflow.
Run Status: Wrong Answer
Progress: 13/17 test cases passed.
input output expected
-2147483648, 1 0 -2147483648 |
|
i**********e
发帖数: 1145 | 38 没有考虑 overflow，思路跟楼上的一样。
我首先想到的是 binary search 的思路，这个用 bit 的思路还是没那么直接和容易想
到。
typedef unsigned int uint;
uint divide(uint a, uint b) {
uint x = 0, ret = 0;
int numBits = sizeof(uint) * 8;
for (int i = numBits - 1; i >= 0; i--) {
x |= ((a >> i) & 1);
if (x >= b) {
ret |= 1;
x -= b;
}
if (i > 0)
ret <<= 1;
x <<= 1;
}
return ret;
}
int divide(int a, int b) {
assert(b != 0);
int sign = 1;
if ((a... 阅读全帖 |
|
i**********e
发帖数: 1145 | 39 Just tried running your code here:
http://www.leetcode.com/onlinejudge
it seemed it failed for some test cases when a or b == -2147483648.
This is because if (a < 0) a = -a; cause it to overflow for negative
integers. Since Java doesn't have unsigned int, you may have to use long
long to avoid overflow.
Run Status: Wrong Answer
Progress: 13/17 test cases passed.
input output expected
-2147483648, 1 0 -2147483648 |
|
|
f*******l
发帖数: 66 | 41 why not just convert signed number to unsigned number? |
|
f*******l
发帖数: 66 | 42 why not just convert signed number to unsigned number? |
|
|
w****x
发帖数: 2483 | 44
溢出那题是不是可以把传入的unsigned int 转成double, 然后两个double相加, 然后
和UNSIGNED_INT_MAX比较
或者通过除2并判断奇偶得情况绕弯来做 |
|
H****r
发帖数: 2801 | 45 // the following requires key is of type int or unsigned int
a[i].key = aidx++;
// which might not be true. The key might be only 2 bits for "00", "01", and
"10" |
|
m********1
发帖数: 31 | 46 comparison between signed and unsigned integer expressions |
|
s*****n
发帖数: 994 | 47 Yes, you are correct. Always use "unsigned int i" when comparing with size()
function.
I am using index instead of iterator is because I have one more situation
which is not any of the vector elements to consider. This is the way to add
it in and save some duplicate lines. |
|
m*********e
发帖数: 55 | 48 signed and unsigned compare应该有warning的 |
|
c*********t
发帖数: 2921 | 49 学习了。
是不是寄存器本身看不出有无符号？
是否按有符号数操作是由指令决定的？
一个signed和一个unsigned 比较的时候，用的指令同两个signed数作比较时用的指令
相同吗？ |
|
|
