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 SDE2 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 ((iarr[j]) > 0) {
if (sum[iarr[j]]==true) {
sum[i] = true;
break;
}
}
}
}
return sum[tot];
}

iwanna
November 16, 2014 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);
}

iwanna
September 25, 2014 void printtriangle(array<int>arr) {
int len = arr.size();
if (len==0) return;
array<int,len1> newarr;
for (int i=0;i<len1;i++) {
newarr.fill(arr[i]+arr[i+1]);
}
printtriangle(newarr);
cout << "{{ ";
for (int j=0;j<len;j++) {
cout << arr[i] << ",";
}
cout << "}} ";
}

iwanna
September 23, 2014 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..m1], Y[0..n1] */
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..i1] and Y[0..j1] */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0  j == 0)
L[i][j] = 0;
else if (X[i1] == Y[j1])
L[i][j] = L[i1][j1] + 1;
else
L[i][j] = max(L[i1][j], L[i][j1]);
}
}
/* L[m][n] contains length of LCS for X[0..n1] and Y[0..m1] */
return L[m][n];
}

iwanna
July 10, 2014 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;
}
}

iwanna
July 10, 2014 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);
}

iwanna
July 02, 2014 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);
}

iwanna
July 01, 2014 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;
}

iwanna
May 09, 2014 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;
}

iwanna
May 06, 2014 /* 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 &&
pathLenk1 >= 0 && visited[pathLenk1] == false)
{
cout << path[pathLenk1] << " ";
visited[pathLenk1] = 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);
}

iwanna
February 16, 2014 Open Chat in New Window
*minheap. Whenever we find an expense less than top, remove top and add new expense element
 iwanna November 17, 2014