Algorithm Notes
  • Introduction
  • Search & Backtracking 搜索与回溯
    • Tree 与 BackTracking 的比较
    • Subsets, Combination 与 Permutation
    • Subsets & Combinations & Combination Sum
    • 枚举法
    • N 皇后 + 矩阵 Index Trick
    • Sudoku 数独 + 矩阵 Index Trick
    • Word Ladder I & II
    • Number of ways 类
    • DFS flood filling
    • Strobogrammatic 数生成
    • String 构造式 DFS + Backtracking
    • Word Pattern I & II
    • (G) Binary Watch
    • (FB) Phone Letter Combination
    • 常见搜索问题的迭代解法
  • String,字符串类
    • 多步翻转法
    • Substring 结构和遍历
    • Palindrome 问题
    • Palindrome Continued
    • String / LinkedList 大数运算
    • 序列化与压缩
    • 5/24 String 杂题
    • Knuth–Morris–Pratt 字符串匹配
    • Lempel–Ziv–Welch 字符串压缩算法
    • (G) Decode String
    • (G) UTF-8 Validation
  • Binary Tree,二叉树
    • 各种 Binary Tree 定义
    • LCA 类问题
    • 三序遍历,vertical order
    • Post order traversal 的应用
    • Min/Max/Balanced Depth
    • BST
    • 子树结构
    • Level Order traversal
    • Morris 遍历
    • 修改结构
    • 创建 / 序列化
    • 子树组合,BST query
    • 路径与路径和
    • NestedInteger 类
    • (FB) 从 Binary Tree Path 看如何递归转迭代
    • (FB) Binary Tree Path 比较路径大小
    • 比较好玩的 Binary Tree 概率题
  • Segment & Fenwick Tree,区间树
    • Segment Tree 基础操作
    • Segment Tree 的应用
    • Fenwick Tree (Binary Indexed Tree)
    • Range Sum Query 2D - Immutable
  • Union-Find,并查集
    • Union-Find,并查集基础
    • Union-Find, 并查集应用
  • Dynamic Programming, 动态规划
    • 6/20, 入门 House Robber
    • 7/12, Paint Fence / House
    • 6/24, 滚动数组
    • 6/24, 记忆化搜索
    • 6/24, 博弈类 DP
    • 博弈类DP, Flip Game
    • 6/25, 区间类DP
    • 6/27, subarray 划分类,股票
    • 7/2, 字符串类
    • Bomb Enemies
    • 8/2,背包问题
    • (G) Max Vacation
    • (11/4新增) AST 子树结构 DP
  • LinkedList,链表
    • 6/9, LinkedList,反转与删除
    • 6/11, LinkedList 杂题
    • (FB) 链表的递归与倒序打印
  • LinkedIn 面经,算法题
    • 6/17, LinkedIn 面经题
    • 6/28, LinkedIn 面经题
    • 7/6, LinkedIn 面经
    • Shortest Word Distance 类
    • DFA Parse Integer
  • Two Pointers,双指针
    • 3 Sum, 3 Sum Closest / Smaller, 4 Sum
    • 对撞型,灌水类
    • 对撞型,partition类
    • Wiggle Sort I & II
    • 双指针,窗口类
    • 双指针,窗口类
    • Heap,排序 matrix 中的 two pointers
  • Bit & Math,位运算与数学
    • Bit Manipulation,对于 '1' 位的操作
    • Math & Bit Manipulation, Power of X
    • 坐标系 & 数值计算类
    • Add Digits
    • 用 int 做字符串 signature
  • Interval 与 扫描线
    • Range Addition & LCS
    • 7/5, Interval 类,扫描线
  • Trie,字典树
    • 6/9, Trie, 字典树
  • 单调栈,LIS
    • 4/13 LIS
    • 栈, 单调栈
    • Largest Divisible Subset
  • Binary Search 类
    • Matrix Binary Search
    • Array Binary Search
    • Find Peak Element I & II
    • **Median of Two Sorted Arrays
  • Graph & Topological Sort,图 & 拓扑排序
    • 有向 / 无向 图的基本性质和操作
    • 拓扑排序, DFS 做法
    • 拓扑排序, BFS 做法
    • Course Schedule I & II
    • Alien Dictionary
    • Undirected Graph, BFS
    • Undirected Graph, DFS
    • 矩阵,BFS 最短距离探索
    • 欧拉回路,Hierholzer算法
    • AI, 迷宫生成
    • AI, 迷宫寻路算法
    • (G) Deep Copy 无向图成有向图
  • 括号与数学表达式的计算
  • Iterator 类
  • Majority Element,Moore's Voting
  • Matrix Inplace Operations
  • 常见数据结构设计
  • (G) Design / OOD 类算法题
  • 随机算法 & 数据结构
  • (FB) I/O Buffer
  • (FB) Simplify Path, H-Index I & II
  • (FB) Excel Sheet, Remove Duplicates
  • Integer 的构造,操作,序列化
  • Frequency 类问题
  • Missing Number 类,元素交换,数组环形跳转
  • 8/10, Google Tag
  • (FB) Rearrange String k Distance Apart
  • Abstract Algebra
    • Chap1 -- Why Abstract Algebra ?
    • Chap2 -- Operations
    • Chap3 -- The Definition of Groups
