Re: [algogeeks] problem with increment operator
yups...it is compiler dependent...but a logic is necessary to get 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] amazon
here is a nice explanation for the problem
http://stackoverflow.com/questions/5131497/given-a-string-and-permutation-of-the-string-find-the-index-of-this-permuted-st
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Tue, May 29, 2012 at 3:37 PM, rahul patil
rahul.deshmukhpa...@gmail.comwrote:
Here is a constant time formula, LetterRankInSortedString is index of
alphabate if all characters in string are sorted lexographically starting
from 1.
Index = 0;
For(i=0; i LengthOfString; i++)
{
Letter = string[i];
Index + = (LetterRankInSortedString(Letter) - 1) *
(TotalPermutationsPossible/ (LengthOfString-i));
}
On Mon, May 28, 2012 at 12:26 AM, saurabh agrawal saurabh...@gmail.comwrote:
@atul:
i dont agree that baa should come once or twice is arguable.
It definitely have to be one time only..
we are supposed to get all lexicographic combinations (which implicitly
means no two strings will be same..)
On Mon, May 28, 2012 at 12:23 AM, atul anand atul.87fri...@gmail.comwrote:
@saurabh : i kinda assumed that string will not contain
repeated character. reason being if string has repeated character , say in
your case baa then baa will be repeated
twice hence it would be difficult to justify the output for this
input answer could be say 2 or 3 or both are correct.
On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal
saurabh...@gmail.comwrote:
@atul:
if i have understood ..
ur solution will break when the string has repeated characters.
e.g. for baa
On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
sorry it was treeset Here is the code..
public class asd1 {
public static TreeSetString t = new TreeSetString();
public static int j = 0;
public static void main(String args[]) {
String s= edcba;
permute(, s);
System.out.println(t.toString());
int length=t.size();
String[] arr=(String[]) t.toArray(new String[length]);
for(int i =0;ilength;i++)
{
System.out.println(arr[i]);
if(arr[i].equals(s)){
System.out.println(i+1);
break;
}
}
}
public static void permute(String st, String chars) {
if (chars.length() = 1)
t.add(st+chars);
else
for (int i = 0; i chars.length(); i++) {
try {
String newString = chars.substring(0,
i)
+ chars.substring(i +
1);
permute(st + chars.charAt(i),
newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
Java has something call treeMap. it stores strings lexographically..
u can always do permutations and store them in a treeMap. and get the
rank
then... just the idea.. will post the solution once i am done.. what do u
guys think.abt the idea???
On Tue, May 22, 2012 at 9:46 AM, atul anand
atul.87fri...@gmail.comwrote:
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after
temp_rank=(found_index - start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will
come.
so to find out the exact index sort(input-1) i.e removing 1st
character ('c') from the input(cadb) we will get abd
now permute string abd and compare with input - 1 character i.e
(abd).
and keep inc the counter , if match is found then you have to add
this counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute
string and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can
calculate minimum number of swaps required to convert input - 1 to
sorted
input -1 (removing 1st character )using edit distance ...will this
work??
.
On Mon, May 21, 2012 at 11:33 PM, atul anand
atul.87fri...@gmail.com wrote:
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted
string abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1
elements in (index-1) ! and right elements from found index in
(lastIndex -
index)! before character 'c'
[algogeeks] 567 of UVA - WA
hi...
I've used BFS algorithm to solve 567 of UVA...
but it takes WA...
here's my solution in c++:
#include iostream
#include queue
#include cstring
#include stdio.h
using namespace std;
int mat[21][21];
int mark[21];
int tc = 0;
int n, m, t;
int a, b;
void bfs ()
{
queue int q;
q.push (a);
mark[a] = 0;
while (!q.empty())
{
int temp = q.front();
q.pop();
if (temp == b)
return;
for (int i = 1; i = 20; i++)
if (mat[temp][i] == 1 mark[i] == -1)
{
q.push (i);
mark[i] = mark[temp] + 1;
}
}
}
int main ()
{
//freopen (input.in, r, stdin);
while (!cin.eof())
{
tc++;
for (int i = 0; i 21; i++)
memset (mat[i], 0, sizeof mat[i]);
for (int i = 1; i = 19 cin n; i++)
for (int j = 0; j n cin m; j++)
{
mat[i][m] = 1;
mat[m][i] = 1;
}
cin t;
cout Test Set # tc endl;
for (int i = 0; i t cin a b; i++)
{
memset (mark, -1, sizeof mark);
bfs ();
printf (%2d, a);
cout to ;
printf (%2d, b);
cout : mark[b] endl;
}
cout endl;
}
return 0;
}
Is there anyone to help me?!
tnx
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: problem with increment operator
It's output will be compiler dependent.
So on Turbo C, compiler will perform all pre-increment operation first then
will start adding.
like in your problem all ++a operation will go first. then addition will
happen.
so 6+6+6=18.
on gcc, first two variables will it take, performs pre-increment operation
and then adding and then third variable will come.as it continues.
As in this case in gcc it will be performed like,
(++a + ++a) + (a++)=(6+6)+6=18
post-increment will be unaffected during entire expression.
Feel free to ask if you didn't got what i explained.
On Monday, May 28, 2012 11:02:03 AM UTC+5:30, ashish wrote:
#includestdio.h
int main()
{
int a=4;
printf(%d\n,++a + ++a + a++);
return 0;
}
according to me output should be 17, but it is coming out to be 18.
plz explain it??
--
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/-/eBcLatQS34kJ.
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: problem with increment operator
The order of evaluation of sub-expressions is not defined since there is no
sequence point in the sub-expression. So, the behavior is not defined, and
one cannot rely on a specific compiler implementation - gcc, MSVC, or any
other.
As a general rule of thumb, you should avoid this type of complex
expressions where the same object is modified within the sub-expressions.
Regards,
Ashot Madatyan
From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On
Behalf Of holmes
Sent: Wednesday, May 30, 2012 3:21 PM
To: algogeeks@googlegroups.com
Subject: [algogeeks] Re: problem with increment operator
It's output will be compiler dependent.
So on Turbo C, compiler will perform all pre-increment operation first then
will start adding.
like in your problem all ++a operation will go first. then addition will
happen.
so 6+6+6=18.
on gcc, first two variables will it take, performs pre-increment operation
and then adding and then third variable will come.as it continues.
As in this case in gcc it will be performed like,
(++a + ++a) + (a++)=(6+6)+6=18
post-increment will be unaffected during entire expression.
Feel free to ask if you didn't got what i explained.
On Monday, May 28, 2012 11:02:03 AM UTC+5:30, ashish wrote:
#includestdio.h
int main()
{
int a=4;
printf(%d\n,++a + ++a + a++);
return 0;
}
according to me output should be 17, but it is coming out to be 18.
plz explain it??
--
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/-/eBcLatQS34kJ.
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
nice explanation..
On 30 May 2012 06:05, Amol Sharma amolsharm...@gmail.com wrote:
here is a nice explanation for the problem
http://stackoverflow.com/questions/5131497/given-a-string-and-permutation-of-the-string-find-the-index-of-this-permuted-st
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Tue, May 29, 2012 at 3:37 PM, rahul patil
rahul.deshmukhpa...@gmail.com wrote:
Here is a constant time formula, LetterRankInSortedString is index of
alphabate if all characters in string are sorted lexographically starting
from 1.
Index = 0;
For(i=0; i LengthOfString; i++)
{
Letter = string[i];
Index + = (LetterRankInSortedString(Letter) - 1) *
(TotalPermutationsPossible/ (LengthOfString-i));
}
On Mon, May 28, 2012 at 12:26 AM, saurabh agrawal
saurabh...@gmail.comwrote:
@atul:
i dont agree that baa should come once or twice is arguable.
It definitely have to be one time only..
we are supposed to get all lexicographic combinations (which implicitly
means no two strings will be same..)
On Mon, May 28, 2012 at 12:23 AM, atul anand atul.87fri...@gmail.comwrote:
@saurabh : i kinda assumed that string will not contain
repeated character. reason being if string has repeated character , say in
your case baa then baa will be repeated
twice hence it would be difficult to justify the output for this
input answer could be say 2 or 3 or both are correct.
On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal saurabh...@gmail.com
wrote:
@atul:
if i have understood ..
ur solution will break when the string has repeated characters.
e.g. for baa
On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
sorry it was treeset Here is the code..
public class asd1 {
public static TreeSetString t = new TreeSetString();
public static int j = 0;
public static void main(String args[]) {
String s= edcba;
permute(, s);
System.out.println(t.toString());
int length=t.size();
String[] arr=(String[]) t.toArray(new String[length]);
for(int i =0;ilength;i++)
{
System.out.println(arr[i]);
if(arr[i].equals(s)){
System.out.println(i+1);
break;
}
}
}
public static void permute(String st, String chars) {
if (chars.length() = 1)
t.add(st+chars);
else
for (int i = 0; i chars.length(); i++) {
try {
String newString = chars.substring(0,
i)
+ chars.substring(i +
1);
permute(st + chars.charAt(i),
newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
Java has something call treeMap. it stores strings lexographically..
u can always do permutations and store them in a treeMap. and get the
rank
then... just the idea.. will post the solution once i am done.. what do
u
guys think.abt the idea???
On Tue, May 22, 2012 at 9:46 AM, atul anand atul.87fri...@gmail.com
wrote:
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after
temp_rank=(found_index - start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will
come.
so to find out the exact index sort(input-1) i.e removing 1st
character ('c') from the input(cadb) we will get abd
now permute string abd and compare with input - 1 character i.e
(abd).
and keep inc the counter , if match is found then you have to add
this counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute
string and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can
calculate minimum number of swaps required to convert input - 1 to
sorted
input -1 (removing 1st character )using edit distance ...will this
work??
.
On Mon, May 21, 2012 at 11:33 PM, atul anand
atul.87fri...@gmail.com wrote:
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted
string abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1
Re: [algogeeks] problem with increment operator
Hai i tried the same in TC compiler. i got the output as 17. I guess the
output should be 17 as explained by Prateek Jain
On 30 May 2012 02:26, rahul ranjan rahul.ranjan...@gmail.com wrote:
it first calculates from right to left and then performs addition
so after a++ its still 4(with a promise to increment in next
statement). then ++a makes it 5. then further ++a makes it 6
now the addition phase comes into play value of a is 6 now so total
18 if it wud hav been a++ + a++ + a++ sum wud hav been 12
and for next statement 'a' wud hav been 7
On Wed, May 30, 2012 at 1:32 AM, Hassan Monfared hmonfa...@gmail.comwrote:
I implemented ++ for a simple class and got 17.
class A
{
public :
int val;
A(int v):val(v){}
int operator++()
{
cout empty arg called\n;
return ++val;
}
int operator++(int x)
{
cout x:arged arg called\n;
return val++;
}
};
--
A b(4);
cout ++a + ++a +a++endl;
17
but story is different for your sample.
let me tell the fact with a simpler problem :
int b=4;
cout ++b + ++b ;
will print 12 instead of 11!
amazing huh ?
what happens from right to left is :
in the right statement : b becomes 5:
in the left statement : b becomes 6 ( now be is 6 in both sides !)
so right_b + left_b = 6+6 = 12
Regards
On Tue, May 29, 2012 at 11:43 PM, Prateek Jain prateek10011...@gmail.com
wrote:
how is it 6?
++a(5) + ++a(6) + a++(6) it shud be 17
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] The following problem is a variation of Tower of hanoi problem...Plz suggest on how to approach the following problem...
There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves. A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg. At anypoint of time, the decreasing radius property of all the pegs must be maintained. Constraints: 1= N=8 3= K=5 Input Format: N K 2nd line contains N integers. Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration. 3rd line denotes the final configuration in a format similar to the initial configuration. Output Format: The first line contains M - The minimal number of moves required to complete the transformation. The following M lines describe a move, by a peg number to pick from and a peg number to place on. If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one. Sample Input #00: 2 3 1 1 2 2 Sample Output #00: 3 1 3 1 2 3 2 Sample Input #01: 6 4 4 2 4 3 1 1 1 1 1 1 1 1 Sample Output #01: 5 3 1 4 3 4 1 2 1 3 1 (question taken from facebook hiring sample test .) -- 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: # of paths betweek two nodes in a DAG
@Amol
I think the solution given above is fine except that i missed to initialize
A[src] =1. Thats the reason why u end up getting 0's for all A[i]'s.
Modification to the third step:
3) Scan the linearized list from left to right initialize all the
corresponding values in array A to 0.
Set A[src]=1.
On Wednesday, 30 May 2012 23:49:46 UTC+5:30, Amol Sharma wrote:
just check, In the above loop(posted by lucifer) it will only return zero
everytime..
corrected after getting the linearized list after topological sort :
take an auxillary array, A of size N*A[i] represent the number of
paths from i to target.
*
initialize A[target] to 1 and values at all other indexes as zero .
Do this in the While loop --
scan the linearized list from target and move towards source
as soon as you see a node x in the list while scanning then A[x]=sum of
all A[j] where j are all the childs of x.
when you reach source return A[source]
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Wed, May 30, 2012 at 11:11 PM, sourabh datta sourabhd2...@gmail.comwrote:
Y?
On May 30, 2012 9:58 PM, Amol Sharma amolsharm...@gmail.com wrote:
@lucifer: your algo seems correct but in the last step you should start
loop from target to source rather from source to target..
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Mon, May 28, 2012 at 1:08 AM, Lucifer sourabhd2...@gmail.com wrote:
1) Linearize the DAG using DFS. ( topological sorting)
2) Now take an array of size A[N] ( N - nodes in the DAG ), where A[i]
mimics the 'i'th node in the linearized list.
3) Scan the linearized list from left to right to get to the source
node and initialize all the corresponding values in array A to 0.
i.e. A[1] to A[src].
4) Now use the below equation to calculate the value for no. of paths
to any node after the src node in the linearized list as follows.
i= src + 1;
while( i =dest )
{
A[i]= sum of all ( A[j] 's);
// where (j i) and there is a directed edge from j to
i
++i;
}
5) Return A[dest].
On May 24, 11:23 pm, MeHdi KaZemI mehdi.kaze...@gmail.com wrote:
Hi.
DFS( k ) returns the number of paths from node k to your destination.
so DFS( k ) is equal to the sum of DFS( p ) such that there is a
forward
edge from k-p.
You have to memoize DFS for each node to prevent calculating the
number of
paths from that node more than one time. I do that with array 'ans'.
Read the code and take a look at the picture and ask your question if
there
is any.
On Thu, May 24, 2012 at 4:50 PM, Ashish Goel ashg...@gmail.com
wrote:
My bad, i am not able to conceptualize this known problem, can
anyone help
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.
--
MeHdi KaZemI
paths in dag.cpp
1KViewDownload
paths in dag.png
22KViewDownload
--
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.
On Wednesday, 30 May 2012 23:49:46 UTC+5:30, Amol Sharma wrote:
just check, In the above loop(posted by lucifer) it will only return zero
everytime..
corrected after getting the linearized list
Re: [algogeeks] problem with increment operator
okk -- 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] The following problem is a variation of Tower of hanoi problem...Plz suggest on how to approach the following problem...
built a tree (not binary) where the root node is the initial configuration of pegs. For each possibility of movement of the initial configuration of disks, a child node is created. Thus, for each child node created, I check if the current configuration is the final configuration. If yes, problem was solved and we are done =). Otherwise its creates other child nodes of the current node. Note that the verification of the current configuration with the final configuration of the nodes is done by breadth-first searchhttp://en.wikipedia.org/wiki/Breadth-first_search(this is the secret of this solution to find the smallest number of moves). If u need i can give u the JAVA code for this -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: The following problem is a variation of Tower of hanoi problem...Plz suggest on how to approach the following problem...
Since the number of moves must be optimal, this seems to be a search problem. A-Star is the right search algorithm. This is an algorithm that's somewhere between depth first and breadth first. It expands the tree according to a heuristic that you choose, which can shrink the run time enormously. The Wikipedia page on this is not bad http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode On May 30, 2:41 pm, g4ur4v gauravyadav1...@gmail.com wrote: There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves. A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg. At anypoint of time, the decreasing radius property of all the pegs must be maintained. Constraints: 1= N=8 3= K=5 Input Format: N K 2nd line contains N integers. Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration. 3rd line denotes the final configuration in a format similar to the initial configuration. Output Format: The first line contains M - The minimal number of moves required to complete the transformation. The following M lines describe a move, by a peg number to pick from and a peg number to place on. If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one. Sample Input #00: 2 3 1 1 2 2 Sample Output #00: 3 1 3 1 2 3 2 Sample Input #01: 6 4 4 2 4 3 1 1 1 1 1 1 1 1 Sample Output #01: 5 3 1 4 3 4 1 2 1 3 1 (question taken from facebook hiring sample test .) -- 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 with increment operator
Hey answer will be 18 as follows. First ++a(5)+ ++a(6) + a++(6)=17 + one post increment= 18. On Thu, May 31, 2012 at 3:13 AM, Prateek Jain prateek10011...@gmail.comwrote: okk -- 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] Linked list using void pointer
how to implement generioc linked list..using void pointer...i havent used void pointer much so, m not able to use it properly in linked list..please help asap !!! -- 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 : exponentiation(x,n)
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written as
x*xE when odd or xE otherwise.
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.
