## The Artist

BAN USERi'll rather maintain two trie (1 for all known nouns and other for all known verbs) and then read character by character out of the book breaking at each space to check in the trie for a match

- The Artist July 09, 2013nice search jagat....finally a valid explanation

- The Artist January 17, 2013the solution may work but the explanation is wrong...try with [12,8,12,12] and check what happens at all the five step in the second iteration

- The Artist January 01, 2013it will only work if the lone number was 0, 1, or 2..mod 3 of any number wull be either of those 3 values

- The Artist December 31, 2012the solution might work if the bitwise operators are doing what the logic above says it is doing but the explanation of the 5 statements given above is totally wrong...for instance how is ones & x = ones when x appears the first time? for example if the array was of the form 12,8,.....and current value of x was 8 then ones = 12 and 12 & 8 = 8 and then 12 ^ 8 = 4 then not_three will become 2^32-1 (all 1) and the next two steps lets ones and two unchanged....this analysis at least proves that it is not at every iteration that ones and twos will hold the xor's of the elements till that time that has apperared once or twice? do let me know if something is wrong in my analysis...

- The Artist December 31, 2012@DashDash: although the question doesn't mentions it, it is implied that the stack property (LIFO) should not be lost.

- The Artist December 31, 2012logic is simple: any element can be selected as root. once you select a root you will have to put the left of it to the left child and right of it to the right child recursively. for [1,2, 3] case below is how the five BST gets created. (represents the order of insertion to the BST)

1. 1->2->3

2. 1->3->2

3. 2->1->3 or 2->3->1 (generates the same BST)

4. 3->1->2

5. 3->2->1

@juny: i don't think there's a concept of HashMap in C#. Dictionary is a close match in which if you try to add two entries with the same key, it throws an exception. you need to first check the dictionary using the ContainsKey() method

- The Artist December 28, 2012if seeking attention is your intent behind all your fuss over nothing, then you are at the wrong forum buddy

- The Artist December 28, 2012@cobra: you are absolutely right. had the same doubt. funny that the people have come up with solutions to a question that doesn't sound at all right

- The Artist December 28, 2012now you are just trying to make yourself feel good by arguing on unimportant points. number of upvoting of Mike's solution is a proof enough for his ingenuity specially for the second part. i would have walked out of the interviewer if the interviewer argued the way you are doing. Looking back at all your comment i am damn sure that until yesterday you didn't even know about Count Sort. Looking at youur comment about the O(n) extra space makes you look even more stupid. sweetie there's nothing wrong in accepting the fact that you did not know something and someone else helped you learn it. demeaning/destroyin someone's work would not make you greater than the creator of that work.

- The Artist December 28, 2012But yes you are sweetie...the knowledge of "Count Sort" :P

- The Artist December 27, 2012one thing that can be done is update all the threads of the database update using asynchronous event notifications and handling...generally large applications uses something like a MVC design...even there might not be a UI, you can use similar kind of architecture where the database interaction is done through a seperate Singeleton thread altogether.

- The Artist December 22, 2012i wish the question was that simple but i think what the interviewer wants here is that you are given a fixed chunk of memory (say some byte array) from which you need to allocate memory chunks when malloc is called.

- The Artist December 22, 2012Yes, you are right. I was just pulling legs :P sorry about that. Even if m = n then O(m+n) = O(2n) = O(n) and therefore there ain't any difference between O(m+n) or O(max(m,n)) as m, n tends to infinity

- The Artist December 22, 2012Shouldn't we be writing the complexity as O(m+n) :)

- The Artist December 21, 2012if what you say is what it is required then below is what i'll do:

1. Assign coordinate (0,0) to the root node.

2. If the coordinate of a node is (x,y) then its left child should have a coordinate (x-1,y+1) and right child should have (x+1,y+1)

3. Recurse through the tree assigning coordinate to each node and also maintaining a hash table with x values as key and a linked list of nodes with that values of x as value. When you reach the leaf node the hash table values are the required link list. Instead of hash tabke an array of linked list can be used where array index will define the value of x.

@BoredCoder: small correction in ur pseudo code. the first line should be:

list *curr = slist->next;

Nice one Mario, it is better than my solution and Kamy you are right if we ignore the call stack memory consumption in will be O(1) space algorithm but even if we consider the call stack memory the worse case memory will be 2*log(n) when recursing through a leaf node (for a balanced tree assuming the 2 int params of max and min) which makes it O(log n) space still better than inorder traversal for all n > 2, But even this can be reduced by senfing the pointers to the actual min node and max node rather than the data in it.

- The Artist December 18, 2012if a binary tree is a bst, an inorder traversal should return a sorted array...O(n) in both space and time...let me think if i can find something better

- The Artist December 16, 2012i too don't think that it is possible to do it in O(log n) time

