Daniel Johnson
BAN USERI am coder
- 1of 0 votes
Answersvoid groupThatEquals( int total, int groupSize, int[] numbers )
- Daniel Johnson
This is a prototype of the function where number is given an array of ints, total is given as a number and groupsize is also given as parameter.
For example, an array of numbers is 3,4,16,2,13,8,5,7,2,9
Suppose Total= 28, groupSize = 3
So we have to come up with a group size of 3 in this example whose sum will be equal to 28. In this case it is 3,16 and 9 which makes total = 28. Array is not sorted and number need not be contiguous.
We have to find all possible groups that sum to Total.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
Very nice solution.
- Daniel Johnson February 28, 2008Hi Vairaghi,
It looks like you had an onsite Amazon Interview. Can you share your experience. I also have one in 2 weeks time in Seattle. Any helpful tips will be greatly appreciated.
Thanks in advance.
In my opinion the solution should go like this:
Search rowise first:
start looking for element in Row=0 and as soon as you find two columns, one which is less than your SEARCH number and one which has higher than your SEARCH number. So we can look for our number in these 3 columns, which is worst case would give us a running time of 3N i.e. O(N).
Please correct me if I am wrong or if you have any other interesting solution.
was it onsite or telephonic ?
- Daniel Johnson February 14, 2008It is too general....I guess a better solution should check all the cases.
- Daniel Johnson February 14, 2008I completely agree with this solution.
- Daniel Johnson February 11, 2008How about using linked list and hash map together ? i.e. a linked list to enqueue in O(1) time and while dequeing, find the element in O(1) time using hash map which has the address of the lined list and address of node. You delete the node in O(1) time.
So essentially we can have both the operations in constant time.
Please correct me if I am wrong. Your comments are appreciated.
An elegant solution, I would say...
- Daniel Johnson February 11, 2008Is there a way we can indent the code in career cup ?
- Daniel Johnson February 10, 2008XORing is an excellent idea and operations at bit level are faster, so they solution is as elegant as it gets.
- Daniel Johnson February 09, 2008Onsite. Can you help with the solution ?
- Daniel Johnson February 08, 2008first of all, a sorted DLL is asked so you must use inorder traversal.
If you do an inorder traversal and arrange left and right pointers of child as left and right element in a DLL you can convert it to an DLL. Only thing is that you must do a iterative Inorder traversal rather than recursive one.
I hope you get the solution.
it will be worthwhile to provide an insight as to how grep is written ?
Using readymade function is not the best idea in such interviews.
The question is how do you move up the tree
- Daniel Johnson February 08, 2008This is an intelligent solution.
In any connected graph if you have Number of edges>= Number of Nodes then there is a tree.
Now it remains how to find number of nodes and edges. DFS seems to be a good choice.
How about huffman coding ?
- Daniel Johnson February 08, 2008B+ sorting is surely a possible solution we can look for.
I could think of external sort...Any comments ?
so what is going to be the index and value in the hast table ?
Is it going to be as follows..where you hash the index and store index and pointer. Please correct me if I am wrong ?
Key: Value == Index : Pointer
Thanks.
Can you please tell how to create the tree.
By using inorder and preorder tree traversal can be re-created. I was trying to write a recursive as well as non recursive algorithm for it but I am stuck on it.
The prototype is
btreenode* create_binary_tree(char *inorder, char *preorder, int length)
where length is the length of the string when contents of binary tree are written in sequential fashion.
btreenode is as follows
typedef struct btreenode{
struct btreenore *left;
char data;
struct btreenode *right;
}
Can you help me with the solution. I know that this can be done using divide and conquer by assigning the first element of the preorder to be root. then looking for root node content in inorder string. All elements left of root are in the left sub tree and all elements after root are in right subtree. You then recursively go on to build the tree. But unforutnately I was unable to get a working solution for it.
Everybody asks the questions when it is there turn for an interview but after interview they don't help forum members with their questions. Is that fair ?
I appreciate the work of all the members who post their questions for other to succeed.
My approach would be
function FindFirstCommonElement()
len 1 = length of first linked list (traverse it all the way to find it)
len 2 = length of second linked list (traverse it all the way to find it)
diff = len1 - len2 (absolute difference of their lengths)
if (diff >= 0)
{
for i = 1 to diff{
head1 = head1->next;
}
}else{
for i = 1 to |diff|{
head2 = head2->next;
}
}
while (head1->next != head2->next){
head1 = head1->next
head2 = head2->next
}
return (head1->next)
Can somebody post the pusedo code instead of C Code ?
- Daniel Johnson October 17, 2007
Repjosiredhima, AT&T Customer service email at Aricent
I am an architect with three years experience planning and designing commercial buildings. I am working as principal architect on ...
Repsusanaminick, Research Scientist at CapitalIQ
I am Susan from Dallas, I am working as a Property manager in Kohl's Food Stores company. I love ...
Repmelissattaylor, AT&T Customer service email at Bankbazaar
Je suis membre participant du chapitre de Virginie de l'Association nationale du travail social. J'aime lire et écrire ...
Khoa,
- Daniel Johnson March 02, 2008You have posted way too many questions. Do you just put questions to generate discussion or were they really microsoft or amazon questions ?
I personally think that lot of your questions are just to generate discussion and if you put them as Microsoft or Amazon questions, the likelihood of other people taking part is high. Its a good tactics you are employing but you must be truthful at the same time.