Powered by GitBook
On this page
  • Two Sum III - Data structure design
  • 需要注意的 corner case 是,[add(0), find(0)],这类情况,还有 [add(2), add(2), find(4)] 这类。
  • Quick-Find:
  • 事实证明,拿到 iterator 手动 iter.next 要比直接用 enhanced for loop 快。
  • Quick-Add:
  • Text Justification

Was this helpful?

  1. LinkedIn 面经,算法题

6/28, LinkedIn 面经题

Previous6/17, LinkedIn 面经题Next7/6, LinkedIn 面经

Last updated 4 years ago

Was this helpful?

这是个典型的 data structure design trade off 问题,因为 add() 和 find() 函数总有一个会很慢,问题在于让那个慢,就要取决于具体的 workload. 真问到这种问题一定要先问清楚。

需要注意的 corner case 是,[add(0), find(0)],这类情况,还有 [add(2), add(2), find(4)] 这类。

Quick-Find:

public class TwoSum {

    HashSet<Integer> num = new HashSet<>();
    HashSet<Integer> sum = new HashSet<>();

    // Add the number to an internal data structure.
    public void add(int number) {
        if(num.contains(number)) {
            sum.add(number * 2);
        } else {
            Iterator<Integer> iter = num.iterator();
            while(iter.hasNext()){
                int num = iter.next();
                sum.add(num + number);
            }
            num.add(number);
        }
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        return sum.contains(value);
    }
}

事实证明,拿到 iterator 手动 iter.next 要比直接用 enhanced for loop 快。

Quick-Add:

public class TwoSum {

    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    // Add the number to an internal data structure.
    public void add(int number) {
        if(map.containsKey(number)){
            map.put(number, 2);
        } else {
            map.put(number, 1);
        }
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        Iterator<Integer> iter = map.keySet().iterator();

        while(iter.hasNext()){
            int key = iter.next();
            if(map.containsKey(value - key)){
                if(key != value - key || map.get(key) == 2) return true;
            }
        }
        return false;
    }
}

这题不怎么考算法思想和数据结构,就是看你怎么处理各种 test case 以及字符串边边角角的细节问题。。

假如 L = 10 的话,我们需要重点考虑的是这么几种情况;

  • x x x _ _ x x _ x x

  • x x x x x _ _ _ _ _

  • x x x _ x _ x _ x _

  • 每一行最左面肯定是填满的,没有空余;

  • 每一个单词后面都要空格分开,结尾除外;

  • 每一行最右面可能正好填满,也可能有空格;

  • 如果正好到了最后一个单词,或者连续两个大单词无法 fit 到同一行,则只有一个单词,后面全是空格;

于是我们的设计思路围绕着这几种情况考虑:

  • 维护目前空间占用,如果下一个单词放不下了就开始在 [start, end] 区间内构造单词

  • 让每个单词自带一个空格占用

  • 为了应对一个单词正好占满整行的情况,起始空间占用为 -1,此后依次增加 word[i].length + 1;

进入填词阶段:

  • 每个单词后面的空格数为标准 space + extra,其中 space 默认为 1, extra 默认为 0;

  • 如果不是一行只有一个单词的情况,则根据 gap 数计算 space 与 extra 值;

    • space = (剩余空间 / gap 数) + 1;

    • extra = (剩余空间 % gap 数);

  • 启动 StringBuilder,先把第一个单词填上;

  • 而后进入循环按照 space 与 extra 数填充;extra 最坏情况下也只会在一个单词后面多加上一个;

  • 如果是一个单词一行的情况,则计算剩余空白,都填上空格。

  • 设立新起点,新一轮扫描。

public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> list = new ArrayList<String>();

        int N = words.length;
        int right = 0;
        for(int left = 0; left < N; left = right){
            // Each word comes with one space;
            // Except the first word, so start with -1.
            int len = -1;
            for(right = left; right < N && len + words[right].length() + 1 <= maxWidth; right ++){
                len += words[right].length() + 1;
            }

            // Those are in case there's only one word picked, or in last line
            int space = 1;
            int extra = 0;
            if(right != left + 1 && right != N){
                // right - left - 1 is number of gaps
                space = (maxWidth - len) / (right - left - 1) + 1;
                extra = (maxWidth - len) % (right - left - 1);
            }
            StringBuilder sb = new StringBuilder(words[left]);
            for(int i = left + 1; i < right; i++){
                for(int j = 0; j < space; j++) sb.append(' ');
                if(extra-- > 0) sb.append(' ');
                sb.append(words[i]);
            }

            int rightSpace = maxWidth - sb.length();
            while(rightSpace-- > 0) sb.append(' ');
            list.add(sb.toString());
        }

        return list;
    }
}

Two Sum III - Data structure design
Text Justification