Fwd: [algogeeks] Interview Question
See this amazing list here: http://www.writeulearn.com/interview-questions/ -- Forwarded message -- From: Umer Farooq <the.um...@gmail.com> Date: Fri, Apr 8, 2011 at 4:22 PM Subject: Re: [algogeeks] Interview Question To: algogeeks@googlegroups.com Ankur, you are rite. He mentioned that we may not know what the data might be. And yes, I agree that he kept the restriction because we may not know what the data is. In that case, I guess bit by bit copying of data from the next node to the current node (it is possible since both the nodes are of same size) and deleting the next node might be the only solution. Anyway, thanks to all for replying :) I owe you guys one :) On Fri, Apr 8, 2011 at 1:08 PM, ankur bhardwaj <ankibha...@gmail.com> wrote: > For the 2nd ques, wat i think is the interviewer has kept the restriction > of not moving the data since you may have a linked list about which you > donot have much information about the structure of the node of the > list(only know about the next pointer) and hence you cannot move the data. > For that, you can free the middle node and copy the last node bit by bit at > the location of the middle node. > > If you still dont want to use the method above, you will have to free the > middle node and reallocate the next node at the location of the middle > node. For this wat i could think was to use the realloc() and put it in a > while loop and terminate the loop only when the address returned matches > with the address possesed by the middle node. But this method is not > efficient and also unwise. If anyone can think of something better, he/she > is invited > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > 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. > -- Umer -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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. -- Regards Tarun Sharma -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Interview Question
Given m*n matrix and k students how can they be placed such that cheatig is minimised. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Interview Question
an useful link http://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-tim On Fri, Apr 19, 2013 at 11:30 PM, kartik n kartik.car...@gmail.com wrote: Hi Nishant i did not understand the code can u please describe a bit Thanks On Fri, Apr 19, 2013 at 10:48 AM, rahul sharma rahul23111...@gmail.comwrote: search the previous posts before posting search for [algogeeks] Amazon Interview Question you will get this -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Interview Question
the code is simply utilizing the xor property as u know xor sets on odd one so, if any array would have numbers odd times repeated their bit will only stay in xor operation else will get nulify. so in first loop bit of 1 and 3 are set, to seperate them we need to divide them using any of their set bits and after that in second loop we are xoring only odd ones whose bits are set and we get our ans in variable x and y. Hope u got it . On Fri, Apr 19, 2013 at 11:30 PM, kartik n kartik.car...@gmail.com wrote: Hi Nishant i did not understand the code can u please describe a bit Thanks On Fri, Apr 19, 2013 at 10:48 AM, rahul sharma rahul23111...@gmail.comwrote: search the previous posts before posting search for [algogeeks] Amazon Interview Question you will get this -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Interview Question
In an array, some numbers occur only once, some numbers occur twice, only one number occur thrice. Find the number occuring thrice ? Space complexity O(1) Time Complexity O(n). We should not use Hash Maps. Please someone help.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Interview Question
int main() { int a[] = {1,2,2,3,3,3,4,4}; int size = sizeof(a)/sizeof(a[0]); int xorr=0; for(int i=0;isize;i++) { xorr^=a[i]; } int x=0,y=0; int xor1=xorr ~(xorr-1); for(int i=0;isize;i++) { if(xor1 a[i]) x^=a[i]; else y^=a[i]; } cout xy; } in this 1 and 3 would be output. as it would be print the number repeated odd times. so ur answer would be in y ie 3 . If there issue with the code let me knw. On Fri, Apr 19, 2013 at 10:52 AM, Krishnan aariyankrish...@gmail.comwrote: In an array, some numbers occur only once, some numbers occur twice, only one number occur thrice. Find the number occuring thrice ? Space complexity O(1) Time Complexity O(n). We should not use Hash Maps. Please someone help.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Interview Question
search the previous posts before posting search for [algogeeks] Amazon Interview Question you will get this -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Interview Question
Hi Nishant i did not understand the code can u please describe a bit Thanks On Fri, Apr 19, 2013 at 10:48 AM, rahul sharma rahul23111...@gmail.comwrote: search the previous posts before posting search for [algogeeks] Amazon Interview Question you will get this -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] INTERVIEW QUESTION
you are right. k is the edit distance we are searching for and a critical parameter. In short you can say- k represents how much error(in terms of edit-distance) you want to tolerate for between document word 'w' and your suggestion. since our data structure can answer queries for e.g. Find all words with k=5) I think we can do better as loading the tree and searching could be costly so, instead of repeatedly firing queries many times for k=1, 2, 3,... i think it's better to do it like: 1. for a given document word 'w': you could start k = 0 (for exact matching, i.e. if w is present in dictionary or not) if returned list.size() =1 then its' a valid word else, if it's NULL fire a query for k=2. From the function return a list of all dictionary words which are *=2*distance from 'w' and return a sorted list based on edit distance. sometimes returned list could be large so you need to filter out the Best possible Suggestions for 'w'. like- you might wanna give preference to those words which were 1 distance away than 2. and in that - those edits which have the edited 'alphabet close to the mispelled one'... like the example- w = REDT [REST is more likely than RENT as 'S' appears closer to 'D' on keyboard than 'N'] etc. or they sound same based on some phoneme model etc. 2. if for k=2 returned list was NULL, you can query for k=5, and check if there are any words with edit-distance *=5*., again returned list could possibly be NULL as well. you might want to limit your search for k (say 5). e.g. if document contains w = ijljhflkjjiulgihh It's highly unlikely that your dictionary will contain any word closer to this (unless ur dictionary contains crazy volcano names from iceland): so for cases like these, after k=5 you can return No Suggestion. It's actually experimentative. you could try any other way also but this way you can limit your no. of queries/per word to 2. A correction: I realize previously I've interchangeably used teh name 'KDTree' and 'bk-tree', both are metric trees but what I really meant was a 'bkTree'. where, a node has arbitrary no. of children and the parent-child edge represents the corresponding Levenshtein distance between them. The basic idea here is to store your dictionary in a data-structure whcih facilitates searching of words based on their edit-distances. On 27 October 2012 22:40, payal gupta gpt.pa...@gmail.com wrote: the question mentioned is as it isi just copy pasted it here. @saurabh thanx for the explainaton of the cube problem i guess that is an appropriate soln for the question. and for the other question on detection of typos and suggestion i would like to know to know what 'k' in your explaination stands for?how are the values allocated to it ? should it be for each wrong word not mentioned in the dictionary we got to check if the word exists with edit distance equal to 1 in dictioanry and so on until we get the correct word??? on Sat, Oct 27, 2012 at 8:12 AM, Saurabh Kumar srbh.ku...@gmail.comwrote: could you please share the link? coz at first glance a Trie looks like a bad choice for this task. I'd go with the Levenshtein distance and a kd-tree. First implement the Levenshtein distance algorithm to calculate the edit distance of two strings. Second, since Levenshtein distance qualifies as a metric space we can use a metric tree like BK-tree to populate it with our dictionary. Choose a random word from dictionary as a root and subsequently insert dictionary words(picking them up randomly) into the tree. A node has arbitrary no. of children. The parent-child edge represents the corresponding Levenshtein distance between them. Building the tree is one time process. Once the tree is built we can devise a way to serialize it and store it. Using this tree we can find all the words with edit-distance less than or equal to, say k. Lets, define a function call in Tree class as: List KDTreeSearch(s, k); which searches for all strings s' in the tree such that |s-s'| = k i.e. all strings which are less than or equal to an edit distance of k. Searching: Start with the Root and calculate the edit-distance of s from root. If its', say d then we know exactly which children we need to descend to in order to find the words with distance =k. Looking for typos: Scan the document and for each word 'w' make a call: list = KDTreeSearch(w, 0); if, list.size() = 1. //We have the word in dictionary. else, list = KDTreeSearch(w, 2); // searching for all words with edit distance of 2 from w returned 'list' can sometimes be large, we can subsequently filter it out by narrowing down our definition of 'typos' e.g. for typo w = REDT [REST is more likely than RENT] or maybe some Phoneme model etc you should discuss this at length with the interviewer. On 27 October 2012 07:03, Raghavan its...@gmail.com wrote: By any chance did you read the new blog post by Gayle Laakmaan.. I guess to detect typos we can use some sort of Trie
Re: [algogeeks] INTERVIEW QUESTION
could you please share the link? coz at first glance a Trie looks like a bad choice for this task. I'd go with the Levenshtein distance and a kd-tree. First implement the Levenshtein distance algorithm to calculate the edit distance of two strings. Second, since Levenshtein distance qualifies as a metric space we can use a metric tree like BK-tree to populate it with our dictionary. Choose a random word from dictionary as a root and subsequently insert dictionary words(picking them up randomly) into the tree. A node has arbitrary no. of children. The parent-child edge represents the corresponding Levenshtein distance between them. Building the tree is one time process. Once the tree is built we can devise a way to serialize it and store it. Using this tree we can find all the words with edit-distance less than or equal to, say k. Lets, define a function call in Tree class as: List KDTreeSearch(s, k); which searches for all strings s' in the tree such that |s-s'| = k i.e. all strings which are less than or equal to an edit distance of k. Searching: Start with the Root and calculate the edit-distance of s from root. If its', say d then we know exactly which children we need to descend to in order to find the words with distance =k. Looking for typos: Scan the document and for each word 'w' make a call: list = KDTreeSearch(w, 0); if, list.size() = 1. //We have the word in dictionary. else, list = KDTreeSearch(w, 2); // searching for all words with edit distance of 2 from w returned 'list' can sometimes be large, we can subsequently filter it out by narrowing down our definition of 'typos' e.g. for typo w = REDT [REST is more likely than RENT] or maybe some Phoneme model etc you should discuss this at length with the interviewer. On 27 October 2012 07:03, Raghavan its...@gmail.com wrote: By any chance did you read the new blog post by Gayle Laakmaan.. I guess to detect typos we can use some sort of Trie implementation.. On Fri, Oct 26, 2012 at 7:50 PM, payal gupta gpt.pa...@gmail.com wrote: Given a cube with sides length n, write code to print all possible paths from the center to the surface. Thanx in advance. Regards, PAYAL GUPTA, NIT-B. -- 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/-/ZaItRf_9A_IJ. 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. -- Thanks and Regards, Raghavan KL -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] INTERVIEW QUESTION
Firstly, that question is missing a lot of details. In absence of those details I'm going to make soem assumptions: 1. cube is odd lengthed, so that we can define a unique center of cube. 2. While traversing from a cell(x, y, z) we can only move into any of the 6 adjacent cells[x(+-)1, y(+-)1, z(+-)1] or you can assume all 8 neighbours also, accordingly change your function to get neighbours. 3. Traversing Paths to surface would be done in a manner such that you cannot revisit a cell, else there can be infinite many possibilities. Since there will be exponential no. of such paths so enumerating them will take exponential amount of time. Simple recursive implementation could go something like this: Algorithm(x, y, z, Path, Visited): // 'Path' is a list of cells visited till now starting from the center cell. 'Visited' is a boolean NxNxN array. or, you can choose to drop the 'Visited' array and implement IsAlreadyVisited(x, y, z) function by searching in teh list 'Path'. If current cell(x, y, z) is a surface cell. Report a Path found and output the 'Path'. return; else for each of the 6 neighbours (unvisited): //(x' y' z') is an unvisited neighbour of (x, y, z) Path.append(x', y', z') Visited(x', y', z') = true; Algorithm(x', y', z', Path, Visited) Depth of recursion is O(N^3). You can use the symmetry argument here and only count the paths ending on a particular surface (say- Top surface) rest of the paths can be calculated by mirroring them onto other surfaces easily, but this will not cut down the asymptotic complexity of the solution. In fact paths ending on a particular face will also exhibit symmetry. On 27 October 2012 10:11, payal gupta gpt.pa...@gmail.com wrote: Sorry ,posted the wrong question initially actually i needed the algo for this question. Thanx. On Saturday, October 27, 2012 7:04:10 AM UTC+5:30, raghavan wrote: By any chance did you read the new blog post by Gayle Laakmaan.. I guess to detect typos we can use some sort of Trie implementation.. On Fri, Oct 26, 2012 at 7:50 PM, payal gupta gpt@gmail.com wrote: Given a cube with sides length n, write code to print all possible paths from the center to the surface. Thanx in advance. Regards, PAYAL GUPTA, NIT-B. -- 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/-/ZaItRf_9A_IJhttps://groups.google.com/d/msg/algogeeks/-/ZaItRf_9A_IJ . To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, Raghavan KL -- 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/-/vVmz5r1gpIYJ. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] INTERVIEW QUESTION
the question mentioned is as it isi just copy pasted it here. @saurabh thanx for the explainaton of the cube problem i guess that is an appropriate soln for the question. and for the other question on detection of typos and suggestion i would like to know to know what 'k' in your explaination stands for?how are the values allocated to it ? should it be for each wrong word not mentioned in the dictionary we got to check if the word exists with edit distance equal to 1 in dictioanry and so on until we get the correct word??? on Sat, Oct 27, 2012 at 8:12 AM, Saurabh Kumar srbh.ku...@gmail.com wrote: could you please share the link? coz at first glance a Trie looks like a bad choice for this task. I'd go with the Levenshtein distance and a kd-tree. First implement the Levenshtein distance algorithm to calculate the edit distance of two strings. Second, since Levenshtein distance qualifies as a metric space we can use a metric tree like BK-tree to populate it with our dictionary. Choose a random word from dictionary as a root and subsequently insert dictionary words(picking them up randomly) into the tree. A node has arbitrary no. of children. The parent-child edge represents the corresponding Levenshtein distance between them. Building the tree is one time process. Once the tree is built we can devise a way to serialize it and store it. Using this tree we can find all the words with edit-distance less than or equal to, say k. Lets, define a function call in Tree class as: List KDTreeSearch(s, k); which searches for all strings s' in the tree such that |s-s'| = k i.e. all strings which are less than or equal to an edit distance of k. Searching: Start with the Root and calculate the edit-distance of s from root. If its', say d then we know exactly which children we need to descend to in order to find the words with distance =k. Looking for typos: Scan the document and for each word 'w' make a call: list = KDTreeSearch(w, 0); if, list.size() = 1. //We have the word in dictionary. else, list = KDTreeSearch(w, 2); // searching for all words with edit distance of 2 from w returned 'list' can sometimes be large, we can subsequently filter it out by narrowing down our definition of 'typos' e.g. for typo w = REDT [REST is more likely than RENT] or maybe some Phoneme model etc you should discuss this at length with the interviewer. On 27 October 2012 07:03, Raghavan its...@gmail.com wrote: By any chance did you read the new blog post by Gayle Laakmaan.. I guess to detect typos we can use some sort of Trie implementation.. On Fri, Oct 26, 2012 at 7:50 PM, payal gupta gpt.pa...@gmail.com wrote: Given a cube with sides length n, write code to print all possible paths from the center to the surface. Thanx in advance. Regards, PAYAL GUPTA, NIT-B. -- 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/-/ZaItRf_9A_IJ. 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. -- Thanks and Regards, Raghavan KL -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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] INTERVIEW QUESTION
Design the data structures and algorithms to detect typos in a document and then provide suggestions to the user. Thanx in advance, Regards, PAYAL GUPTA, NIT-B. -- 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/-/Y_OwlNJ_9f4J. 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] INTERVIEW QUESTION
Given a cube with sides length n, write code to print all possible paths from the center to the surface. Thanx in advance. Regards, PAYAL GUPTA, NIT-B. -- 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/-/ZaItRf_9A_IJ. 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.
Re: [algogeeks] INTERVIEW QUESTION
By any chance did you read the new blog post by Gayle Laakmaan.. I guess to detect typos we can use some sort of Trie implementation.. On Fri, Oct 26, 2012 at 7:50 PM, payal gupta gpt.pa...@gmail.com wrote: Given a cube with sides length n, write code to print all possible paths from the center to the surface. Thanx in advance. Regards, PAYAL GUPTA, NIT-B. -- 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/-/ZaItRf_9A_IJ. 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. -- Thanks and Regards, Raghavan KL -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] INTERVIEW QUESTION
@payal why u need this..??...:P:P -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] INTERVIEW QUESTION
Sorry ,posted the wrong question initially actually i needed the algo for this question. Thanx. On Saturday, October 27, 2012 7:04:10 AM UTC+5:30, raghavan wrote: By any chance did you read the new blog post by Gayle Laakmaan.. I guess to detect typos we can use some sort of Trie implementation.. On Fri, Oct 26, 2012 at 7:50 PM, payal gupta gpt@gmail.comjavascript: wrote: Given a cube with sides length n, write code to print all possible paths from the center to the surface. Thanx in advance. Regards, PAYAL GUPTA, NIT-B. -- 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/-/ZaItRf_9A_IJ. To post to this group, send email to algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, Raghavan KL -- 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/-/vVmz5r1gpIYJ. 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] Interview Question - Probability
You are given n white balls in the beginning. Each day you pick up a ball randomly, color it red and put it back. If it is already colored, you simply put it back. This operation is performed for 'd' days. What is the probability that after d days you will have greater than 'k' balls colored? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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] Interview Question
Divide 2D array into 4 parts. Compute sum of each partition and get max value from the four of them. For all possible partitions get min value of such max values computed. -- 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/-/G5YC7Lq0ovkJ. 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.
Re: [algogeeks] Interview Question based on histogram
//A -area of the cell of histogram // volarr[] -holds the vol of water already present at particular index void fn(int index,int volpoured) { int vcapacity=A*heightarr[index]; if(volpoured+volarr[index]vcapacity) { volarr[index]+=volpoured; return; } if(volpoured+volarr[index]vcapacity) { volpoured-=vcapacity-volarr[index]; volarr[index]=vcapacity; // if the height of the adjacent left and right columns are both less then equal amt of water overflows on either sides if(heightarr[index-1]=heightarr[index] heightarr[index+1]=heightarr[index]) { fn(index+1,volpoured/2); fn(index-1,volpoured/2); } //if the left column has height greater and left has lesser then entire amt flows to left else if(heightarr[index-1]heightarr[index] heightarr[index+1]=heightarr[index] index!=n-1) fn(index+1,volpoured); //if the right column has height lesser and right has height greater then entire amt flows to right else if(heightarr[index+1]heightarr[index] heightarr[index-1]=heightarr[index] index!=0) fn(index-1,volpoured); //if both left and right have height greater then water overflows at the same index else { printf(overflow occurs at index %d\n,index); return; } } // sum of the all elemnts of volarr[] gives the water trapped On Fri, May 18, 2012 at 10:36 AM, Prem Krishna Chettri hprem...@gmail.comwrote: Algo Dear.. Algo.. implementation Anyone can Do.. Req ppl to share their own algo.. No Someones Code Implementation.. On Fri, May 18, 2012 at 9:54 AM, payal gupta gpt.pa...@gmail.com wrote: hope this works.. http://ideone.com/XSJRJ On Fri, May 18, 2012 at 8:20 AM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: It depends on which column you are pouring the water. For example If you choose the shortest column to pour the water then only that column will be filled with water. Please correct me if I am wrong. On Thu, May 17, 2012 at 11:27 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com 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 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. -- regards, Bhaskar Kushwaha Student CSE Third year M.N.N.I.T. Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question based on histogram
It depends on which column you are pouring the water. For example If you choose the shortest column to pour the water then only that column will be filled with water. Please correct me if I am wrong. On Thu, May 17, 2012 at 11:27 AM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: 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 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. -- regards, Bhaskar Kushwaha Student CSE Third year M.N.N.I.T. Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question based on histogram
hope this works.. http://ideone.com/XSJRJ On Fri, May 18, 2012 at 8:20 AM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: It depends on which column you are pouring the water. For example If you choose the shortest column to pour the water then only that column will be filled with water. Please correct me if I am wrong. On Thu, May 17, 2012 at 11:27 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com 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 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. -- regards, Bhaskar Kushwaha Student CSE Third year M.N.N.I.T. Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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] Interview question
*What are the different ways to say, the value of x can be either a 0 or a 1.* -- Nitin Garg Personality can open doors, but only Character can keep them open -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview question
If I have understood the question correctly, Infinite :P You can have infinite ways to express 0 or 1 given that the ways are differentiable amongst themselves. An even number can be considered as a 0 and an odd number as a 1... etc On Wed, Nov 30, 2011 at 8:37 AM, Nitin Garg nitin.garg.i...@gmail.comwrote: *What are the different ways to say, the value of x can be either a 0 or a 1.* -- Nitin Garg Personality can open doors, but only Character can keep them open -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview question
@anup an example what the question meant if(x==1||x==0) { /*stuff*/ } On Wed, Nov 30, 2011 at 11:07 AM, Anup Ghatage ghat...@gmail.com wrote: If I have understood the question correctly, Infinite :P You can have infinite ways to express 0 or 1 given that the ways are differentiable amongst themselves. An even number can be considered as a 0 and an odd number as a 1... etc On Wed, Nov 30, 2011 at 8:37 AM, Nitin Garg nitin.garg.i...@gmail.comwrote: *What are the different ways to say, the value of x can be either a 0 or a 1.* -- Nitin Garg Personality can open doors, but only Character can keep them open -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview question
from where does the index starts, 0 or 1 ? in this, array to be moved is {7, 5, 8} ? and source array the destination | | {9, 7, 5, 8, 1, 5, 4, 8, 10, 1} please explain move_set operation ? On Sat, Jul 9, 2011 at 6:06 PM, Gopi kodaligopi...@gmail.com wrote: Write code to move a set of elements (represented by start and end indexed) in an array to a given destination location (denoted by destination index). For example: Let say our array is {9, 7, 5, 8, 1, 5, 4, 8, 10, 1} move_set (array, start = 1, end = 3, destination = 8) should rearrage the array such that the new array looks like {9, 1, 5, 4, 8, 10, 7, 5, 8, 1} Try to come up with an algorithm that is faster than O(n^2) Thanks Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] interview question
needs explicit function specialisation. be careful with constant strings. T Add(T a, T b) {return a+b ;} template char* Add char* a, char* b) {return strcat((char*)a,b); } surender On Tue, Jul 19, 2011 at 10:17 PM, Anika Jain anika.jai...@gmail.com wrote: here T becomes char *.. u r trying to add two addreses here... On Tue, Jul 19, 2011 at 9:46 PM, nidhi jain nidhi.jain311...@gmail.comwrote: Consider a c++ template funtion templateclass T T Add(T a, T b) {return a+b ;} if this function is called as T c = Add(SAM, SUNG); what will happen? What is the problem in the template declaration/ How to solve the problem. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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] interview question
Consider a c++ template funtion templateclass T T Add(T a, T b) {return a+b ;} if this function is called as T c = Add(SAM, SUNG); what will happen? What is the problem in the template declaration/ How to solve the problem. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] interview question
here T becomes char *.. u r trying to add two addreses here... On Tue, Jul 19, 2011 at 9:46 PM, nidhi jain nidhi.jain311...@gmail.comwrote: Consider a c++ template funtion templateclass T T Add(T a, T b) {return a+b ;} if this function is called as T c = Add(SAM, SUNG); what will happen? What is the problem in the template declaration/ How to solve the problem. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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] Interview question
Write code to move a set of elements (represented by start and end indexed) in an array to a given destination location (denoted by destination index). For example: Let say our array is {9, 7, 5, 8, 1, 5, 4, 8, 10, 1} move_set (array, start = 1, end = 3, destination = 8) should rearrage the array such that the new array looks like {9, 1, 5, 4, 8, 10, 7, 5, 8, 1} Try to come up with an algorithm that is faster than O(n^2) Thanks Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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] Interview Question
Given two arrays of numbers, find if each of the two arrays have the same set of ntegers ? Suggest an algo which can run faster than NlogN without extra space? -- 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/-/W921z1woFOQJ. 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.
Re: [algogeeks] Interview Question: Puzzle: Probability
Navneet, Your answer is correct, it would have been great if you could have explained it for others. I myself took good time to understand it... Here is the answer http://exploreriddles.blogspot.com/2011/06/interview-questions-puzzle.html To maximize the chances of retrieving Red Ball, it is mandatory to reduce the chances of retrieving Blue ball. To reduce the chances. 1. It is possible to put all the black ball in one jar. It will reduce the probability of retrieving black ball to half. 2. Now to reduce the probability of withdrawing Blue balls, need to maximize number of red balls in the jar with blue balls. Maximum red balls we have is 50. So based on above 2 points... one jar can have 1 Red ball, and other will contain rest 99 balls. So probability of choosing red ball is (Probability of Choosing Jar 1)*(Probability of Choosing Red Ball From jar 1) + (Probability of Choosing Jar 2)*(Probability of Choosing Red Ball From jar 2) (1/2)*(1) + (1/2)(49/99) Thanks Regards Vishal Jain MNo: +91-9540611889 Tweet @jainvis Blog @ jainvish.blogspot.com Success taste better when target achieved is bigger. P *We have a responsibility to the environment.* *Before printing this e-mail or any other document, let's ask ourselves whether we need a hard copy.* On Tue, Jun 14, 2011 at 7:47 PM, Navneet Gupta navneetn...@gmail.comwrote: Put one red ball in one jar and rest 99 balls in other jar. Probability in that case is 1/2*1 + 1/2*49//99 On Tue, Jun 14, 2011 at 7:45 PM, Vishal Jain jainv...@gmail.com wrote: Folks, This question was asked during a screening process of a product based company. Please answer. http://exploreriddles.blogspot.com/2011/06/interview-questions-puzzle.html Thanks Regards Vishal Jain Success taste better when target achieved is bigger. P *We have a responsibility to the environment.* *Before printing this e-mail or any other document, let's ask ourselves whether we need a hard copy.* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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] Interview Question: Puzzle: Probability
Folks, This question was asked during a screening process of a product based company. Please answer. http://exploreriddles.blogspot.com/2011/06/interview-questions-puzzle.html Thanks Regards Vishal Jain Success taste better when target achieved is bigger. P *We have a responsibility to the environment.* *Before printing this e-mail or any other document, let's ask ourselves whether we need a hard copy.* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question: Puzzle: Probability
Put one red ball in one jar and rest 99 balls in other jar. Probability in that case is 1/2*1 + 1/2*49//99 On Tue, Jun 14, 2011 at 7:45 PM, Vishal Jain jainv...@gmail.com wrote: Folks, This question was asked during a screening process of a product based company. Please answer. http://exploreriddles.blogspot.com/2011/06/interview-questions-puzzle.html Thanks Regards Vishal Jain Success taste better when target achieved is bigger. P *We have a responsibility to the environment.* *Before printing this e-mail or any other document, let's ask ourselves whether we need a hard copy.* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
For the 2nd ques, wat i think is the interviewer has kept the restriction of not moving the data since you may have a linked list about which you donot have much information about the structure of the node of the list(only know about the next pointer) and hence you cannot move the data. For that, you can free the middle node and copy the last node bit by bit at the location of the middle node. If you still dont want to use the method above, you will have to free the middle node and reallocate the next node at the location of the middle node. For this wat i could think was to use the realloc() and put it in a while loop and terminate the loop only when the address returned matches with the address possesed by the middle node. But this method is not efficient and also unwise. If anyone can think of something better, he/she is invited -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
@ anurag temp - data = ( temp - next ) - data ; but data cannot be moved, ryt?? On 4/6/11, Anurag atri anu.anurag@gmail.com wrote: in case you are given a pointer to the first node simply do temp -next = ( temp - next ) - next . if you are given a pointer to the second node do , temp - data = ( temp - next ) - data ; temp - next = NULL ; correct me if I am wrong . On Mon, Apr 4, 2011 at 9:48 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
@akash ur rite u cannot move data there On Thu, Apr 7, 2011 at 2:35 PM, Akash Mukherjee akash...@gmail.com wrote: @ anurag temp - data = ( temp - next ) - data ; but data cannot be moved, ryt?? On 4/6/11, Anurag atri anu.anurag@gmail.com wrote: in case you are given a pointer to the first node simply do temp -next = ( temp - next ) - next . if you are given a pointer to the second node do , temp - data = ( temp - next ) - data ; temp - next = NULL ; correct me if I am wrong . On Mon, Apr 4, 2011 at 9:48 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Assalaam A'laykum wa Rahmatullahi Wa Barkatuhu Wa A'laykum Assalaam wa Rahmatullahi Wa Barkatuhu Ehab Abdul Rahman Shariff -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
So, is there any other way of doing this? I did it the way anurag did it; but the interviewer asked me to do it without moving the data. On Thu, Apr 7, 2011 at 6:38 PM, Abdul Rahman Shariff ears7...@gmail.comwrote: @akash ur rite u cannot move data there On Thu, Apr 7, 2011 at 2:35 PM, Akash Mukherjee akash...@gmail.comwrote: @ anurag temp - data = ( temp - next ) - data ; but data cannot be moved, ryt?? On 4/6/11, Anurag atri anu.anurag@gmail.com wrote: in case you are given a pointer to the first node simply do temp -next = ( temp - next ) - next . if you are given a pointer to the second node do , temp - data = ( temp - next ) - data ; temp - next = NULL ; correct me if I am wrong . On Mon, Apr 4, 2011 at 9:48 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Assalaam A'laykum wa Rahmatullahi Wa Barkatuhu Wa A'laykum Assalaam wa Rahmatullahi Wa Barkatuhu Ehab Abdul Rahman Shariff -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
in the first case temp -next = ( temp - next ) - next . The middle node will become orphan and it won't be deleted, I guess. in second case I did it the same way. Then he asked me to solve this without moving the data? On Wed, Apr 6, 2011 at 8:03 PM, Anurag atri anu.anurag@gmail.comwrote: in case you are given a pointer to the first node simply do temp -next = ( temp - next ) - next . if you are given a pointer to the second node do , temp - data = ( temp - next ) - data ; temp - next = NULL ; correct me if I am wrong . On Mon, Apr 4, 2011 at 9:48 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
@anurag:the second case of yours requires movement of data if I am not wrong... @umer farooq:pls calrify what does movement of data mean? On Wed, Apr 6, 2011 at 8:33 PM, Anurag atri anu.anurag@gmail.comwrote: in case you are given a pointer to the first node simply do temp -next = ( temp - next ) - next . if you are given a pointer to the second node do , temp - data = ( temp - next ) - data ; temp - next = NULL ; correct me if I am wrong . On Mon, Apr 4, 2011 at 9:48 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards, Kamakshi kamakshi...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
That can be moved. Basically, he is trying to convey that move the data of temp-next to temp. That's perfectly fine. On Thu, Apr 7, 2011 at 2:05 PM, Akash Mukherjee akash...@gmail.com wrote: @ anurag temp - data = ( temp - next ) - data ; but data cannot be moved, ryt?? On 4/6/11, Anurag atri anu.anurag@gmail.com wrote: in case you are given a pointer to the first node simply do temp -next = ( temp - next ) - next . if you are given a pointer to the second node do , temp - data = ( temp - next ) - data ; temp - next = NULL ; correct me if I am wrong . On Mon, Apr 4, 2011 at 9:48 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
1st case: if ptr points to the first node, then ptr-next=(ptr-next)-next will do. 2nd case:i think tehre has to be movement of data from third node to the second node. On 4/4/11, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards, Kamakshi kamakshi...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
@All yeah my solution does move data ... I am very interested in knowing a solution that moves no data , someone please come up with a solution . On Thu, Apr 7, 2011 at 9:23 PM, balaji a peshwa.bal...@gmail.com wrote: lets say there are two pointers - temp1,temp2 and the start of the node is head now, temp1=head; temp2=head-next; temp1-next=temp2-next; now temp1 points to the first node and the temp2 points to the second node(which got deleted from the list). On Thu, Apr 7, 2011 at 5:43 PM, Umer Farooq the.um...@gmail.com wrote: That can be moved. Basically, he is trying to convey that move the data of temp-next to temp. That's perfectly fine. On Thu, Apr 7, 2011 at 2:05 PM, Akash Mukherjee akash...@gmail.comwrote: @ anurag temp - data = ( temp - next ) - data ; but data cannot be moved, ryt?? On 4/6/11, Anurag atri anu.anurag@gmail.com wrote: in case you are given a pointer to the first node simply do temp -next = ( temp - next ) - next . if you are given a pointer to the second node do , temp - data = ( temp - next ) - data ; temp - next = NULL ; correct me if I am wrong . On Mon, Apr 4, 2011 at 9:48 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- A.Balaji -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards Anurag Atri II year Computer Engineering Delhi College Of Engineering -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
Moving the data is unnecessary if in case the whole pointer shifting is meant for the entire node and not for individual elements of the node. temp -next = ( temp - next ) - next the above statement is more than enough to remove the midlle node from the list... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
@ your name last name : please read the question carefully. * * * * On Fri, Apr 8, 2011 at 12:11 AM, your name last name ac08...@gmail.comwrote: Moving the data is unnecessary if in case the whole pointer shifting is meant for the entire node and not for individual elements of the node. temp -next = ( temp - next ) - next the above statement is more than enough to remove the midlle node from the list... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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] Interview Question
Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview Question
in case you are given a pointer to the first node simply do temp -next = ( temp - next ) - next . if you are given a pointer to the second node do , temp - data = ( temp - next ) - data ; temp - next = NULL ; correct me if I am wrong . On Mon, Apr 4, 2011 at 9:48 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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.
Re: [algogeeks] Interview question amazon
int hasPathSum(struct node* node, int sum) { // return true if we run out of tree and sum==0 if (node == NULL) { return(sum == 0); } else { // otherwise check both subtrees int subSum = sum - node-data; return(hasPathSum(node-left, subSum) || hasPathSum(node-right, subSum)); } } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jan 5, 2011 at 12:21 PM, ADITYA KUMAR aditya...@gmail.com wrote: problem has many properties like its a BST with parent pointer we shud think of such a solution which uses its both property If we will think abt the brute force recursive solution its complexity will be O(no_of_nodes*height) which can be made more efficient by putting some restrictions in each recursion sum s remaining sum rs if node.value rs/2 then search in left subtree for rs-node.value and s if node.value rs/2 then search in both subtree for rs-node.value and s stop recursion if rs-node.value ==0 or node.value=s On Sun, Dec 26, 2010 at 10:38 PM, MAC macatad...@gmail.com wrote: you are given a bst where each node has a int value , parent pointer , and left and right pointers , write a function to find a path with a given sum value. Path can go from left subtree tree , include root and go to right tree as well . we need to find these paths also . 5 1 10 0 2 6 11 so to find 16 we say it is 1 to 5 to 10 -- thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. 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] Interview Question
Given a dictionary find out if given word can be made by two words in dictionary. For eg. given newspaper you have to find if it can be made by two words. (news and paper in this case). I cant think of anything but brute force. Thanks, Vikas -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
you can optimize BF newspaper first word you will search n then ne then new then news..and so onif at any point of time first word exist in dictionary then only see whether the word with the remaining characters exist in the dictionary or not. On Tue, Jan 11, 2011 at 5:57 PM, Vikas Singh vikas.sing...@gmail.comwrote: Given a dictionary find out if given word can be made by two words in dictionary. For eg. given newspaper you have to find if it can be made by two words. (news and paper in this case). I cant think of anything but brute force. Thanks, Vikas -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
Use trie (or similar DS). For each word, try to find second part of the target in a linear time O(length). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
lalla..bruteforce na bako.. :P On Tue, Jan 11, 2011 at 6:07 PM, manoj lalavat manoj.lala...@gmail.comwrote: you can optimize BF newspaper first word you will search n then ne then new then news..and so onif at any point of time first word exist in dictionary then only see whether the word with the remaining characters exist in the dictionary or not. On Tue, Jan 11, 2011 at 5:57 PM, Vikas Singh vikas.sing...@gmail.comwrote: Given a dictionary find out if given word can be made by two words in dictionary. For eg. given newspaper you have to find if it can be made by two words. (news and paper in this case). I cant think of anything but brute force. Thanks, Vikas -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
please ignore earlier message...it was supposed to be a private message.. On Tue, Jan 11, 2011 at 6:52 PM, Vikas Singh vikas.sing...@gmail.comwrote: lalla..bruteforce na bako.. :P On Tue, Jan 11, 2011 at 6:07 PM, manoj lalavat manoj.lala...@gmail.comwrote: you can optimize BF newspaper first word you will search n then ne then new then news..and so onif at any point of time first word exist in dictionary then only see whether the word with the remaining characters exist in the dictionary or not. On Tue, Jan 11, 2011 at 5:57 PM, Vikas Singh vikas.sing...@gmail.comwrote: Given a dictionary find out if given word can be made by two words in dictionary. For eg. given newspaper you have to find if it can be made by two words. (news and paper in this case). I cant think of anything but brute force. Thanks, Vikas -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
Wouldn't that be O(n2) . what if n, ne, new, news, newsp etc all are valid words ? Cant it be optimized? On Tue, Jan 11, 2011 at 6:27 PM, juver++ avpostni...@gmail.com wrote: Use trie (or similar DS). For each word, try to find second part of the target in a linear time O(length). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
how abt this.. Pass1 = look whether words like n,ne,new,news.exist or not...store information in some array like n is not found so is ne but new is found and news is found so array will be like 0,0,1,1. Pass2 = do d same from from the end... r,er,per,aper,paper 0,0,1,0,1 Pass3 on first array whenever you find 1see index [len(newspaper) - (index of one in first array)] in second array...if its one we have words n so on On Tue, Jan 11, 2011 at 6:58 PM, Vikas Singh vikas.sing...@gmail.comwrote: Wouldn't that be O(n2) . what if n, ne, new, news, newsp etc all are valid words ? Cant it be optimized? On Tue, Jan 11, 2011 at 6:27 PM, juver++ avpostni...@gmail.com wrote: Use trie (or similar DS). For each word, try to find second part of the target in a linear time O(length). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
What do you mean by N? If N - size of the dictionary. And L- maximum length of the words then above algo is O(N*L) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
words and...so on... on dictionaries lookup is O(1) now think abt complexity... pass1 for (1 to N) example here N=strlen(newspaper) other passes are also same... On Tue, Jan 11, 2011 at 8:07 PM, juver++ avpostni...@gmail.com wrote: What do you mean by N? If N - size of the dictionary. And L- maximum length of the words then above algo is O(N*L) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
If you represent dictionary as a hash table, lookup costs you O(L) at least! Cause you need to calculate hash for the string. But for the trie it is O(L) in a worst case. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
I agree with the trie solution. But now how do you generalise it for K. I mean a word can be made from k other words. On Wed, Jan 12, 2011 at 12:53 AM, juver++ avpostni...@gmail.com wrote: If you represent dictionary as a hash table, lookup costs you O(L) at least! Cause you need to calculate hash for the string. But for the trie it is O(L) in a worst case. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview Question
This problem has DP solution in O(n^2) I think. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Interview question amazon
problem has many properties like its a BST with parent pointer we shud think of such a solution which uses its both property If we will think abt the brute force recursive solution its complexity will be O(no_of_nodes*height) which can be made more efficient by putting some restrictions in each recursion sum s remaining sum rs if node.value rs/2 then search in left subtree for rs-node.value and s if node.value rs/2 then search in both subtree for rs-node.value and s stop recursion if rs-node.value ==0 or node.value=s On Sun, Dec 26, 2010 at 10:38 PM, MAC macatad...@gmail.com wrote: you are given a bst where each node has a int value , parent pointer , and left and right pointers , write a function to find a path with a given sum value. Path can go from left subtree tree , include root and go to right tree as well . we need to find these paths also . 5 1 10 0 2 6 11 so to find 16 we say it is 1 to 5 to 10 -- thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Interview question
Given a Binary Matrix of 0's and 1's. Write an algorithm to: 1) Print the largest Rectangular Sub-matrix with all 1's. 2)Print the largest Sub-matrix with all boundary elements 0. Explain your whole algorithm with an example. -- thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] interview-question
given a complete binary tree (either a node is a leaf node or has two children) every leaf node has value 0 or 1. every internal node has value as the AND gate or OR gate. you are given with the tree and a value V. you have to output the minimum number of flips (AND to OR or OR to AND) if the evaluated value is not equal to V, if it is equal return 0, if not possible return -1. you can just change the value of internal nodes i.e can make and to or , or to and to get the desired output give the minimum number of flips required to get the desired output. -- -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] interview question
write a program for catlog catlog contain subcatlog or product . we can futher expand catlog/subcatalog. product is leaf of catalog [like composite pattern] 1. write a c++ program to display the product on basis of product id. write a copy constucter and assingement operator for catalog class example Business / \ Compurter Cloths /\ \ monitor(product) sell shirt(prodcut [business,computer,cloths,sell are catalog] [monitor and shits are product] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Interview question: can this be done?
Just back from an job interview, one question really sucks! Any idea? It is given 45 mintues to state your thought (either how to do it, or why you can not do it). (Type from what I remember) 1) You choose 5000 different intergers (you can choose any 5000 integers you want to use, just be sure they are different from each other). 2) Take 200 numbers from them by random to form a set. Repeat this many times so you will have many such set. If you like, you can assume these sets are saved to disk (cause there are many of them), and step 3 is to test them one by one. 3) For each set (200 numbers), can you design a method that can QUICKLY test whether a certain number k is in it or not? (k belongs to the initial 5000 numbers) 4) Repeat step 3 many times with different k. 5) Require: the memory and time is limited, which means: the most naive method of scaning through (linear or use a hashtable) each set to test k, and repeat for each set will not give you credit. 6) If your method needs some calculation time, make sure the test step takes as littile time as possible (if you have whatever preprocess, they can take longer time). 7) If you think this can not be done (you can not do much better than the naive method above), please state your reasons (what will be the limit). - Try to think it over before read my wrong method, in case it may mislead you. :-)) .. .. .. .. .. What I think is to find a method to hash these 200 integers to one or two small values. My answer at that time, which unluckly did not work, was to use prime numbers: Select 5000 prime numbers. For each 200 randomly selected numbers, times them up to get a hash value v. When test, just see if v can be divided by k. So the test step only has a divide operation, and since we hash 200 numbers to one value, this does not need to use much memory since we only need to keep one v for each set. However, when I came back from interview, I found my method will not work with 5000 initial numbers: times 200 prime number will get value out of range even if we use long type data. Prime numbers are so big, even if I define my own number type, it is quite possible to use more memory than the 200 number set itself! Maybe this can not be done, I am thinking, but I can not say why it can not be done efficiently. :-(