Hai.Vincent
BAN USER- 0of 0 votes
Answers1. concept of TCP and UDP and use case.
- Hai.Vincent
2. serialize and deserialize.
say given ab,cd,fgh, output a single string
given that single string output ab,cd,fgh
string serialize(string str[], int n)
{
string result = "";
if(n < 1)
return result;
for (int i = 0; i < n; i++)
{
result += "\"";
for(int j = 0; j < str[i].length(); j++)
{
if(str[i][j] == '\\')
{
result += "\\\\";
}
else if(str[i][j] == '\"')
{
result += "\\\"";
}
else
{
result += str[i][j];
}
}
result += "\"";
}
cout<<result<<endl;
return result;
}
void deserialize(string str)
{
if(str == "")
return ;
string token;
bool doubleQuoteBegin = false;
bool skip = false;
for (int i = 0; i < str.length(); i++)
{
if(str[i] == '\\' && !skip)
{
skip = true;
}
else if(str[i] == '\"')
{
if(skip)
{
token += '\"';
skip = false;
}
else
{
if(doubleQuoteBegin)
{
doubleQuoteBegin = false;
cout<<token<<endl;
token = "";
}
else
{
doubleQuoteBegin = true;
}
}
}
else if(str[i] == '\\' && skip)
{
token += '\\';
skip = false;
}
else if(str[i] == '\\' && !skip)
{
skip = true;
}
else
{
token += str[i];
}
}
}| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding
int findKthLargestInArray(int arr[], int n, int k)
{
if(n < 1 || n < k)
return -1;
int lastCandidate = INT_MIN;
int candidate = INT_MIN;
int rank;
//first we find the largest number in array
for (int i = 0; i < n; i++)
{
if(arr[i] > candidate)
candidate = arr[i];
}
//lastCandidate is the largest number
lastCandidate = candidate;
if(k == 0)
return lastCandidate;
bool found = false;
for (rank = 1; rank <= k; rank++)
{
found = false;
candidate = INT_MIN;
for (int i = 0; i < n; i++)
{
if(arr[i] > candidate && arr[i] < lastCandidate)
{
found = true;
candidate = arr[i];
}
}
//now lastCandidate is the rankth largest number
lastCandidate = candidate;
}
if(found)
return lastCandidate;
return -1;
}
bool isBSTHelper(Node* node, int lowerbound, int upperbound)
{
if(node == NULL)
return true;
if(node->value < lowerbound || node->value > upperbound)
return false;
return isBSTHelper(node->left,lowerbound,node->value) && isBSTHelper(node->right,node->value+1,upperbound);
}
bool isBST(Node* root)
{
return isBSTHelper(root,INT_MIN,INT_MAX);
}
void oddeven_sort(vector<int>& v)
{
size_t i = 0;
size_t j = v.size()-1;
while(i < j)
{
if(v[i] % 2 == 0 && v[j] % 2 == 1)
{
exchange(v[i],v[j]);
i++;
j--;
}
else if(v[i] % 2 == 0 && v[j] % 2 == 0)
{
j--;
}
else if(v[i] % 2 == 1 && v[j] % 2 == 1)
{
i++;
}
else
{
i++;
j--;
}
}
quick_sort(v,0,i-1);
quick_sort(v,i,v.size()-1);
for(i = 0; i < v.size(); i++)
cout<<v[i]<<"\t";
cout<<endl;
}
time complexity is O(logn) + 2 * ( O(logn) + O(log(n/2)) + O(log(n/4)) +... O(1)) = 5*O(logn) = O(logn)
- Hai.Vincent December 28, 2010my 2 cents:
int binary_search_boundary_helper(int *a,int start, int end, int key)
{
if(end < start)
{
return -1;
}
if(start == end)
{
if(a[start] == key)
return start;
return -1;
}
int left = start;
int right = end;
int mid;
while(left < right)
{
mid = left + (right - left)/2;
if(a[mid] > key)
{
right = mid - 1;
}
else if(a[mid] < key)
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
void binary_search_boundary(int* a, int n, int key)
{
int start = n-1, end = 0;
int tempStart = binary_search_boundary_helper(a,0,n-1,key);
int tempEnd = tempStart;
if(tempStart == -1)
{
start = end = -1;
}
while(tempStart >= 0)
{
if(tempStart <= start)
start = tempStart;
tempStart = binary_search_boundary_helper(a,0,start-1,key);
}
while(tempEnd >= 0)
{
if(tempEnd >= end)
end = tempEnd;
tempEnd = binary_search_boundary_helper(a,end+1,n-1,key);
}
cout<<start<<endl<<end<<endl;
}
time complexity is O(kn)
- Hai.Vincent January 05, 2011