题目

给定两个有序链表的头指针head1和head2, 打印两个链表的公共部分.
链表使用如下结构:

1
2
3
4
5
6
7

public class Node {
    public int value;
    public Node next;
    public Node(int data) {
        this.value = data;
    }
}

思路

• head1 < head2, head1后移
• head1 > head2, head2后移
• head1 = head2, 打印value, head1和head2同时后移
• 阅读全文 »

题目

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

题目

一个栈中的元素类型为整型, 现在想将栈从顶到底按从大到小的顺序排序, 只需申请一个栈.
除此之外, 可以申请新的变量,但不能申请额外的数据结构, 如何完成排序?

思路

• 利用两个栈+临时变量, 通过比较, 使得辅助栈中元素有序
  申请一个辅助栈, 将原始栈的元素挨个取出, 通过比较最终使得辅助栈内的元素顶->底, 小->大排序.

  阅读全文 »

题目

宠物、狗和猫的类如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Pet {
    private String type;

    public Pet(String type) {
      this.type = type;
    }

    public String getPetType() {
      return this.type;
    }
  }

  public class Dog extends Pet {
    public Dog() {
      super("dog");
    }
  }

  public class Cat extends Pet {
    public Cat() {
      super("cat");
    }
  }

实现一种猫狗队列的结构, 要求如下:

题目

实现栈中元素的逆序, 但是只能用递归函数来实现, 不能使用其它数据结构.

思路

递归获取栈底元素

题目

编写一个类, 用两个栈实现队列, 支持队列的基本操作(add, poll, peek).

思路

栈是FILO, 队列是FIFO.
一个栈stackPush按用户操作顺序存储, 提供入队操作.
另一个栈stackPop按照相反顺序存储, 提供出队操作.

题目

实现一个特殊的栈, 在实现栈的基本功能的基础上, 再实现返回栈中最小元素的操作.

要求

1. pop, push, getMin操作的时间复杂度都是O(1)
2. 设计的栈类型可以使用现有的栈结构

思路

先考虑下getMin的特殊情况

1. 应该有一个数据结构能存储,并在入栈和出栈时都要维护当前最小值
2. 可以用另一个栈来存储当前的最小值.
   阅读全文 »

一. 背景

日志收集面临诸多难题：

• 数据源种类繁多： 各服务产生日志格式不同，产生的方式也不同（本地文件，HTTP远程发送等）
• 数据源是物理分布的： 日志是在分布式机器上，甚至跨机房
• 流式的、不间断产生： 有些日志需要实时或近实时收集到，以供后端分析挖掘
• 对可靠性有一定要求
  阅读全文 »

Block的副本放置策略

• 第一个副本: 放置在上传文件的DataNode; 如果是集群外提交, 随机挑选一台 磁盘不太满, CPU不太忙的节点
• 第二个副本: 放置在跟第一个副本不同机架的节点上(容灾备份)
• 第三个副本: 尽量跟第二个副本相同机架(节约网络资源)
• 更多副本: 随机节点

深入理解事务

ACID的含义

原子性（Atomicity）

在出错时中止事务， 并将部分完成的写入全部丢弃

可中止性。简化了排错过程，事务如果中止， 应用可以安全地重试

一致性(Consistency)

对数据有特定的预期状态， 任何数据更改必须满足这些状态约束（或者恒等条件）

本质上要求应用层来维护一致

应用程序可能借助数据库提供的原子性和隔离性， 以达到一致性， 但一致性本身并不源于数据库