Re: [algogeeks] MS interview question

[achala sharma]

1. Make a trie of all dictionary words.
2.then run a loop for all characters of string
3.suppose start from I ,as I is a word in dictionary,"word found" then
increment counter
4.Now counter comes to X,no word found
5.Now it comes to A,two word could start from A(A and AM)
now run this loop till end of string or till you didn't find M
if find M,then word is AM ,otherwise it's A.then increment counter for
outer loop
6.counter comes to F,no word found
7.G,M,J so on(No word found)
8.then A, again inner loop would run till the end of string length or till
u didn't find M.
In this way I think we could find all valid words in dictionary
time complexity would be O(n^3)
n for outer loop,n for inner loop and n for searching in trie


On Sun, Apr 14, 2013 at 12:41 PM, rahul sharma wrote:

> Suppose you are given a string IAMABOY
>
> and a dictionary then divide it into I AM A BOY if it is possible to break
> form as many dictionary words from a string giveM able to solve it..but
> how if we are given a string like IXAFGMJAHBDSOXDY.
>
> how can we form I AM A BOY..will be done in Opower(2,n)..for every
> character we consider it and not and form 2 ways...plz anyone shre the code
> for this approach...if the word is not a cotiguous subarray..
>
> --
> 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.

[algogeeks] MS interview question

[rahul sharma]

Suppose you are given a string IAMABOY

and a dictionary then divide it into I AM A BOY if it is possible to break
form as many dictionary words from a string giveM able to solve it..but
how if we are given a string like IXAFGMJAHBDSOXDY.

how can we form I AM A BOY..will be done in Opower(2,n)..for every
character we consider it and not and form 2 ways...plz anyone shre the code
for this approach...if the word is not a cotiguous subarray..

-- 
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.

Re: [algogeeks] MS interview

[Navin Kumar]

Anagram problem solution using TRIE..

For each word in dictionary we will put it in TRIE as..
 1. First sort the word
 2. Search in trie using sorted word. If search found then we will add the
original word in that TRIE node.
 3. If node node not found then using simple TRIE insertion insert sorted
word with original value stored at  last node.

For example: "CAT"

sort it => "ACT"

Search in trie with "ACT" : if node found then add "CAT" in that node.

If not found then create node with search key "ACT" store value "CAT".

Time complexity for listing all anagram :

For a given word sort it in O(L) and go to the node by traversing with
sorted word as a search key and will display all the value present at that
node.

Total time complexity : O(L) ,L = length of string


On Fri, Aug 24, 2012 at 11:18 AM, GAURAV CHAWLA wrote:

> Ques  Given a large text... in the text.. there are  > , < etc
> representing > and <.(there can be others like &eq;  etc)
>the task is to replace such (>) with the '>' symbol...
> and (<) with '<'
>given the table which have corresponding matches... and
> table is finite .
>   suggest an efficient algo...
>
>
>
>
>
> --
> Regards,
> G 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.
>

-- 
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 interview

[GAURAV CHAWLA]

Ques  Given a large text... in the text.. there are  > , < etc
representing > and <.(there can be others like &eq;  etc)
   the task is to replace such (>) with the '>' symbol...
and (<) with '<'
   given the table which have corresponding matches... and
table is finite .
  suggest an efficient algo...




-- 
Regards,
G 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.

Re: [algogeeks] MS interview

[Navin Kumar]

@Ashish: According to your algo making multimap itself takes O(mn) time
complexity (preprocessing). After then getting anagram of a string takes
O(n) time. Am i right?

On Thu, Aug 23, 2012 at 6:51 AM, Ashish Goel  wrote:

> O(n)
> convert each string into format a1b2and then insert into multimap
> wityh this a1b2...as key and original word as value. All words with same
> key are anagrams
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Wed, Aug 22, 2012 at 11:39 PM, GAURAV CHAWLA 
> wrote:
>
>> Ques..
>>
>> Given a m-word dictionary ... and a n-sized word... .. now suggest DS for
>> dictionary such that you can find out all the anagrams of the given word
>> present in dictionary...
>>
>>
>> --
>> Regards,
>> G 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.
>>
>
>  --
> 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] MS interview

[Ashish Goel]

