iwanna
BAN USER- 2of 2 votes
AnswersHow would you implement virtual functions in C
- iwanna in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer C# - 0of 0 votes
AnswersHow would you implement virtual functions in C?
- iwanna in United States| Report Duplicate | Flag | PURGE
Akamai Software Engineer / Developer C - 0of 2 votes
AnswersHow to implement virtual functions in C?
- iwanna in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer C - 0of 0 votes
AnswersYou have a set of pairs of characters that gives a partial ordering between the characters. Each pair (a, b) means that a should be before b. Write a program that displays a sequence of characters that keeps the partial ordering (topological sorting).
- iwanna in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersCount the number of shapes in a given (1/0) matrix. A cluster of consecutive (not diagonal) 1's defines one shape.
- iwanna in United States
eg
1 1 0 0 1
1 0 0 1 0
1 1 0 1 0
0 0 1 0 0
No of shapes = 4| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Aggregate count of lines of all log files :
wc -l *.log | tail -1
If we assume multiple threads are reading the files, put the filenames in a queue pipe and assign files to the thread as read, Once a thread has read a file, it will fetch the next one in the pipe.
First sort the array then pass the array, array length and total value to function
bool isTot(int arr[],int len,int tot) {
bool sum[tot+1];
sum[0] = true;
for (int i=1;i < =tot;i++) {
if (sum[i] < arr[0]) {
sum [i] = false;
continue;
}
sum[i] = false;
for (int j = 0; j < len; j++) {
if ((i-arr[j]) > 0) {
if (sum[i-arr[j]]==true) {
sum[i] = true;
break;
}
}
}
}
return sum[tot];
}
pthread_cond _t cv;
pthread_mutex_t mt;
bool flag=0;
int main() {
pthread_t even,odd;
pthread_create(&even,&attr,printeven,NULL);
pthread_create(&odd,&attr,printodd,NULL);
pthread_join(even,NULL);
pthread_join(odd,NULL);
}
void printeven( ) {
for (int i=0; i+=2) {
pthread_mutex_lock(&mt);
if (flag)
pthread_cond_wait(&cv,&mt);
flag = 1;
printf("%d",i);
pthread_cond_signal(&cv,&mt);
pthread_mutex_unlock(&mt);
}
void printodd( ) {
for (int i=1; i+=2) {
pthread_mutex_lock(&mt);
if (!flag)
pthread_cond_wait(&cv,&mt);
flag = 0;
printf("%d",i);
pthread_cond_signal(&cv,&mt);
pthread_mutex_unlock(&mt);
}
void printtriangle(array<int>arr) {
int len = arr.size();
if (len==0) return;
array<int,len-1> newarr;
for (int i=0;i<len-1;i++) {
newarr.fill(arr[i]+arr[i+1]);
}
printtriangle(newarr);
cout << "{{ ";
for (int j=0;j<len;j++) {
cout << arr[i] << ",";
}
cout << "}} ";
}
void findclosestkey(node *root, int target, int& diff, int& closest) {
if (root==NULL) return;
int cur_diff == abs(root->data - target);
if (cur_diff < diff) {
diff = cur_diff;
closest = root->data;
}
if (diff == 0) return;
else {
if (target > root->data)
findclosestkey(root->right, target,diff,closest);
else
findclosestkey(root->left, target,diff,closest);
}
}
}
- iwanna September 22, 2014Dynamic programming solution :
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
int L[m+1][n+1];
int i, j;
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}
assuming such splitting exists, get the average of the whole array, The average of the 2 parts should also be equal to this average. Then we need to find a subset of the array that averages to this. This can be got by the subset solution :(O2^n)
int max = 1 << set.size();
vector <int> subset1,subset2;
for (i=1;i<max,i++) {
int k=i;
int index = 0,cnt=0,sum=0;
subset1.empty();
while (k>0) {
if((k&1)>0) {
cnt++;
subset1.insert(index);
sum+=arr[index];
}
index++;
k>>1;
}
if (sum/cnt==AVG) {
break;
}
}
//Now get subset2:
set<int>::iterator it = subset.begin();
for(i=0;i<set.size();i++) {
if (i!=*it) {
subset2.insert(i);
} else
++*it;
}
}
1
/ \
2 3
/ \
4 5
/ \ \
6 7 8
/ \ \
9 a b
At any given node :
path len with current node as root = max pathlen with node->left as root (L) + max pathlen with node->right as root (R) + 1
At each recursion function will return the maximum length possible with that node, whcih is either 1+ max(left) or 1 + max(right),
Also it will update the max length if the current path length is more that current max.
int maxlen;
len = maxpath(root,maxlen);
cout << maxlen;
int maxpath(node *root, int &maxlen) {
if (root==NULL) {
return 0;
}
int l = maxpath(root->left,maxlen);
int r = maxpath(root->right,maxlen);
int curmax = 1 + l + r;
if (curmax > maxlen) maxlen = curlen;
return max(1+l, 1+r);
}
A solution with 2 in order traversals and one array:
1) Do an in order traversal of the tree and store all data at odd levels in the array (storealt)
2) reverse this array
3) Do in order traversal again - this time replacing the data at odd levels with the reversed data in the array (modifytree)
void storealt (node* root, int arr[], int *index,int level) {
if root==NULL return;
storealt(root->left,arr,index,level+1);
if (level%2 == 0) {
arr[*index] = root->data;
*index++;
}
storealt(root->right,arr,index,level+1);
}
class Logger {
private:
bool db_flag;
string log_name;
static Logger *m_pInstance;
Logger (){};
Logger(const Logger &);
Logger &( operator =(const Logger &) {};
public:
static Logger * Instance() {};
bool openlogfile(bool flag,string logname);
void writetoLog();
bool closeLog();
}
Logger * Logger::m_pInstance = NULL;
Logger * Logger :: Instance(bool flag,string logname) {
if (!m_pInstance)
m_pInstance = new Logger(flag,logname);
return m_pInstance;
}
bool Logger::openlogfile(bool flag,string logname) {
db_flag = flag;
log_name = logname;
if (db_flag){
//connect to DB
} else
open (logname);
}
Call in main :
Logger ::Instance()->openlogfile(bool true,"myDB");
Logger::Instance()->writetofile("message 1..");
Logic :
1) Start print the current node and all its siblings
2) If there is a left node , go there and print its siblings
else if it has rightnode, go there and print the siblings
3) if there is no left or right for current node, then search its siblings for one that has a left or right., Then select that node and repeat step 1)
void printfBFS (node* root) {
if (root==NULL) return;
node *tmp = root;
while (tmp) {
cout << tmp->data;
tmp = tmp->foo;
}
if (root->left) printBFS (root->left);
else if (root->right) printfBFS (root->right);
else {
while (root) {
if (root->left) {
return printfBFS (root->left);
break;
} else if (root->right) {
return printfBFS (root->left);
break;
}
root = root->foo;
}
return;
}
int returnlongestword ( string wrds[],int lenw, char chars[], int lenc) {
int dict[256] = {0}, mydict[256] = {0};
int i, j, index;
int maxlen = 0;
for (i = 0; i < lenc; i++ )
dict[chars[i]]++;
for (i=0; i < lenw; i++) {
memcpy(mydict,dict,256);
string str = wrds[i];
int curlen;
int len = str.length;
for (j=0;j<len;j++) {
if (!mydict[str[j]]) {
break;
} else {
mydict[str[j]]--;
curlen++;
}
}
if (curlen > maxlen) {
maxlen = curlen;
index = i;
}
}
return index;
}
/* This function prints all nodes that are distance k from a leaf node
path[] --> Store ancestors of a node
visited[] --> Stores true if a node is printed as output. A node may be k
distance away from many leaves, we want to print it once */
void kDistantFromLeafUtil(Node* node, int path[], bool visited[],
int pathLen, int k)
{
// Base case
if (node==NULL) return;
/* append this Node to the path array */
path[pathLen] = node->key;
visited[pathLen] = false;
pathLen++;
/* it's a leaf, so print the ancestor at distance k only
if the ancestor is not already printed */
if (node->left == NULL && node->right == NULL &&
pathLen-k-1 >= 0 && visited[pathLen-k-1] == false)
{
cout << path[pathLen-k-1] << " ";
visited[pathLen-k-1] = true;
return;
}
/* If not leaf node, recur for left and right subtrees */
kDistantFromLeafUtil(node->left, path, visited, pathLen, k);
kDistantFromLeafUtil(node->right, path, visited, pathLen, k);
}
/* Given a binary tree and a nuber k, print all nodes that are k
distant from a leaf*/
void printKDistantfromLeaf(Node* node, int k)
{
int path[MAX_HEIGHT];
bool visited[MAX_HEIGHT] = {false};
kDistantFromLeafUtil(node, path, visited, 0, k);
}
RepAlicaKnight, Blockchain Developer at ABC TECH SUPPORT
Alica , an Employment Consultant with extraordinary achievements in providing beneficial career consultation, organizing various workshops and webinars, and helping clients ...
RepAllegroMiller, abc at A9
I am working as a Courier service in the limanger company. I possess great communication skills, a highly professional attitude ...
*min-heap. Whenever we find an expense less than top, remove top and add new expense element
- iwanna November 17, 2014