void findPaths(int x, int y, int depth)
{
if (isEnd(x,y)) showSolution(); // One path will be marked by
letters A,B,C...
else
{
maze[x][y] = 'A' + depth;
if (x (maze[x-1][y]=='1')) findPaths(x-1,y,depth+1);
if (y (maze[x][y-1]=='1')) findPaths(x,y-1,depth+1);
BFS
On Sun, Oct 14, 2012 at 4:21 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
response awaited!!!
anyone??
On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
Pls help to solve this que.. does any one have DP solution for following
que.
@jaspreet : i dont find much difference between using BFS or
backtracking...which is doing similar to DFS.
On Tue, Oct 16, 2012 at 4:28 AM, Jaspreet Singh
jassajjassaj...@gmail.comwrote:
BFS
On Sun, Oct 14, 2012 at 4:21 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
response
response awaited!!!
anyone??
On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
Pls help to solve this que.. does any one have DP solution for following
que.
http://www.geeksforgeeks.org/archives/24488
section 5/question 2
Write a program to find all the
@All *Here is the working code: test on input {-1,5,3,-8,4,-6,9} and
{1,-1,2}*
Algo:
increment current till first +ve number(p) and decerement end till last
-ve number(n)
now consider only array between [p..n]
If current is negetive, increment current
If current is positive, swap it with end and
@Dave :- a minor change
Initially, decrement the end pointer till it points to positive number,
Now end points to the last negative number.
Now,
If current is negative , increment current
If current is positive , swap it with the element at end and decrement
current and end both
If current =
@Navin: If I am correctly executing your algorithm on the data in the
original posting, {-1,5,3,-8,4,-6,9}, I get {-1,-6,-8,4,3,5,9}, when the
correct answer is {-1,-8,-6,5,3,4,9}. The array contains the correct
numbers, but the order of the positive numbers and the order of the negtive
+1 naveen
On Thursday, June 28, 2012 8:29:26 PM UTC+5:30, Navin Gupta wrote:
Keep two pointers - one at start of the array and other at end of the
array
Now current points to start of the array
If current is negative , increment current
If current is positive , swap it with the element
@Navin: Try this with {1,-1,2}. current points to the 1 and end points to
the 2. Since 1 is positive, the algorithm swaps the 1 and the 2, giving
{2,-1,1}. Then it decrements current to point outside the array and end to
point to the -1. How can this be right?
Dave
On Thursday, June 28, 2012
keep swaping left most -ve and left most positive untill counter reaches at
the end of array, can be done in o(n) no extra space required..
3rd year
manit bhopal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on
Keep two pointers - one at start of the array and other at end of the array
Now current points to start of the array
If current is negative , increment current
If current is positive , swap it with the element at end and decrement
current and end both
If current = end , then break.
Navin
@wgp the ques is to maintain the order intact..
--
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
@akshat ur code doesn't give intact output, so i modified ur code and
here is the code :
int j=0,k=0;
for (i = 0; i n; ++i)
{
if(a[i]0)
{
a[j] = a[i];
j++;
}
else
{
temp[k] = a[i];
k++;
}
}
k=0;
for (i = j; i n; ++i)
{
guys this is my solution to the problem, it's a bit sloppy but as far as I
checked it was working please have a go at it?
#include stdio.h
#include stdlib.h
int main() {
int arr1[] = {0,-5,3,0,4,-6,-9};
int arr2[7];
int j = 0;
for ( int i = 0 ; i 7 ; i++ ) {
//loop for
can this be done in single pass in O(n) .
On Thu, Jun 21, 2012 at 8:10 PM, rusty dafc1...@gmail.com wrote:
guys this is my solution to the problem, it's a bit sloppy but as far as I
checked it was working please have a go at it?
#include stdio.h
#include stdlib.h
int main() {
single traversal n O(n) are 2 diff things...plz specify???
--
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
Well they are the same you're going over an array once. As long as they are
not nested they are still counted as O(n) because leading constants are
dropped, at least that's what my acumen says. Need inputs on this guys!
On Friday, June 22, 2012 12:53:02 AM UTC+5:30, suzi wrote:
single
i mean o(n) in single traversal .
On Fri, Jun 22, 2012 at 12:53 AM, sanjay pandey
sanjaypandey...@gmail.comwrote:
single traversal n O(n) are 2 diff things...plz specify???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
@ayush goel couldnt really understand your algo , can you please explain
little bit more .
On Wednesday, 13 June 2012 21:49:49 UTC+5:30, Krishna Kishore wrote:
Given a array of integers both positive and negative and you need to shift
positive numbers to one side
and negative numbers to
Root of a graph can be any node whose in-degree is zero. i.e. there are no
nodes pointing to that node.
It can be found by using O( |V| ) space and O( |E| ) time .
Now we can choose any node whose in-degree is zero if present.
or choose any random node
and itf DFS-tree is the desired tree.
@Gaurav: you are taking ia and ib as int so they will have 32 bits in
Java. So you can not set the bits for numbers in the array greater
than 32.
e.g if you have a[i]=59876 so you would want to set the 59876th bit in
ia : ia=ia | (159876) but that is not possible. How do you handle
this?
Also how
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3}
and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
No way u can do it in O(1) space and O(n) time.sols above are not
gonna work..yeah, it is possible in O(n) space and O(n) time.
On May 20, 12:29 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is a
permutation of a.
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for that particular key. If some char
not there in HT, return false, else
^not an O(n)
On May 21, 6:53 pm, Ashish Goel ashg...@gmail.com wrote:
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero
in space
On May 21, 6:53 pm, Ashish Goel ashg...@gmail.com wrote:
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for
@Ashish: Using a hash table violates the O(1) space requirement given in
the original problem.
Dave
On Monday, May 21, 2012 8:53:44 AM UTC-5, ashgoel wrote:
Dave,
Cant we have a hash table with the item as key and its count as value
(walk over array A and build HT).
For permutation
constant space vs no additional space and then O(n) time complexity not
possible..
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 8:01 PM, Dave dave_and_da...@juno.com wrote:
@Ashish: Using a hash table violates the O(1)
@ashish.. it wont be constant space then.. surely it will be o(n) though
On Mon, May 21, 2012 at 7:23 PM, Ashish Goel ashg...@gmail.com wrote:
Dave,
Cant we have a hash table with the item as key and its count as value
(walk over array A and build HT).
For permutation check, walk over
a[] = [-1,-3,4,0,7,0,36,2,-3]
b[] = [0,0,6,2,-1,9,28,1,6]
b1[] = [0,7,0,36,4,-6,3,0,0]
b2[] =[-1,-3,11,0,0,0,35,0,0]
suma = 42 proda = -84*72*3
sumb = 51 prodb = -84*72*3
sumb1 = 44 prodb1 = -84*72*3
sumb2 = 42 prodb2 = 33*35
do the sum and prod operation w/o 0s and compare the values..
@Partha
try with:
A = {2, 2, 9}
B= {1, 6, 6}
On Mon, May 21, 2012 at 7:08 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
a[] = [-1,-3,4,0,7,0,36,2,-3]
b[] = [0,0,6,2,-1,9,28,1,6]
b1[] = [0,7,0,36,4,-6,3,0,0]
b2[] =[-1,-3,11,0,0,0,35,0,0]
suma = 42 proda = -84*72*3
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
U are checking if the sum is same or not.. which can be same even if the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [
@piyush :
your solution will fail for the case
a={5,1,1}
b={3,3,1}
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0;
Piyush. I think we can use your logic. But You should check the product also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then
@Piyush: Try this i/p 8,0,0 ; 2,6,0-- Ur algo aint adequate..
On Sat, May 19, 2012 at 11:24 PM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
@umer : did interviewer told any one of the solution provided in the given
link below or different?
http://www.geeksforgeeks.org/archives/1155
On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Well, the interviewer gave a hint to use hash-table.
The key of hash-table will be memory address of original node and value
will be the memory address of the new node.
On Wed, Mar 14, 2012 at 9:43 PM, atul anand atul.87fri...@gmail.com wrote:
@umer : did interviewer told any one of the
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
Given a linked l
On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
- Given a linked a linked list with one pointer pointing to next,
another
http://www.geeksforgeeks.org/archives/1155
On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more
This problem is close to copying a graph. For that as you said, just
do DFS or BFS and maintain a map from original nodes to copies. Use
the copy to set pointers whenever it exists. When it doesn't exist,
make a new node and add it to the map.
You can implement the map in various ways. A hash
Copying a full graph requires a BFS or DFS. But here we have a big
advantage. We know the nodes are linked in a single chain. So we
don't need to search to find all nodes. We can just use .next
pointers.
No matter how we do things, we will need Map(A) that returns the copy
of node A if it
Sorry, a small test showed a loop quitting one iteration too soon.
Here is the fix.
import java.util.Random;
public class ListCopy {
class Node {
int val;
Node next, other;
Node() { }
Node(int val, Node next, Node other) {
this.val = val;
I would assume that in addition to functional testing through
automation(combination of various fonts,sizes etc) the tenets like
reliability, accessibility, interoperability, security(fuzz testing),
different architectures(amd, intel 32 bit, 64 bit etc), stress(extremely
long file reaching space
Well, this is a white box test. In a wbt, you look for edge and corner
cases. Edge cases in this scenario are the largest and smallest point sizes.
The fonts with largest kerning values. Largest ascenders and descenders.
Largest number of printable characters. You'd probably concentrate on
use suffix tree it's much faster than simple trie
with ukkonen's method you can build it in O(size of document) and then
searching in it is practically O(1)
http://en.wikipedia.org/wiki/Suffix_tree
http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
On Fri, Dec 10, 2010 at 7:54 PM, ADITYA
@aditya
there is always trade-off. for what it's asking, TRIE is probably the
fastest. the problem already stated, using data structure, which to
me, means, you index a document. indexing is expensive, but it's
overhead process and it has nothing to do w/ finding an existing word
in a doc.
On Dec
@ligerdave
agree with u :)
--
Regards
Aditya Kumar
B-tech 3rd year
Computer Science Engg.
MNNIT, Allahabad.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe
2010/12/7 ritesh riteshcseit...@gmail.com:
q = (len 1) 1;
what this line is accomplishing?
q = len 0xFFFE;
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
It sets the rightmost bit to 0. Could also be done with
q = len ~1;
Dave
On Dec 7, 12:50 am, ritesh riteshcseit...@gmail.com wrote:
q = (len 1) 1;
what this line is accomplishing?
On Dec 4, 12:38 pm, Abioy Sun abioy@gmail.com wrote:
Hello,
2010/12/4 siva viknesh
q = (len 1) 1;
what this line is accomplishing?
On Dec 4, 12:38 pm, Abioy Sun abioy@gmail.com wrote:
Hello,
2010/12/4 siva viknesh sivavikne...@gmail.com:
Modified 2 color sort problem i.e. you are given an array of integers
containing only 0s and 1s.You have to place all the 0s
@Mohit:
I dont think it really matters here.We just have to validate the snapshot of
the game board.Number of players should not have any relevance here.
On Sat, Sep 25, 2010 at 2:46 PM, mohit ranjan shoonya.mo...@gmail.comwrote:
@Ashita,
Your logic is fine for one vs one game, but as per
@ ashita and vrinda
can u please write ur ms written and interview questions..
i ll be really thankful to both of u as ms is going to visit my campus
soon.. so plz help...
On Sep 26, 1:58 pm, ashita dadlani ash@gmail.com wrote:
@Mohit:
I dont think it really matters here.We just have to
@Ashita,
Your logic is fine for one vs one game, but as per question it's one vs
many game
Any idea what is that ?
Mohit
On Sat, Sep 25, 2010 at 1:18 PM, ashita dadlani ash@gmail.com wrote:
1.The soldiers are initially placed at row 2 or row 7th(each-one of white
and either of
Valid must mean that you can get from an initial board to the the
current game state by a series of legal moves.
This is a classic branch and bound game tree search problem. You
could search either from a starting configuration and try to find
the current game state. Or start from the current
1.The soldiers are initially placed at row 2 or row 7th(each-one of white
and either of black).Also let white ones be at row 2.So they can never be at
row 1st.Incase it is so in the game,its not a valid game.
2.There are Bishops.Each color has one of its Bishop which moves diagonally
on all white
its an infinite loop. Beware.
On Mon, Aug 23, 2010 at 5:32 AM, Gene gene.ress...@gmail.com wrote:
This doesn't work on abb for example.
On Aug 22, 9:28 am, Ashish Goel ashg...@gmail.com wrote:
use a array
arr[char]=count char represent say a-z
count is # of occurances
while
This is the answer i have given and interviewer said, Optimise it
further in terms of memory and character need not be ASCII
On Aug 22, 6:28 pm, Ashish Goel ashg...@gmail.com wrote:
use a array
arr[char]=count char represent say a-z
count is # of occurances
while (*s!='\0')
{
Maybe to reduce the memory usage and to include all types of characters we
could create a one to one mapping between the character and the number
of occurrences.And while retrieving start from reverse checking the mapping
value,print if it's one.
On Sun, Aug 22, 2010 at 7:59 PM, Saikat Debnath
optimization, use bitmap instead of array...
char can be unicode, char may take 1 or 2 bytes, that can be written, big
deal..
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Aug 22, 2010 at 7:59 PM, Saikat Debnath saikat@gmail.comwrote:
This doesn't work on abb for example.
On Aug 22, 9:28 am, Ashish Goel ashg...@gmail.com wrote:
use a array
arr[char]=count char represent say a-z
count is # of occurances
while (*s!='\0')
{
arr[*s-'a']++;
if (arr[*s-'a']==1) lastchar=*s;
}
lastchar is the last non repeating char
63 matches
Mail list logo