[algogeeks] Amazon Interview Question
Given an array of integers where some numbers repeat once, some numbers repeat twice and only one number repeats thrice, how do you find the number that gets repeated 3 times? Does this problem have an O(n) time and O(1) space solution? No hashmaps please! -- 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] Re: seperate diff types of coins
@Gupta: Given the balance scale and only the eight coins, with no knowledge of the values of their weights, here is an algorithm, probably not optimal, to label each coin x, y, a, or b, with three x's, three y's, one a, and one b. 1. Weigh the coins pairwise, c1 vs c2, then min(c1,c2) vs c3, etc., to find the lightest coin and note whether it occurs only once or three times. If the lightest coin occurs three times, label those coins x and set them aside. If it occurs once, label it a and set it aside. This takes 7 weighings. 2a. If there are seven coins remaining after step 1 (we labeled a), the heavier coin in the last weighing in step 1 is the second lightest of the eight coins. Compare the other six coins to find the lightest and note whether it occurs once or twice. If it occurs twice, label those two coins and the second-lightest from step 1 as x. If it occurs once, label that coin b. This takes 5 weighings. 2b. If there are five coins remaining after step 1 (we have labeled x), repeat the process to find the lightest of them and note whether it occurs one or three times. If the lightest coin occurs three times, label them y and set them aside. If it occurs once, label that coin a. and set them aside. This takes 4 weighings. 3a. If there are six coins remaining after step 2 (we have labeled a and b), then the heaver coin in the last weighing of step 2 is the third-lightest of the eight coins. Compare it with any four of the remaining coins. If it matches 2 of them, label those three coins x. If it matches only 1 of them, label those two coins and the one that was unweighed in this step as x.Label the remaining coins y. This takes 4 weighings. 3b. If there are four coins remaining after step 2 (we have labeled x and a), find the lightest of them and note whether the lightest occurs one or three times.Label the set of three coins y and the single coin b. This takes 3 weighings. 3c. If there are two coins remaining after step 2 (we have labeled x and y), label one of the remaining coins a and the other b. This takes no weighings. This solves the problem in at most 7 + 5 + 4 = 16 weighings. Dave On Tuesday, July 10, 2012 9:30:31 PM UTC-5, payal gupta wrote: > @ Dave sir > the balance considered here is simple balance scale incapable of > giving any numeric reading and the we are unaware of any relationship > between x,y,a,b or any kind denominations prioirity in terms of > weights... > @navin.. > "3 of them weigh x" means 3 of the coins individually weigh x gms,it > isnt the cumulative sum of the coins as u considered ,thats what i got > from the question.. > Correct me if i'm wrong. > Could it be done it done in lesser than 8 weighings?? > > Regards, > PAYAL GUPTA. > > On 7/10/12, Dave wrote: > > @Gupta: You haven't defined the problem sufficiently. > > > > What type of scale do we have, a balance scale or one that gives a > numeric > > reading? > > > > Do we know x, y, a, and b, or are you just saying that one set of three > > coins weigh the same, another set of three also weigh the same but have > > different weight that the first set, and the remaining two weigh > different > > amounts than each other and the two sets? > > > > Is there any known relationship between x, y, a, and b? We can assume > > without loss of generality that x < y and a < b, but what about the > > relationships between x and a, x and b, y and a, and y and b? Knowing > more > > will allow a solution with fewer weighings than knowing less. > > > > Dave > > > > On Tuesday, July 10, 2012 12:33:47 AM UTC-5, payal gupta wrote: > > > >> You have 8 coins. 3 of them weigh x units, 3 y units, 1 a units and 1 b > >> units. They are all mixed and look identical. What are the minimum no > of > >> weighings reqd to seperate the for types of coins??? > >> > > > > -- > > 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/-/c41Sw3CqNz4J. > > 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/1iUGyrlu90AJ. 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] Need links for Problem solving interview questions(non DS and algorithmic) probably with how to reach a solution
http://uva.onlinejudge.org/index.php http://www.careercup.com/ http://www.codershunt.com/ http://www.cs.sunysb.edu/~skiena/392/programs/ https://www.interviewstreet.com/challenges/# and in last topcoder, codechef and stack overflow all three are best... On Wed, Jul 11, 2012 at 10:37 AM, raghavan M wrote: > hi > I am looking for some web links where i can find problem solving questions > and method that one can use to solve the problems that are asked in > interviews.Please let me know if you came across one. > > Thanks > Rag > > -- > 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. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, India Mobile No: +91-8798049298, +91-9424738542 -- 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] Re: [Google] Finds all the elements that appear more than n/3 times
can some body please explain voting algo to me .
On Wed, Jul 11, 2012 at 12:42 PM, Navin Kumar wrote:
> @sachin:
>
>
> http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
>
> On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal
> wrote:
>
>> To Mr. B
>> how will you find median in O(n) time? please elaborate.
>>
>>
>> On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:
>>>
>>> I found a similar solution looking somewhere else.
>>>
>>> The solution for this problem is:
>>> a. There can be atmost 3 elements (only 3 distinct elements with each
>>> repeating n/3 times) -- check for this and done. -- O(n) time.
>>> b. There can be atmost 2 elements if not above case.
>>>
>>> 1. Find the median of the input. O(N)
>>> 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
>>> for output if yes}*
>>> 3. partition the array based on median found above. - O(n) --
>>> {partition is single step in quicksort}
>>> 4. find median in left partition from (3). - O(n)
>>> 5. check if median element is repeared n/3 times or more - O(n) *{mark
>>> for output if yes}*
>>> 6. find median in right partition from (3). - O(n)
>>> 7. check if median element is repeared n/3 times or more - O(n) *{mark
>>> for output if yes}*
>>>
>>> its 7*O(N) => O(N) solution. Constant space.
>>>
>>> we need not check further down or recursively. {why? reason it.. its
>>> simple}
>>>
>>>
>>> On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:
Design an algorithm that, given a list of n elements in an array, finds
all the elements that appear more than n/3 times in the list. The algorithm
should run in linear time
( n >=0 ).
You are expected to use comparisons and achieve linear time. No
hashing/excessive space/ and don't use standard linear time deterministic
selection algo.
--
>> 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/-/PxIJd3So3tkJ.
>>
>> 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]
hi .. can anybody tell the Nth term of the following series... 9 96 685 4992. -- 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] Need links for Problem solving interview questions(non DS and algorithmic) probably with how to reach a solution
hi I am looking for some web links where i can find problem solving questions and method that one can use to solve the problems that are asked in interviews.Please let me know if you came across one. Thanks Rag -- 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] Re: MS Q
anybody have informaton regarding questions asked in written and interview of capillary technology for developer post please share at bhardwaj.ankit...@gmail.com thanks in advance. On 5/22/12, Navin.nitjsr wrote: > If the matrix is 4-connected, we can use the same matrix. > now we have to find the total number of connected components of a graph. > consider > 1 1 1 0 0 1 1 0 1 > 0 1 1 1 0 0 1 0 0 > 1 1 0 1 0 1 1 1 0 > 0 0 0 0 0 0 0 0 1 > we can use bfs/dfs to mark the nodes as visited and thus total connected > components can be counted. > > > On Tuesday, 10 January 2012 07:09:46 UTC+5:30, ashgoel wrote: >> >> there is a matrix of 1 and 0 >> 1 is a island and 0 is water >> 1-1 together makes one island >> calculate total no of islands >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/JiDXnyVHn4YJ. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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] Re: how to print "tata" from "tatapower" using only strcat and strcpy???
char str[5] , *p , str1[]="tatapower;
p=str1
while(*p)
{
if(*p=='t'||*p=='a')
if(str==NULL)
strcpy(str,*p);
else
strcat(str,*p);
p++;
}
On Tuesday, 10 July 2012 16:15:16 UTC+5:30, amrit harry wrote:
>
>
--
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/-/143UOL5GkJMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: [Linkedlist] Given only a pointer to a node to be deleted in a singly linked list how you handle deleting last node
Even if assuming the allocation is uniform. Knowing the address of previous node is the limitation on SLL in constant time. Also, if we know the address of previous node. we are done. But, finding it will take O(n) time. On Wednesday, 11 July 2012 03:36:46 UTC-4, invictus wrote: > > Well, we can do one thing but it might not work in all cases. > > First of all you need to know the node structure. Assume it has an int and > a next pointer. > > Assumption - Memory allocation for nodes did not happened at random > location but uniformly. > 1. Find out the memory address contained in the next pointer of current > node. Compute the difference between address of current and next node. > 2. Compute the address for previous node (to check the above assumption, > figure out the address at memory for the next pointer is allocated, check > the contents of that pointer, if that content matches the memory location > of the current node address , then our above assumption was right. > 3. Now we have the address of the last node, copy the current node's data > in the last node and modify it's next pointer to point to current node's > next > we can also have a temporary pointer for recording the location of current > node and deleting it after step.3 > > Hope the solution is clear. > > On Tuesday, 10 July 2012 01:36:17 UTC+5:30, subharansu wrote: >> >> Is there any solution which will take care deleting a node Given only a >> pointer to a node to be deleted in a singly linked list( >> *How Do we consider deleting the last node*) * >> * >> >> *Subhransu >> * >> > -- 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/-/2MBS7TD8_aAJ. 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] Directi Interview Ques
@abinesh: The solution given has a very very high complexity. as it finds all possiblilities and tests each one of it. is it *n*[(2n!)/(n! * n!)]* --> This is exponential solution. I am not sure but, there must be a DP solution to this . --Sravan Reddy On Wed, Jul 11, 2012 at 12:15 AM, arumuga abinesh wrote: > http://www.geeksforgeeks.org/archives/17743 > > Using the above problem we get all possible merges , at each possible > merge, we can calculate the sum. > > On 7/11/12, Mr.B wrote: > > I think you missed the question: > > Its a stable merge. (order of elements in each array should be same) > > Sorting will destroy the original order. > > > > Thanks, > > Mr.B > > [Please include complexities and pseudo-code] > > > > On Tuesday, 10 July 2012 16:18:04 UTC-4, Akshat wrote: > >> > >> Here you have to first sort both the arrays A and B and merge both the > >> arrays to form the sorted array C > >> > >> -- > >> > >> > >> Akshat Sapra > >> Under Graduation(B.Tech) > >> IIIT-Allahabad(Amethi Campus) > >> *--* > >> sapraaks...@gmail.com > >> akshatsapr...@gmail.com > >> rit20009008@ iiita.ac.in > >> > > > > -- > > 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/-/uCRLEzDBWAAJ. > > 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] Re: [Linkedlist] Given only a pointer to a node to be deleted in a singly linked list how you handle deleting last node
Well, we can do one thing but it might not work in all cases. First of all you need to know the node structure. Assume it has an int and a next pointer. Assumption - Memory allocation for nodes did not happened at random location but uniformly. 1. Find out the memory address contained in the next pointer of current node. Compute the difference between address of current and next node. 2. Compute the address for previous node (to check the above assumption, figure out the address at memory for the next pointer is allocated, check the contents of that pointer, if that content matches the memory location of the current node address , then our above assumption was right. 3. Now we have the address of the last node, copy the current node's data in the last node and modify it's next pointer to point to current node's next we can also have a temporary pointer for recording the location of current node and deleting it after step.3 Hope the solution is clear. On Tuesday, 10 July 2012 01:36:17 UTC+5:30, subharansu wrote: > > Is there any solution which will take care deleting a node Given only a > pointer to a node to be deleted in a singly linked list( > *How Do we consider deleting the last node*) * > * > > *Subhransu > * > -- 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/-/u2WRmvPkGTUJ. 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] Re: [Google] Finds all the elements that appear more than n/3 times
@sachin:
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal wrote:
> To Mr. B
> how will you find median in O(n) time? please elaborate.
>
>
> On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:
>>
>> I found a similar solution looking somewhere else.
>>
>> The solution for this problem is:
>> a. There can be atmost 3 elements (only 3 distinct elements with each
>> repeating n/3 times) -- check for this and done. -- O(n) time.
>> b. There can be atmost 2 elements if not above case.
>>
>> 1. Find the median of the input. O(N)
>> 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
>> for output if yes}*
>> 3. partition the array based on median found above. - O(n) -- {partition
>> is single step in quicksort}
>> 4. find median in left partition from (3). - O(n)
>> 5. check if median element is repeared n/3 times or more - O(n) *{mark
>> for output if yes}*
>> 6. find median in right partition from (3). - O(n)
>> 7. check if median element is repeared n/3 times or more - O(n) *{mark
>> for output if yes}*
>>
>> its 7*O(N) => O(N) solution. Constant space.
>>
>> we need not check further down or recursively. {why? reason it.. its
>> simple}
>>
>>
>> On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:
>>>
>>>
>>> Design an algorithm that, given a list of n elements in an array, finds
>>> all the elements that appear more than n/3 times in the list. The algorithm
>>> should run in linear time
>>>
>>> ( n >=0 ).
>>>
>>> You are expected to use comparisons and achieve linear time. No
>>> hashing/excessive space/ and don't use standard linear time deterministic
>>> selection algo.
>>>
>>> --
> 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/-/PxIJd3So3tkJ.
>
> 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] Re: [Google] Finds all the elements that appear more than n/3 times
@sachin: you can find median in linear sort.
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal wrote:
> To Mr. B
> how will you find median in O(n) time? please elaborate.
>
>
> On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:
>>
>> I found a similar solution looking somewhere else.
>>
>> The solution for this problem is:
>> a. There can be atmost 3 elements (only 3 distinct elements with each
>> repeating n/3 times) -- check for this and done. -- O(n) time.
>> b. There can be atmost 2 elements if not above case.
>>
>> 1. Find the median of the input. O(N)
>> 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
>> for output if yes}*
>> 3. partition the array based on median found above. - O(n) -- {partition
>> is single step in quicksort}
>> 4. find median in left partition from (3). - O(n)
>> 5. check if median element is repeared n/3 times or more - O(n) *{mark
>> for output if yes}*
>> 6. find median in right partition from (3). - O(n)
>> 7. check if median element is repeared n/3 times or more - O(n) *{mark
>> for output if yes}*
>>
>> its 7*O(N) => O(N) solution. Constant space.
>>
>> we need not check further down or recursively. {why? reason it.. its
>> simple}
>>
>>
>> On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:
>>>
>>>
>>> Design an algorithm that, given a list of n elements in an array, finds
>>> all the elements that appear more than n/3 times in the list. The algorithm
>>> should run in linear time
>>>
>>> ( n >=0 ).
>>>
>>> You are expected to use comparisons and achieve linear time. No
>>> hashing/excessive space/ and don't use standard linear time deterministic
>>> selection algo.
>>>
>>> --
> 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/-/PxIJd3So3tkJ.
>
> 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.
