发钱网面试算法题总结

前言

由于周五要面发钱网，昨天把网上搜到的面试题汇总了一下，简单写一下思路。题目都不难，主要是熟悉一下解题过程。

真题

1. Remove / Find duplicate characters in String

如果只是将遇到的重复的 char 移除的话，可以建立一个 HashSet 和一个 ArrayList。HashSet 判断 char 是否重复，list 中按顺序储存不重复元素。

Traverse each character in the string
    if the character not in HashSet
        add it to both HashSet and ArrayList
convert the list to string by using StringBuilder and then toString

• 如果不是 remove 是 find，可以用 HashSet 存已经出现的元素，另一个 HashSet 存重复元素。这样可以保证找出的重复元素不重复。
• 但如果遇到 LeetCode 316 的要求，remove 肯定不能这样做了。鉴于 316 是道 hard，而面试基本上不可能考，等这些题全总结完回头再做。
• 还有一题是这样的：Given an array of unknown length, how would you determine if there are multiple items repeated within.
  • 这题还是用 HashSet。If the item are not in the set, add it to the set; else return true (there are repeated items).

2. Recursion to solve Fibonacci sequence

首先找出前后项关系式：f(n) = f(n - 1) + f(n - 2)。

• Recursion

  public int fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
  }

• Dynamic Programming

  public int fib(n) {
  int[] f = new int[n];
  f[0] = 0; f[1] = 1;
  for (int i = 2; i < n; i++) {
  f[n] = f[n - 1] + f[n -2];
  }
  return f[n];
  }

3. Count number of each element in an array

不知道题目是不是这个意思。

用 HashTable 就行，没出现的元素 map.put (e, 1);

出现的元素 map.put (e, map.get (e) + 1);

4. LeetCode 319 - Bulb Switcher

The intuitive way to solve the problem is to traverse n switchers by 1, 2, ..., n steps.

Initialize an array of length n with all zeros.

for i in 1 : n steps
    for j = i; j < n; j = j + i
        if the switch is on: turn off;
        else: turn on
return count of 1s in the array;

这个方法在复杂度过高，在 n 很大时会报错。 319 discuss 里有数学解法和证明。

5. LeetCode 242 - Valid Anagram

How to tell two strings are anagram?

Convert them to two char arrays and sort them.

If the two sorted arrays are equal then they are anagram.

Or record the times of appearance for each character in an array of size 26, for string t, add the counter of each charater by 1 if it apprears, and for string t, minus the counter by 1 if it appears. The final values in the array should all be 0s. This takes O(n) time.

• Advanced: Leetcode 49 - Group Anagrams - 使用 HashMap
• Follow Up: What if the inputs contain unicode characters? How would you adapt your solution to such case?
  • Use HashMap to store each character and the times it appears.
  • Traverse String s first to count appearance of characters and add the times into each key.
  • Then Traverse String t to minus the count if the character appears. If the count of a chacter is 1, remove it. Or there is no count of such character, return false.
  • After the traverse, the map should be empty. If it is the case, return true. If not, return false.

6. To check whether one string is the substring of the other

Use two pointers with a fixed length equal to the shorter string's length.

Travese the longer string by using two pointers.

// Suppose two strings, s1, s2, and s1 is longer.
Initialize p1 = 0; p2 = length of s2
while (p2 <= length of s1) {
    \\compare 
    if (!s1.substring(p1, p2) equals to s2) return false;
    p1++; p2++;
}
return true if quit the while-loop

• 如果是找是否是 subsequence, 看 LeetCode 392 - Is Subsequence

7. Detect the start of a loop in a linked list

Set faster pointer and slower pointer starting at the head of linked list;

// Detect the loop
while (slower and faster not meet)
    slower move one step;
    faster move two steps;
if they meet, there is a loop

// Find the head of the loop
set a pointer p1 at the head of linked list, the other pointer p2 at the position slower and faster first meet;
while (p1 and p2 not meet)
    move both of them one step
The first time they meet is the head of the loop

• To prove why this is true, see - Why Floyd's cycle detection algorithm works? Detecting loop in a linked list
• Follow up: Remove the cycle, see - Detect and Remove Loop in a Linked List | GeeksforGeeks

8. Find if a number was a stepping number (Best Solution)

9. Determine if a word is a palindrome using any pseudo code you want.

Ask if we need to ignore the case.

Use two pointers to traverse the String from both ends. return false if the char in two positions are not equal.

initialize i = 0 and j = length of string - 1 
while (i < j) {
    if (charAt(i) != charAt(j)) return false;
    i++; j--;
}
return true when quit the while loop;

本作品采用《CC 协议》，转载必须注明作者和本文链接