## Saturday, November 28, 2015

### Random Flip false to true - Google Interview

1. 给一个2D matrix，bool 型，初始状态是都是false,要求写一个flip函数，实现把其中一个element由false变成true。 要求是所有false element被翻转的概率相等。
-- flip will be called repeatedly
1. 应该是random with blacklist，2维转1维,（i,j)->(i*n+j). from: 1point3acres.com/bbs

void flip(vector<vector<bool>> & matrix) {
int row = matrix.size();
if (row == 0) return;
int col = matrix.size();
if (col == 0) return;
vector<pair<int,int>> co;  // stores all the false elements’ coordinates
for (int i=0;i<row;i++) {
for (int j=0;j<col;j++) {
if (matrix[j] == false) co.push_back(make_pair<i,j>);
}
}
myFlip(matrix,co);
}

void myFlip(vector<vector<bool>> & matrix, vector<pair<int,int>> & co) {
int total = co.size();
int ran = rand()%total;  // generate a number between 0 and total-1
inr r = co[ran].first;
int c = co[ran].second;
matrix[r][c] = true;
co.erase(co.begin() + ran);  // erase (r ,c)
return;
}

0 1 0 0
1 0 0 1
0 0 1 0

[3 5 9]

When can't use extra space, 用reservior resampling

private static void flip(boolean[][] table){
int count = 1;
int m = table.length;
int n = table[0].length;

int[] index = new int[]{-1, -1};
Random r = new Random();

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(table[i][j] == false){
int x = r.nextInt(count);
if(x == 0){
index[0] = i;
index[1] = j;
}

count++;
}
}
}

if(index[0] != -1){
table[index[0]][index[1]] = true;
}
}