IBM的OA

1.给一个字符串和一组query index,找出离index最近的相同char的idx,距离相同的话就返回小的那个。

2.给一个0,1数组,只能交换相邻的元素,问最少交换多少次可以将0和1都放在一起。 这题 separating students 看面经的时候以为就是把0换到最右边,把1挪到最左边,看到题目才发现,就是把0,1分开,然后看(把0挪左边)(把1挪左边)哪种swap的次数小

解题思路:
可以用两个pointer记录,第一个记录遇到‍‌‌‍‌‍‍‍‌‌‌‍‍‌‍‌‍‍‌0的位置,第二个从第一个pointer之后开始loop, 遇到1,计算index差,然后pointer++。把list reverse一下再走一遍,取两次值小的。index为i + 1时,重新计算累计和也需要O(n)完成一个cycle,再次来到i + 1时停止

  1. parking dilemma 题目见 IBM OA ,代码大家还是要记得稍微改一下更好
  1. Two strings: 比较2个string有没有share的character,给一串这样的string,对于每一对这样的String,有common的就打印“YES”, 反之打印“NO”。直接Set就可以做了。
  2. Purchasing supplies:这个就是给一定的budget, 去买桶(有货物),每k个用完的空桶可以再换一个有货物的桶,问最后这么多budget能换多少有货物桶,注意老的空桶可以和新的还过来的桶合起来兑换。应该也就是一个while loop, 没啥tricky的
  3. Parking dilemma, 给一个数组,代表一列‍‍‌‌‍‍‌‌‍‌‍‍‍‌‌‍‌‍停车位里面有车的位置,给一个数字k, 要求建一个棚子,cover住至少k个车,我就直接sort,遍历了,没啥tricky的地方貌似
  1. Partitioning Array
    用map统计下词频然后根据条件判断即可
  2. Shifting Strings: 这个主要是看下规律,会发现针对rightShifts移动字符的时候,其实就是针对 leftShifts移动s.length() - rightShifts个字符。 给一个string 和 int leftShifts, int rightShifts. 输出shift 后的strings. 如果s = abcd, leftShift1 = bcda, 然后在rightShift2 = dabc.

IBM_OA.docx (2.5 MB)

public static int optimalPoint(List<Integer> magic, List<Integer> dist) {
        // Write your code here
        int pos = -1, curr = 0, total = 0; 
        for (int i = 0; i < magic.size(); i++) {
            int diff = magic.get(i) - dist.get(i);
            curr += diff; 
            total += diff;
            if (curr < 0) {
                curr = 0;
                pos = i;
            }
        }
        if (total >= 0) 
            return pos + 1; 
        return -1;
    }

Java solution:
This problem looks like https://leetcode.com/problems/gas-station/

public static void main(String[] args) {
	int[] magic = {2,4,5,2};
	int[] dist = {4,3,1,3};
	System.out.println(getStartPoint(magic, dist));
}

private static int getStartPoint(int[] magic, int[] dist) {
	int s = 0, r = 0, d = 0;
    for(int i=0;i<magic.length;i++){
        r += magic[i] - dist[i];
        if(r < 0){
            s = i+1;
            d += r;
            r = 0;
        }
    }
    return d + r >= 0 ? s : -1;
}

public static int optimalPoint(List<Integer> magic, List<Integer> dist) {
        // Write your code here
        int pos = -1, curr = 0, total = 0; 
        for (int i = 0; i < magic.size(); i++) {
            int diff = magic.get(i) - dist.get(i);
            curr += diff; 
            total += diff;
            if (curr < 0) {
                curr = 0;
                pos = i;
            }
        }
        if (total >= 0) 
            return pos + 1; 
        return -1;
    }

public static void commonSubstring(List < String > a, List < String > b) {
      // Write your code here
      boolean[] ch = new boolean[26];
      int flag = 0;
      for (int i = 0; i < a.size(); i++) {
          flag = 0;
          ch = new boolean[26];
          for (int j = 0; j < a.get(i).length(); j++) {
              ch[a.get(i).charAt(j) - 'a'] = true;
          }

          for (int j = 0; j < b.get(i).length(); j++) {
              if (ch[b.get(i).charAt(j) - 'a']) {
                  flag = 1;
                  break;
              }
          }

          if (flag == 1)
              System.out.println("YES");
          else
              System.out.println("NO");
      }
  }

Java solution with BitMask

public static void main(String[] args) {
	String[] a = {"ab", "cd", "ef"};
	String[] b = {"af", "ee", "ef"};
	String[] res = twoStrings(a, b);
	for(String r : res) {
		System.out.println(r);
	}
}

private static String[] twoStrings(String[] a, String[] b) {
	String[] res = new String[a.length];
	for(int i=0;i<a.length;i++) {
		int bitMaskA = 0;
		int bitMaskB = 0;
		for(int j =0;j<a[i].length();j++) {
			char ac = a[i].charAt(j);
			char bc = b[i].charAt(j);
			bitMaskA |= 1 << (ac - 'a');
			bitMaskB |= 1 << (bc - 'a');
		}
		res[i] = (bitMaskA & bitMaskB) > 0 ? "YES" : "NO"; 
	}
	return res;
}

YES
NO
YES

类似 https://leetcode.com/problems/3sum-smaller/