Re: [algogeeks] Amazon Q
Q1 Solution: . we can use doubly linked list with hash to implement all the
operation in O(1).
By keeping track of head and tail pointer we can do enqueue and dequeue in
O(1) time.
In hash we will keep track of each element present in linked list(queue).
With node value as a hash key and address of node as a value. So for
searching we can do it in O(1).
For deleting an element we will directly take address of that value from
hash and delete it. O(1) time.
Q2. /*my code will return NULL if not palindrome and head if it is
palindrome */
count = totalnode/2;
//odd = 0 if totalnode is even else 1
struct node *checkPalindrome(struct node *head, int count)
{
struct node *temp;
if(count == 0) {
if(odd head-next) return head-next;
else return head;
}
if(count 0)
temp = checkPalindrome(head-next, count - 1);
if(temp (temp-data == head-data ) !temp-next)
return head;
else if (temp (temp-data == head-data ))
return temp-next;
else return NULL;
}
On Sun, Aug 26, 2012 at 12:41 AM, Ashish Goel ashg...@gmail.com wrote:
Q1. Design a data structure for the following operations:
I.Enqueue
II. Dequeue
III. Delete a given number(if it is present in the queue,
else do nothing)
IV. isNumberPresent
All these operations should take O(1) time.
Q2. Check if a linked list (each char is a node) is palindrome,
recursively.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To 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] Amazon Q
Q2) get to n/2 nodes Reverse link list after n/2 nodes Now check from 1st node and n/2 node for equality Can make the checking for equality function recursive Sent from my iPhone 4 On 26-Aug-2012, at 12:41 AM, Ashish Goel ashg...@gmail.com wrote: Q1. Design a data structure for the following operations: I.Enqueue II. Dequeue III. Delete a given number(if it is present in the queue, else do nothing) IV. isNumberPresent All these operations should take O(1) time. Q2. Check if a linked list (each char is a node) is palindrome, recursively. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To 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] Amazon Q
Q1. Design a data structure for the following operations: I.Enqueue II. Dequeue III. Delete a given number(if it is present in the queue, else do nothing) IV. isNumberPresent All these operations should take O(1) time. Q2. Check if a linked list (each char is a node) is palindrome, recursively. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To 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 Q: Implement an algorithm to do wild card string matching
Implement an algorithm to do wild card string matching Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To 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 Q : Design a logWritter for server kind of application
Design a logWritter for server kind of application Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To 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 Q: Implement an algorithm to do wild card string matching
match(*input , *pattern)
if(*pat == 0)
return true;
if('?' == *pat)
return match(input+1,pat+1) || match(input,pat+1)
if('*' == *pat)
return match(input+1,pat) || match(input,pat+1)
if(*text == *pat)
return match(input+1,pat+1)
return 0;
take care of base cases..
On Sat, May 26, 2012 at 2:16 PM, Ashish Goel ashg...@gmail.com wrote:
Implement an algorithm to do wild card string matching
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To 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] Amazon Q: Implement an algorithm to do wild card string matching
typo error above resolved :-
match(*input , *pattern)
if(*pat == 0)
return true;
if('?' == *pat)
return match(input+1,pat+1) || match(input,pat+1)
if('*' == *pat)
return match(input+1,pat) || match(input,pat+1)
if(*input == *pat)
return match(input+1,pat+1)
return 0;
On Sat, May 26, 2012 at 2:39 PM, atul anand atul.87fri...@gmail.com wrote:
match(*input , *pattern)
if(*pat == 0)
return true;
if('?' == *pat)
return match(input+1,pat+1) || match(input,pat+1)
if('*' == *pat)
return match(input+1,pat) || match(input,pat+1)
if(*text == *pat)
return match(input+1,pat+1)
return 0;
take care of base cases..
On Sat, May 26, 2012 at 2:16 PM, Ashish Goel ashg...@gmail.com wrote:
Implement an algorithm to do wild card string matching
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To 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] Amazon Q
Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.http://shashank7s.blogspot.com/2012/02/write-method-to-shuffle-deck-of-cards.html -- 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/-/kNoMc6CLVb4J. 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 Q
This is an Age Old Amazon Question ..
int main(void)
{
int card[52];
int n;
srand(time(0));
for(int i=0;i52;i++)
card[i]=i;
while(cinn) {
for(int i=0;i(52-i);i++) {
int r=i+(rand()%(52-i));
int temp=card[i];
card[i]=card[r];
card[r]=temp;
}
for(int c=0;cn;c++)
coutcard[c] ;
coutendl;
}
return 0;
}
Jst For Reference if Anyone Needs...
On Wed, May 23, 2012 at 2:40 PM, Ramindar Singh ramin...@gmail.com wrote:
Write a method to shuffle a deck of cards. It must be a perfect shuffle -
in other words, each 52! permutations of the deck has to be equally likely.
Assume that you are given a random number generator which is
perfect.http://shashank7s.blogspot.com/2012/02/write-method-to-shuffle-deck-of-cards.html
--
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/-/kNoMc6CLVb4J.
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] amazon q
A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? · Pick one of the choices A heap can be used but not a balanced binary search tree A balanced binary search tree can be used but not a heap Both balanced binary search tree and heap can be used Neither balanced binary search tree nor heap can be used -- 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 q
so which is the right option?? -- 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 q
heap is true but i am not getting y we can't use a balanced binary tree searching for the smallest is logn(leftmost node), then deleting it is logn so, should it be both?? thanx :) On Sun, Aug 21, 2011 at 6:54 PM, sukran dhawan sukrandha...@gmail.comwrote: its heap On Sun, Aug 21, 2011 at 6:52 PM, Puneet Chawla puneetchawla...@gmail.comwrote: I think Heap DS should be used as to delete smallest element jst apply min heap and delete it and for insertion add the element and apply max or min as needed Max heap = Min heap both have complexities =O(logn) On Sun, Aug 21, 2011 at 6:46 PM, priya ramesh love.for.programm...@gmail.com wrote: A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? · Pick one of the choices A heap can be used but not a balanced binary search tree A balanced binary search tree can be used but not a heap Both balanced binary search tree and heap can be used Neither balanced binary search tree nor heap can be used -- 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. -- With regards Puneet Chawla Computer Engineering Student NIT Kurukshetra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] amazon q
Its both. Both can perform the operations in a maximum of O(logn) time. On Sun, Aug 21, 2011 at 7:13 PM, priya ramesh love.for.programm...@gmail.com wrote: i have the same doubt :) -- 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. -- Nikhil Gupta Senior Co-ordinator, Publicity CSI, NSIT Students' Branch NSIT, New Delhi, India -- 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 Q
We must use
BIThttp://www.topcoder.com/tc?module=Staticd1=tutorialsd2=binaryIndexedTreesto
solve this problem with O(nlogn).
Here http://ideone.com/IaU3F is my implementation.
Thanks Regards
Anantha Krishnan
On Tue, Jul 26, 2011 at 7:18 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
* https://www.facebook.com/profile.php?id=10655377926 NEVER SAY
NEVER
*
--
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] AMAZON Q
Here is an algorithm which solves this problem in O(nlog^2 n):
Create a set of pairs B= {ar [i],i : i= 1..n}.
Sort B.
Now use the following Divide and Conquer algorithm (Ar_Low is a global
array):
Fill (Start, End, Low_Array)
if Start= End then
Low_Array [Start]= 0
else
Initialize Low_Array with zero.
Fill (Start, (Start+ End)/ 2, Low_Array)
Fill ((Start+ End)/ 2+ 1, End, Low_Array)
Scan B (the list of sorted pairs) and select the pairs whose
second value is in range (End/ 2+ 1, End), call the resulting list B'
For each i in (Start, (Start+ End)/ 2):
Lets j be the position of arr [i] in B'
Set Low_Array [i]= Low_Array [i]+ j
The running time of this algorithm is:
n\log n for sorting B+
T(n)= 2T(n/2)+ n\log n = T(n)= n\log^2 n
So, the total running time is: n\log^2 n .
Amir
On 07/26/2011 06:48 AM, Piyush Sinha wrote:
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space 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.
[algogeeks] AMAZON Q
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
* https://www.facebook.com/profile.php?id=10655377926 NEVER SAY
NEVER
*
--
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 Q
On Tue, Jul 26, 2011 at 7:18 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote:
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.
A straight forward question
for i in 0 to n-1:
temp = 0;
for j in i+1 to n-1:
if arr[j]= arr[i]:
temp++;
ar_low[i] = temp
But the trick is to find a better algorithm with better complexity
Regards,
B.C.Someshwar
--
'Talk sense to a fool and he calls you foolish.' - Euripides
My Blog: somsekaran.wordpress.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] AMAZON Q
Construct a BST using ar[], where each node contains the ar index
information as well (in addition to the value).
Now iterating through ar. For each element, traverse the BST by value,
counting only those nodes where the value AND index# are greater then self.
Once done traversal, update ar_low.
--
On Tue, Jul 26, 2011 at 7:18 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
* https://www.facebook.com/profile.php?id=10655377926 NEVER SAY
NEVER
*
--
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] AMAZON Q
have head and tail pointer for every hash bucket this is how linux scheduler works add at the end, remove from front each bucket represents the prioirty or unique hash value.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 7, 2011 at 1:11 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: Design your hash_map that allow the following Add in O(1) , delete in O(1) , iterate in O(n)? -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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] AMAZON Q
Design your hash_map that allow the following Add in O(1) , delete in O(1) , iterate in O(n)? -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 Q
The input number is n. Find the closest Fibonacci series number i where i n. Show the time complexity of the problem. For eg : if n = 10, the output i should be 8 -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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.
