Re: [algogeeks] Find longest consecutive subsequence
Use bitwise hashmap.
On Thu, Jan 30, 2014 at 8:46 PM, Don dondod...@gmail.com wrote:
No. If you start at any number in a sequence it will find the entire
sequence. There is no need to start again at some other number in that
sequence.
Don
On Wednesday, January 29, 2014 12:19:21 AM UTC-5, Varun Sachdeva wrote:
If we don't process the same number more than once, does it not create a
situation when we miss out on the solution?
For example the digit 6 in this sequence:
1,2,3,4,0,2,3,1,4,5,2,4,3,4,5,6,7,8,9
Varun
Varun Sachdeva
On 28 January 2014 00:29, Don dond...@gmail.com wrote:
This works, and I think is O(N*log(N)) which is similar to sorting and
scanning.
An unordered map will be faster, in general. It could be made faster in
most cases by looping over items left in the map, to avoid processing the
same number more than once. Also, when the number of items left in the map
is less than max, there is no need to continue because you know they can't
form a sequence longer than max.
int longest_sequence(vectorint nums)
{
unordered_mapint,bool mp;
int max = 0;
for(unsigned int i = 0; i nums.size(); i++)
mp[nums[i]] = true;
while(mp.size() max)
{
int i;
int n = mp.begin()-first; // Pick first item in map
mp.erase(n);
int count = 1;
for(i = n+1; mp.contains(i); ++i)
{
++count;
mp.erase(i);
}
for(i = n-1; mp.contains(i); --i)
{
++count;
mp.erase(i);
}
if (count max) max = count;
}
return max;
}
On Monday, January 27, 2014 9:17:56 AM UTC-5, Nishant Pandey wrote:
I think this the most optimized code i have writen :
#include iostream
#include vector
#include map
using namespace std;
int longest_sequence(vectorint nums) {
mapint,bool mp;
int count;
int max = -;
int n = 0;
for(unsigned int i = 0; i nums.size(); i++) {
mp[nums[i]] = true;
}
for(unsigned int i =0;inums.size();i++) {
n = nums[i];
mp.erase(n);
count = 1;
while(mp.find(n+1)!= mp.end()) {
count++;
mp.erase(n+1);
n++;
}
n = nums[i];
while(mp.find(n-1)!= mp.end()) {
count++;
mp.erase(n-1);
n--;
}
if(count max) {
max = count;
}
}
return max;
}
int main() {
// your code goes here
cout Jai Ganesha;
vectorint vc;
vc.push_back(5);
vc.push_back(20);
vc.push_back(45);
vc.push_back(3);
vc.push_back(98);
vc.push_back(4);
vc.push_back(21);
vc.push_back(1);
vc.push_back(99);
vc.push_back(2);
cout endl longest_sequence(vc);
return 0;
}
NIshant Pandey
Cell : 9911258345
Voice Mail : +91 124 451 2130
On Mon, Jan 27, 2014 at 4:29 PM, Amol Sharma amolsh...@gmail.comwrote:
Given an array of positive numbers arranged in any order. You have
to find the length of longest continuos(difference of +1, -1) sequence in
the array.
for eg.
A[] = *5*, 20, 45, *3*, 98, *4*, 21, *1*, 99, *2*
then longest continuos subsequence is [1, 2, 3, 4, 5] and hence the
output should be *5*, the length of this sequence.
Other Continuos sequence are -
[20, 21]
[45]
[98, 99]
[21]
A[i] can be 10^6, so hashing is not an option.
Possible Approach is by sorting and time complexity will be O(nlogn).
Does anyone have better approach for this ?
--
Thanks and Regards,
Amol 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+...@googlegroups.com.
--
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+...@googlegroups.com.
--
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.
--
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] kth smallest element in 2 sorted arrays
Maintain the invaraint : i + j = k -1 if B[j-1] A[i] B[j], then A[i] must be the kth smallest else if A[i-1] B[j] A[i], then B[j] must be the kth smallest If the above conditions are not satisfied, subdivide the arrays. On Thu, Jun 13, 2013 at 1:41 PM, sourabh jain wsour...@gmail.com wrote: its same as finding a median of two sorted arrays only. http://www.geeksforgeeks.org/median-of-two-sorted-arrays/ On Sun, Jun 9, 2013 at 4:49 PM, rahul sharma rahul23111...@gmail.comwrote: Please suggest logm+logn aproach... can be easily done in o(k) How to do in logm +logn plz suggest algo -- 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. -- Regards, Sourabh Kumar Jain +91-8971547841 -- 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. -- 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] UTF-8 encoding
Lets suppose there is a UTF8 encoding scheme. You have to check if a string is valid UTF8 or not. Just read the below given description. UTF-8 is a variable-length encoding of letters or runes. If the most significant bit of the first byte is 0, the letter is 1 byte long. Otherwise, its length is the number of leading 1’s in the first byte. If a letter is more than one byte long, all subsequent runes start with 10. Here’s a chart: UTF-8 encoding scheme is described below: 0XXX = this is the entire rune 10XX = this is a continuation of the rune from the previous byte 110X = this is the start of a 2-byte rune. 1110 = this is the start of a 3-byte rune. 0XXX = this is the start of a 4-byte rune. 10XX = this is the start of a 5-byte rune. 110X = this is the start of a 6-byte rune. 1110 = this is the start of a 7-byte rune. = this is the start of a 8-byte rune. For example, a 3-byte rune would be 1110 10XX 10XX. Write a function that decides whether a given byte array (or string) is valid UTF-8 encoded text. -- 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] least common ancestore bst
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int );
/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
/* If we have reached a leaf node then LCA doesn't exist
If root-data is equal to any of the inputs then input is
not valid. For example 20, 22 in the given figure */
if(root == NULL || root-data == n1 || root-data == n2)
return -1;
/* If any of the input nodes is child of the current node
we have reached the LCA. For example, in the above figure
if we want to calculate LCA of 12 and 14, recursion should
terminate when we reach 8*/
if((root-right != NULL)
(root-right-data == n1 || root-right-data == n2))
return root-data;
if((root-left != NULL)
(root-left-data == n1 || root-left-data == n2))
return root-data;
if(root-data n1 root-data n2)
return root-data;
if(root-data n1 root-data n2)
return leastCommanAncestor(root-left, n1, n2);
if(root-data n1 root-data n2)
return leastCommanAncestor(root-right, n1, n2);
}
On Sat, May 18, 2013 at 2:29 AM, Mangal Dev Gupta dev.it...@gmail.comwrote:
static Node LCA(Node root, int a, int b) {
if (root == null)
return null;
if (root.getData() == a || root.getData() == b)
return root;
Node root1 = LCA(root.getLeft(), a, b);
Node root2 = LCA(root.getRight(), a, b);
if (root1 != null root2 == null)
return root1;
else if (root1 == null root2 != null)
return root2;
else if (root1 != null root2 != null)
return root;
else
return null;
}
On Fri, May 17, 2013 at 9:49 AM, avinesh saini avinesh.sa...@gmail.comwrote:
If one node is parent of other then Parent Node is lowest common
ancestor.
Source- http://en.wikipedia.org/wiki/Lowest_common_ancestor (just read
it)
On Mon, May 13, 2013 at 1:42 AM, rahul sharma rahul23111...@gmail.comwrote:
[image: BST_LCA]
what should be ancestor of 12 and 14.it should be 12 or
14...if 12 then for 20 and 22 also it is 20...if 12 ans 14 has
ancestor as 8 then for 20 and 22 it is NULL.
@allplz give me clear one line definition in case if one node is
parent of other then what is LCA
On Sun, Apr 21, 2013 at 10:32 PM, Tushar Patil
tushar01pa...@gmail.comwrote:
@rahul : It's fine solution, but can we check the root-data == n1 ||
n2 before calling function recursively, I think if we check this condition
1st it will reduce unnecessary function calls.
Correct me if i am wrong?
Thanks,
Tushar Patil.
On Sun, Apr 21, 2013 at 10:26 PM, rahul sharma rahul23111...@gmail.com
wrote:
int leastCommanAncestor(struct node* root, int n1, int n2)
{
if(root==NULL)
return -1;
if(root-datan1 root-datan2)
return leastCommanAncestor(root-left,n1,n2);
else if(root-datan1 root-datan2)
return leastCommanAncestor(root-right,n1,n2);
return root-data;
}
Does this code miss any case?N suppose if we have to find LCA of n1
and n2 and suppose n1 is parent of n2 ..then this will return n1..is this
fyn or if n1 is parent of n2 then we should return -1??
Plz. comment
--
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.
--
*
*
*regards,*
*Avinesh Kumar
National Institute of Technology, Calicut.*
*Kerala- 673601*
*+91 7849080702*
--
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.
--
Mangal Dev
Ph No. 7411627654
Member Technical Staff
Oracle India Pvt Ltd
mangal@oracle.com mangal.d...@oracle.com
--
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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop
Re: [algogeeks] Re: Highest reminder
Hi Ankit, If that is the case, I can very well say, 23 = 2 X 1 + 21 If you divide 23 by 11, remainder would be 1 and not 12. On Thu, May 30, 2013 at 1:16 PM, Ankit Agarwal ankuagarw...@gmail.comwrote: Hi, 23 = 11 X 1 + 12. Thus 12 would the highest remainder. Not 11 On Thu, May 30, 2013 at 10:24 AM, Sreenivas Sigharam sighar...@gmail.comwrote: Dave's explanation was clear..and informative.. Thank you Dave.. Thank you , Soumya Prasad, for a simple but nice topic.. Thank you, Sigharam. On Thu, May 30, 2013 at 10:16 AM, Sanjay Rajpal sanjay.raj...@live.inwrote: Hi Ankit, for 23, how can the remainder be 12 ? Can you elaborate more ? *Regards,* *Sanjay Kumar* *Software Engineer(Development)* *Winshuttle Softwares(India) Pvt. Ltd.* *Mobile +91-89012-36292, +91-80535-66286* *Email: sanjay.ku...@winshuttle.com* * *** * * ** * * On Thu, May 30, 2013 at 9:40 AM, Ankit Agarwal ankuagarw...@gmail.comwrote: @Dave: For N = 23, the highest remainder is 12, not 11 On Thu, May 30, 2013 at 5:02 AM, Dave dave_and_da...@juno.com wrote: The highest remainder when dividing n by a number less than n is floor((n-1)/2). For n = 11, floor((11-1)/2) = floor(10/2) = floor(5) = 5. For n = 17, floor((17-1)/2) = 8 For n = 23, floor((23-1)/2) = 11 For n = 12, floor((12-1)/2) = floor(11/2) = floor(5.5) = 5. Etc. Dave On Wednesday, May 29, 2013 1:36:13 PM UTC-5, Ankit wrote: Hi, Number 23: = 11 * 1 + 12 Number/2 = 11.5 Number 17: = 9 * 1 + 8 Number/2 = 8.5 So, its neither floor(n/2) +- 1, nor ceil(n/2) +- 1 On Wed, May 29, 2013 at 2:19 PM, Ankit Sambyal ankitsam...@gmail.com wrote: Hi Nikhil, Highest remainder can't be floor(n/2) - 1. If n = 11, highest remainder would be 5 when it is divided by 6, but your formula gives 4. On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar niksin...@gmail.comwrote: Since we need to divide so the quotient should be at least 1, and we need greatest remainder, so we need the least no. which will give the quotient 1 upon dividing and that would be the no. you described. Also you would have noted the greatest remainder would be floor(n/2)-1 . On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote: For a given number when divided by a number between 1 and n. I figured out that highest reminder can be got if I divide the number by (⌊(n/2)⌋+1) .Can anyone give me pointers ? -- 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+...@**googlegroups.com. -- 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+...@**googlegroups.com. -- *Ankit Agarwal* -- 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. -- *Ankit Agarwal* *Software Engineer* *Datacenter Cloud Division* *Citrix RD India Pvt. Ltd.* *Ph. No. +91-8095470278* -- 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. -- 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. -- 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. -- *Ankit Agarwal* -- 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. -- 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] Re: Highest reminder
Hi Nikhil, Highest remainder can't be floor(n/2) - 1. If n = 11, highest remainder would be 5 when it is divided by 6, but your formula gives 4. On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar niksingha...@gmail.comwrote: Since we need to divide so the quotient should be at least 1, and we need greatest remainder, so we need the least no. which will give the quotient 1 upon dividing and that would be the no. you described. Also you would have noted the greatest remainder would be floor(n/2)-1 . On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote: For a given number when divided by a number between 1 and n. I figured out that highest reminder can be got if I divide the number by (⌊(n/2)⌋+1 ) .Can anyone give me pointers ? -- 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. -- 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] Array of intergers with repeating elements
Are these n+1 elements range from 1 to n+1 ? On Wed, May 8, 2013 at 12:02 AM, MAC macatad...@gmail.com wrote: I was asked this in recent amazon onsite interview and asked o write code Given an Array of integers . N elements occur k times and one element occurs b times, in other words there are n+1 distinct Elements. Given that 0 b k find the element occurring b times. We know k is NOT even . thanks --mac -- 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. -- 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] MS question
You have to make a package library which will do the calculation of (a^b)mod(c), where a, b, c are very large size of 1 digits. (^- power). Design a data structure for the numbers' storage and suggest what functions will you be providing to user with them. Also mention the advantages of using that DS. -- 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] MS question
@sagar : What is the best answer for this question ?? -- 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] Remove spaces
void delExtraSpaces (char *Str)
{
int Pntr = 0;
int Dest = 0;
int flag=0;
while (Str [Pntr])
{
if (Str [Pntr] != ' ')
{
Str [Dest++] = Str [Pntr];
flag=0;
}
else if(Str[Ptr]==' ' flag==1)
Str [Dest++] = Str [Pntr];
else
flag=1;
Pntr++;
}
Str [Pntr] = '/0';
}
--
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] Remove spaces
Guys sorry for posting the buggy code . Here is the working code :
void delExtraSpaces (char Str[])
{
int Pntr = 0;
int Dest = 0;
int flag=0;
while (Str[Pntr]!='\0')
{
if (Str[Pntr] != ' ')
{
Str[Dest++] = Str[Pntr];
flag=0;
}
else if(Str[Pntr]==' ' flag==0)
{
Str[Dest++] = Str[Pntr];
flag=1;
}
Pntr++;
}
Str[Dest] = '\0';
}
--
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: Amazon question.
@kunal, anuj : step 2 of my algo takes O(n^2). So how can the TC be O(nlogn) -- 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] Problems on Linked List
Ques 1: Let l1 and l2 be the 2 lists. Step 1 : Reverse l1 O(n) Step 2 : Compare l1 and l2 by comparing each node and traversing ahead.--O(n) Step 3: Reverse l1 -O(n) Ques 2: Let cur be the node of the linked list which is to be deleted. LinkedList temp=cur-next; cur-data=temp-data; cur-next=temp-next; free(temp); TC : O(1) This solution does not work if cur is the last node of the link list. In that case u will have to traverse the whole link list and TC will be O(n) -- 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] problem regarding output??
its because void pointer is incremented by 1, when we do k++ whereas integer pointer is incremented by 4, when we do j++ -- 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] problem regarding output??
The typecasting tells the compiler that the void pointer is now pointing to an integer and when we use this pointer to access the integer it takes value from 4 bytes. But when we try to increment that pointer, it will point to the next byte. Try taking k as pointer to double instead of void, u will c the same result. -- 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] MS question
Given an array of characters, change the array to something as shown in the following example. Given : ddbbccae O/P : 2d4a2b2c1a1e Do it in the most efficient manner both in terms of time and space ... -- 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] MS question
@shady : I think there is a catch in that approach. Plz post ur code -- 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] MS question
@raghavan: ur approach uses O(n) space -- 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] MS question
@sagar: for abcd, ur pgm gives abcd. I was trying a pgm which gives 1a1b1c1d. But now i think this problem is wrong, because in this case it exceeds the size of the array if we try to o/p as 1a1b1c1d. Hence we require a new array for it. -- 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] MS question
ya got it now. I misunderstood the question -- 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] Amazon question.
1. Square each element of the array and then sort it---O(nlogn)
2. for(i=0;i(size-3);i++)
{
j=i+1; k=size-1;
while(jk)
{
if(a[[i] + a[j] == a[k])
printf(\n%d %d %d,sqrt(a[i]),sqrt(a[j]),sqrt(a[k]));
else if(a[i] + a[j] a[k])
j++;
else
k--;
}
}O(n^2)
Time O(n^2)
--
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] mcq
C -- 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] Amazon Question
Plz give the answers ... 1. In a binary max heap containing n numbers, the smallest element can be found in time ?? 2. The number of total nodes in a complete balanced binary tree with n levels is, a)3^n + 1 b)2^(n+1) - 1 c) 2^n + 1 d) none of above 3. In a country where everyone wants a boy, each family continues having babies till they have a boy. After some time, what is the proportion of boys to girls in the country? (Assuming probability of having a boy or a girl is the same) a) 1:2 b) 2:1 c)1:1 d)1:4 4. A parallel program consists of 8 tasks – T1 through T8. Each task requires one time step to be executed on a single processor. Let X - Y denote the fact that task X must be executed before task Y is executed. Suppose only the tasks X, Y are to be executed. On any multiprocessor machine it would require at least 2 time steps since in the first step X could be executed, and Y could be executed in the next time step (since it requires X to complete first). Now, suppose the following dependencies exist between the tasks T1 – T8: T1 - T2 T2 - T3 T3 - T6 T2 - T4 T4 - T7 T2 - T5 T5 - T8 What is the minimum number of time steps required to execute these 8 tasks on a 2 processor machine and a 4 processor machine? a)4 2 b)5 2 c)5 4 d)6 2 -- 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: amazon question
the order of printfs depend on the scheduling algorithms which OS is following and can't be predicted -- 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] amazon question
@aditi : the ans is 3. Why do u think there is no definite ans ? -- 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] Doubts
@aditya : can u explain how u got c part as the answer for question 2 -- 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] MS test
@programming love : 6.5 can be represented accurately in binary -- 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] MS test
@programming love : 0.1 can't be represented accurately in binary. If u try to convert it into binary, it will not terminate. Try it !! But 6.5 can be converted. -- 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] Sum from array
@swetha: This problem can't be solved in O(n) -- 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] MICROSOFT INTERVIEW QUESTIONS faced by my frenz nd me
Can anybdy explain the following questions :
(5) Find the output
int arr[2][3]={{1,2,3},{4,5,6}};
int (*ptr)[3]=a[0];
printf((%d,%d),(*ptr)[1],(*ptr)[2]);
ptr+=1;
printf((%d,%d),(*ptr)[1],(*ptr)[2]);
Will this program compile properly or will end in segmentation
fault ??
(9) Given a inorder traversal eg 1 2 3 4 5 6 7 8 9 , Check which of
the following preorder traversal will it return .
a.1 6 3 2 7 8 4 9
b.6 7 3 8 1 9 2 7
c,2 4 6 8 1 3 5 7
d.1 3 5 7 2 4 6 8
--
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] amazon
bubble sort -- 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] Probability Puzzle
17/80 On Sun, Aug 7, 2011 at 10:34 AM, Algo Lover algolear...@gmail.com wrote: A bag contains 5 coins. Four of them are fair and one has heads on both sides. You randomly pulled one coin from the bag and tossed it 5 times, heads turned up all five times. What is the probability that you toss next time, heads turns up. (All this time you don't know you were tossing a fair coin or not). -- 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] MICROSOFT INTERVIEW QUESTIONS faced by my frenz nd me
@coder : Cud u plz explain the approach for question 9 ?? -- 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: probablity
the answer is 1/2 -- 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: amazon online test format
Is there any time limit for the questions in amazon online test ? I mean shud we write efficient code or shud we just make our pgm rum ? -- 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] MS test
4. a 6 b -- 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] MS test
the code given in question 5 should not terminate because of the condition of the for loop -- 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] MS test
ya the answer for 1st one is b -- 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] MS test
@sukran: 40%of work i.e. 120 sec of work is sequential and can't be distributed among multiple processors. Since we hv to complete the work in 150 sec, so we r left with 30 sec. Remaining 60% work=180sec. 180/30=6 So we require 5 additional processors -- 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] MS test
@neha: Cud u explain how r u getting d option for ques 4 ?? -- 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] address calculation
A[3][4]= 1049 B[3][4]= 2196 -- 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] address calculation
@aditi: explain ur answer.. How u got it ? -- 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] Header Files
yeah Siddarath's point is correct that they do hv preprocessors to prevent multiple includes. And they would be using #ifndef instead of #pragma as it is not a documented standard -- 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: remove duplicate words in a string
First traverse the string and hash each word into a hash table if it is not present in the hash table. Then again traverse the string and hash each word. If the word is not present in the hash table, output it to the console. -- 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: remove duplicate words in a string
If no extra memory is allowed, then I think we can't do better than O(n^2), which is pretty straight forward. -- 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] Structure Q
error because head is a pointer to the structure, hence head.x gives an error -- 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] My senior's Interview Experience at Microsoft who got selected and offered a 16lacks package
Can anybody explain following questions from the above interview:
Question:
Output:
int main()
{
char *str = “junk”;
scanf (“%[A telephonic girl]”, str);
printf (“%s\n”, str);
return 0;
}
Question : Data Structure that can be useful for the calculation like ab
mod m.
--
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] Normal Form
BCNF -- 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] OS question
What happens when a thread calls exec ?? What happens to the other threads of the same process ?? -- 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] OS question
@Dipankar: But all the threads of a process share code and data section. So, how is it possible that they are not affected ??? -- 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] OS question
Thnks Azhar :) got the point -- 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: Puzzle
@aditi:Thats a non uniform rope. The 1st half may burn faster than 2nd half. btw Priyanka's solution is correct. -- 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] Least Common Ancestor in an n ary tree
Find LCA in n ary tree ? -- 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] Complexity Help..
@Aanchal : My mistake... Its complexity can't be O(n^2) -- 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] Amazon Question
Given two lists write a function which returns a list which is the intersection of the two lists.the original lists should remain same. (Intersection - if first list is say,1,20 3,45 and second list is 3,24 ,45,90,68 then intersection should be 3,45 ) -- 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] C question.. increment decrement operator..
Its compiler dependent. Acc. to the C standard an object's stored value can be modified only once in an expression. -- 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] Amazon Question
ya, I also can't think anything better than O(m*n) -- 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] MS [Written Question]
For question 1: Take 2 arrays prod_before[N] and prod_after[N] which hold product of elements before and after i respectively For i=1 to N-1 calculate prod_before[i] For i=N-2 to 0 calculate prod_after[i] prod_before[0]=prod_after[N-1]=1 For i=0 to N-1 prod[i]=prod_before[i] * prod_after[i] -- 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] MS [Written Question]
For question 2: 1. check with empty string. 2. check with a string which is in the file 3. check with a string which is not in the file 4.check with a string which has a different case as that in the file. eg. if the file contains structure and does not contain Structure, check find and replace with input string as Structure 5. check with a string having a space followed by a string 6. check with a string having a string followed by a space 7. check with a string having only space or tabs -- 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] MS [Written Question]
Anybody having any of question 3 ??? -- 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 [Written Question]
@Poised: Whats the answer of :
double round(double num)
{ return (int)(num+0.5)
}
will it work all the time?
I think the answer should be Yes.
--
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] Amazon Aptitude questions
1.*What is the wrong in this program
*main()
{
char *p,*q;
p=(char *)malloc(25);
q=(char*) malloc(25);
strcpy(p,amazon );
strcpy(q,hyd);
strcat(p,q);
printf(%s,p);
}
2.*write prefix and post fix notation for (a+b)*c-(d+e)^(f-g)
3.**what is valid in cpp char *cp; const char *cpp; 1) cpp=cp; 2) cp=cpp;
4.**write a shell command to find all java files present in nested
directories.
5. **There are 6 pairs of black socks and 6 pairs of white socks.What is the
probability to pick a pair of black or white socks when 2 socks are selected
randomly in darkness. *
--
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: Minimum cuts required so that each sub string is a palindrome
@amit: can u supply the code for ur approach ?? -- 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: Amazon Aptitude questions
for question 3: cpp=cp is the correct answer. Can anybody explain ? -- 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: Minimum cuts required so that each sub string is a palindrome
thnks amit.. -- 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] Amazon Question
@payel : Is it sub-sequence or sub-array ?? A sub-sequence may not be continuous but a sub-array must be continuous. eg : What wud be the answer for- 100110 ?? -- 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] Minimum cuts required so that each sub string is a palindrome
You are given a large string. You need to cut the string into chunks such that each substring that you get is a palindrome. Remember that each 1 length string is always a palindrome. You need to find the minimum number of cuts that you need to make such that each substring is a palindrome. -- 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] Complexity Help..
@Ravinder : Its not a DP problem.. If it was, where are the sub problems
reused or in other words, where is memoization ??
@Anchal : Its complexity is O(n^2). Look at the following segment in ur code
:
for(int i=index[n];isz;i++)
{
index[n+1]=i;
solve(index,arr,target,cursum+arr[i],n+1,sz);
}
Here sz is the number of elements in the array i.e. n for complexity. There
is a recursive call to solve ..
I hope its clear now .
--
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] Max subarray of no 2 adjacent elements
just use the following recurrence relation :
let arr[] be the array of integers and take an array a[]
a[i]=max(a[i-2], a]i-1], a[i-2]+arr[i]);
a[0]=arr[0];
a[1]=max(arr[0],arr[1]);
a[N-1] contains the final answer
@abhishek : the output for {3,5,7,10} should be 5+10=15 and not 13 as
pointed by u !! Correct me if I am wrong
--
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] Sort IT
@raja : The range is 1-N^2 and not 1-N. Had it been 1-N , we could have easily sorted the array in O(N) time using bit map. -- 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: C doubt
yup its correct... -- 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] Write C code to check if an integer is a power of 2 or not in a single line?
If x is the number which is to be checked, if (x !(x (x-1)) == 0) then power of 2 -- 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] Programming Puzzle!!!!!!!
Let S be the exact amount for which minimum coins are to found. And denom[] be the array which contains different denominations. Let N be the size of the denom[] array. Algo: 1. int memo[S] 2. initialize all its elements to infinite 3.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 4. return memo[S] -- 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] Programming Puzzle!!!!!!!
I have used dynamic programing to solve the problem. I have used memo[] array to memoize the value of previous state. You should take an example and try to work it out using the algo... -- 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] Programming Puzzle!!!!!!!
It means a very large value, can be the max value that an integer can hold -- 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] Programming Puzzle!!!!!!!
@aman: My mistake. set* memo[0]=0* The revised algo is : Algo: 1. int memo[S] 2. initialize all its elements to infinite. * 3.memo[0]=0* 4.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 5. return memo[S] -- 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]
@anika: Here is the iterative code:
void iter_mirror(Node *root)
{
if(root==NULL)
return;
Node *stack[100];
Node *temp,*temp1;
int top=-1;
stack[++top]=root;
while(top!=-1)
{
temp=stack[top];
temp1=temp-left;
temp-left=temp-right;
temp-right=temp1;
top--;
if(temp-left!=NULL)
stack[++top]=temp-left;
if(temp-right!=NULL)
stack[++top]=temp-right;
}
}
--
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: binary search tree question!!!!
Here the required program :
void findkthSmallest(Node *root,int k)
{
Node *stack[100];
int top=-1,count=0;
Node *temp;
stack[++top]=root;
/*First we will find the minimum node*/
temp=root;
while(temp-left != NULL)
{
stack[++top]=temp-left;
temp-left=NULL; //Make it NULL so that we do not traverse it
again
temp=temp-left;
}
//Now top of the stack contains the minimum node.
//Now we will do inorder traversal
while(top!=-1)
{
temp=stack[top];
count++; //Increment the count for every eleemnt traversed
if(count==k) //If count reaches k, we have kth smallest
element as the top of the stack
return stack[top]-value;
else if(temp-left!=NULL)
{
stack[++top]=temp-left;
temp-left=NULL; //Make it NULL so that we do not traverse
it again
count++;
}
else if(temp-right!=NULL)
{
stack[++top]=temp-right;
temp-right=NULL; //Make it NULL so that we do not traverse
it again
count++;
}
else
top--;
}
}
--
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] DE Shaw - Data Structure Section Qn
In the question it is specified that the data structure should have a worst case time complexity of O(N) -- 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] Puzzle!!!!!
use the following recursive equation :
S{i]=max(S[i-2]+a[i],S[i-1])
S[0]=a[0]
S[1]=max(a[0],a[1])
S[size-1]is the required answer
--
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] Puzzle!!!!!
1. Make an array S equal to the length of the given array where S[0] = a[0] and S[1] = max(a[0],a[1]) 2. for i:2 to n-1 S[i] = max(S[i-2]+a[i], S[i-1]) 3. return S[n-1] -- 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] direct i
O(n^2) algo is trivial. Can anybody think of a better approach ??? -- 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: Fwd: SORTING ARRAYS
Following is the working code :Time complexity : O(n^2) Space
complexity : O(1)
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
/*num is the number which is searched in the array arr[]. index is the index
in the array arr[] by which the searched number is to be replaced*/
int searchAndReplace(int arr[],int size,int num,int index)
{
int i=index+1;
while(isize)
{
if(arr[i]==num)
break;
i++;
}
if(isize)
swap(arr[i],arr[index]);
}
void sort(int arr1[],int arr2[],int size)
{
int i=0,j;
while(isize)
{
j=0;
while(jsize)
{
if(arr2[j]arr1[i])
searchAndReplace(arr1,size,arr2[j],i);
j++;
}
i++;
}
}
int main()
{
int arr1[]={2,5,1,7};
int arr2[]={5,7,1,2};
sort(arr1,arr2,4);
int i;
for(i=0;i4;i++)
printf(%d ,arr1[i]);
return 0;
}
--
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: Fwd: SORTING ARRAYS
@anand: How are you building minheap ?? Comparison of same array elements is not allowed ! -- 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] Least Common Ancestor
First make an iterative DFS function which stores node pointers on the stack
instead of node values and break as soon as the node value of the node
pointer on the top of the stack reaches a specified value.
void iterative_dfs(Node *root,int n1);
Let n1 and n2 be the values whose LCA is to be found in a binary tree whose
root pointer is : root
Step1 : iterative_dfs(root,n1)
Step2 : int arr1[];
for i=0 to top // top is the index of the top of the
stack
arr1[i]=stack[i]
Step3: iterative_dfs(root,n2)
Step4:int arr2[];
for i=0 to top
arr2[i]=stack[i]
Step5: for i=0 to n
{
if(arr1[i]!=arr2[i])
break;
}
Step6:
return arr1[i-1]-value; // arr1[i-1] or arr2[i-1] contains
the node pointer of least common ancestor
Time : O(n)
Space: O(n)
--
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] DE Shaw - Data Structure Section Qn
d) Hast table with bucket, made up of linked list, where linked list have no ordering. -- 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] Array question
The O/P of ur example should be 2,2,1,1,1,-1,-1 or am I getting it wrong ?? -- 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: Array question
@Akshata : Plz explain ur algo... Its not clear. Like in the first iteration, else l = stk.top; is getting executed. but stack is empty, so how r u assigning value to l -- 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] Amazon Question
@Swetha :Number of possible sub strings of a string of length n is of the order of n^2. So, there can,t be a better solution than O(n^2) -- 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] Competetive C-Question
D) S1 and S2 both are true S2 is true because return a[i+2]-3; takes more time than return t2-3; -- 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: Amazon Question
@vivin : Suffix trees are memory intensive.. This problem can be solved just by running 2 nested loops in O(1) space and O(n^2) time -- 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: AMAZON Q
@vivin : Your algo seems to be wrong. Plz take an example and explain. I may hv misunderstood u .. -- 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: please help
int getFirstIndexInLex(char arr[],int size)
{
int minindex=0,i;
for(i=1;isize;i++)
{
if(arr[i] arr[minindex])
minindex=i;
else if(arr[i]==arr[minindex])
minindex=checkmin(arr,size,minindex,i);
}
return minindex;
}
int checkmin(char arr[],int size,int i,int j)
{
int k=0;
while(arr[i]!=arr[j] ksize)
{
i=(i+1)%size;
j=(j+1)%size;
k++;
}
if(k==0)
return i; //Strings at i and j are
both same. You can return either index
else if(arr[i]arr[j])//String starting at index i
is less than string starting at index j
return i;
else//String starting at index
j is less than string starting at index i
return j;
}
--
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: please help
There is a mistake in my code: In the function int checkmin(char arr[],int size,int i,int j) after the while loop in the line if(k==0) It shud be : if(k==size) instead of if(k==0) -- 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: please help
@coder: my mistake. There is a typo in my code. the condition is : while(arr[i]==arr[j] ksize) -- 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: please help
@coder : No, my solution gives the correct answer. Check it out again !! -- 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: please help
@coder :Got my mistake. There is a slight change in the checkmin function.
Actually I was returning the modified value of i and j. Following is the
correct code :
#includeiostream
using namespace std;
int checkmin(char arr[],int size,int i,int j)
{
int k=0,*m=i,n=j*;
while(arr[i]==arr[j] ksize)
{
i=(i+1)%size;
j=(j+1)%size;
k++;
}
if(k==size)
*return m; * //Strings at i and j are both
same. You can return either index
else if(arr[i]arr[j]) //String starting at index i is
less than string starting at index j
* return m;*
else//String starting at index j is
less than string starting at index i
*return n;*
}
int getFirstIndexInLex(char arr[],int size)
{
int minindex=0,i;
for(i=1;isize;i++)
{
if(arr[i] arr[minindex])
minindex=i;
else if(arr[i]==arr[minindex])
minindex=checkmin(arr,size,minindex,i);
}
return minindex;
}
int main()
{
coutgetFirstIndexInLex(ABCDEAABCCDA,12);
}
--
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: AMAZON Q
@rajeev:ur algo does not give the correct answer. -- 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: AMAZON Q
@bharath :I think array C is not the resultant array. Take an example and explain -- 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] Question
Incomplete Information -- 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.
