There are two main reasons to use concurrency in an application:
#include <stack>
#include <vector>
static bool is_pop_order (std::vector<int>& pushV, std::vector<int>& popV)
{
/*
* 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
* 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
* 序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
* （注意：这两个序列的长度是相等的）
* ------------------------------
* Given two integer sequences, one is push sequence of stack.
* Please justify if the other one is a possible popup sequence of stack.
* Assume all pushed numbers are different. eg. 1,2,3,4 is stack's push sequence,
* 4,5,3,2,1 is a possible popup sequence while 4,3,5,1,2 is not a possible popup sequence
*
* Given pushV 1234, popV 4321
* train of thought:
* Use another stack to simulate pushs and pops
* for ele0 in popV:
* for ele1 in pushV:
* if ele1 is not ele0:
* push to stack tmp # tmp stack can be 123 when visiting all eles in pushV()
* if ele1 is last ele in popV:
* compare each ele in tmep stak with ele0:
* if not equal:
* then return false
* else:
* pop tmp stack
* return true if temp stack empty else false
*/
if (pushV.empty ())
return false;
std::stack<int> tmp;
int pushsize = pushV.size ();
int popsize = popV.size ();
int j = 0;
for (int i = 0; i < popsize; i++)
{
if (j < pushsize)
{
while (popV[i] != pushV[j])
{
tmp.push (pushV[j]);
j++;
}
j++;
}
else
{
if (popV[i] != tmp.top ())
return false;
tmp.pop ();
}
}
return tmp.empty ();
}
TEST_F(mpath,test_is_pop_order)
{
std::vector<int> pushV =
{ 1, 2, 3, 4, 5 };
std::vector<int> popV =
{ 4, 5, 3, 2, 1 };
bool ret = is_pop_order (pushV, popV);
ASSERT_TRUE(ret);
popV.clear ();
popV =
{ 4,3,5,2,1};
ret = is_pop_order (pushV, popV);
ASSERT_FALSE(ret);
}
The steps to use tdd is like this:
a. write down “real code” class and methods signatures based on the design
b. write down some comments about the initial implementations.
c. write down one unit test in the order of the implementation comments
d. write down one piece of implementation
e. do simply desktop review of the lines of codes when you think it finishes
f. test it until it gets green
g. refactor the codes and the unit tests
h. repeat steps c – g until finishing the whole function.
static void replace_empty_space_in_string (char *str, int length)
{
/**
* Given a string and please repalce all empty char of " " with "%20"
* eg. input "hello world", should output "hello%20world"
*
* train of thought:
* for char in str from right to left:
* if char is ' ':
* replace char with %20
* decrment index by 2 as we copy two more chars
* else:
* copy char
*/
if (str == NULL || length < 0)
return;
int newlen = 0;
int str_len = strlen (str) + 1;
for (int i = 0; i < str_len; i++)
{
if (str[i] == ' ')
newlen += 2;
}
newlen += str_len;
if (newlen > length)
return;
for (; str_len >= 0 && newlen >= 0; str_len--, newlen--)
{
if (str[str_len] == ' ')
{
str[newlen] = '0';
newlen--;
str[newlen] = '2';
newlen--;
str[newlen] = '%';
}
else
str[newlen] = str[str_len];
}
}
TEST_F(mpath,test_replace_empty_space)
{
char str[1024];
const char* msg = "hello world";
strcpy (str, msg);
replace_empty_space_in_string (str, 1024);
ASSERT_STREQ(str,"hello%20world");
}
#include <vector>
static bool find_number_from_two_decimen_array (int target,std::vector<std::vector<int>>& array)
{
/**
* 在一个二维数组中，每一行都按照从左到右递增的顺序排序，
* 每一列都按照从上到下递增的顺序排序。
* 请完成一个函数，输入这样的一个二维数组和一个整数，
* 判断数组中是否含有该整数
* ----------------------
* Given a two dimension array with elements
* in each row increasing from left to right and
* in each column increasing from top to bottom
* Please complete a function with parameters of
* a two-dimension-array and an integer and justify
* if the integer is contained in the array.
* eg. input ({ 0, 1, 3, 4, 5},{ 1, 4, 6, 8, 11},23)
* should output 23 is not in the given array
*
* train of thought:
* for next row in all rows:
* for val in this row:
* if val == target:
* return found
* if target > val:
* continue to next val
* if target < val:
* go back to the left column besides current one
* break current loop to jump down to next row
* outter loop done, must not found
*/
if (array.empty ())
return false;
int row = 0, col = 0, rows = array.size ();
for (; row < rows; row++)
{
if (array[row].empty ())
continue;
int cols = array[row].size ();
int max = array[row][cols - 1];
int min = array[row][0];
if (target == min || target == max)
return true;
if (target < min)
return false;
if (target > max)
continue;
if (array[row][col] == target)
return true;
if (array[row][col] > target)
{
col = 0;
cols--;
}
else
col++;
for (; col < cols; col++)
{
int v = array[row][col];
if (v == target)
return true;
if (target > v)
continue;
if (target < v)
{
col--;
break;
}
}
}
return false;
}
TEST_F(mpath, test_alg0)
{
std::vector<std::vector<int>> arrary =
{
{ 0, 1, 3, 4, 5, 7, 8, 11, 13, 15, 18, 21, 24, 27, 30 },
{ 1, 4, 6, 8, 11, 12, 15, 17, 18, 20, 23, 24, 27, 30 },
{ 4, 7, 8, 11, 14, 16, 18, 20, 21, 24, 27, 29, 32, 35, 89, 91, 93, 96 },
{ 5, 8, 10, 13, 15, 19, 21, 23, 24, 27, 29, 31 },
{ 6, 11, 14, 16, 18, 22, 24, 27, 29, 32, 33, 35, 94, 97, 99, 101,102 },
{ 9, 13, 16, 19, 21, 23, 25, 29, 31, 35, 38, 39, 42, 45, 48, 51,54, 56 } };
bool find = find_number_from_two_decimen_array (22, arrary);
ASSERT_TRUE(find);
}
Basically, be is the store format in memory while ve is the human-readable values that be represents.
eg. short a = 128
its value expression is looking like this: 00000000 10000000
its binary expression is looking like this:
little endian 10000000 00000000
big endian 00000000 10000000
the aim of this blog is to highlight a misunderstanding I used to have. That is I mixed up the be and ve. Take the example above, I used to thought little endian 10000000 00000000 should be calculated as value of 2^10 because the bit 1 is at the index of 10.
Actually, the correct way to calculate the value by cpu is like this: because the first byte 100000 is stored in low address so it should be high byte in value expression, and the second byte 000000 should be the low byte in value expression, take attention on the bold fonts, this is highlighted because it was where I made mistakes. So, the final value expression should be 00000000 10000000, and it value is therefore 2^8 that equals to the old value.