面试算法题一则

就是给定三个字符串A,B,C;判断C能否由AB中的字符组成,同时这个组合后的字符顺序必须是A,B中原来的顺序,不能逆序;例如:A:mnl,B:xyz;如果C为mnxylz,就符合题意;如果C为mxnzly,就不符合题意,原因是z与y顺序不是B中顺序。

/**
 * User: SunDP
 * Date: 12-12-15
 * Time: 下午11:14
 */
public class StringTest {

    public static void main(String[] args) {
        int flagX = 0, flagY = 0;
        String a = "aaaaaaaa";
        String b = "aaaaaaba";
        String c = "aaaaaaaabaaaaaaa";
        if (a.length() + b.length() != c.length())
            System.out.println(false);
        else
            System.out.println(dsp(flagX, flagY, a, b, c));
    }

    private static boolean dsp(int flagX, int flagY, String a, String b, String c) {
        if (flagX == a.length() && flagY == b.length())
            return true;
        if (flagX != a.length() && a.charAt(flagX) == c.charAt(flagX + flagY))
            if (dsp(flagX + 1, flagY, a, b, c))
                return true;
        if (flagY != b.length() && b.charAt(flagY) == c.charAt(flagX + flagY))
            if (dsp(flagX, flagY + 1, a, b, c))
                return true;
        return false;
    }
}

一道算法题

问题,有两个有序int数组A,B,长度均为k,
求一个新有序数组C,C中元素为A中取一个元素与B中取一个元素的和~
比如
a = {1, 2, 3, 4, 5, 6, 7};
b = {1, 2, 3, 4, 5, 6, 7};

结果为
1+1=2
1+2=3
2+1=3
1+3=4
2+2=4
1+4=5
2+3=5

我的解题思路

设置一组指针数组pointA ,表示A值和B组合以后的位置

pointA[0]=0表示指向a1 b1的点
pointA[3]=4表示指向a4 b5的点
pointA[4]=-1表示a5和任意b的组合都不用考虑

指针不断向下向右走,判断所有指针上点,取个和最小的就是结果

A
^  指针  1   2   3   4   5   6   7  > B
1   0   2   3
2   0   3
3  -1
4  -1
5  -1
6  -1
7  -1

下面附带上我写的代码

/**
 * Created with IntelliJ IDEA.
 * User: SunDP
 * Date: 12-11-6
 * Time: 下午10:44
 * To change this template use File | Settings | File Templates.
 */
public class Sort {

    static int pointRound = 2;

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 5, 7 , 9, 11,15,24,99};
        int[] b = {2, 3, 6, 8, 10, 11,13,17,19,20};
        int[] result = new int[a.length];
        int[] pointA = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            pointA[i] = -1;
        }
        pointA[0] = 0;
        pointA[1] = 0;

        for (int i = 0; i < a.length; i++) {
            compare(pointA, a, b, result, i, pointRound);
        }
    }

    public static void compare(int[] pointA, int[] a, int[] b, int[] result, int round, int tempPointRound) {
        int temp = 10000000;
        int tempPoint = 0;
        for (int i = 0; i < tempPointRound; i++) {
            if (pointA[i] != -1) {
                if (a[i] + b[pointA[i]] < temp) {
                    temp = a[i] + b[pointA[i]];
                    tempPoint = i;
                }
            }
        }
        result[round] = a[tempPoint] + b[pointA[tempPoint]];
        System.out.println(a[tempPoint] + "+" + b[pointA[tempPoint]] + "=" + result[round]);
        if (pointA[tempPoint] == 0 && tempPoint < pointA.length - 1) {
            pointA[tempPoint + 1] = 0;
            pointRound = tempPointRound+1;
        }
        if (pointA[tempPoint] < a.length - 1) {
            pointA[tempPoint]++;
        } else {
            pointA[tempPoint] = -1;
        }
    }
}

这个时间复杂度是k平方,貌似又不是k平方,求高人帮计算~

