由买买提看人间百态

topics

全部话题 - 话题: nret
(共0页)
w****x
发帖数: 2483
1
一直认为面试出这么难得题真是过分啊!!
================= kth element in young tablet (M+N)log(numeric range)
solution ===========
const int M = 4;
const int N = 4;
int getOrder(int A[M][N], int tg)
{
int c = 0;
int i = 0;
int j = N-1;
while (i < M && j >= 0)
{
if (A[i][j] >= tg)
j--;
else
{
c += j+1;
i++;
}
}
return c+1;
}
int getKthMin(int A[M][N], int k)
{
if (k <= 0 || k > M*N)
return INT_MIN;
int nBe... 阅读全帖
w****x
发帖数: 2483
2
来自主题: JobHunting版 - 今天面的太惨了....
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
int getHeight(NODE* pNode, bool bLft)
{
int nRet = 0;
NODE* pIter = pNode;
while (NULL != pIter)
{
if (bLft)
pIter = pIter->pLft;
else
pIter = pIter->pRgt;
nRet++;
}
return nRet;
}
int getNum(int h)
{
return pow((double)2, h) -1;
}
int getNumberOfNodes(NODE* pRoot)
{
NODE* pNode = pRoot;
int h = get... 阅读全帖
w****x
发帖数: 2483
3
来自主题: JobHunting版 - 为什么做了400道算法题还是那么菜

不知道有没有其他bug
int myatoi(const char* p)
{
assert(p);
int nFlg = 1;
if ('-' == *p)
nFlg = -1;
if ('-' == *p || '+' == *p)
p++;
if ('\0' == *p)
throw CException("Invalid expression");
int nRet = 0;
while('\0' != *p)
{
if (*p < '0' || *p > '9')
throw CException("Invalid character");
int nVal = *p - '0';
int nNew = nRet*10 + nFlg * nVal;
if (nRet != 0 && ((nNew & 0x80000000) != (nRet & 0x80000000)))
... 阅读全帖
w****x
发帖数: 2483
4
来自主题: JobHunting版 - 发个一直没有见过满意答案的题吧

那个因该不是最优解,但是想法蛮独特的,是csdn上一个人告诉我的,后来我实现了一
下,很久以前做的。
===============================================================
// Find the kth element in young table
// young table is a two dimensional matrix with its rows and columns sorted
// Solution
// It's hard to find the kth element directly, but its easy to find how many
elements are smaller than a given number.
// So, use binary search to find a number which is bigger than k elements in
the young table. Then, travel through
// the table to the ele... 阅读全帖
w****x
发帖数: 2483
5
N queen
int _inner_get_ways(int pRec[], int n, int nCur)
{
if (nCur >= n)
return 1;
int nRet = 0;
for (int i = 0; i < n; i++)
{
bool bNoneAttack = true;
for (int j = 0; j < nCur && bNoneAttack; j++)
{
if (pRec[j] == i || abs(nCur - j) == abs(i - pRec[j]))
bNoneAttack = false;
}
if (bNoneAttack)
{
pRec[nCur] = i;
nRet += _inner_get_ways(pRec, n, nCur+1);
}
}
... 阅读全帖
w****x
发帖数: 2483
6
来自主题: JobHunting版 - N queen problem 很难想啊
int _inner_get_ways(int pRec[], int n, int nCur)
{
if (nCur >= n)
return 1;
int nRet = 0;
for (int i = 0; i < n; i++)
{
bool bNoneAttack = true;
for (int j = 0; j < nCur && bNoneAttack; j++)
{
if (pRec[j] == i || abs(nCur - j) == abs(i - pRec[j]))
bNoneAttack = false;
}
if (bNoneAttack)
{
pRec[nCur] = i;
nRet += _inner_get_ways(pRec, n, nCur+1);
}
}
return n... 阅读全帖
w****x
发帖数: 2483
7
来自主题: JobHunting版 - 直方图下雨这道题怎么解?
int CalculateContain(int a[], int n)
{
assert(a && n > 0);
int nRet = 0;
stack stk;
for (int i = 0; i < n; i++)
{
if (!stk.empty() && a[stk.top()] < a[i])
{
int nPrev = stk.top();
stk.pop();
while (!stk.empty() && a[stk.top()] <= a[i])
{
int nCur = stk.top();
stk.pop();
int nLimit = a[nCur] <= a[i] ? a[nCur] : a[i];
nRet += (nLimit - a[nPrev]) *... 阅读全帖
w****x
发帖数: 2483
8
来自主题: JobHunting版 - 刚才重新回顾了一下那题
struct NODE
{
vector vecGUID;
NODE* nodes[256];

NODE() { memset(nodes, 0, sizeof(nodes)); }
};
void _inner_get_guid(NODE* pNode, const char* str, int k, vector& vec)
{
if (NULL == pNode)
return;
if (k <= 0)
{
vec = pNode->vecGUID;
return;
}
_inner_get_guid(pNode->nodes[*str], str+1, k-1, vec);
}
vector getGUID(const char* str, NODE* pRoot, int k)
{
vector vecRet;
if (NULL == pRoot || NULL == str || *str == 0 ... 阅读全帖
w****x
发帖数: 2483
9
来自主题: JobHunting版 - 罗马转数字,数字转罗马问题

//Turn Roman number to decimal
//I(1), V(5), X(10), L(50), C(100), D(500), M(1000)
int GetNum(char c)
{
if (c == 'I' || c == 'i')
return 1;
else if (c == 'V' || c == 'v')
return 5;
else if (c == 'X' || c == 'x')
return 10;
else if (c == 'L' || c == 'l')
return 50;
else if (c == 'C' || c == 'c')
return 100;
else if (c == 'D' || c == 'd')
return 500;
else if (c == 'M' || c == 'm')
return 1000;

return 0;
}
... 阅读全帖
w****x
发帖数: 2483
10
/*
Say you have an array for which the ith element is the price of a given
stock on day i.
Design an algorithm to find the maximum profit. You may complete as many
transactions as you like (ie, buy one and sell one share of the stock
multiple times). However, you may not engage in multiple transactions at the
same time (ie, you must sell the stock before you buy again).
*/
class Solution {
public:
int maxProfit(vector &a) {

int n = a.size();
int* rec = new int[n]... 阅读全帖
w****x
发帖数: 2483
11
发现这道题属于没见过肯定想不出来,知道怎么解也很难写对。昨天重新写了一下,觉
得学到蛮多的,分享一下。
以前写过一个很挫的DP版本:
int GetEditDist(const char* str1, const char* str2)
{
assert(str1 && str2);
int nLen1 = strlen(str1);
int nLen2 = strlen(str2);
int* rec = new int[nLen2];
bool bFound = false;
for (int i = 0; i < nLen2; i++)
{
if (str2[i] == str1[0])
bFound = true;
rec[i] = bFound ? i : i+1;
}
bFound = (str2[0] == str1[0]); //(str2[0] == str1[0]) not false
for (int i = 1; i < nLe... 阅读全帖
w***o
发帖数: 109
12
来自主题: JobHunting版 - 罗马转数字,数字转罗马问题
倒着来想法很新颖,但好像有问题,比如 IVX = (V - I) + X, not (X - V - I)

const char* pIter = szNum + nLen - 1;
int nRet = 0;
int nPrev = 0;
while (pIter >= szNum)
{
int nCur = GetNum(*pIter);
if (nCur >= nPrev)
nRet += nCur;
else nRet -= nCur;
nPrev = nCur;
pIter--;
}
w****x
发帖数: 2483
13
来自主题: JobHunting版 - 被thank you的fb电面面经
int _inner_ways(const char* pStr)
{
if (*pStr == 0)
return 1;
if (*pStr <= '0' || *pStr > '9')
return 0;
int n = _inner_ways(pStr+1);
if ((*pStr == '1' && *(pStr + 1) >= '0' && *(pStr + 1) <= '9')
|| (*pStr == '2' && *(pStr + 1) >= '0' && *(pStr + 1) <= '6'))
n += _inner_ways(pStr+2);
return n;
}
int GetWays(const char* pStr)
{
if (NULL == pStr || *pStr == 0)
return 0;
return _inner_ways(pStr);
}
int GetWaysDP(const char* pStr)
... 阅读全帖
w****x
发帖数: 2483
14
来自主题: JobHunting版 - 比较久之前T家的面试
vector getJumpSteps(int nCur, int nMaxStep)
{
vector vec;
if (nCur <= 0 || nMaxStep < nCur)
return vec;
int flg = 1;
while (nCur + flg <= nMaxStep)
{
vec.push_back(nCur + flg);
flg = (flg << 1);
}
flg = 1;
while (nCur - flg > 0)
{
vec.push_back(nCur - flg);
flg = (flg << 1);
}
return vec;
}
int getMinStep(int n, int nMaxStep)
{
if (n <= 0 || nMaxStep < n)
return -1;
int* rec = new int[nM... 阅读全帖
d**********x
发帖数: 4083
15
来自主题: JobHunting版 - 比较久之前T家的面试
应该没问题,和coldknight的程序在2-10000之内做了对比,结果完全一致。他的
nMaxStep我设置为了2 * target,不知道会不会引起问题。
在纸面上也做了不太严格的证明。。这样复杂度就是O(logn)。
对比程序:(前半部分还是coldknight的)
#include
#include
#include
using namespace std;
vector getJumpSteps(int nCur, int nMaxStep)
{
vector vec;
if (nCur <= 0 || nMaxStep < nCur)
return vec;
int flg = 1;
while (nCur + flg <= nMaxStep)
{
vec.push_back(nCur + flg);
flg = (flg << 1);
}
flg = 1;
while (nCur - ... 阅读全帖
(共0页)