[algogeeks] Questions
Given two arrays , one is 1D array and other is 2D array . Now u need to find out whether 2D array contains the subset of 1D array . The elements of 1D array not neccessary present in the same row it can be either on the up or down but should be continuous in the 2D array .. -- 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/-/GKvCpIqLjt8J. 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: Hash Table
from high level and with a very few collisions, it's O(1). there isn't much to prove because this is based on a common sense. for example, have the world as a hashtable and all countries as the keys of it. boxes(storage) marked by different country names(key) and you know where to locate them. now, you are given a mail and asked to put it into the box which goes to its destination country. so how many operations does it take you to put a mail in the box? 1 if you realized the mail wasn't misplaced and you need to take it out, how many operations does it take you to take the mail out of the box? i hope this helps a bit -- 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/-/ZamCyJETdscJ. 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: Find all possible combination of integers for a given sum
Are we talking about only positive integers here? On Wed, Oct 26, 2011 at 11:33 PM, Vaibhav Mittal vaibhavmitta...@gmail.comwrote: +1 Prem @ligerdave : I knew about the recursion method..but can u throw some light on the pointer based method..(with a small example maybe).. Specifically I wanted to know the implementation part and the running time of the algorithm. On Wed, Oct 26, 2011 at 8:33 PM, ligerdave david.c...@gmail.com wrote: @meng You already have the pattern figured out. each time subtract 1 from the lowest digit and add to higher digit(only once), until the lowest digit equals to closest higher digit. the selection of which number to start could be figured out with given parameters sum and combination @Prem, no recursion needed here. it make it more complex than necessary. one loop with a pointer should be able to resolve this On Oct 24, 6:28 pm, Meng Yan mengyan.fu...@gmail.com wrote: Hi, my question is given sum=N and combination constraint=M (the number of elements), how to find all possible combinations of integers? For example, given sum=6, combination=3; how to get the result as following: 1+1+4; 1+2+3; 2+2+2; We don't care about order of the elements, which means 1+1+4 and 1+4+1 are considered as same combination. Thanks a lot! Meng -- 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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: FACEBOOK ONLINE CODING ROUND
logic: N=3.. k=5th(position).length... no. of setbit :0... 000 k =5 no. of setbit :1.. on every loop get next number of same number of bits and decrement k by 1. 001k = 4 010k=3 100k= 2 no. of setbit: 2 011 k=1.. 101 110 Therefore answer is 011 complexity : O(n)... With regards, Praveen Raj DCE-IT 735993 praveen0...@gmail.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] Re: Hash Table
If N Element is already hashed and when you insert next element , Does hashing will take log N time to find the next available position? Actually the next insertion typically does not have any co-relation to pre-existing table content (Until your Hash function is badly designed to hash always on the same key everytime). So, its actually the design of Hash that has to be efficient.Hence every operation cannot be mapped to the number of data which is present in the existing table. On Thu, Oct 27, 2011 at 12:49 AM, ligerdave david.c...@gmail.com wrote: from high level and with a very few collisions, it's O(1). there isn't much to prove because this is based on a common sense. for example, have the world as a hashtable and all countries as the keys of it. boxes(storage) marked by different country names(key) and you know where to locate them. now, you are given a mail and asked to put it into the box which goes to its destination country. so how many operations does it take you to put a mail in the box? 1 if you realized the mail wasn't misplaced and you need to take it out, how many operations does it take you to take the mail out of the box? i hope this helps a bit -- 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/-/ZamCyJETdscJ. 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] Re: Hash Table
suppose the problem is
Problem 4: Find all unique pairs of element in an array that sum to S. For
ex. If array = {2,4,6,4,6} and S = 8 then answer is {2,6, 4,4}
suppose we use STL c++ hash class to solve the problem . In the first we
hash all the elements . in the second pass we take each element and subtract
it from '8' and then we search for that difference in the hash table. if it
is found then the pair exists .otherwise it does not exist.
My questions are
1) What is the space complexity used by hash table . is it O(n) becoz 'n'
elements are hashed into hash table.
2) Does the time to search an element is hash table is still O(1) ,but there
are 'n' elements in hash table .Then how could it be O(1)
Please clear my above doubts .These doubts are haunting me .I am very
thankful to them ...
On 27 October 2011 06:18, Prem Krishna Chettri hprem...@gmail.com wrote:
If N Element is already hashed and when you insert next element , Does
hashing will take log N time to find the next available position? Actually
the next insertion typically does not have any co-relation to pre-existing
table content (Until your Hash function is badly designed to hash always on
the same key everytime). So, its actually the design of Hash that has to be
efficient.Hence every operation cannot be mapped to the number of data which
is present in the existing table.
On Thu, Oct 27, 2011 at 12:49 AM, ligerdave david.c...@gmail.com wrote:
from high level and with a very few collisions, it's O(1).
there isn't much to prove because this is based on a common sense.
for example, have the world as a hashtable and all countries as the keys
of it. boxes(storage) marked by different country names(key) and you know
where to locate them. now, you are given a mail and asked to put it into the
box which goes to its destination country.
so how many operations does it take you to put a mail in the box? 1
if you realized the mail wasn't misplaced and you need to take it out, how
many operations does it take you to take the mail out of the box?
i hope this helps a bit
--
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/-/ZamCyJETdscJ.
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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: Questions
Forgot to mention this was asked in Amazon Interview .. -- 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: Hash Table
I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- 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/-/G_0Wm4NQIyIJ. 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: Hash Table
Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- 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/-/G_0Wm4NQIyIJ. 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] Re: Hash Table
@Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- 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/-/G_0Wm4NQIyIJ. 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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: Hash Table
I am asking for the above quesiton On 27 October 2011 07:38, kumar raja rajkumar.cs...@gmail.com wrote: @Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- 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/-/G_0Wm4NQIyIJ. 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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: Hash Table
@Kumar: It's O(1) for searching an element in hash table as long as there is no collision. -Vicki On Thu, Oct 27, 2011 at 10:38 AM, kumar raja rajkumar.cs...@gmail.comwrote: @Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- 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/-/G_0Wm4NQIyIJ. 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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] Searching In a large file
Given a file containing roughly 300 million social security numbers(9-digit numbers), find a 9-digit number that is not in the file. You have unlimited drive space but only 2megabytes of RAM at your disposal. -- 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] TI internship
Texas is coming for internship for computer science, so if anyone know the pattern of exam or interview please tell.. -- 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] Intersection of arrays
I think , in the worst case this hashing technique 'll take O(n^(k-1)) time? so i wud stick with sorting idea with confirm : O(mlogm) + O(m) time complexity where m is avg length of arrays. On Tue, Oct 25, 2011 at 6:02 PM, kumar raja rajkumar.cs...@gmail.comwrote: Dheeraj can u please tell me how to keep track count for an element ,in hash table. I want the exact structure of the hash table The hash function uses the input as the elements value ,and stores it in some slot by computing hash function..then where is the question of storing count for that number. I am pretty much confused with this hashing and how these details are exactly implemented in STL hash map class. On 24 October 2011 23:32, Dheeraj Sharma dheerajsharma1...@gmail.comwrote: use hashing.. let the no. of array be 1 to K increment the count of element for that array..(in hash table) only if its count value in hash table is one less then the array no.(which means that..it is present in all the arrays..preceding it) now search the hash table..in which element count is equal to K On Tue, Oct 25, 2011 at 11:47 AM, kumar raja rajkumar.cs...@gmail.comwrote: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. what data structure is useful here?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- *Dheeraj Sharma* -- 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 Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- *MOHIT VERMA* -- 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: Hash Table
One sentence answer to your query is all Hash DataStructure is suppose to provide Constant Time Complexity .i.e.O(1). However as an when HashTable fills up,Data Value collision occurs becoz,common key will generated by HashFunction.Thats where HashFunction dependibility comes into picture.. Well the Worst Case of Time Complxity extremgely poor hash function may go upto O(n). Which is very rare and when data is hash table is fully filled with all colliding values.. On 10/27/11, kumar raja rajkumar.cs...@gmail.com wrote: I am asking for the above quesiton On 27 October 2011 07:38, kumar raja rajkumar.cs...@gmail.com wrote: @Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- 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/-/G_0Wm4NQIyIJ. 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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] Searching In a large file
Clearly this is an external sorting question.. Merge sort Can Be Used.. On 10/27/11, shiva@Algo shiv.jays...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9-digit numbers), find a 9-digit number that is not in the file. You have unlimited drive space but only 2megabytes of RAM at your disposal. -- 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] Searching In a large file
I've been working on similar things lately. 1st, if the file is unsorted, you'll have to just go through it, it'll be O(n) worst case, which is preferred rather than sorting it. 2nd if it is sorted, read and store the maximum chunk of the file that you can, a program is allotted 4 GB of address space, out of which in reality may be 3 GB is useable. So an array worth 3 GB, which is roughly ( ( 3 * 1024 * 1024 * 1024 ) / 4 ) 805306368 integer elements ( assuming each number fits in 4 bytes ), do a binary search. If not found, go to the next chunk.. etc On Thu, Oct 27, 2011 at 10:17 PM, Prem Krishna Chettri hprem...@gmail.comwrote: Clearly this is an external sorting question.. Merge sort Can Be Used.. On 10/27/11, shiva@Algo shiv.jays...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9-digit numbers), find a 9-digit number that is not in the file. You have unlimited drive space but only 2megabytes of RAM at your disposal. -- 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. -- Anup Ghatage -- 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: Questions
I guess this is just like finding a word in a matrix On Thu, Oct 27, 2011 at 7:32 PM, SAMMM somnath.nit...@gmail.com wrote: Forgot to mention this was asked in Amazon Interview .. -- 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. -- Anup Ghatage -- 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] FACEBOOK ONLINE CODING ROUND
small typo.. in part 2) it should say 13-(1+4+6)=2. Basically when the position becomes smaller than the element, you stop subtracting. -- 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: Intersection of arrays
Hashing all of the K arrays seems like a bit much. How about this? You have K seperate arrays to start with, each array having N elements (is that correct?). 1) Sort the first array. 2) Step through the 2nd array, 1 element at a time say Array(2).element(i) Check to see if the value of Array(2).element(i) is in the first sorted array. If it is, add this numeric value to your list of intersection elements. As you pass through all elements of the 2nd array, the values found which are intersecting need to be saved ( maybe in the 1st arrays space to save memory). Ideally, these should be saved in sorted order as they are found. ( how you store the sorted array will affect speed of this check of course. I'd keep it simple on the 1st round, then optimize the code once everything appears to be working well, ie with buckets or pointers or whatever. How you determine if an element in array 2 intersects with an element of array 1 will depend on how you store your sorted array. You might do a linear search or a binary search or a bucket search of some sort ). 3) Now... step through the 3rd array, 1 element at a time, looking to see if each value is in the just created list of intersection elements 4) Do the save thing now with each of the remaining original K arrays. Dan:-) On Oct 24, 10:17 pm, kumar raja rajkumar.cs...@gmail.com wrote: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. what data structure is useful here?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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] Searching In a large file
read the question guys, only 2 mb of memory... i would perhaps try to find the range of the numbers... say the range is 300 million here... so i would maintain a count array, count[i]+=1 if on traversing the large file i find a number from chunk i, here chunk can be decided suitably, for example ith chunk means all numbers occuring between 1i and 1(i+1)... (chunk size decided upon the size of the RAM)... then suppose each chunk should have say 5000 elements, so each count should have 5000 elements... suppose the jth count variable has less than 5k elements... so on the nest pass, i will maintain a 1 element bit array, and set correcponding bit to 1 if the number is found in the file... after going through the bit array once, we can find the desired number... -- 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: Searching In a large file
@Shiva: Using an integer array a[10], initialized to 0, read through the file and for each number n, increment a[n%10]. At the end of the file, find any k such that a[k] != 1. Then read through the file again. For any number n such that n%10 == k, set a[n/ 10] = -1. At the end of file, find any j 1 such that a[j] = 0. Then 10 * j + k is a number that is missing from the file. Dave On Oct 27, 10:25 am, shiva@Algo shiv.jays...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9-digit numbers), find a 9-digit number that is not in the file. You have unlimited drive space but only 2megabytes of RAM at your disposal. -- 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: Intersection of arrays
Don, As you said, the intersection set, won't really be in sorted order as it depends on the elements of the second array, which are unsorted. Still, sorting them wouldn't be much different as it'd be worst case O(n logn).. [ Array 2 == Array 1 ] But sorting the First Array has already cost O(n logn) So I guess the worse case complexity has to be O(n logn) anyway.. On Thu, Oct 27, 2011 at 10:54 PM, Dan dant...@aol.com wrote: Hashing all of the K arrays seems like a bit much. How about this? You have K seperate arrays to start with, each array having N elements (is that correct?). 1) Sort the first array. 2) Step through the 2nd array, 1 element at a time say Array(2).element(i) Check to see if the value of Array(2).element(i) is in the first sorted array. If it is, add this numeric value to your list of intersection elements. As you pass through all elements of the 2nd array, the values found which are intersecting need to be saved ( maybe in the 1st arrays space to save memory). Ideally, these should be saved in sorted order as they are found. ( how you store the sorted array will affect speed of this check of course. I'd keep it simple on the 1st round, then optimize the code once everything appears to be working well, ie with buckets or pointers or whatever. How you determine if an element in array 2 intersects with an element of array 1 will depend on how you store your sorted array. You might do a linear search or a binary search or a bucket search of some sort ). 3) Now... step through the 3rd array, 1 element at a time, looking to see if each value is in the just created list of intersection elements 4) Do the save thing now with each of the remaining original K arrays. Dan:-) On Oct 24, 10:17 pm, kumar raja rajkumar.cs...@gmail.com wrote: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. what data structure is useful here?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Anup Ghatage -- 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.
