微信

使用微信服务,更方便

职友集>程序员面试题 > 纳拓软件(Nextop Software)面试题

纳拓软件(Nextop Software)面试题

2015-07-17 06:30:03 阅读( 43 )

1249人 收藏本页

标签:程序员面试题

Problem 1 : Fast one-hot checker
A bit vector is one-hot if and only if there is at most one 1 in the vector. For example, 0000 and 00100 are one-hot and 00110 is not one-hot. Please find the fastest way to check whether a bit vector is one-hot or not.

Problem 2 : 3-Inverter
Assume that a logical blackbox has three Boolean inputs x, y, z and three Boolean outputs X, Y, Z where the outputs are defined as

X = ~x
Y = ~y
Z = ~z

Note that ~ stands for a NOT gate. Please realize this blackbox using only two NOT gates, and as many as possible AND and OR gates.

Problem 3 : Is it a loop ?
Assume that we have a head pointer to a link-list. Also assume that we know the list is single-linked. Can you come up an algorithm to check whether this link list includes a loop by using O(n) time and O(1) space where n is the length of the list? Furthermore, can you do so with O(n) time and only one register?
方法:使用两个指针,从头开始,一个一次前进一个节点,一个前进2个节点,则最多2N,后两个指针可以重合;如果无环,则正常停止。
同样的,可以找到链表的中间节点。同上。

Problem 4 : Detect same sequence
Assume that we have a m*n matrix A where both m >= 1K and n >= 100K. X_i is a row vector of A where 1 <= i <= m. In other words, A = {X_1, X_2, …, X_m}. Please find a fastest algorithm to detect all pairs (X_i, X_j), where X_i == X_j.

来自分智网

下一篇:常见算法笔试或面试题

上一篇:找一个最小的自然数x,使它等于不同的两对自然数的三次幂之和

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题