刚遇到这个问题:
List<DataNode> a1 = new ArrayList<DataNode>();
List<Tree> b1 = a1; // compile error: incompatible type
DataNode类型是Tree的子类型.
public class DataNode implements Tree
令我惊讶的是,这适用于数组:
DataNode[] a2 = new DataNode[0];
Tree[] b2 = a2; // this is okay
这有点奇怪.谁能对此作出解释？
基本上我们有一个table(original table),它被备份到另一个table(backup table); 因此这两个表具有完全相同的模式.
在开始时,两个表(original table和backup table)包含完全相同的数据集.由于某种原因,我需要验证数据集是否original table已更改.
为了做到这一点,我必须将数据集进行比较的original table反对backup table.
假设它original table具有以下模式:
create table LemmasMapping (
lemma1 int,
lemma2 int,
index ix_lemma1 using btree (lemma1),
index ix_lemma2 using btree (lemma2)
)
我怎样才能实现数据集比较？
更新:表没有主键.它只是存储两个ID之间的映射.
给定一个未排序的整数序列,它作为流流入您的程序.
整数太多,不适合记忆.
想象一下有一个功能:
int getNext() throws NoSuchElementException;
它返回流中的下一个整数.
写一个函数来找到中位数.
解决O(n)中的问题.
有任何想法吗？
给出提示(使用堆数据结构..)
这个问题与从两个字符串中找到最长序列或子字符串的类型略有不同.
给定两个大小相同的字符串N,找到每个字符串中最长的子字符串,使得子字符串包含相同的字符包.
两个子串可能不一定具有相同的序列.但他们必须拥有相同的字符包.
例如,
a = ABCDDEGF b = FPCDBDAX
最长匹配的字符包是ABCDD(来自a的ABCDD,来自b的CDBDA)
如何解决这个问题呢？
UPDATE
目标是从每个输入字符串中找到子字符串,以便它们具有相同的字符包.通过说"子串",它们必须是连续的字符.
更新:最初我想到了一种动态编程方法.它的工作原理如下.
为了比较相同长度K的两袋字符,需要O(K)时间来实现.将每个字符串转换为缩短形式:
ABCDDEGF -> A1B1C1D2E1G1F1
FPCDBDAX -> A1B1C1D2F1P1X1
缩短形式是按字母表排序的字母表,后跟字符串中的频率数.构造,排序和比较缩短形式总共需要O(K)时间.(虽然可以通过使用字符数组来实现)
如果两个字符的缩短形式具有相同的字符和相应的频率,则它们是相同的.
此外,需要O(logK)时间才能找到两个字符串之间的差异字符.
现在,对于两个输入字符串:
最坏的情况是O(N 3),最好的情况是O(N).有什么好主意吗？
假设您有一个包含有效单词的字典.
给定删除了所有空格的输入字符串,确定该字符串是否由有效单词组成.
您可以假设字典是提供O(1)查找的哈希表.
Some examples:
helloworld-> hello world (valid)
isitniceinhere-> is it nice in here (valid)
zxyy-> invalid
如果一个字符串有多个可能的解析,只需返回true就足够了.
字符串可能很长.因此,想一个兼顾空间和时间的算法.
昨天我读了一个问题,可以通过稍加修改转化为以下问题:
点的坐标在2D空间中由(x,y)表示.
输入:点阵ARRAY = (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn)
和另一个点D = (xi, yi)
找到ARRAY距离最近的点D.
通过说"最近",我指的是欧几里德距离.
有一个明显的解决方案:遍历每个点ARRAY并计算其欧几里德距离D.然后,找到最短的距离.这可以在O(N)时间内完成.
我们可以在O(logN)中做得更快吗？我试图使用分而治之的方法,但尚未得出具体的想法.
问题的推广:如何在K维空间中找到最近的点？我们能否在低于O(N)的情况下做到这一点？
这是我最近面临的一个面试问题.
给定1和0的数组,找到一种方法来对位进行分区,in place以便将0组合在一起,并将1组合在一起.1是在0之前还是0在1之前是无关紧要的.
示例输入是101010101,输出是111110000或000011111.
在不到线性的时间内解决问题.
使问题更简单.输入是一个整数数组,每个元素为1或0.输出是相同的整数数组,整数分区很好.
对我来说,这是一个简单的问题,如果它可以在O(N)中解决.我的方法是使用两个指针,从数组的两端开始.增加和减少每个指针; 如果它没有指向正确的整数,则交换两者.
int * start = array;
int * end = array + length - 1;
while (start < end) {
// Assume 0 always at the end
if (*end == 0) {
--end;
continue;
}
// Assume 1 always at the beginning
if (*start == 1) {
++start;
continue;
}
swap(*start, *end);
}
然而,采访坚持认为存在一个亚线性解决方案.这让我苦苦思索,但仍未得到答案.
有人可以帮忙解决这个面试问题吗？
更新:看到SO中的回复表明问题无法在次线性时间内解决,我可以确认我原来的想法,即不存在子线性的解决方案.
面试官有可能发挥作用吗？
我们有两个相同大小的排序数组n.我们称之为数组a和b.
如何找到由a和b合并的排序数组中的中间元素？
Example:
n = 4
a = [1, 2, 3, 4]
b = [3, 4, 5, 6]
merged = [1, 2, 3, 3, 4, 4, 5, 6]
mid_element = merged[(0 + merged.length - 1) / 2] = merged[3] = 3
更复杂的情况:
情况1:
a = [1, 2, 3, 4]
b = [3, 4, 5, 6]
案例2:
a = [1, 2, 3, 4, 8]
b = [3, 4, 5, 6, 7]
案例3:
a = [1, 2, 3, 4, 8]
b = …我刚接触<time.h>并且有关于time_t和的问题time().
我读了函数time(),记录如下:
time_t time(time_t*timer); 获取当前时间
获取当前日历时间作为time_t对象.
该函数返回此值,如果参数不是空指针,则该值也设置为timer指向的对象.
文档没有谈论时区.
因此,对于以下C++代码:
time_t t = time(NULL);
如果两台机器(一台在美国,另一台在英国)同时执行函数调用time(NULL),返回的time_t对象是否相同？
time()会返回一个值而不考虑时区吗？
考虑一个方法中声明的对象:
public void foo() {
final Object obj = new Object();
// A long run job that consumes tons of memory and
// triggers garbage collection
}
在 foo()返回之前 obj会被垃圾收集吗？
更新:以前我认为obj不受垃圾收集的影响,直到 foo()返回.
但是,今天我发现自己错了.
我花了几个小时来修复一个bug,最后发现问题是由obj垃圾收集引起的!
谁能解释为什么会这样？如果我想要obj固定如何实现它？
这是有问题的代码.
public class Program
{
public static void main(String[] args) throws Exception {
String connectionString = "jdbc:mysql://<whatever>";
// I find wrap is gc-ed somewhere
SqlConnection wrap = new SqlConnection(connectionString);
Connection con = wrap.currentConnection();
Statement stmt = con.createStatement(ResultSet.TYPE_FORWARD_ONLY,
ResultSet.CONCUR_READ_ONLY);
stmt.setFetchSize(Integer.MIN_VALUE);
ResultSet rs = …这是一棵树:
会有一个根.
每个树节点都有零个或多个子节点.
允许两个节点指向同一个子节点.比如,节点A和节点B都有子C.
但是,禁止
节点A是节点B的后代,节点B是节点A的后代.
一个被禁止的案例是
节点A有一个子节点C和节点D,
Node C和D都有一个子节点E,
节点E有一个孩子A.
问题是,如何以最快的方式确定这个圈子？
更新:我意识到这是在有向图中找到任何循环.刚才我设法想出了类似于Tarjan算法的解决方案.
感谢您的评论.