O(n)
convert each string into format a1b2and then insert into multimap wityh
this a1b2...as key and original word as value. All words with same key are
anagrams
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Wed, Aug 22, 2012 at 11:39 PM, GAURAV CHAWLA wrote:

> Ques..
>
> Given a m-word dictionary ... and a n-sized word... .. now suggest DS for
> dictionary such that you can find out all the anagrams of the given word
> present in dictionary...
>
>
> --
> Regards,
> G 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.
>

-- 
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 interview

[GAURAV CHAWLA]

Ques..

Given a m-word dictionary ... and a n-sized word... .. now suggest DS for
dictionary such that you can find out all the anagrams of the given word
present in dictionary...


-- 
Regards,
G 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.

Re: [algogeeks] MS interview

[Abhishek Yadav]

What should be the answer to above questions...?

On Sat, Sep 17, 2011 at 5:01 AM, bharatkumar bagana <
bagana.bharatku...@gmail.com> wrote:

> Memory management has following things..
> 1.Relocation
> To maintain the free pages and when a page is to be swapped, we have to add
> that page into free page list ..
> For this ,if we maintain a bool array which is equal to # pages in RAM,it
> gives whether it is free or not ..
>
> 2.Protection
> If ours is strict paging , then this is easy task to implement ... any way
> we have the fixed page size ...
> In segmentation , we maintain length of the segment..we can achieve
> protection...
>
> 3.Sharing
> for each page if we maintain the list of users this page has been given
> permission (either read or write)
>
> 4.Logical Organization
>
> 5.Physical Organization
>
>
>
>
> On Thu, Sep 15, 2011 at 2:06 PM, teja bala wrote:
>
>> 13. Propose an algo/data struct for memory manager.
>> 14. Propose and algo/data struct for timer manager.
>>
>> --
>> 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.
>>
>>
>
>
> --
>
> **Please do not print this e-mail until urgent requirement. Go Green!!
> Save Papers <=> Save Trees
> *BharatKumar Bagana*
> **http://www.google.com/profiles/bagana.bharatkumar
> *
> Mobile +91 8056127652*
> 
>
>
> --
> 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] MS interview

[bharatkumar bagana]

Memory management has following things..
1.Relocation
To maintain the free pages and when a page is to be swapped, we have to add
that page into free page list ..
For this ,if we maintain a bool array which is equal to # pages in RAM,it
gives whether it is free or not ..

2.Protection
If ours is strict paging , then this is easy task to implement ... any way
we have the fixed page size ...
In segmentation , we maintain length of the segment..we can achieve
protection...

3.Sharing
for each page if we maintain the list of users this page has been given
permission (either read or write)

4.Logical Organization

5.Physical Organization



On Thu, Sep 15, 2011 at 2:06 PM, teja bala wrote:

> 13. Propose an algo/data struct for memory manager.
> 14. Propose and algo/data struct for timer manager.
>
> --
> 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.
>
>


-- 

**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*


-- 
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 interview

[teja bala]

13. Propose an algo/data struct for memory manager.
14. Propose and algo/data struct for timer manager.

-- 
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 interview:

[Anantha Krishnan]

Here is a Java code :

*private static void _printTree(String root,int depth)
{
if(root==null || root.trim().length()==0)
return;
File f=new File(root);
if(f.isFile()==true)
{
printTab(depth);
System.out.printf("%s\n",f.getName());
return;
}
if(f.isDirectory()==true)
{
printTab(depth);
System.out.printf("%s\n",f.getName());
String[] filelist=f.list();
if(filelist==null)
return;
for(String file:filelist)
{
_printTree(root+File.separator+file, depth+1);
}
return;
}
return;
}

public static void printTree(String root)
{
_printTree(root, 0);
}*

Thanks & Regards
Anantha Krishnan

On Wed, Jul 27, 2011 at 1:21 PM, geek forgeek  wrote:

> can some one give me the code plz?
>
>
> On Wed, Jul 27, 2011 at 12:26 AM, sunny agrawal 
> wrote:
>
>> yes Preorder recursion will be good for displaying in User Friendly way...
>>
>>
>> On Wed, Jul 27, 2011 at 12:49 PM, Anand Saha  wrote:
>>
>>> Implement Preorder Traversal in the File system tree.
>>>
>>> --
>>>
>>>
>>>
>>> On Wed, Jul 27, 2011 at 12:06 PM, geek forgeek wrote:
>>>
 Function to display the directory structure in a user friendly way
 taking root dir as arg
 for a general OS. You may assume and state some basic APIs available in
 that OS

 --
 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.
