Find the two numbers whose difference is minimum among the set of numbers. For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19 The algorithm should return min diff = 20-19 = 1. Make an efficient algorithm, yeah best could be O(n). Not sure if i could use DP here, will post a solution tommorow. Let me know if you find a answer. Algorithm:MiniMumDiffN Get the size of array , say n. Get the range of array, range. Bucket Sort the above array. Search the above sorted array for minimum difference. This will be the minimum difference numbers. Now question comes where the range of above given array is very big. Algorithm:DivideArray Take an random element. Search for its position in array. Return the index of element. Algorithm:MiniMumDiff if array_range > MAXRANGE int mid = divideArray (arr,start,end); d1,max1 = MiniMumDiff( arr,start,mid-1); d2,max2 = MiniMumDIff(arr,mid+1,end); d3 = difference max1 and arr[mid] d4 = difference max2 and arr[mid] return minimum( d1,d2
22. No of permutations with n numbers. (1/(n+1)2ncn).
ReplyDeletea) No of permutations are 1/(n+1) (2n)cn.
b) No of stack permutation possible.
c) No of binary trees possible with n nodes.
d) No of ways to parenthesise with n data element.
23. A string with a’s and b’s and with one special character ‘x’. Find out whether its palindrome or not.
a) Take two pointer one from start and another from end. Start comparing till pointers don’t cross each other.
24. Implement queue by stack with enque and deque of order O(1);
Pop all the element and push in second stack2. The top2 will point to the beginning of
Deque and top1 will be at end. Maintain size1 and size2 for the bottom removing with both the cases.
Add at beg: push in stack2, size1 and size2 incremented.
Add at end: push in stack1, size1 and size2 incremented.
Delete at beg: pop in stack2 and decrement size1 and size2.
Delete at end: pop in stack2 and decrement size1 and size2.
25. Convert infix expression to postfix.
While ( ch )
{
If ( ch is alphanumeric ) push (ch);
If ( ch is ‘)’ ) pop from operatorstack and push(ch);
If ( ch is operator) pushoperator(ch);
}