这是一个面试问题.您需要设计一个包含整数值的堆栈,以便getMinimum()函数返回堆栈中的最小元素.
例如:考虑下面的例子
case #1 5 --> TOP 1 4 6 2 When getMinimum() is called it should return 1, which is the minimum element in the stack. case #2 stack.pop() stack.pop() Note: Both 5 and 1 are poped out of the stack. So after this, the stack looks like, 4 --> TOP 6 2 When getMinimum() is called is should return 2 which is the minimum in the stack.
制约性:
我的一位同事使用的一个有趣的访谈问题:
假设您有一个非常长的未排序的无符号64位整数列表.您如何找到列表中未出现的最小非负整数？
后续行动:现在已经提出了通过排序的明显解决方案,你能比O(n log n)更快地完成吗？
FOLLOW-UP:您的算法必须在具有1GB内存的计算机上运行
澄清:列表在RAM中,但它可能会消耗大量的内容.您将提前获得列表的大小,例如N.
定义:
回文是单词,短语,数字或其他单元序列,具有在任一方向上读取相同的属性
如何检查给定的字符串是否是回文？
这是前一段时间的FAIQ [常见问题访谈问题]之一,但主要是使用C.
寻找任何和所有语言的解决方案.
我在Reddit上看到了这个问题,并没有提出积极的解决方案,我认为这是一个完美的问题.这是关于面试问题的一个主题:
编写一个采用大小为m的int数组的方法,如果数组由数字n ... n + m-1组成,则返回(True/False),该范围内的所有数字以及该范围内的数字.不保证数组已排序.(例如,{2,3,4}将返回true.{1,3,1}将返回false,{1,2,4}将返回false.
我遇到的问题是我的采访者一直要求我优化(更快的O(n),更少的内存等),他声称你可以在数组的一次传递中使用恒定量的记忆.从未想过那一个.
除了您的解决方案,请指出他们是否认为该阵列包含唯一的项目.同时指出您的解决方案是否假设序列从1开始.(我稍微修改了一下这个问题以允许它变为2,3,4 ......)
编辑:我现在认为在空间算法中不存在处理重复的线性时间和常数.任何人都可以验证吗？
重复问题归结为测试以查看数组是否在O(n)时间,O(1)空间中包含重复项.如果可以这样做,您可以先测试,如果没有重复,则运行算法.那么你可以在O(n)时间O(1)空间中测试欺骗吗？
T9词典如何运作？它背后的数据结构是什么.如果我们输入'4663',当我们按下按钮时我们会'好',然后'去'然后'回家'等...
编辑:如果用户键入46然后它应显示'go',按下箭头时应显示'去'等...
这是一个面试问题.考虑以下:
struct A {};
struct B : A {};
A a;
B b;
a = b;
b = a;
为什么b = a;抛出错误,虽然a = b;完全没问题？
确定链表是否有循环的最佳(暂停)算法是什么？
[编辑]对时间和空间的渐近复杂性的分析将是甜蜜的,因此可以更好地比较答案.
[编辑]原始问题没有解决超过1的节点,但有一些关于它的讨论.这个问题更像是"在有向图中检测周期的最佳算法".
[描述]给定两个长度相同的整数数组.设计一种能够判断它们是否相同的算法."相同"的定义是,如果这两个数组按排序顺序排列,则相应位置的元素应该相同.
[Example]
<1 2 3 4> = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>
[限制]算法应该需要恒定的额外空间和O(n)运行时间.
我有一个x由y矩阵,其中每行和每列是按升序排列如下面给出的.
1 5 7 9
4 6 10 15
8 11 12 19
14 16 18 21
如何搜索此矩阵中的数字O(x+y)？
我被问到这个问题接受采访,但无法弄明白.很想知道它是否可以完成.