>>>
>>
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>>  --
>> 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] MS interview:

[geek forgeek]

can some one give me the code plz?

On Wed, Jul 27, 2011 at 12:26 AM, sunny agrawal wrote:

> yes Preorder recursion will be good for displaying in User Friendly way...
>
>
> On Wed, Jul 27, 2011 at 12:49 PM, Anand Saha  wrote:
>
>> Implement Preorder Traversal in the File system tree.
>>
>> --
>>
>>
>>
>> On Wed, Jul 27, 2011 at 12:06 PM, geek forgeek wrote:
>>
>>> Function to display the directory structure in a user friendly way taking
>>> root dir as arg
>>> for a general OS. You may assume and state some basic APIs available in
>>> that OS
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> 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] MS interview:

[sunny agrawal]

yes Preorder recursion will be good for displaying in User Friendly way...

On Wed, Jul 27, 2011 at 12:49 PM, Anand Saha  wrote:

> Implement Preorder Traversal in the File system tree.
>
> --
>
>
>
> On Wed, Jul 27, 2011 at 12:06 PM, geek forgeek wrote:
>
>> Function to display the directory structure in a user friendly way taking
>> root dir as arg
>> for a general OS. You may assume and state some basic APIs available in
>> that OS
>>
>> --
>> 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.
>



-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
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 interview:

[Anand Saha]

Implement Preorder Traversal in the File system tree.

-- 



On Wed, Jul 27, 2011 at 12:06 PM, geek forgeek wrote:

> Function to display the directory structure in a user friendly way taking
> root dir as arg
> for a general OS. You may assume and state some basic APIs available in
> that OS
>
> --
> 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] MS interview:

[geek forgeek]

Function to display the directory structure in a user friendly way taking
root dir as arg
for a general OS. You may assume and state some basic APIs available in that
OS

-- 
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 interview

[subramania jeeva]

consider two matrices A & B
Its solution is based on transposing a matrix B, so that its solution can be
computed easily.
Here I gave the solution in which each node has three variables index i,j
and value.


#include
using namespace std;
struct node
{
int val,i,j;
node *next;
};
node *mul(node *head1,node *head2,node *head3)
{
node *head=head1,*t1,*t2,*t3,*t4=head1;
for(t1=head1,t2=head2,t3=head3;t1!=NULL;)
{
t3->val=0;
while((t2->next!=0) && (t2->next->j>=t2->j))
{
t3->val+=t2->val * t1->val;
t1=t1->next;
t2=t2->next;
}
t3->val+=t1->val*t2->val;
coutnext==0)
{
t1=t1->next;
t4=t1;
ll=1;
}
else if(t2->next->j < t2->j)
t1=t4;
t3=t3->next;
if(t2->next!=0)
t2=t2->next;
else
t2=head2;
}
return head3;//output list
}
node *transpose(node *head)//transposing list B
{
int g;
node *head1=head,*temp,*head2;
head2=head1->next;
temp=head;
while((temp->next->j)!=(temp->j) || (temp->next->i)<=(temp->i))
{
coutnext!=0)
{
if(temp->next->j < temp->j)
{
node *t,*t1;
t1=temp->next->next;
t=temp->next;
temp->next=t1;
t->next=head1->next;
head1->next=t;
head1=t;
head2=head1->next;
}
temp=temp->next;
if(temp==0 || temp->next==0)
{
head1=head1->next;
head2=head1->next;
temp=head2;
}
}
}
int i=0,j=0,o;
for(temp=head;temp!=NULL;temp=temp->next)
{
o=1;

if(temp->next!=0 && temp->j != temp->next->j)
{
o=0;
}
if(!o)
{
 temp->i=i;
temp->j=j;
i++;j=0;
}
else
{
temp->i=i;
temp->j=j;
}
j++;
}
return head;
}
node *create_matrix_list(int n,int x)
{
node *head,*temp;
for(int i=0;i>head->val;
head->next=NULL;
head->i=i;
head->j=j;
temp=head;
}
else
{
temp->next=new node();
temp=temp->next;
if(x!=3)
cin>>temp->val;
temp->i=i;
temp->j=j;
temp->next=0;
}
}
}
return head;
}
int main()
{
 node *h1=NULL,*h2=NULL,*h3=NULL;
cout<<"Enter the size of matrix :";
int m;
cin>>m;
cout<<"Enter values for matrix A :";

h1=create_matrix_list(m,1);

cout<<"Enter values for matrix B :";

h2=create_matrix_list(m,2);
h3=create_matrix_list(m,3);
h2=transpose(h2);

h3=mul(h1,h2,h3);

for(temp=h3;temp!=NULL;temp=temp->next)
cout<<"i :"2->3->4->5->6->7->8->9
B   : 5->6->2->1->3->7->8->2->1
C   : 31->18->19->73->51->49->115->84->79



Cheers
  ~ Jeeva ~

-- 
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 interview

[((** VICKY **))]

Given a linked list with a n*n matrix elements write an algo to
compute product of two such linked list.
say n  = 3then

1 2 3
4 5 6
7 8 9

will be given as 1->2->3->4->5->6->7->8->9

now given two matrices , given a algo to perform  matrix
multiplication giving result in thrid linked list.

-- 
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 Interview

[Aniket Dutta]

you can sort it using external merge sort. if ur file is greater than memory
refer henry F. korth Database System Concept

On Wed, Jul 13, 2011 at 10:26 AM, rShetty  wrote:

> Given a very big file of words, a word in each line, sort the words .
> Please provide the algorithm and explanation .
>
> --
> 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] MS Interview

