hao.liu0708
BAN USER- 3of 3 votes
AnswersGiven an array of object A, and an array of object B. All A's have
- hao.liu0708 in United States
different sizes, and all B's have different sizes. Any object A is of the
same size as exactly one object B. We have a function f(A, B) to compare the
size of one A and one B. But we cannot compare between two A's or two B's.
Give an algorithm to match each A with each B.| Report Duplicate | Flag | PURGE
Google Software Development Manager Algorithm
#include <iostream>
void print_uniques(int a[], int len)
{
int i = 0;
int j = 1;
while (j < len)
{
if (a[i] != a[j])
{
i = j;
std::cout << a[j] << " ";
}
++j;
}
};
int main()
{
int arr[] = {INT_MAX, 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9, 9, 10, 11, 12 ,13};
int length = sizeof(arr) / sizeof(arr[0]);
print_uniques(arr, length);
return 0;
}
#include <iostream>
void my_atoi(char str[], int& output)
{
int res = 0;
int i = 0;
int length = strlen(str);
bool is_negative = false;
while (i < length)
{
if (str[i] == ' ')
{
++i;
continue;
}
if (str[i] == '-')
{
++i;
is_negative = true;
}
break;
}
int j = length - 1;
while (j > 0)
{
if (str[j] == ' ')
{
--length;
--j;
}
else
break;
}
while (i < length)
{
if (str[i] <= '9' && str[i] >= '0')
{
int temp_res;
temp_res = res * 10 + str[i] - '0';
if ((temp_res + '0' - str[i]) / 10 != res)
{
std::cout << "Overflow!";
break;
}
else
{
res = temp_res;
}
}
else
{
std::cout << "Invalid input!";
break;
}
++i;
}
if (is_negative)
output = -1 * res;
else
output = res;
}
int main()
{
int res;
my_atoi(" -345 ", res);
return 0;
}
#include <iostream>
int main()
{
unsigned int N = 1024;
unsigned int M = 21;
unsigned int i = 2, j = 6;
unsigned int temp = ~0;
unsigned int left = temp >> (32 - i);
std::cout << "left: " << left << std::endl;
unsigned int right = temp << (j + 1);
std::cout << "right: " << right << std::endl;
unsigned int res = (N & (left | right)) | (M << i);
std::cout << "result: " << res << std::endl;
}
good one!
- hao.liu0708 August 27, 2012#include<iostream>
bool checkIsPermutation(const char* a, const char* b)
{
if (strlen(a) != strlen(b))
return false;
char arr[256];
memset(arr, 0, sizeof(arr));
for (int i = 0; i < strlen(a); i++)
{
arr[a[i]]++;
arr[b[i]]--;
}
for (int i = 0; i < 256; i++)
{
if (arr[i] != 0)
return false;
}
return true;
};
int main()
{
char* a = "microsoft";
char* b = "softmciro";
bool res = checkIsPermutation(a, b);
return 0;
}
I do not really prefer to solve this using recursion. This version will be better I think.
#include<iostream>
int power(int x, int n)
{
if (n < 0)
return 1 / power(x, -n);
int res = 1;
int base = x;
while (n > 0)
{
if (n & 1 == 1)
res *= base;
base *= base;
n >>= 1;
}
return res;
};
int main()
{
int res = power(3, 3);
return 0;
}
#include <iostream>
char pre[7];
char in[7];
int cnt = 0;
struct node
{
char data;
node* left;
node* right;
node(int eData, node* eLeft, node* eRight)
{
data = eData;
left = eLeft;
right = eRight;
}
};
void preOrder(node* n)
{
if (!n)
return;
pre[cnt++] = n->data;
preOrder(n->left);
preOrder(n->right);
};
void inOrder(node* n)
{
if (!n)
return;
inOrder(n->left);
in[cnt++] = n->data;
inOrder(n->right);
};
node* restoreTree(int left, int right, int inLeft, int inRight)
{
if (left < right)
{
char curData = pre[left];
int i = inLeft;
for (; i <= inRight; i++)
{
if (in[i] == curData)
break;
}
int num = i - inLeft;
node* curNode = new node(curData, NULL, NULL);
curNode->left = restoreTree(left + 1, left + num, inLeft, i - 1);
curNode->right = restoreTree(left + num + 1, right, i + 1, inRight);
return curNode;
}
else if (left == right)
return new node(pre[left], NULL, NULL);
};
int main()
{
node* n6 = new node('G', NULL, NULL);
node* n5 = new node('D', n6, NULL);
node* n4 = new node('E', NULL, NULL);
node* n3 = new node('B', n5, n4);
node* n2 = new node('F', NULL, NULL);
node* n1 = new node('C', n2, NULL);
node* n0 = new node('A', n3, n1);
cnt = 0;
preOrder(n0);
cnt = 0;
inOrder(n0);
node* root = restoreTree(0, 6, 0, 6);
return 0;
}
1. Keep two pointers (fast and slow), you only need O(n) with the help with a stack.
2. Could find the mid point when fast pointer reaches the end of the list.
3. Then compare the top of stack with current slow pointer's data.
Below is the code:
#include <iostream>
#include <stack>
struct node
{
int data;
node* next;
node(int eData, node* eNext)
{
data = eData;
next = eNext;
}
};
bool isPanli(node* head)
{
std::stack<node*> stk;
node* slow = head;
node* fast = head;
bool flag = false;
while (fast)
{
stk.push(slow);
slow = slow->next;
fast = fast->next;
if (fast)
{
fast = fast->next;
}
else
flag = true;
}
if (flag)
stk.pop();
while (!stk.empty())
{
if (stk.top()->data == slow->data)
{
stk.pop();
slow = slow->next;
}
else
return false;
}
return true;
};
int main()
{
node* n5 = new node(1, NULL);
node* n4 = new node(2, n5);
node* n3 = new node(3, n4);
//node* n2 = new node(3, n3);
node* n1 = new node(2, n3);
node* n0 = new node(1, n1);
bool res = isPanli(n0);
return 0;
}
#include <iostream>
void multipy(char* a, char* b, char* res)
{
int lenA = strlen(a);
int lenB = strlen(b);
int i, j;
int* c = new int[lenA + lenB];
memset(c, 0, sizeof(int) * (strlen(a) + strlen(b)));
for (i = lenA - 1; i >= 0; i--)
for (j = lenB - 1; j >= 0; j--)
c[i + j + 1] += (b[j] - '0') * (a[i] - '0');
for (i = lenA + lenB - 1; i >= 0; i--)
{
if (c[i] >= 10)
{
c[i - 1] += c[i] / 10;
c[i] %= 10;
}
}
i = 0;
while (c[i] == 0)
i++;
j = 0;
while (i < lenA + lenB)
{
res[j] = c[i] + '0';
i++; j++;
}
res[j] = 0;
delete[] c;
};
int main()
{
char* a = "999";
char* b = "9999";
char* res = new char[strlen(a) + strlen(b)];
multipy(a, b, res);
return 0;
}
#include <iostream>
void removeDoubleZeros(char* src)
{
int len = strlen(src);
int idxSrc = 0;
int idxDest = 0;
while (idxSrc + 1 < len)
{
if (src[idxSrc] == '0' && src[idxSrc + 1] == '0')
{
if (
((idxSrc - 1 >= 0 && src[idxSrc - 1] != '0') || idxSrc - 1 < 0) &&
((idxSrc + 2 < len && src[idxSrc + 2] != '0') || idxSrc + 2 >= len)
)
{
idxSrc += 2;
}
else
src[idxDest++] = src[idxSrc++];
}
else
{
src[idxDest++] = src[idxSrc++];
}
}
src[idxDest++] = src[idxSrc];
src[idxDest] = 0;
};
int main()
{
char src[] = "a3409jd00dk000d";
removeDoubleZeros(src);
return 0;
}
Do not really get the point, anyway, here is the power function.
#include <iostream>
double power(double x, int y)
{
if (y < 0)
return 1 / power(x, -y);
double res = 1;
double base = x;
while (y > 0)
{
if (y & 1 == 1)
{
res *= base;
}
base *= base;
y >>= 1;
}
return res;
};
int main()
{
double res = power(2, 5);
return 0;
}
#include <iostream>
#include <stack>
#include <hash_set>
#define N 26
struct node
{
int adjVex;
node* next;
}adj[N];
int inDegree[N];
std::hash_set<int> map;
void init()
{
memset(inDegree, 0, sizeof(inDegree));
for(int i = 0; i < N; i++)
{
adj[i].adjVex = i;
adj[i].next = NULL;
}
};
void create(int u, int v)
{
if(map.find(u) == map.end())
map.insert(u);
if(map.find(v) == map.end())
map.insert(v);
node* n = new node();
n->adjVex = v;
n->next = adj[u].next;
adj[u].next = n;
inDegree[v]++;
};
void printAdjList()
{
std::cout << "Adj list:\n";
for(int i = 0; i < N; i++)
{
char curElem = adj[i].adjVex + 'A';
node* n = adj[i].next;
bool printBreak = false;
if(n)
{
printBreak = true;
std::cout << curElem << " ";
}
while(n)
{
char cur = n->adjVex + 'A';
std::cout << cur << " ";
n = n->next;
}
if(printBreak)
std::cout << "\n";
}
};
bool topo()
{
std::stack<int> st;
//int cnt = 0;
for(int i = 0; i < N; i++)
{
if(inDegree[i] == 0 && map.find(i) != map.end())
st.push(i);
}
int top;
std::cout << "Topo result:\n";
while(!st.empty())
{
top = st.top();
st.pop();
char cur = top + 'A';
std::cout << cur << " ";
//cnt++;
node* n = adj[top].next;
while(n)
{
int k = n->adjVex;
inDegree[k]--;
if(inDegree[k] == 0)
st.push(k);
n = n->next;
}
}
std::cout << "\n";
for(int i = 0; i < N; i++)
{
if(inDegree[i] != 0)
return false;
}
return true;
};
int main()
{
int total;
std::cout << "Put the total of the pairs: ";
std::cin >> total;
init();
char u, v;
std::cout << "-u- -v-\n";
while(total--)
{
std::cin >> u >> v;
create(u - 'A', v - 'A');
}
printAdjList();
int canTopo = topo();
if(!canTopo)
std::cout << "This graph could not be topoed!\n";
return 0;
}
asc ii extended has larger range
- hao.liu0708 July 04, 2015