Viraj Shah
BAN USEROne condition for the above to work is that the value stored instead of the missing variable should be 0.
- Viraj Shah January 27, 2015Anyone ?
- Viraj Shah December 31, 2014@Rahul
generating the array is as simple as
newArr[i]=newArr[i-1]*arr[i];
So yes, it is O(n).
Pseudo Code:
1. Create a vector<vector<int> > levelorder,2 queues of queue<Node*> q1 and q2, counter=0
2. Add NULL pointer to q1.
3. while q1 and q2 are not empty
while(q1 not empty)
current=dequeue a pointer from the q1
iterate over the nodes in the list to find a node which has a parent as current.
add the element to the q2 and vector
increment counter.
push vector to levelorder
q1=q2; clear q2.
4. print out the vectors in round robin fashion with required output spacing.
Time Complexity: O(n*n)
Space complexity: O(n)
where n is the number of nodes in the input.
This is a brute force solution. I am sure there must a better solution to this problem.
- Viraj Shah August 19, 2014
How about a min_heap of size k ? If we come across an element greater than the top of the heap, remove top, add new element to heap, and heapify. So the top of the heap will have the kth highest price.
- Viraj Shah February 10, 2015