suwei19870312
BAN USER#include <iostream>
#include <vector>
using namespace std;
class solution
{
public:
void printMatrix(vector<vector<int> >& ivvMatrix)
{
int n = ivvMatrix.size();
if(n <= 0) return;
int m = ivvMatrix[0].size();
int top = 0, bottom = n -1, left = 0, right = m -1;
while(true)
{
for(int i = left; i<= right; i++ )
{
cout << ivvMatrix[top][i] << ' ';
}
top ++;
if(top > bottom)break;
for(int j = top; j<= bottom; j++)
cout << ivvMatrix[j][right] << ' ';
right --;
if(right < left) break;
for(int i = right; i>= left; i--)
cout << ivvMatrix[bottom][i] << ' ';
bottom --;
if(bottom < top) break;
for(int j = bottom; j>= top; j--)
cout << ivvMatrix[j][left] << ' ';
left ++;
if(right < left)
break;
}
}
};
int main() {
// your code goes here
int m, n, a;
cin >> m >> n;
vector<vector<int> > lvvMatrix(n, vector<int>(m, 0));
for(int i = 0; i< n; i++)
{
for(int j = 0; j< m; j++)
{
cin >> lvvMatrix[i][j];
}
}
solution mS;
mS.printMatrix(lvvMatrix);
return 0;
}
I think for each person, the contact list will not so large, so I think brute string match can handle this problem.
- suwei19870312 November 19, 2014I like this solution, dfs to seach mine cluster.
- suwei19870312 November 18, 2014thanks for your solution
- suwei19870312 November 10, 2014Count every bit of the element in this array, after Count, then mode 3, so the left bit should be the element which appear once.
int GetSingleNumber(vector<int>& irvector)
{
vector<int> lvBitCount;
for(int i = 0; i< irvector.size(); i++)
{
int Cur = irvector[i];
int BitC = 0;
while(Cur)
{
if(Cur & 1)
{
while(BitC >= lvBitCount.size())
{
lvBitCount.push_back(0);
}
lvBitCount[BitC] += 1;
}
Cur = Cur >> 1;
BitC ++;
}
}
reverse(lvBitCount.begin(), lvBitCount.end());
int result = 0;
for(int i = 0; i< lvBitCount.size(); i++)
{
lvBitCount[i] = lvBitCount[i] % 3;
result = (result << 1) + lvBitCount[i];
}
return result;
}
I think the interviewer ask this problem is to check the knowledge of read file.
need to use the way to reduce the system call time.
so mmap() is good choice I think.
use simple LRU strategy cache, or use memcached.
for the read operation, it check the Cache first,
if hit the cache, it return the value directly.
if can not hit the cache, it need to read from the Database, and reset the the KV to the Cache.
for the write operation, it should delete the KV in the cache first, to make sure no one will hit the stale data, then write the KV to the Database.
wish it can help.
thank your for your answer.
- suwei19870312 July 04, 2014template pattern
- suwei19870312 July 03, 2014actually I am not so understand the question.
does this question is ask how to make trie tree become scalability if there has so much long string?
trie structure can handle huge string input with short length. but if the string length is large, which will make trie become buge,
so in this case, we can build sub trie on sub machine,
for web site, the major component is web server, database, also may need some cache level to speed the access.
and the way the web server connect with user should be https protocal with encode body to make sure user account is save.
for scalling problem to support more user access, we should add more database server, and use some strategy to move user info to different database server, may be use location to partition user to there own database server,
for the database server goes down problem, we should add duplicate database server for each master database server. when master database server is down, we can use duplicate database server replace the master server. and also it will lead to data Sync problem.
I think GeoHash can help to solve this problem.
for each position on the map, can use the GeoHash to encode the position to an string.
so for each location, we will store , geohash Key, location.
and the benefit of geohash is the near location will has the same prefix of the hash key.
which can help to fast get the near location from Data base.
with select location where hashKey likes "hashkey prefix"
here are some basic Idea.
1. there should has many file server, which used to store data from user client.
2. master web server tell user client send the file to which file server. and save the file with encode name, or even data encode.
3. and use the encode name and file server to generate url, user then can use this url to access the text.
4. there should has account service, which used to make sure this user's storage limitation.
5. there should has duplicate logic, which make sure the file is can not access because file server down.
good solution.
- suwei19870312 June 16, 2014I think the most direct way is build hash on title, on category, on author,
for example hash on title, need to store the map<title, Product Num>,
we can use same strategy,
we can use queue to store data, every time, we read 2 data into the queue, than remove 1 data out of queue,
so at the end of the stream. we will get the middle element in front of the queue, and we need to store n/2 element.
class strshift
{
string mStr;
public:
strshift()
{
}
strshift(char* istr):mStr(istr)
{
}
string operator << (int n)
{
n = n% mStr.length();
if(n == 0)
return mStr;
return (mStr + mStr).substr(mStr.length() -n, mStr.length());
}
};
here some basic idea:
1. There are more users than can fit in the cache.
which means the cache can not fit all the users, we need use some strategy
to remove useless user, may be LRU, or some thing else.
so in the Cache layer, we have to store the (user ID, User login time, visit time)
2. There are far more calls to the service than users in the database.
3. There are other programs that update the database other than this one.
which means the data in the database maybe not consistence with the data in the cache, so we need think of way to make the data consistence.
so if we can not control other program to update the database, we can modify the setLastLoginForUser() function to update the Cache when other program want to update database, which make sure consistence.
may be you can use enum type in class instead const.
- suwei19870312 June 12, 2014I think we need to move the right car to the empty pos, in this way, we can move with min swap.
if in some case, empty pos is in right pos, but there still some car in wrong pos, we need to move this wrong car to empty pos, then still with this rule, move right car to the empty pos.
for example:
expected pos:
1 4 5 2 3 6 9 _ 7 8
but init car pos:
1 5 7 3 9 _ 2 4 6 8
==>> move 6 to the empty pos:
1 5 7 3 9 6 2 4 _ 8
=>> move 7 to empty pos:
1 5 _ 3 9 6 2 4 7 8
1 _ 5 3 9 6 2 4 7 8
1 4 5 3 9 6 2 _ 7 8
==> in this case empty pos is in right pos. but there are still some car in wrong place.
1 4 5 _ 9 6 2 3 7 8
1 4 5 2 9 6 _ 3 7 8
1 4 5 2 _ 6 9 3 7 8
1 4 5 2 3 6 9 _ 7 8
10 swaps.
I think we can use rand5 to implementation rand2 and rand10 first.
int rand2()
{
int k = 0;
do
{
k= rand5();
}
while(k > 2);
return k;
}
int rand10()
{
return rand2() * 5 + rand5();
}
for the rand7(). we can use rand10 to implementation:
int rand7()
{ k = 0;
do
{
k = rand10();
}while(k > 7);
return k;
}
if cnode->left and cnode->right both Null, there has noting need to be done, just set cnode->parent's left or right is NULL.
if cnode->left is not Null, you need to find the left tree's right most one node(which is the largest node in left tree), and delete it, and replace cnode with that node.
if cnode->right is not Null, you need to find the right tree's left most node(which is the largest node in right tree), and delete it, and replace cnode with that node.
wish this can help
the question is a little confuse.
here has some idea.
if the question is ask to count number of all the words in the matrix, we can use Trie tree to help to count the number for all the words.
if he quesion is ask to count number of given word, we can directly DFS.
I think if Sum2 == Sum1, there has no need to continue search.
- suwei19870312 April 10, 2014class Solution
{
public:
int GetMinCoins(vector<int>& coins, int Sum)
{
if(Sum <= 0) return 0;
vector<int> lvdp(Sum + 1, INT_MAX);
lvdp[0] = 0;
hGetMinCoins(coins, Sum, lvdp);
return lvdp[Sum] == INT_MAX? -1: lvdp[Sum];
}
void hGetMinCoins(vector<int>& coins, int leftSum, vector<int>& ovdp)
{
if(ovdp[leftSum] != INT_MAX) return;
for(int i = 0; i< coins.size(); i++)
{
if(leftSum >= coins[i])
{
hGetMinCoins(coins, leftSum - coins[i], ovdp);
if(ovdp[leftSum - coins[i]] < INT_MAX)
ovdp[leftSum] = min(ovdp[leftSum], ovdp[leftSum - coins[i]] + 1);
}
}
}
};
please try the input(2, 4, 6, 9, 5, 10)
the output should be (-1, 1, 2, 3, 2, 5)
some basic Idea. welcome comment.
1, define abstractChessPiece.
class abstractChessPiece
{
define PieceType.
define the target typePiece it can beat.
define move() function.
}
2. for each type of concreteChessPieces, need to inherit from abstractChessPiece to define there own PieceType, and target TypePiece, and move behavior.
3. for the ChessBoard,
need to define function to create ChessPieces suit for one side and for the other side.
need hold these ChessPieces and postition for each Pieces.
need to define Move function, and check this move is legal or not, and one side win or not.
you can use hash_table to do the group job.
- suwei19870312 December 01, 2014use the list2<sex, occupation> as the key, and the value will the index in the list1.
so after iterator the list1, you will get the group by result.