rank-from-stream-lcci

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。

英文版：Cracking the Coding Interview，源自硅谷程序员的面试红宝书

LCCI

Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number <code>x</code> (the number of values less than or equal to <code>x</code>). lmplement the data structures and algorithms to support these operations. That is, implement the method <code>track (int x)</code>, which is called when each number is generated, and the method <code>getRankOfNumber(int x)</code>, which returns the number of values less than or equal to <code>x</code>.

Note:&nbsp;This problem is slightly different from the original one in the book.

Example:

<pre>
Input:
[&quot;StreamRank&quot;, &quot;getRankOfNumber&quot;, &quot;track&quot;, &quot;getRankOfNumber&quot;]
[[], [1], [0], [0]]
Output:
[null,0,null,1]
</pre>

Note: 

<ul>
	<li><code>x &lt;= 50000</code></li>
	<li>The number of calls of both&nbsp;<code>track</code>&nbsp;and&nbsp;<code>getRankOfNumber</code>&nbsp;methods are less than or equal to 2000.</li>
</ul>

Rank from Stream LCCI

Design

Binary Indexed Tree

Binary Search

Data Stream

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

实现 <code>track(int x)</code>&nbsp;方法，每读入一个数字都会调用该方法；

实现 <code>getRankOfNumber(int x)</code> 方法，返回小于或等于 x 的值的个数。

注意：本题相对原题稍作改动

示例：

<pre>
输入：
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出：
[null,0,null,1]
</pre>

提示：

<ul>
	<li><code>x &lt;= 50000</code></li>
	<li><code>track</code>&nbsp;和&nbsp;<code>getRankOfNumber</code> 方法的调用次数均不超过 2000 次</li>
</ul>