小编del*_*del的帖子

我正在准备接受采访,这让我想起曾经在之前的一次采访中被问过的一个问题:

"您被要求设计一些软件,以便在Google上连续显示前10个搜索字词.您可以访问提供无限实时搜索字词流的Feed,目前正在Google上搜索.请说明算法和数据结构你会用来实现这个.你要设计两个变种:

(i)显示所有时间的前10个搜索词(即自您开始阅读提要以来).

(ii)仅显示过去一个月的前10个搜索字词,每小时更新一次.

您可以使用近似值来获得前十名,但您必须证明自己的选择是合理的."
我在这次采访中遭到轰炸,但仍然不知道如何实现这一点.

第一部分要求在无限列表的不断增长的子序列中的10个最频繁的项目.我查看了选择算法,但找不到任何在线版本来解决这个问题.

第二部分使用有限列表,但由于处理的数据量很大,您无法将整个月的搜索项存储在内存中并每小时计算一次直方图.

前十名列表不断更新,这个问题变得更加困难,所以不管怎样你需要在滑动窗口上计算前十名.

有任何想法吗？

如何在pip需求文件中指定可选依赖项？根据pip文档,这是可能的,但文档没有解释如何做到这一点,我在网上找不到任何示例.

我正在寻找一个直观的,现实世界的问题示例,该问题需要(最坏的情况)指数时间复杂度来解决我正在给出的谈话.

以下是我提出的其他时间复杂性的例子(其中许多来自这个SO问题):

• O(1) - 确定数字是奇数还是偶数
• O(log N) - 在字典中查找单词(使用二进制搜索)
• O(N) - 读一本书
• O(N log N) - 排序一副扑克牌(使用合并排序)
• O(N ^ 2) - 检查您的购物车上是否包含所有物品
• O(无穷大) - 掷硬币直到落在头上

有任何想法吗？

鉴于城市列表和每个城市之间的飞行成本,我试图找到访问所有这些城市的最便宜的行程.我目前正在使用MATLAB解决方案找到最便宜的路线,但我现在想修改算法以允许以下内容:

1. 重复节点 - 应允许重复节点,因为通过枢纽城市旅行通常会导致更便宜的路线
2. 动态边缘权重 - 返回/往返航班与两个等效单程航班的成本不同(通常较低)

目前,我忽略了航班日期的问题,并假设可以从任何城市前往任何其他城市.

有没有人有任何想法如何解决这个问题？我的第一个想法是使用像GA或ACO这样的进化优化方法来解决第2点,并根据行程中是否包含返程/往返航班来评估目标函数时简单地调整边权重,但也许其他人有更好的理念.

(注意:我使用的是MATLAB,但我不是专门寻找编码解决方案,更多的是关于可以使用哪种算法的高级想法.)

编辑 - 在考虑了这个之后,允许"重复节点"似乎过于松散了约束.我们可以进一步约束问题,以便尽管可以重复访问节点,但每个有向边只能访问一次.忽略任何不止一次包含同一航班的行程似乎是合理的.

我在将任何Maven项目导入IntelliJ IDEA时遇到问题.我创建一个空的Maven项目,如下所示:

$ mvn archetype:generate -DgroupId=com.mycompany.app -DartifactId=my-app -DarchetypeArtifactId=maven-archetype-quickstart -DinteractiveMode=false

然后我尝试在IDEA中打开项目(文件>打开项目,然后选择pom.xml).一个表示"阅读pom.xml"的进度框显示几分钟,然后在没有打开项目的情况下消失.

查看IDEA日志,我看到一些连接超时异常,如下所示:

2012-10-03 11:55:38,502 [      0]   INFO -        #com.intellij.idea.Main - ------------------------------------------------------ IDE STARTED ------------------------------------------------------ 
2012-10-03 11:55:38,512 [     10]   INFO -        #com.intellij.idea.Main - IDE: IntelliJ IDEA (build #IC-117.798, 25 Jul 2012 00:00) 
2012-10-03 11:55:38,512 [     10]   INFO -        #com.intellij.idea.Main - JRE: 1.6.0_25-b06 (Sun Microsystems Inc.) 
2012-10-03 11:55:38,512 [     10]   INFO -        #com.intellij.idea.Main - JVM: 20.0-b11 (Sun Microsystems Inc.) 
2012-10-03 11:55:38,539 [     37]   INFO - .intellij.idea.IdeaApplication - WM detected: Compiz 
2012-10-03 …

我试图找到3个或更多字符串的最长公共子序列.维基百科的文章很好地描述了如何为2个字符串执行此操作,但我不太确定如何将其扩展为3个或更多字符串.