[saurabh singh]

maintain a key.Associate with each word a key.When comparing the string,if
string1>string2 swap the keys instead of the words.Saves enormous time.

On Wed, Jul 13, 2011 at 10:32 AM, nicks  wrote:

> Algorithm along with code is explained very well in K&R refer page 108
>  ;)
>
>
> On Wed, Jul 13, 2011 at 10:26 AM, rShetty  wrote:
>
>> Given a very big file of words, a word in each line, sort the words .
>> Please provide the algorithm and explanation .
>>
>> --
>> 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.
>



-- 
Saurabh Singh
B.Tech (Computer Science)
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 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 Interview

[nicks]

Algorithm along with code is explained very well in K&R refer page 108;)

On Wed, Jul 13, 2011 at 10:26 AM, rShetty  wrote:

> Given a very big file of words, a word in each line, sort the words .
> Please provide the algorithm and explanation .
>
> --
> 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] MS Interview

[rShetty]

Given a very big file of words, a word in each line, sort the words .
Please provide the algorithm and explanation .

-- 
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 Interview

[李峰]

A1.bitmap.
A2.xor.

On Thu, Jun 09, 2011 at 02:45:48AM -0700, Dumanshu wrote:
 > Q1. I  have a file in which there are supposed to be 4 billion
 > numbers,
 > starting from 1 to 4,000,000,000 but unfortunately one number is
 > missing,
 > i.e there are only 3,999,999,999 numbers, I need to find the missing
 > number.
 > 
 > 
 > Q2.  I have an array consisting of 2n+1 elements. n elements in it are
 > married, i.e they occur twice in the array, however there is one
 > element
 > which only appears once in the array. I need to find that number in a
 > single pass using constant memory. {assume all are positive numbers}
 > Eg :- 3 4 1 3 1 7 2 2 4
 > Ans:- 7
 > 
 > -- 
 > 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.

-- 
TAOCP
大地母亲在忽悠着你.
http://cn.linkedin.com/pub/feng-li/29/95b/640
http://gentoo-taocp.blogspot.com
http://groups.google.com/group/szlug

-- 
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 interview question

[Rohit Sindhu]

I this this code will solves it ...

*#include 
#include 

struct node{
int val;
struct node *next;
};

int main(){

struct node *head = NULL , *next_ptr = head;
int n = 1;

while ( n <= 6 ){
struct node *temp = (struct node*) malloc (sizeof(struct node) );
temp->val = n++;
temp->next = NULL;

if (head == NULL ){
head = temp ;
next_ptr = head;
}else{
next_ptr->next = temp;
next_ptr = temp;
}

}

next_ptr = head;
head = NULL;
struct node *prev = NULL;

while ( next_ptr != NULL && next_ptr->next != NULL ){
struct node *swp = next_ptr->next->next;

if ( head == NULL){
head = next_ptr->next;
}


if ( prev == NULL ){
prev = next_ptr;
}else{
prev->next = next_ptr->next;
prev = next_ptr;
}

next_ptr->next->next = next_ptr;
next_ptr->next = swp;
next_ptr = swp;

}


while ( head != NULL ){
printf("%d \n" , head->val);
head = head->next;
}

return 0;
}
*





