小编Sec*_*ish的帖子

这是一个面试问题:

给定一个包含40亿个整数的输入文件,提供一个算法来生成一个未包含在文件中的整数.假设您有1 GB内存.如果您只有10 MB内存,请跟进您的操作.

我的分析:

文件大小为4×10 ⁹ ×4字节= 16 GB.

我们可以进行外部排序,因此我们可以了解整数的范围.我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么？

我的理解(阅读完所有答案后):

假设我们正在讨论32位整数.有2 ^ 32 = 4*10 ^9个不同的整数.

情况1:我们有1 GB = 1*10 ⁹*8位= 80亿位内存.解决方案:如果我们使用一个代表一个不同整数的位,那就足够了.我们不需要排序.执行:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

情况2:10 MB内存= …

在一般的二进制搜索中,我们正在寻找出现在数组中的值.但是,有时我们需要找到比目标更大或更小的第一个元素.

这是我丑陋,不完整的解决方案:

// Assume all elements are positive, i.e., greater than zero
int bs (int[] a, int t) {
  int s = 0, e = a.length;
  int firstlarge = 1 << 30;
  int firstlargeindex = -1;
  while (s < e) {
    int m = (s + e) / 2;
    if (a[m] > t) {
      // how can I know a[m] is the first larger than
      if(a[m] < firstlarge) {
        firstlarge = a[m];
        firstlargeindex = m;
      }
      e = m - …

让我们假设每个线程正在进行一些FP计算,我感兴趣

• CPU在切换线程时使用了多长时间而不是运行它们
• 共享内存总线上创建了多少同步流量 - 当线程共享数据时,它们必须使用同步机制

我的问题:如何设计测试程序来获取这些数据？

问题:给定一个矩阵,其中每行和每列都被排序,编写一个方法来查找其中的元素.

这是一个经典的面试问题,这是我的解决方案

boolean F(int[][] matrix, int hs, int he, int ws, int we)
{
    if (hs > he || ws > we) 
        return false; 

    int m = (hs + he) / 2; 
    int n = (ws + we) / 2;

    if (matrix[m][n] == t)
    {
        return true;
    }
    else if (matrix[m][n] < t)
    {
        // find the ele in the same row, right to [m][n]
        F(m, m, n + 1, we);

        // find the ele in the same col, upper …

给定包含符号{true,false,和,或xor}的布尔表达式,计算括号表达式的方式的数量,使其计算结果为true.

例如,只有一种方法可以将'true和false xor true'括起来,使其计算结果为true.

这是我的算法

we can calculate the total number of parenthesization of a string
Definition:  
N - the total number of 
True -  the number of parenthesizations that evaluates to true
False - the number of parenthesizations that evaluates to false
True + False = N 
Left_True - the number of parenthesization in the left part that evaluates to True
same to Left_False, Right_True, Right_False

we iterate the input string from left to right and deal with each …

哈希函数在实现哈希表时很重要.我知道在java Object中有它的哈希码,它可能是从弱哈希函数生成的.

以下是一个"补充哈希函数"的片段

static int hash(Object x) {
    int h = x.hashCode();

    h += ~(h << 9);
    h ^=  (h >>> 14);
    h +=  (h << 4);
    h ^=  (h >>> 10);
    return h;
}

任何人都可以帮助解释哈希算法的基本思想是什么？生成非重复整数？如果是这样,这些按位操作如何实现呢？

给定凸多边形作为n个顶点的逆时针列表,给出O(lgn)算法以确定给定点是否在多边形内.假设基本操作采用O(1).

我认为一个方向:如果一个点位于凸多边形内,那么这些点与所有椎体或边缘之间的特殊关系是什么？此外,我猜这里的技巧是凸多边形,使算法lgn.

我想将2TB数据写入一个文件,将来它可能是一个PB级.

数据由所有数据组成'1'.例如,2TB数据由"1111111111111......11111"(每个字节由'1'表示)组成.

以下是我的方式:

File.open("data",File::RDWR||File::CREAT) do |file|
  2*1024*1024*1024*1024.times do
  file.write('1')
  end
end

这意味着,File.write被称为2TB次.从Ruby的角度来看,有没有更好的方法来实现它？

这是个问题.我想知道是否有明确有效的证据:

顶点覆盖:输入无向G,整数k> 0.是否有顶点S的子集,| S | <= k,覆盖所有边？

支配集:输入无向G,整数k> 0.是否有一个顶点S的子集,| S | <= k,它支配所有顶点？

顶点覆盖了它的入射边缘,并支配它的邻居和自身.

假设VC是NPC,证明DS是NPC.

这是问题所在:

假设有两个人在社交网站上注册,如何决定他们是否有联系？

我的分析(在阅读更多之后):实际上,问题是寻找 - 图中从A到B的最短路径.我认为BFS和Dijkstra的算法在这里工作,时间复杂度完全相同(O(V + E)),因为它是一个未加权的图,所以我们不能利用优先级队列.因此,一个简单的队列可以解决问题.但是,它们都没有解决这个问题:找到它们之间的路径.

此时Bidrectrol应该是更好的解决方案.

编辑:从解释,答案和示例中可以理解:

我有三个变量,每个变量只能假设两个特定值.例如,该值可以是0或1.

我想要一个逻辑,其中输出将是三个变量中的大多数存在的值.

例如:

如果x=0,y=0和z=1,输出将为0.

如果x=1,y=0和z=1,输出将是1.

来自@Femaref的答案在可能的值为0和1时给出了一个好的结果,但我需要一个通用的解决方案,它可以处理变量的任何可能的值.

例如,这是内存中的一个当前实现

String companies [] = {"Alice Berned","Beyonce Cathy","Kelly Boldt"};

要求是在运行时动态扩展此目录.记录可能多达数千.数据结构应该有助于搜索,添加,删除等基本功能.

我的解决方案

我的第一个想法是使用ArrayList,易于获取和添加.

问题:有什么好方法可以解决这个问题吗？