有很多库可以找到2个字符串的LCS,所以我想尽可能使用其中一个.如果我有3个字符串A,B和C,找到A和B的LCS作为X是有效的,然后找到X和C的LCS,或者这是错误的方法吗？

我在Python中实现了如下:

import difflib

def lcs(str1, str2):
    sm = difflib.SequenceMatcher()
    sm.set_seqs(str1, str2)
    matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
    return "".join(matching_blocks)

print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])

这输出"ba",但它应该是"baa".

我已经开始使用Scrapy来搜索一些网站.如果我稍后在我的模型中添加一个新字段或更改我的解析函数,我希望能够"重播"下载的原始数据,以便再次删除它.看起来Scrapy能够在一个点上将原始数据存储在重放文件中:

http://dev.scrapy.org/browser/scrapy/trunk/scrapy/command/commands/replay.py?rev=168

但是这个功能似乎已经在当前版本的Scrapy中被删除了.还有另一种方法来实现这一目标吗？

我对Scala没有经验,所以这个问题可能是基本的.我试图在Java中使用Scala类,基于本教程中的"Person"示例:http://www.codecommit.com/blog/java/interop-between-java-and-scala

我创建了两个源文件,一个Scala和一个Java,如下所示.

Person.scala:

class Person {
  def getName() = "Daniel Spiewak"
}

Test.java:

public class Test {
  public static void main(String[] args) {
    Person p = new Person();
    p.getName();
  }
}

我可以编译(带有警告,我不明白),但是当我尝试运行程序时,我得到一个ClassNotFoundException.

$ scalac Person.scala
$ javac Test.java
./Person.class: warning: Cannot find annotation method 'bytes()' in type 'ScalaSignature': class file for scala.reflect.ScalaSignature not found
1 warning
$ java Test
Exception in thread "main" java.lang.NoClassDefFoundError: scala/ScalaObject
        at java.lang.ClassLoader.defineClass1(Native Method)
        at java.lang.ClassLoader.defineClass(ClassLoader.java:787)
        at java.security.SecureClassLoader.defineClass(SecureClassLoader.java:142)
        at java.net.URLClassLoader.defineClass(URLClassLoader.java:447)
        at java.net.URLClassLoader.access$100(URLClassLoader.java:71)
        at …

我正在尝试创建使用多列作为输入的用户定义聚合函数,并输出单个列.

例如,计算加权平均值,我们可以使用两列名为num_samples和quantity,像这样的查询:

SELECT sum(num_samples * quantity) / sum(num_samples) AS weighted_avg FROM table; 

但是,我想要定义的函数非常复杂(例如加权标准偏差)并且被多次使用.我想定义自己的聚合函数,以便可以在select查询中轻松使用它们.例如,如果我想找到加权平均值和总和,我会使用如下查询:

SELECT weighted_avg(num_samples, quantity), sum(quantity)

但是,从文档中看,用户定义的聚合看起来只允许使用单个状态变量,但是这个示例需要两个状态变量:一个用于运行总计,quantity一个用于运行总计num_samples.

是否有可能通过用户定义的聚合函数实现我想要的,或者有更好的方法吗？我正在使用PostgreSQL 8.3.

我正在使用Python创建一个带有时间戳列的内存中sqlite3数据库.当我在查询中对此列使用min()或max()时,该列将作为字符串而不是Python datetime对象返回.我读了一个关于Stackoverflow的上一个问题,该问题提供了普通SELECT语句的解决方案,但是如果使用max()或min()则它不起作用.这是一个例子:

>>> db = sqlite3.connect(':memory:', detect_types=sqlite3.PARSE_DECLTYPES)
>>> c = db.cursor()
>>> c.execute('create table foo (bar integer, baz timestamp)')
<sqlite3.Cursor object at 0x7eff420e0be0>
>>> c.execute('insert into foo values(?, ?)', (23, datetime.datetime.now()))
<sqlite3.Cursor object at 0x7eff420e0be0>
>>> c.execute('select * from foo')
<sqlite3.Cursor object at 0x7eff420e0be0>
>>> c.fetchall()
[(23, datetime.datetime(2010, 12, 14, 1, 15, 54, 685575))]
>>> c.execute('select max(baz) from foo')
<sqlite3.Cursor object at 0x7eff420e0be0>
>>> c.fetchall()
[(u'2010-12-14 01:15:54.685575',)]

我试图将结果转换为时间戳,但它只返回年份:

>>> c.execute('select cast(max(baz) as timestamp) from …