后续:没事的时候思考了一下,把他想象成一个汉诺塔,塔的编号分别是b0,b1,b2….横竖都是有序的,所以左下角的点一定是最小值,

a6 a6 a6 a6 a6 a6 a6
a5 a5 a5 a5 a5 a5 a5
a4 a4 a4 a4 a4 a4 a4
a3 a3 a3 a3 a3 a3 a3
a2 a2 a2 a2 a2 a2 a2
a1 a1 a1 a1 a1 a1 a1
a0 a0 a0 a0 a0 a0 a0
------------------------------
b0 b1 b2 b3 b4 b5 b6

最小值为a0+b0,将这个值取出,此时计算所有柱子上最底下元素的值,
即a1+b0,a0+b1,a0+b2,a0+b3,a0+b4,a0+b5,a0+b6
此时a0+b1,a0+b2,a0+b3,a0+b4,a0+b5,a0+b6一定是有序的,这时,我们可以看成把a1+b0进行插入排序

a6 a6 a6 a6 a6 a6 a6
a5 a5 a5 a5 a5 a5 a5
a4 a4 a4 a4 a4 a4 a4
a3 a3 a3 a3 a3 a3 a3
a2 a2 a2 a2 a2 a2 a2
a1 a1 a1 a1 a1 a1 a1
a0 a0 a0      a0 a0 a0
——————————
b1 b2 b3 b0 b4 b5 b6

(假设b0+a1的位置在b3+a0和b4+a0之间)

那么此时最小值一定是 a0+b1,在b1中取出a0,再次进行排序,不断执行,直到n次。

算法分析:折半查找时间复杂度是log(n),共要执行n次,所以该算法的时间复杂度是n*log(n)

 

 

 

 

Question 1:

为什么折半查找时间复杂度是log(n):

Answer:

假设对n个元素的折半查找需要消耗的时间为t(n)。容易知道:
如果n = 1,则t(n) = c1
如果n > 1,则t(n) = t(n/2) + c2
其中n/2需要取整,c1、c2都是常数

对于正整数n,可以有:
t(n) = t(n/2) + c2
= t(n/4) + 2*c2
= t(n/8) + 4*c2
= …
= t(n/(2的k次方)) + k*c2
一直推演下去,直到n/(2的k次方)等于1,也就是k = log2(n),此时等式变为:
t(n) = t(1) + k*c2
= c1 + log2(n)*c2

于是时间复杂度为log2(n)。注意log2(n)和log(n)其实是同样的复杂度,因为它们之间仅仅差了一个常量系数而已。

这个是不严格的推导,因为没有考虑整数除以2之后可能有余数的情况。但即使有余数,也是不影响时间复杂度的。

2013新浪哈尔滨笔试总结(转帖)

过程很纠结,估计新浪让很多同学心寒了~不表

笔试题很基础,40道选择,包括Java基础、读程序、数据库基础、linux基础
感觉怎么也能对个30+吧
一道程序设计题
题目大概是这样的 有个Attention类保存的是一个微博用户的关注列表,请你完成这个结构,要求能保存uid(Long)和关注时间,并实现共同关注这个功能SetgetSameAttentions(Attention user1,Attention user2)
但是觉得这题没什么
直接写代码

import java.util.Date;
import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * User: SunDP
 * Date: 用户关注类,Key是uid,Value是关注时间
 */
public class Attention extends HashMap< Long,Date  >{

}
Set< Long > getSameAttentions(Attention user1,Attention user2){
     Set< Long > sameAttentions = new HashSet< Long >();
     for(Long uid : user1.keySet()){
          if(user2.containsKey(uid)){
                sameAttention.add(uid);
          }
     }
     return sameAttetion;
}

结果面试木有进!!
反思啊~~~~~~~~
觉得问题应该出在最后一题上,问题出在哪呢,我猜sina的大大们是不是在考大数据处理的问题捏,比如两个同时有2000个关注的人,但是只有一个相同关注….