Microwish
BAN USER- 2of 2 votes
AnswersGiven a normal binary tree, write a function to serialize the tree into a string representation (returning the string), and also a function to deserialize a serialized string into the original binary tree.
- Microwish in China| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - -2of 2 votes
AnswersGiven a normal binary tree, write a function to serialize it into a string representation (returning a string), and also a function to deserialize the string into the original binary tree
- Microwish in China| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm
What's the point of this question?
int *foo2(int a[], int n)
{
int *b, carry = 1, t;
if ((b = (int *)malloc(n + 1)) == NULL) {
fprintf(stderr, "malloc failed\n");
return NULL;
}
for (int i = n - 1; i >= 0; i--) {
t = a[i] + carry;
if (t == 10) {
t = 0;
carry = 1;
} else {
carry = 0;
}
b[i + 1] = t;
}
b[0] = carry;
return b;
}
int main()
{
int a[] = { 2, 0, 9, 9 }, *b;
b = foo(a, 4);
if (b != NULL) {
for (int i = 0; i < 5; i++) printf("%d ", b[i]);
printf("\n");
}
free(b);
b = foo2(a, 4);
if (b != NULL) {
for (int i = 0; i < 5; i++) printf("%d ", b[i]);
printf("\n");
}
free(b);
return 0;
}
My native idea.
2.h, header file for a simple dict implementation with a hash table
// 2.h
#include <string>
#include <map>
class Dict {
private:
static std::map<std::string, int> ht_;
static bool inited_;
public:
static bool has(const std::string& word);
};
2.cpp, impelmentation file
#include "2.h"
std::map<std::string, int> Dict::ht_;
bool Dict::inited_ = false;
bool Dict::has(const std::string& word)
{
if (!inited_) {
inited_ = true;
ht_["COT"] = 1;
ht_["DOT"] = 1;
ht_["COG"] = 1;
}
return ht_.find(word) != ht_.end();
}
main file
#include "2.h"
#include <stdio.h>
#include <string.h>
int foo(size_t pos, char *src, const char *dest)
{
static int count = 0;
printf("calling %d\n", ++count);
if (strcmp(src, dest) == 0) {
printf("%s\n", src);
return 0;
}
char temp;
for (size_t i = pos, l = strlen(dest); i < l; i++) {
if (src[i] == dest[i]) {
printf("%s\n", src);
continue;
}
temp = src[i];
src[i] = dest[i];
if (Dict::has(src)) {
printf("%s\n", src);
return foo(i + 1, src, dest);
} else {
src[i] = temp;
continue;
}
}
return 0;
}
int main()
{
char src[] = "CAT", dest[] = "DOG";
printf("%s\n", src);
foo(0, src, dest);
printf("%s\n", dest);
return 0;
}
#include <stdio.h>
inline char lowercase(char c)
{
if (c >= 65 && c <=90) return c + 32;
return c;
}
inline void tell_coordinate(char c, int *row, int *col)
{
int d = c - 'a';
*row = d / 5;
*col = d % 5;
}
int control(const char *input)
{
int curr_row = 0, curr_col = 0, row, col, n = 0;
const char *p = input;
char c;
for (; *p != '\0'; p++) {
c = lowercase(*p);
tell_coordinate(c, &row, &col);
printf("%c: (%d,%d)\n", *p, row, col);
if (curr_row < row) {
do {
printf("DOWN\n");
curr_row++;
n++;
} while (curr_row < row);
} else if (curr_row > row) {
do {
printf("UP\n");
curr_row--;
n++;
} while (curr_row > row);
}
if (curr_col < col) {
do {
printf("RIGHT\n");
curr_col++;
n++;
} while (curr_col < col);
} else if (curr_col > col) {
do {
printf("LEFT\n");
curr_col--;
n++;
} while (curr_col > col);
}
printf("SELECT %c\n", *p);
}
return n;
}
int main()
{
int n = control("CON");
printf("%d steps\n", n);
return 0;
}
finding the maximum length of a bitonic subsequence as a reference:
int find_max_bitonic_len(int a[], int n)
{
int i, j, k, l, maxl;
l = maxl = 0;
i = 0;
while (i < n) {
//finds possible heads of bitonic subsequences
while (i < n - 1 && a[i + 1] < a[i]) i++;
if (i == n - 1) return maxl;
//monotonic increasing
j = i;
while (j < n - 1 && a[j + 1] >= a[j]) j++;
if (j == n - 1) return maxl;
//monotonic decreasing
k = j;
while (k < n - 1 && a[k + 1] <= a[k]) k++;
l = k - i + 1;
if (l > maxl) maxl = l;
i = k;
}
return maxl;
}
When serializing a binary tree, treat it as a complete binary tree (not a full binary tree), like adding NULL pointer to a single-child node (not really added).
When deserializing a string to a binary tree, first extract real contents (BinTreeNode.val) into a assistant double-ended queue, by removing L or R in between. And then constructing the binary tree, using another double-ended queue to maintain parents/children relationship.
/** my implementation */
#include <iostream>
#include <string>
#include <deque>
struct BinTreeNode {
int val;
BinTreeNode *left, *right;
BinTreeNode() {}
BinTreeNode(int v, BinTreeNode *l = NULL, BinTreeNode *r = NULL):
val(v), left(l), right(r)
{}
};
void bin_tree_to_str(BinTreeNode *root, std::string& str)
{
if (root == NULL) return;
std::deque<BinTreeNode *> que;
BinTreeNode *p;
que.push_back(root);
str.append(std::to_string(root->val));
while (!que.empty()) {
//undef NDEBUG
//std::cout << "curr size: " << que.size() << std::endl;
p = que.front();
que.pop_front();
//undef NDEBUG
//std::cout << "size after pop_font: " << que.size() << std::endl;
//undef NDEBUG
//std::cout << p->val << std::endl;
//leaves
if (p->left == NULL && p->right == NULL) continue;
str.append("L");
if (p->left) {
que.push_back(p->left);
str.append(std::to_string(p->left->val));
} else {
str.append("#");
}
str.append("R");
if (p->right) {
que.push_back(p->right);
str.append(std::to_string(p->right->val));
} else {
str.append("#");
}
}
std::cout << str << std::endl;
}
BinTreeNode *str_to_bin_tree(const std::string& str)
{
std::deque<std::string> que;
size_t i, j, l;
for (i = 0, j = 0, l = str.size();
i < l;
/* void */) {
while (str[i] != 'L' && i < l) i++;
std::string ss = str.substr(j, i - j);
que.push_back(ss);
if (i == l) break;
j = i + 1;
i++;
while (str[i] != 'R' && i < l) i++;
ss = str.substr(j, i - j);
que.push_back(ss);
j = i + 1;
i++;
}
std::deque<BinTreeNode *> que2;
std::string str_val;
BinTreeNode *root, *left, *right;
BinTreeNode *temp;
str_val = que.front();
que.pop_front();
root = temp = new BinTreeNode(std::stoi(str_val));
que2.push_back(temp);
//while (!que2.empty()) {
while (!que.empty()) {
//for (i = 0, l = (que.size() - 1) / 2; i < l; i++) {
temp = que2.front();
que2.pop_front();
str_val = que.front();
que.pop_front();
if (str_val == "#") left = NULL;
else left = new BinTreeNode(std::stoi(str_val));
str_val = que.front();
que.pop_front();
if (str_val == "#") right = NULL;
else right = new BinTreeNode(std::stoi(str_val));
temp->left = left;
temp->right = right;
if (left) que2.push_back(left);
if (right) que2.push_back(right);
}
return root;
}
void foo(const char *s1, const char *s2)
{
int l1, l2, l;
char *s;
if (s1 == NULL || s2 == NULL || s1[0] == '\0' || s2[0] == '\0') return;
l1 = strlen(s1);
l2 = strlen(s2);
if (l1 < l2) {
l = l2 + 1;
} else {
l = l1 + 1;
}
s = (char *)malloc(l + 1);
if (s == NULL) return;
s[l] = '\0';
l1--;
l2--;
l--;
int sum, carry = 0;
while (l1 >= 0 && l2 >= 0) {
//printf("carry: %d\n", carry);
sum = s1[l1] - '0' + s2[l2] - '0' + carry;
//printf("sum: %d\n", sum);
if (sum > 1) {
sum -= 2;
carry = 1;
} else {
carry = 0;
}
s[l--] = (char)(sum + '0');
l1--;
l2--;
}
while (l1 >= 0) {
sum = s1[l1] - '0' + carry;
if (sum > 1) {
sum -= 2;
carry = 1;
} else {
carry = 0;
}
s[l--] = (char)(sum + '0');
l1--;
}
while (l2 >= 0) {
sum = s2[l2] - '0' + carry;
if (sum > 1) {
sum -= 2;
carry = 1;
} else {
carry = 0;
}
s[l--] = (char)(sum + '0');
l2--;
}
if (l >= 0) {
if (carry > 0) s[l--] = '1';
else while (l >= 0) s[l--] = '0';
}
printf("s1: %s\ns2: %s\nsum: %s\n", s1, s2, s);
free(s);
}
Except for bit operation, a naive idea:
- Microwish December 26, 2014