BAN USER
- 0of 0 votes
AnswersDesign OOP constructs for the following functinoarlity. There are multiple types of phones (android, iphone etc). Each phone has a subset of features (voice, text, etc). How would you write the classes and inheritance esp. in C++?
-| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Object Oriented Design - 0of 0 votes
AnswersWhat data structure would you use to implement spell correction in a document. The goal is to find if a given word typed by the user is in the dictionary or not (no need to correct it).
-
What is the complexity? What if you have to support multiple languages/dictionaries?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersGiven a matrix of 1s and 0s. Implement an algorithm that sets all cells of row i and column j to 0 if the original matrix has a 0 in cell (i,j). Would the algo change if you have to set it to 1 instead of 0?
-| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer
similar to above methods...hopefully easier to understand?
the idea is to store the elements of partition in a vector and sum of the partition so far in sum. to avoid permutations of the same partition, we make sure to add elements that are atleast as big as the biggest number in the partition so far.
start the algorithm with empty partition and sum=0;
Partition(int n, int m, vector<int> part, int sum)
{
if(part.size() == m)
{
if(sum == n) print(part);
return;
}
// part.back() returns the max element of the partition
// initially when partition is empty we start with 1
int minval = part.size() > 0 ? part.back() : 1;
for(int i=minval; sum+i <= n; i++)
{
part.push_back(i);
Partition(n,m,part,sum+i);
part.pop_back();
}
}
Store a vector that holds the parent node values during DFS. When printing a node, set the corresponding entries in matrix to 1.
Path(node* root, vector<char> parents)
{
if(root == NULL) return;
//Update Matrix for current node
for(int i=0;i<parents.size();i++)
{
M[root->val][parents[i]] = 1;
}
parents.push_back(root->val);
Path(root->left, parents);
Path(root->right,parents);
}
dynamic programming...
Let A[i] hold the cost of house i.....S[i] holds the maximum loot that we can get when the loot includes ith house and any houses among 0,...i-2
the optimal substructure is: S[i] = max(S[i-2],S[i-3]) + A[i]
the key is that we need to consider only S[i-2] and S[i-3] because max(S[k], for k=0...i-4) is already included in S[i-2] or S[i-3].
max value of this array is our maximum loot..because it has to include some house i.
complexity...O(n)
MaxLoot(int A[], int n)
{
int S[n];
S[0] = A[0];
S[1] = A[1];
S[2] = S[0] + A[2];
maxloot = max(S[1],S[2]);
for(int i=3;i<n;i++)
{
S[i] = max(S[i-2],S[i-3]) + A[i];
maxloot = max(maxloot,S[i]);
}
return maxloot;
}
// Algorithm: For each color find the number of connected components where a connected component includes all cells that can be reached through same color.
// Use a variation of flood fill algorithm to find connected components
// Map black color to 1 (true) and white to 0 (false)
struct cell
{
int color;
bool visit;
cell()
{
color = -1; visit = false;
}
};
int getOriginal(bool** C, int n)
{
//Copy Color matrix into B
cell** B = new cell*[n];
for(int i=0;i<n;i++)
{
B[i] = new cell[n];
for(j=0;j<n;j++)
{
B[i][j].color = C[i][j] == true? 1 : 0;
}
}
reset(B,n);
int numblack_regions = Count(1,B,n);
reset(B,n);
int numwhite_regions = Count(0,B,n);
if(numblack_regions > numwhite_regions) return 1;
if(numblack_regions < numwhite_regions) return 0;
return 2;
}
void reset(cell**B, int n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
B[i][j].visit = false;
}
}
}
int Count(int color, cell** B, int n)
{
int numregions = 0;
while(true)
{
int x = -1, y = -1;
pick_unvisited(B,n,x,y);
if(x == -1 || y == -1) return num_regions;
Fill(B,n,color,x,y);
num_regions++;
}
}
Fill(cell**B, int n, int color, int x, int y)
{
if(B[x][y].color != color || B[x][y].visit == true) return;
B[x][y].visit = true;
Fill(B,n,color,x+1,y+1);
Fill(B,n,color,x-1,y+1);
Fill(B,n,color,x-1,y-1);
Fill(B,n,color,x+1,y-1);
Fill(B,n,color,x,y+1);
Fill(B,n,color,x+1,y);
Fill(B,n,color,x,y-1);
Fill(B,n,color,x-1,y);
}
void pick_unvisited(cell**B, int n, int color, int& x, int& y)
{
int x = -1. y = -1;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(B[i][j].color == color && B[i][j].visit == false)
{
x = i; y = j;
return;
}
}
}
}
Delete(node** head, int k)
{
node* curr = *head;
node* prev = NULL;
while(curr != NULL)
{
if(curr->val == k)
{
if(prev != NULL)
{
prev->next = curr->next;
delete curr;
curr = prev->next;
}
else
{
curr = curr->next;
delete *head;
*head = curr;
}
}
else
{
prev = curr;
curr = curr->next;
}
}
}
if the address of tail nodes in both linked lists are equal then the linked lists intersect.
to find the intersection..increment a pointer from head of the longer list by L1-L2...where L1 and L2 are lengths of longer and shorter lists. The pointer on L2 starts from its head. Now keep incrementing the pointers of both L1 and L2 till they intersect.
//Assume: The exclusion rules are converted into a vector of numbers where each number's binary representation tells us which numbers are in the exclusion set
e.g: {(a1,a3,a5), (a1,a2)} = {00010101, 00000011)
// Assume: We have n distinct numbers
vector<vector<int>> Subsets(int n, vector<int> E)
{
vector<vector<int>> subsets;
//Generate all subsets
for(int i=0;i< 1<<n;i++)
{
int violate = 0;
// Check if it violates an exclusion set
for(int j=0; j< E.size(); j++)
{
if(i&E[j] != 1)
{
violate = 1;
break;
}
}
if(!violate)
{
// i represents a valid subset
vector<int> sub;
for(int k=0;k<n;k++)
{
if(i & 1<<k == 1)
{
sub.push_back(k);
}
}
subsets.push_back(subset)
}
}
return subsets;
}
i think the worst case for minimum is when the array has all unique elements in the beginning e.g: {1 2 3 4 4 4}
the first element has to be compared with n/2 elements..the second one to n/2-1 elements and so on till we have to compare with only 1 element
so total no.of comparions is 1+2+3+....n/2 = (n/2)(n/2+1)/2
how can both left and right children of the deleted node be linked to its parent? if all duplicated nodes are either leaves or have only one child, then the problem is relatively easier.
Otherwise, I think we need to build a new tree from scratch. Traverse the old tree and keep inserting nodes into the new tree as long as they are not a duplicate. Duplicates can be checked by a hash map on node values.
we can do a simple modified version of count sort...
O(n+m)...n is length of input string and m is length of order string
Reorder(char* I, char* R)
{
int Count[MAX_ASCII];
memset(Count,0,MAX_ASCII);
// Normal count sort
for(int i=0;i<strlen(I);i++)
{
Count[I[i]]++;
}
k = 0;
//Output according to order array first
for(int i=0;i<strlen(R);i++)
{
while(Count[R[i]]-- > 0)
I[k++] = R[i]
}
// Append all remaining characters
for(int i=0;i<MAX_ASCII;i++)
{
while(Count[i]-- > 0)
I[k++] = i
}
}
no...at any given time recursion works on a branch of the tree. and max length of any branch is O(n).
- April 21, 2011