[algogeeks] Re: Microsoft Interview Question
Root of a graph can be any node whose in-degree is zero. i.e. there are no nodes pointing to that node. It can be found by using O( |V| ) space and O( |E| ) time . Now we can choose any node whose in-degree is zero if present. or choose any random node and itf DFS-tree is the desired tree. Time complexity of DFS is O(|E|). On Monday, 12 March 2012 15:05:49 UTC+5:30, Umer Farooq wrote: > > Hello friends, > > I recently had an onsite MS interview. One of the questions that they > asked was: > > >- Given a directed graph, write a program that takes root of the graph >and returns root of a tree which comprises of all the nodes of the graph > in >the same way as they appeared in the graph (the graph contains no cycles). > > > -- > Umer > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/l-xn8uxltrwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: symmetric binary tree
For this we simple need to check if the left subtree and right subtree are
mirror images of each other.
bool isSymmetric(Node root)
{
if(isMirror( root->left, root->right )
return true;
return false;
}
The mirror utility can be implemented as :->
bool isMirror(Node a,Node b)
{
if(!a && !b ) return true;
if(!a || !b ) return false;
if(isMirror(a->left,b->right) && isMirror(a->right,b->left))
return true;
return false;
}
On Tuesday, 22 May 2012 10:50:38 UTC+5:30, algogeek wrote:
>
> How to check if a given binary tree is structurally symmetric ie. the
> left sub tree should be mirror image of right sub tree and vice-versa.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/sSYEjeKx1FsJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: finding anagrams in a list of words
Sign each word such that two words having same signature are anagrams of each other. The signature for every word can be :-> given word in lexicographically sorted order. Keep a trie data structure to store all the signatures. Now every leaf node points to a list having all the words which are anagrams of the corresponding signature. Algo:- take a word and sort a copy of it it lexicographically. Now insert this sorted copy into the trie. If the sorted copy already exists, add the corresponding word to the list pointed by the leaf node. else create a new list and add the word to the list. Time complexity :- O(N x W) // worst case if all words are unique and no two words are anagrams of each other. N-> total words W-> max word size For example :- "post" , "spot" , "pots" above 2 words have same signature :- "opst" . Hence they are anagram of each other and would be added to the same list. On Friday, 11 May 2012 17:24:01 UTC+5:30, mayur wrote: > > Hi all, > > I am stuck with a question for a long time...can someone provide the best > algorithm for this.. > > Question).. find all the anagrams in a list of words. The algorithm should > be efficient as the list can be very large. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kupYYjDXnbwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Microsoft Question
Queue can be defined as a priority queue where priority decreases with time. Hence an element inserted later has lower priority and goes to back of queue. (FIFO) Stack can be defined as a priority queue where priority increases with time.Hence an element inserted later has higher priority and goes to front of stack.(LIFO) On Tuesday, 13 September 2011 02:15:01 UTC+5:30, Ankur Garg wrote: > > How to Implement a Queue with a Priority Queue > Similarly how woud you implement Stack with Priority Queue > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/SDq590tCZHkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS Q
If the matrix is 4-connected, we can use the same matrix. now we have to find the total number of connected components of a graph. consider 1 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 we can use bfs/dfs to mark the nodes as visited and thus total connected components can be counted. On Tuesday, 10 January 2012 07:09:46 UTC+5:30, ashgoel wrote: > > there is a matrix of 1 and 0 > 1 is a island and 0 is water > 1-1 together makes one island > calculate total no of islands > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/JiDXnyVHn4YJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Interview Question
I think adjacency list can be implemented by vector of vector. vector< vector > Nodes; The size of vector Nodes is total no of nodes. Every element of the vector will store all its adjacent edges. Nodes[i] is a vector containing all the edges adjacent to node i. So, we can copy the graph easily. On Wednesday, 25 April 2012 17:40:16 UTC+5:30, Radhakrishnan IT wrote: > > How will you implement a graph data structure ? > Give an linked implementation as we do not know how many nodes will be > there and how many edges will be there. > Make a copy of this graph.. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/w49HbR_IySIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Print longest string duplicated M times
I think a better approach can be :- using suffix array.
Suffix array is an array data structure which stores all suffixes of the
input string, sorted in lexicographical order.
Now we need to consider that substring which is repeated m times.
Now since all the suffixes starting with same character are contiguous, we
can use the following logic :-
1:- iterate from left of suffix array till we get m suffixes having same
prefix
2:- update the longest prefix P found so far
3:- if at any time we get a new prefix , start from that current suffix
After we reach end , P contains the result if any string is repeated M
times otherwise NULL
Space Complexity :- O(N) , N is length of input string
Time Complexity :- Building the suffix array is N^2 LogN (Worst Case ) +
Finding_Substring - O(N)
On Tuesday, 15 May 2012 12:22:25 UTC+5:30, ashgoel wrote:
>
>
> I am unclear about the answer provided by Programming Pearls on the question.
> What this does is to find longest string whose beginning is separated by
> exactly M chars.
>
> The original question is to find the longest string duplicated M times. Any
> ideas on the approach for this? I could think of having a suffix tree with
> each node keeping a count to keep track of "while insertion how many times
> this node was passed while going down"
>
> #include
> #include
> #include
>
> int pstrcmp(char **p, char **q)
> { return strcmp(*p, *q); }
>
> int comlen(char *p, char *q)
> { int i = 0;
> while (*p && (*p++ == *q++))
> i++;
> return i;
> }
>
> #define M 1
> #define MAXN 500
> char c[MAXN], *a[MAXN];
>
> int main()
> { int i, ch, n = 0, maxi, maxlen = -1;
> while ((ch = getchar()) != EOF) {
> a[n] = &c[n];
> c[n++] = ch;
> }
> c[n] = 0;
> qsort(a, n, sizeof(char *), pstrcmp);
> for (i = 0; i < n-M; i++)
> if (comlen(a[i], a[i+M]) > maxlen) {
> maxlen = comlen(a[i], a[i+M]);
> maxi = i;
> }
> printf("%.*s\n", maxlen, a[maxi]);
> return 0;
> }
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/569uLe79pdcJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Algo for Search in a 2D Matrix
We can consider the 2-d matrix as a heap(also called Young Tableau). We just need to heapify(Youngify) it k-1times,then the element at 0,0 will be kth smallest element. This means we need to remove the k-1 smallest elements from matrix and still maintaining its Row-Col sorted property. Youngify algo:- 1:- put a sentinel value (i,e, INF) 0,0 2:- Now push it leftwards/downwards to maintain the initial property of matrix 3:- If at any point the current element is smaller than both its left and down element, then STOP. This is an in-place operation. We need to consider the sentinel value as highest value,not present in the matrix. It works.Although the matrix is being modified. On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: > > Given a 2D matrix which is both row wise and column wise sorted. Propose > an algorithm for finding the kth smallest element in it in least time > complexity > > A General Max Heap can be used with k space and n+klogk complexity > > Any other solution or even a way by which we dont scan the whole matrix > to find the solution ? > > I > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: > > Given a 2D matrix which is both row wise and column wise sorted. Propose > an algorithm for finding the kth smallest element in it in least time > complexity > > A General Max Heap can be used with k space and n+klogk complexity > > Any other solution or even a way by which we dont scan the whole matrix > to find the solution ? > > I > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: > > Given a 2D matrix which is both row wise and column wise sorted. Propose > an algorithm for finding the kth smallest element in it in least time > complexity > > A General Max Heap can be used with k space and n+klogk complexity > > Any other solution or even a way by which we dont scan the whole matrix > to find the solution ? > > I > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: > > Given a 2D matrix which is both row wise and column wise sorted. Propose > an algorithm for finding the kth smallest element in it in least time > complexity > > A General Max Heap can be used with k space and n+klogk complexity > > Any other solution or even a way by which we dont scan the whole matrix > to find the solution ? > > I > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/GtGv_vms-WQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Interview Question based on histogram
we need to find the amount of water stored on every bar of the histogram. For this, we need to find two values :- v1 :- the highest bar to the left - O(n) v2:- the highest bar to the right - O(n) amount of the water stored on the current bar is Res= ( minimum of the two values(v1,v2) - height of the bar ) (assuming the length & breadth of bar is unity) sum all the values of water store on individual bar Time complexity - O(n) Space Complexity - O(n) On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/SRp0wWOK_kUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