On Thu, Jun 2, 2011 at 7:18 AM, Anurag Bhatia  wrote:

> Have a look at this recursive soln in java -
>
> Node convertList(Node head)
>{
>if(head ==null)
>return null;
>
>Node node = head;
>Node next = node.next;
>Node next2next = next.next;
>
>next.next = node;
>node.next = convertList(next2next);
>
>return next;
>}
>
> This soln assumes even number of nodes in the list. The code is quite
> self explanatory.
>
> --Anurag
>
>
> On Wed, Jun 1, 2011 at 6:26 AM, Anand  wrote:
> > Given a linked list of the form, 1->2->3->4->5->6, convert it into the
> form
> > 2->1->4->3->6->5. Note that the nodes need to be altered and not the data
> > contained in them
> >
> > --
> > 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.
>
>


-- 
ROHIT SINDHU
B.Tech (IT) -- 6th sem.
INDIAN INSTITUTE OF INFORMATION TECHNOLOGY, ALLAHABAD.

-- 
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 Interview

[sunny agrawal]

yes, but using xor no need of ULL :)

2011/6/9 • » νιρυℓ « • 

> Sum wont overflow, ULL range will include sum.
>
> On Thu, Jun 9, 2011 at 3:52 PM, sunny agrawal wrote:
>
>> sum can overflow
>> Xor method can also be applied to Q1. no need of numbers to be sorted.
>>
>> 2011/6/9 • » νιρυℓ « • 
>>
>>> For 1.
>>> sum the numbers in the file, subtract it from sum of first 4 billion
>>> numbers.
>>>
>>>
>>> On Thu, Jun 9, 2011 at 3:44 PM, Navneet Gupta wrote:
>>>
 The answer to second question is simple. XORing all the elements
 should do it for you.


 On Thu, Jun 9, 2011 at 3:15 PM, Dumanshu  wrote:
 > Q1. I  have a file in which there are supposed to be 4 billion
 > numbers,
 > starting from 1 to 4,000,000,000 but unfortunately one number is
 > missing,
 > i.e there are only 3,999,999,999 numbers, I need to find the missing
 > number.
 >
 >
 > Q2.  I have an array consisting of 2n+1 elements. n elements in it are
 > married, i.e they occur twice in the array, however there is one
 > element
 > which only appears once in the array. I need to find that number in a
 > single pass using constant memory. {assume all are positive numbers}
 > Eg :- 3 4 1 3 1 7 2 2 4
 > Ans:- 7
 >
 > --
 > 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.
 >
 >



 --
 --Navneet

 --
 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.


>>>
>>>
>>> --
>>> Regards,
>>> Vipul
>>>
>>>  --
>>> 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.
>>>
>>
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>>  --
>> 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.
>>
>
>
>
> --
> Regards,
> Vipul
>
>  --
> 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.
>



-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
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 Interview

[• » νιρυℓ « •]

Sum wont overflow, ULL range will include sum.

On Thu, Jun 9, 2011 at 3:52 PM, sunny agrawal wrote:

> sum can overflow
> Xor method can also be applied to Q1. no need of numbers to be sorted.
>
> 2011/6/9 • » νιρυℓ « • 
>
>> For 1.
>> sum the numbers in the file, subtract it from sum of first 4 billion
>> numbers.
>>
>>
>> On Thu, Jun 9, 2011 at 3:44 PM, Navneet Gupta wrote:
>>
>>> The answer to second question is simple. XORing all the elements
>>> should do it for you.
>>>
>>>
>>> On Thu, Jun 9, 2011 at 3:15 PM, Dumanshu  wrote:
>>> > Q1. I  have a file in which there are supposed to be 4 billion
>>> > numbers,
>>> > starting from 1 to 4,000,000,000 but unfortunately one number is
>>> > missing,
>>> > i.e there are only 3,999,999,999 numbers, I need to find the missing
>>> > number.
>>> >
>>> >
>>> > Q2.  I have an array consisting of 2n+1 elements. n elements in it are
>>> > married, i.e they occur twice in the array, however there is one
>>> > element
>>> > which only appears once in the array. I need to find that number in a
>>> > single pass using constant memory. {assume all are positive numbers}
>>> > Eg :- 3 4 1 3 1 7 2 2 4
>>> > Ans:- 7
>>> >
>>> > --
>>> > 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.
>>> >
>>> >
>>>
>>>
>>>
>>> --
>>> --Navneet
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> Regards,
>> Vipul
>>
>>  --
>> 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.
>>
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> 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.
>