- The Artist December 16, 2012imagine child_nodes as an array of node and child_counts to be the length of that array so you can refer to the ith child as child_nodes[i-1] something similar to a two dimension array which is nothing but array of arrays

- The Artist December 16, 2012@suvrokrov: oh really? and i thought there are couple of algorithms available that can sort the entire list in O(nlogn) time

- The Artist December 16, 2012@suvrokrov: really so according to you (2,2) and (3,1) are equidistant from origin?

- The Artist December 16, 2012@kori: yes of course...if the next point is greater than root just discard it and whenever you delete the root you need to reheapify the heap...every delete and insert operation on a heap is O(log n) operation

- The Artist December 16, 2012@avikodak: do you really think that the two solutions you gave above are different? if you still think so then can you please let me know (through pseudo code) as to how will you implement your solution 2 with an already existing structure which doesn't have a visited bool flag?

- The Artist December 16, 2012excellent inference jk...so now you are sitting infront of the interviewer and you gave your simple solution to him and he asks a follow on question with a partially looped linked list (basically a rho shaped list which is possible and i hope you are not having any difficulty imagining that). can you please give a similar simple solution to that?

- The Artist December 16, 2012no energy to try to understand your logic but since you are doing something with the reverse of a word i seriously think that you need to first find out the meaning of Anagrams

- The Artist December 14, 2012basically what Nueman Fernandez above is suggesting is to apply apply the tortoise and hare algorithm generally used to find the entry point of a rho shaped finite set function

- The Artist December 14, 2012in c this will be your datastructure: node{int val; node* child_nodes; int child_count} and use DFS for cycle detection

- The Artist December 14, 2012a simple nlogn solution will be do a inorder traversal of the tree...at every node calculate val = node.value - k(given number) and do a binary search for val from the root node if node.value < val or from the current node if node.value > val

we can initially find out the max and min values in the tree to increase the efficiency further by using the max or min value to identify whether its worth going to the left or right child of a given node

excellent question visitor...i wish comments to comment can be +1'd

- The Artist December 14, 2012did not have energy to go through your logic but hope you considered that the tree may have negative numbers...

- The Artist December 14, 2012not a good solution...has O(n^2 complexity)...you need to take advantage of the fact that its a BST or that the array you created after inorder traversal is sorted.

- The Artist December 14, 2012well the hash code that i gave as an example is actually count sort and on second though i think you can use count sort (an O(n) algorithm if you know that the letters are only english alphabets

- The Artist December 13, 2012we don't even need to sort the words, we can create a hash code with the alphabets count in a word then use that as the key...it will reduce the complexity to O(n x) rather than O(n x logx). A simple example of such a hash code can be for cat = a1c1t1 bat = a1b1t1 act = a1c1t1 tac = a1c1t1 and so on

- The Artist December 13, 2012how about using a datastructure Node {int value; int indexOfNextElement} as array element and then having three index references, one each for each stack pointing to the position of top element of each stack....adding a new element will simply be at the array index equal to the sum of number of elements in the three stacks or simply max of the top position of the three stack + 1

- The Artist December 13, 2012unfortunately that is not the case

- The Artist December 10, 2012@Lyubomir: 2 minutes max...the question is a rephrase of the general question of k min (or max) elements in a N size array

- The Artist December 07, 2012a max heap of size 100 would be a better design in terms of time complexity

- The Artist December 07, 2012ok...got it. i didn'tha quite understand earlier what you were trying to minimizing with that min statement

- The Artist November 28, 2012if you call the summed array as S then you will have to find 2 points (x1,y1) and (x2,y2) such that S[x1][y1] + S[x2][y2] - S[x1][y2] - S[x2][y1] = 0 and (x1 - x2)*(y1 -y2) is maximum for 0 <= x < m, 0 <= y < n. Even in that case you will have to consider the cases when x1 = x2 or y1 = y2 seperately (this corresponds to the case when the output array is a 1 D array). If you really try to do all this, it will become a O((mn)^2) algorithm again.

- The Artist November 28, 2012Two points here:

1. you are trying to return min of something, I can see one of the element, don't know what's second

2. most probably will go into an infinite loop (will leave it to you to find why)

ha ha...i did not quite get it either...i think he is looking for an interface functionality or something...

- The Artist November 28, 2012Google it. You will find the answer.````

- The Artist November 27, 2012do not quite understand what you want to do when you say make nC2 combinations of rows and sum them up? can you please elaborate a little?

- The Artist November 27, 2012use interfaces

- The Artist November 27, 2012Me too

- The Artist November 27, 2012i think the customer specified properly but the bussiness analyst is incompetent as he can't clearly restate the problem statement :P

- The Artist November 27, 2012**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

how about using already existing infrastructures like log4j in java and windows Trace in .NET

- The Artist January 07, 2014