s*******s
发帖数: 1031 | 1 follow一下我的面经。
http://www.mitbbs.com/article_t/JobHunting/32517841.html
整理了我的几个解答的算法，分享一下。欢迎批评指正。
多谢！
1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
我用的递归+数组大数乘法。
// Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
// Note: the integer numbers are in reversed in the array
// Assume: m>0, n>0, k>0
// Need to check validity outside of this function.
// call calculate(5, 1234566789893943, 1000) to get result.
// Time complexity: O((log n) * k * k)
// Space complexity: O((log n) * k)
vector calculate(unsigned long m, unsigned long n, int k) {
if(k == 0) {
return vector(1, 1);
} else if(k % 2) { // odd number
vector tmp(1, m);
vector result1 = calculate(m, n-1, k);
return multiplyArrays(result1, tmp, k);
} else {
vector result1 = calculate(m, n/2, k);
return multiplyArrays(result1, result1, k);
}
}
vector multiplyArrays(const vector &data1, const
vector &data2, int k) {
vector result;
int sz1 = data1.size();
int sz2 = data2.size();
for(int i=0; i
const char carry = 0;
for(int j=0; j
// we only keep result[0....k-1]
if(i+j+1 > k)
break;
const char value = data1[i] * data2[j];
//if(result.size() < i+j+1) {
while(result.size() < i+j+1) {
result.push_back(0);
}
value += result[i+j] + carry;
carry = value/10;
result[i+j] = value % 10;
}
if(i+sz2<=k && carry) {
while(result.size() < i+sz2) {
result.push_back(0);
}
result[i+sz2-1] += carry;
}
}
return result;
}
2. Given a integer array, test if there is any consequel subarray which sum
of elements is 0.
[7, 1, 1, -2, 3, 4] ==> true [1, 1, -1]
bool validArray(const vector &data) {
unordered_set M;
long long sum = 0;
for(int i=0; i
sum += data[i];
if(M.find(sum) != M.end())
return true;
M.insert(sum);
}
return false;
}
3. 密码锁问题，实现最短密码问题，版上有讨论。
这个题可以这么描述：
一个数字串有4个数字，每个数字是 0 ~9 这10个数字。
那么一共有0000 ~ 9999 共10,000个串。
要求：找出一个最短的串，包含这10，000个数字串
// Assume memory is not an issue here.
// It is easy to find a memory efficiency way
string calculate() {
// assume all the strings are in an array vector input;
string result;
for(int i=0; i
result = input[i];
unordered_set visited;
bool succeed = DFS(visited, input[i], result);
if(succeed)
return result;
}
// Can not generate!
return "";
}
bool DFS(unordered_set &visited, const string &node, string &
result) {
visited.insert(node);
if(visited.size() == 10000)
return true;
string nodeseg = node.substr(1, 3);
for(int i=0; i<10; ++i) {
char ch = '0' + i;
string nextNode = nodeset;
nextNode.push_back(ch);
if(visited.find(nextNode) != visited.end()) {
result.push_back(ch);
bool bSucceed = DFS(visited, nextNode, result);
if(bSucceed)
return true;
result.pop_back();
}
}
visited.erase(node);
return false;
} | u*****o
发帖数: 1224 | | c**********9
发帖数: 12 | | z*********8
发帖数: 2070 | | w*****n
发帖数: 98 | 5 这个密码锁的代码，似乎只是找到一个可行解，而不是最优解？
【在 s*******s 的大作中提到】
: follow一下我的面经。
: http://www.mitbbs.com/article_t/JobHunting/32517841.html
: 整理了我的几个解答的算法，分享一下。欢迎批评指正。
: 多谢！
: 1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
: 我用的递归+数组大数乘法。
: // Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
: // Note: the integer numbers are in reversed in the array
: // Assume: m>0, n>0, k>0
: // Need to check validity outside of this function.
| e*******8
发帖数: 94 | 6 第一题果然是要用fast exponentiation。。。。不过电面中竟然会要写数组大数乘法
啊-_-bbbb | c********p
发帖数: 1969 | | c*****e
发帖数: 59 | | j*******o
发帖数: 22 | 9 第一题的unsigned long要改为unsigned long long才行吧 | c********e
发帖数: 186 | | | | h*****7
发帖数: 103 | 11 请问第二题中，数字特别多时候就会溢出或者空间爆掉吧？
有没有可能有常数空间，也低于平方时间复杂度的解法？ | x***y
发帖数: 633 | 12 For the "password" lock problem, the best solution is to use graph;
each number is a node, the directed edges between 2 nodes indicate extra
cost
if the dest comes after the source
for example "0000" to "0001" will be 1 while "0001" to "0000" is 4
Then problem becomes a hamilton path (np essentially) | c********e
发帖数: 186 | 13 难道理解有误？密码锁这个肯定可以generate吧，就是字符穿多长的问题吧 | s***e
发帖数: 403 | 14 第一题，首先分而治之处理。然后乘数大到一定程度时候只保留最后500位就可以了。 | s***e
发帖数: 403 | | s***e
发帖数: 403 | 16 跟我想得一样，hamilton路径问题。NP。
【在 x***y 的大作中提到】
: For the "password" lock problem, the best solution is to use graph;
: each number is a node, the directed edges between 2 nodes indicate extra
: cost
: if the dest comes after the source
: for example "0000" to "0001" will be 1 while "0001" to "0000" is 4
: Then problem becomes a hamilton path (np essentially)
| s*******s
发帖数: 1031 | 17 follow一下我的面经。
http://www.mitbbs.com/article_t/JobHunting/32517841.html
整理了我的几个解答的算法，分享一下。欢迎批评指正。
多谢！
1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
我用的递归+数组大数乘法。
// Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
// Note: the integer numbers are in reversed in the array
// Assume: m>0, n>0, k>0
// Need to check validity outside of this function.
// call calculate(5, 1234566789893943, 1000) to get result.
// Time complexity: O((log n) * k * k)
// Space complexity: O((log n) * k)
vector calculate(unsigned long m, unsigned long n, int k) {
if(k == 0) {
return vector(1, 1);
} else if(k % 2) { // odd number
vector tmp(1, m);
vector result1 = calculate(m, n-1, k);
return multiplyArrays(result1, tmp, k);
} else {
vector result1 = calculate(m, n/2, k);
return multiplyArrays(result1, result1, k);
}
}
vector multiplyArrays(const vector &data1, const
vector &data2, int k) {
vector result;
int sz1 = data1.size();
int sz2 = data2.size();
for(int i=0; i
const char carry = 0;
for(int j=0; j
// we only keep result[0....k-1]
if(i+j+1 > k)
break;
unsigned char value = data1[i] * data2[j];
//if(result.size() < i+j+1) {
while(result.size() < i+j+1) {
result.push_back(0);
}
value += result[i+j] + carry;
carry = value/10;
result[i+j] = value % 10;
}
if(i+sz2<=k && carry) {
while(result.size() < i+sz2) {
result.push_back(0);
}
result[i+sz2-1] += carry;
}
}
return result;
}
2. Given a integer array, test if there is any consequel subarray which sum
of elements is 0.
[7, 1, 1, -2, 3, 4] ==> true [1, 1, -1]
bool validArray(const vector &data) {
unordered_set M;
long long sum = 0;
for(int i=0; i
sum += data[i];
if(M.find(sum) != M.end())
return true;
M.insert(sum);
}
return false;
}
3. 密码锁问题，实现最短密码问题，版上有讨论。
这个题可以这么描述：
一个数字串有4个数字，每个数字是 0 ~9 这10个数字。
那么一共有0000 ~ 9999 共10,000个串。
要求：找出一个最短的串，包含这10，000个数字串
// Assume memory is not an issue here.
// It is easy to find a memory efficiency way
string calculate() {
// assume all the strings are in an array vector input;
string result;
for(int i=0; i
result = input[i];
unordered_set visited;
bool succeed = DFS(visited, input[i], result);
if(succeed)
return result;
}
// Can not generate!
return "";
}
bool DFS(unordered_set &visited, const string &node, string &
result) {
visited.insert(node);
if(visited.size() == 10000)
return true;
string nodeseg = node.substr(1, 3);
for(int i=0; i<10; ++i) {
char ch = '0' + i;
string nextNode = nodeset;
nextNode.push_back(ch);
if(visited.find(nextNode) != visited.end()) {
result.push_back(ch);
bool bSucceed = DFS(visited, nextNode, result);
if(bSucceed)
return true;
result.pop_back();
}
}
visited.erase(node);
return false;
} | u*****o
发帖数: 1224 | | c**********9
发帖数: 12 | | z*********8
发帖数: 2070 | | | | w*****n
发帖数: 98 | 21 这个密码锁的代码，似乎只是找到一个可行解，而不是最优解？
【在 s*******s 的大作中提到】
: follow一下我的面经。
: http://www.mitbbs.com/article_t/JobHunting/32517841.html
: 整理了我的几个解答的算法，分享一下。欢迎批评指正。
: 多谢！
: 1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
: 我用的递归+数组大数乘法。
: // Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
: // Note: the integer numbers are in reversed in the array
: // Assume: m>0, n>0, k>0
: // Need to check validity outside of this function.
| e*******8
发帖数: 94 | 22 第一题果然是要用fast exponentiation。。。。不过电面中竟然会要写数组大数乘法
啊-_-bbbb | c********p
发帖数: 1969 | | c*****e
发帖数: 59 | | j*******o
发帖数: 22 | 25 第一题的unsigned long要改为unsigned long long才行吧 | c********e
发帖数: 186 | | h*****7
发帖数: 103 | 27 请问第二题中，数字特别多时候就会溢出或者空间爆掉吧？
有没有可能有常数空间，也低于平方时间复杂度的解法？ | x***y
发帖数: 633 | 28 For the "password" lock problem, the best solution is to use graph;
each number is a node, the directed edges between 2 nodes indicate extra
cost
if the dest comes after the source
for example "0000" to "0001" will be 1 while "0001" to "0000" is 4
Then problem becomes a hamilton path (np essentially) | c********e
发帖数: 186 | 29 难道理解有误？密码锁这个肯定可以generate吧，就是字符穿多长的问题吧 | s***e
发帖数: 403 | 30 第一题，首先分而治之处理。然后乘数大到一定程度时候只保留最后500位就可以了。 | | | s***e
发帖数: 403 | | s***e
发帖数: 403 | 32 跟我想得一样，hamilton路径问题。NP。
【在 x***y 的大作中提到】
: For the "password" lock problem, the best solution is to use graph;
: each number is a node, the directed edges between 2 nodes indicate extra
: cost
: if the dest comes after the source
: for example "0000" to "0001" will be 1 while "0001" to "0000" is 4
: Then problem becomes a hamilton path (np essentially)
| D**********d
发帖数: 849 | 33 密码锁问题我要是在 G 家 onsite 前看过你的帖子就好了，
当时就想着找数学规律，没有想过用这种 “brute force”.
以下是我回来后写出的代码:
bool DFS(vector & IsVisited, vector & Result, int CurrNum){
if(Result.size() == 10003) return true;
int pre = (CurrNum % 10000) * 10;
for(int i = 0; i < 9; ++i){
int NextNum = pre + i;
if(IsVisited[NextNum] == true) continue;
Result.push_back('0'+i);
IsVisited[NextNum] = true;
if(DFS(IsVisited,Result,NextNum)) return true;
Result.pop_back();
IsVisited[NextNum] = false;
}
return false;
}
// initialize
vector IsVisited(10000,false);
vector Result(4,'0');
DFS(IsVisited,Result,0); | j*******t
发帖数: 223 | 34 第二题貌似这个过不了啊，[-3, 2, 1, 5, 1, -3] | n****e
发帖数: 678 | 35 第一题的code：
function calculate 里面的条件判断应该是：
(n == 0)
(n % 2)
吧
第二题的code：
完全看不懂第二题的codes。 codes有问题吧
【在 s*******s 的大作中提到】
: follow一下我的面经。
: http://www.mitbbs.com/article_t/JobHunting/32517841.html
: 整理了我的几个解答的算法，分享一下。欢迎批评指正。
: 多谢！
: 1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
: 我用的递归+数组大数乘法。
: // Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
: // Note: the integer numbers are in reversed in the array
: // Assume: m>0, n>0, k>0
: // Need to check validity outside of this function.
| n****e
发帖数: 678 | 36 第一题的code：
function calculate 里面的条件判断应该是：
(n == 0)
(n % 2)
吧
第二题的code：
完全看不懂第二题的codes。 codes有问题吧
【在 s*******s 的大作中提到】
: follow一下我的面经。
: http://www.mitbbs.com/article_t/JobHunting/32517841.html
: 整理了我的几个解答的算法，分享一下。欢迎批评指正。
: 多谢！
: 1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
: 我用的递归+数组大数乘法。
: // Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
: // Note: the integer numbers are in reversed in the array
: // Assume: m>0, n>0, k>0
: // Need to check validity outside of this function.
| w**7
发帖数: 22 | 37 Did you test your code? It crashes...
【在 D**********d 的大作中提到】
: 密码锁问题我要是在 G 家 onsite 前看过你的帖子就好了，
: 当时就想着找数学规律，没有想过用这种 “brute force”.
: 以下是我回来后写出的代码:
: bool DFS(vector & IsVisited, vector & Result, int CurrNum){
: if(Result.size() == 10003) return true;
: int pre = (CurrNum % 10000) * 10;
: for(int i = 0; i < 9; ++i){
: int NextNum = pre + i;
: if(IsVisited[NextNum] == true) continue;
: Result.push_back('0'+i);
| c********p
发帖数: 1969 | | l*********b
发帖数: 1541 | 39 result[i+sz2-1] 对不对？ 不是result[i+sz2] 吗？
【在 s*******s 的大作中提到】
: follow一下我的面经。
: http://www.mitbbs.com/article_t/JobHunting/32517841.html
: 整理了我的几个解答的算法，分享一下。欢迎批评指正。
: 多谢！
: 1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
: 我用的递归+数组大数乘法。
: // Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
: // Note: the integer numbers are in reversed in the array
: // Assume: m>0, n>0, k>0
: // Need to check validity outside of this function.
|
|