-- 
Regards,
Vipul

-- 
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 Interview

[sunny agrawal]

sum can overflow
Xor method can also be applied to Q1. no need of numbers to be sorted.

2011/6/9 • » νιρυℓ « • 

> For 1.
> sum the numbers in the file, subtract it from sum of first 4 billion
> numbers.
>
>
> On Thu, Jun 9, 2011 at 3:44 PM, Navneet Gupta wrote:
>
>> The answer to second question is simple. XORing all the elements
>> should do it for you.
>>
>>
>> On Thu, Jun 9, 2011 at 3:15 PM, Dumanshu  wrote:
>> > Q1. I  have a file in which there are supposed to be 4 billion
>> > numbers,
>> > starting from 1 to 4,000,000,000 but unfortunately one number is
>> > missing,
>> > i.e there are only 3,999,999,999 numbers, I need to find the missing
>> > number.
>> >
>> >
>> > Q2.  I have an array consisting of 2n+1 elements. n elements in it are
>> > married, i.e they occur twice in the array, however there is one
>> > element
>> > which only appears once in the array. I need to find that number in a
>> > single pass using constant memory. {assume all are positive numbers}
>> > Eg :- 3 4 1 3 1 7 2 2 4
>> > Ans:- 7
>> >
>> > --
>> > 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.
>> >
>> >
>>
>>
>>
>> --
>> --Navneet
>>
>> --
>> 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.
>>
>>
>
>
> --
> Regards,
> Vipul
>
>  --
> 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.
>



-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
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 Interview

[Naveen Kumar]

I think numbers in question1 are in sequence (ascending order).

2011/6/9 • » νιρυℓ « • 

> For 1.
> sum the numbers in the file, subtract it from sum of first 4 billion
> numbers.
>
>
> On Thu, Jun 9, 2011 at 3:44 PM, Navneet Gupta wrote:
>
>> The answer to second question is simple. XORing all the elements
>> should do it for you.
>>
>>
>> On Thu, Jun 9, 2011 at 3:15 PM, Dumanshu  wrote:
>> > Q1. I  have a file in which there are supposed to be 4 billion
>> > numbers,
>> > starting from 1 to 4,000,000,000 but unfortunately one number is
>> > missing,
>> > i.e there are only 3,999,999,999 numbers, I need to find the missing
>> > number.
>> >
>> >
>> > Q2.  I have an array consisting of 2n+1 elements. n elements in it are
>> > married, i.e they occur twice in the array, however there is one
>> > element
>> > which only appears once in the array. I need to find that number in a
>> > single pass using constant memory. {assume all are positive numbers}
>> > Eg :- 3 4 1 3 1 7 2 2 4
>> > Ans:- 7
>> >
>> > --
>> > 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.
>> >
>> >
>>
>>
>>
>> --
>> --Navneet
>>
>> --
>> 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.
>>
>>
>
>
> --
> Regards,
> Vipul
>
>  --
> 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.
>



-- 
Cheers
Naveen Kumar

-- 
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 Interview

[• » νιρυℓ « •]

For 1.
sum the numbers in the file, subtract it from sum of first 4 billion
numbers.

On Thu, Jun 9, 2011 at 3:44 PM, Navneet Gupta  wrote:

> The answer to second question is simple. XORing all the elements
> should do it for you.
>
>
> On Thu, Jun 9, 2011 at 3:15 PM, Dumanshu  wrote:
> > Q1. I  have a file in which there are supposed to be 4 billion
> > numbers,
> > starting from 1 to 4,000,000,000 but unfortunately one number is
> > missing,
> > i.e there are only 3,999,999,999 numbers, I need to find the missing
> > number.
> >
> >
> > Q2.  I have an array consisting of 2n+1 elements. n elements in it are
> > married, i.e they occur twice in the array, however there is one
> > element
> > which only appears once in the array. I need to find that number in a
> > single pass using constant memory. {assume all are positive numbers}
> > Eg :- 3 4 1 3 1 7 2 2 4
> > Ans:- 7
> >
> > --
> > 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.
> >
> >
>
>
>
> --
> --Navneet
>
> --
> 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.
>
>


-- 
Regards,
Vipul

-- 
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 Interview

[Dumanshu]

Q1. I  have a file in which there are supposed to be 4 billion
numbers,
starting from 1 to 4,000,000,000 but unfortunately one number is
missing,
i.e there are only 3,999,999,999 numbers, I need to find the missing
number.


Q2.  I have an array consisting of 2n+1 elements. n elements in it are
married, i.e they occur twice in the array, however there is one
element
which only appears once in the array. I need to find that number in a
single pass using constant memory. {assume all are positive numbers}
Eg :- 3 4 1 3 1 7 2 2 4
Ans:- 7

-- 
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 Interview

[varun pahwa]

2nd part can be done just take the xor of all the numbers same number xor
returns 0 so only seven will remain.
1st part can be done in O(n) because estimate sum -> n*(n+1)/2. now sub from
estimated sum each array element. the last value remained is the missing
number.
correct me if i am wrong.

On Thu, Jun 9, 2011 at 9:59 AM, Ershad K  wrote:

> On Thursday 09 June 2011 03:15 PM, Dumanshu wrote:
>
>> Q1. I  have a file in which there are supposed to be 4 billion
>> numbers,
>> starting from 1 to 4,000,000,000 but unfortunately one number is
>> missing,
>> i.e there are only 3,999,999,999 numbers, I need to find the missing
>> number.
>>
>
> Is the array sorted?
>
> --
> Sincerely,
> Ershad K
> http://ershadk.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.
>
>


-- 
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112 ,08011820777
Official Email :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com

People who fail to plan are those who plan to fail.

-- 
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 Interview

[Navneet Gupta]

The answer to second question is simple. XORing all the elements
should do it for you.


On Thu, Jun 9, 2011 at 3:15 PM, Dumanshu  wrote:
> Q1. I  have a file in which there are supposed to be 4 billion
> numbers,
> starting from 1 to 4,000,000,000 but unfortunately one number is
> missing,
> i.e there are only 3,999,999,999 numbers, I need to find the missing
> number.
>
>
> Q2.  I have an array consisting of 2n+1 elements. n elements in it are
> married, i.e they occur twice in the array, however there is one
> element
> which only appears once in the array. I need to find that number in a
> single pass using constant memory. {assume all are positive numbers}
> Eg :- 3 4 1 3 1 7 2 2 4
> Ans:- 7
>
> --
> 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.
>
>



-- 
--Navneet

-- 
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 Interview

[Ershad K]

On Thursday 09 June 2011 09:59 AM, Ershad K wrote:

On Thursday 09 June 2011 03:15 PM, Dumanshu wrote:

Q1. I have a file in which there are supposed to be 4 billion
numbers,
starting from 1 to 4,000,000,000 but unfortunately one number is
missing,
i.e there are only 3,999,999,999 numbers, I need to find the missing
number.


Is the array sorted?


Apology for the previous reply. I mean, is the numbers in the file sorted?

Thanks.
--
Sincerely,
Ershad K
http://ershadk.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] MS Interview

[Freak Algo]

For Q2 "Bitwise X-OR" operation of all input numbers does the trick.

--- On Thu, 9/6/11, Dumanshu  wrote:

From: Dumanshu 
Subject: [algogeeks] MS Interview
To: "Algorithm Geeks" 
Date: Thursday, 9 June, 2011, 9:45 AM

Q1. I  have a file in which there are supposed to be 4 billion
numbers,
starting from 1 to 4,000,000,000 but unfortunately one number is
missing,
i.e there are only 3,999,999,999 numbers, I need to find the missing
number.


Q2.  I have an array consisting of 2n+1 elements. n elements in it are
married, i.e they occur twice in the array, however there is one
element
which only appears once in the array. I need to find that number in a
single pass using constant memory. {assume all are positive numbers}
Eg :- 3 4 1 3 1 7 2 2 4
Ans:- 7

