## havefun

BAN USERHere is how it works with an example:

List: 9->5->7

9 random points to Null

5 random points to 7

7 random points to 9.

After loop1 list:

9->9->5->5->7->7.

New duplicate nodes added after each original node. We also found smallNode, i.e. 5 in this loop. Only next pointer is set for new nodes.

After loop2:

startWith small Node and assign the random pointer for new Nodes.

9->9->5->5->7->7.

After loop3:

Now we have two a list with duplicate values. separate them into two lists.

9->5->7

9->5->7.

Hope this works:)

Here is my approach:

loop1:

temp = smallNode = head;

while(temp != null)

{

if(temp->data < smallNode.data)

{smallNode = temp;}

newNode = getNewNode();

newNode->data = temp->data;

nextNode = temp->next;

temp->next = newNode;

newNode->next = nextNode;

temp = nextNode;

}

loop2:

temp = smallNode;

while(temp->random != null)

{

temp->next->random = temp->random->next;

temp = temp->random;

}

temp->next->random = null;

loop3:

replicateHead = head->next;

temp = head;

replicate = replicateHead;

while(temp != null)

{

temp->next = replicate->next;

if(temp->next != null)

{replicate->next = temp->next->next;}

else

{replicate->next = null;}

temp = temp->next;

replicate = replicate->next;

}

Complexity: O(3N), O(1) space.

Let's construct a matrix as follows:

C(i,(i+1) % n) = Ci - Di for all 0 <= i <= n - 1 (zero based index)

C(i, (i+k) % n) = Sum (C(j, j+1 % n)) for all i <= j < k & for all 2 <= k <= n

Solution is to that find 'i' such that c(i,i) is maximum.

Complexity: O(n^2). Space O(n^2) for remembering the previously computed values.

It only guarantees the values of children are as large/small as it's parent node. Does not guarantee all nodes in next are as large/small as previous level. Suppose in a max heap of 7 elements 30, 10, 20, 5, 6, 18, 19.... you don't know the relation b/w 10 & 18/19 and also b/w 20 & 5/6.

- havefun December 21, 2012instead of two for loops we can use BST property to reduce the complexity to nlogn...

Something like this,

i = 1; j = n;

mid = (i + j)/2;

while( i < j){

value = sum - a[i];

search the array for "value" using the BST property and if found set j to this particular location(print these values) / if not found set it to the location that just greater then value.

increment i;

}

This will run O(nlogn) & space O(n).

Here is the Java code:

public class PrintTriangle {

public static void main(String[] args) {

int i,j,k,l = 0,n;

n = 10;

for( i = 1; i<= n; i++){

k = n - (i - 1);

l = 1;

for ( j = 1; j <= 2 * n - 1; j++){

if (l <= i && j == k){

System.out.print(i + "\t");

k = k + 2;

l++ ;

}

else

System.out.print("*\t");

}

System.out.println();

}

}

}

Hold on guys,

@ML, didn't see the assumption? Only one Bolt is > all the nuts. So In this case if all the nuts are exhausted then the present Bolt is the biggest of all. Further, if there are more then one bolt that is bigger then all nuts, I am sure you don't have an answer of finding the biggest bolt.

@hprem91, it's heaven O(B+N) lol..(this is worst case, avg case might be less than that).......here is the reason why, you won't run either step 3/4 for O(B)/O(N) times...as you are throwing away the nuts/bolts once they fail the condition. Worst case can happen only when the Biggest Bolt you are taking out is the last Bolt in the bag. This takes O(B + N).

Here is the approach:

1) Take a Bolt B.

2) Take a Nut N.

3) while(more nuts && B >= N) {

Throw away this nut & take next Nut N;

}

if(no more nuts)

Print B.

4) while(N > B){

Throw away this Bolt and get next Bolt B;

}

go to Step 3.

Complexity: O(B + N).

Assumption: There is only one Bolt which is > all nuts.

Let's initialize the Inputstream pointers "prev", "now" both of them point to first character.

1) Keep reading the words from the stream as long as they fit in half of the memory.

2) Reverse the whole string in main memory & reverse each word again.

3) write them back to the stream starting from prev.

4) Repeat the process until entire file is processed.

Now we have chunks of string that has the words which are reversed and can fit in half of memory.

Reset Now, Prev to point at the staring again.

Introduce Present.

0) Prev = Present.

1) First half of memory: Now read the half chunk of stream chunk into memory staring from Present. Now = Present.

2) Second half of memory: Read another half chunk of stream starting from Now.

3) Swap the contents of first half & second half.

4) Write back to the stream starting from Prev.

Repeat this process for each half chunk. This will solve the issue without any additional memory.

Rep**paynealiciam**, Apple Phone Number available 24/7 for our Customers at Adap.tvHello I am Sarah Cote, and I live in Missouri, USA. Last year, Web trailblazer. Passionate entrepreneur. Subtly charming bacon ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Construction of Optimal BST's using DP.

- havefun January 04, 2013h t t p://en.wikipedia.org/wiki/Binary_search_tree#Optimal_binary_search_trees