-- 
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] MS Interview

[Ershad K]

On Thursday 09 June 2011 03:15 PM, Dumanshu wrote:

Q1. I  have a file in which there are supposed to be 4 billion
numbers,
starting from 1 to 4,000,000,000 but unfortunately one number is
missing,
i.e there are only 3,999,999,999 numbers, I need to find the missing
number.


Is the array sorted?

--
Sincerely,
Ershad K
http://ershadk.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] MS interview question

[Anurag Bhatia]

Have a look at this recursive soln in java -

Node convertList(Node head)
{
if(head ==null)
return null;

Node node = head;
Node next = node.next;
Node next2next = next.next;

next.next = node;
node.next = convertList(next2next);

return next;
}

This soln assumes even number of nodes in the list. The code is quite
self explanatory.

--Anurag


On Wed, Jun 1, 2011 at 6:26 AM, Anand  wrote:
> Given a linked list of the form, 1->2->3->4->5->6, convert it into the form
> 2->1->4->3->6->5. Note that the nodes need to be altered and not the data
> contained in them
>
> --
> 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] MS interview question

[Azhar Hussain]

struct node  *reverse(struct node *head, int k )
{
struct node *prev = NULL;
struct node *current = head;
struct node *next = NULL;
int count = 0;

while(current && count < k) {
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}

/*** reverse remaining nodes recursively ***/
if (next != NULL) {
head->next = reverse(next, k);
}
 return prev;
}

eg
head = reverse(head, 2);
head = reverse(head, 3);



-
Azhar.


On Thu, Jun 2, 2011 at 2:09 PM, wujin chen  wrote:

> how about this one?
>
> Node* reverseBy2(Node* head){
> Node* p1 = head;
> if(p1 == NULL)
> return NULL;
> Node* p2 = p1->next;
> if(p2 == NULL)
> return head;
> Node* nextHead = p2->next;
> p2->next = p1;
> p1->next = reverseBy2(nextHead);
> return p2;
> }
> [?]
>
> 2011/6/1 Shivaji Varma 
>
>> Hi,
>>
>> Please take a look at this link.
>>
>> http://mycsinterviewsexperiences.blogspot.com/
>>
>>
>> --
>> Shivaji
>>
>>
>> On Wed, Jun 1, 2011 at 6:26 AM, Anand  wrote:
>>
>>> Given a linked list of the form, 1->2->3->4->5->6, convert it into the
>>> form 2->1->4->3->6->5. Note that the nodes need to be altered and not the
>>> data contained in them
>>>
>>> --
>>> 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.

<<1E3.gif>>

Re: [algogeeks] MS interview question

[wujin chen]

how about this one?

Node* reverseBy2(Node* head){
Node* p1 = head;
if(p1 == NULL)
return NULL;
Node* p2 = p1->next;
if(p2 == NULL)
return head;
Node* nextHead = p2->next;
p2->next = p1;
p1->next = reverseBy2(nextHead);
return p2;
}
[?]
2011/6/1 Shivaji Varma 

> Hi,
>
> Please take a look at this link.
>
> http://mycsinterviewsexperiences.blogspot.com/
>
>
> --
> Shivaji
>
>
> On Wed, Jun 1, 2011 at 6:26 AM, Anand  wrote:
>
>> Given a linked list of the form, 1->2->3->4->5->6, convert it into the
>> form 2->1->4->3->6->5. Note that the nodes need to be altered and not the
>> data contained in them
>>
>> --
>> 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.

<<1E3.gif>>

Re: [algogeeks] MS interview question

[Shivaji Varma]

Hi,

Please take a look at this link.

http://mycsinterviewsexperiences.blogspot.com/


--
Shivaji

On Wed, Jun 1, 2011 at 6:26 AM, Anand  wrote:

> Given a linked list of the form, 1->2->3->4->5->6, convert it into the form
> 2->1->4->3->6->5. Note that the nodes need to be altered and not the data
> contained in them
>
> --
> 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] MS interview question

[Anand]

Given a linked list of the form, 1->2->3->4->5->6, convert it into the form
2->1->4->3->6->5. Note that the nodes need to be altered and not the data
contained in them

-- 
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.