Wednesday, August 24, 2011

Write a method to count the number of 2s between 0 and n.

#include <stdio.h>
#include <string.h>
#define NUMBER 1
main ()
{
/*This program calculates the number of 2's present in the number x*/

int arr[]={221};
int i=0,count=0;

for(i=0;i<NUMBER;i++)
{
while(arr[i]>0)
{
int rem,quo;
rem=arr[i]%10;
quo=arr[i]/10;
printf("rem= %d and quo=%d \n ", rem,quo);
if(rem==2&&quo==2)
{
count=count+2;

printf("Number is : %d\n",arr[i]);
arr[i]=arr[i]/10;

}
else if(rem==2)
{
count++;
printf("Number is : %d\n",arr[i]);
}
else if(quo==2)
{
count++;
printf("Number is : %d\n",arr[i]);
arr[i]=arr[i]/10;
}
arr[i]=arr[i]/10;
}
}
printf("THe number of 2's are : %d\n",count);
printf("\n\n\n");
}

Run Here http://ideone.com/JUnXva

Design an algorithm that takes strings S and r and returns if r matches s. (Assume r is a well-formed regular expression.)

Before starting solving we need to think about some test cases  like .,*,?,^,$  e.g about a regular expression grammar.

A regular expression is a sequence of characters that defines a set of
matching strings.For this problem , we define a simple subset of a full
regular expression Language.

Alphabetical and numerical characters match themselves. 
 1.For example aW9 will match that string of 3 letters wherever it appears.
The meta-characters ". and $ stand for the beginning and end of the
string. For example, .....aW9 matches aW9 only at the start of a string
aW9$ matches aW9 only at the end of a string, and ^aW9$ matches a string only if it is exactly equal to aW9.

2.The metacharacter . matches any single character. For example,
a.9 matches a89 and xyaW9123 but not aw89.

3.The metacharacter * specifies a repetition of the single previous
period or a literal character. For example,a. *9 matches aw89.
By definition, regular expression r matches string s if s contains a
substring starting at any position matching r. For example, aW9 and a. 9
match string xyaW9123 but .....aW9 does not.

Algorithm:
The key to solving this problem is using recursion effectively.
If the regular expression r starts with "', then s must match the remainder of r; otherwise, s must match r at some position.
Call the function that checks whether a string S matches r from
the beginning matchHere. This function has to check several cases
(1.) Iength-O regular expressions which match everything, 
(2.) a regular expression starting with a *match, 
(3.) the regular expression $,and 
(4.) a regular expression starting with an alphanumeric character or dot.
Of these, (1.) and (3.) are base cases, (4.) is a check followed by a call
to matchHere, and (3.) requires a new matchStar function.

More Info http://swtch.com/~rsc/regexp/regexp1.html


Given a BST and a number, Find the closest node to that number in the BST. Give an algorithm for that. Let there be binary search tree having nodes with values 12,34,64,23,64,25,76,6 and the number given is 28, then the answer would be 25 as it is the closest node.

We Have to Solve It Efficiently O(Logn) is Desired :)

Given a BST and a number, Find the closest node to that number in the BST. Give an algorithm for that. Let there be binary search tree having nodes with values 12,34,64,23,64,25,76,6 and the number given is 28, then the answer would be 25 as it is the closest node.


Given a BST and a number, Find the closest node to that number in the BST. Give an algorithm for that. Let there be binary search tree having nodes with values 12,34,64,23,64,25,76,6 and the number given is 28, then the answer would be 25 as it is the closest node.


Given a class Card{int value, int suit, Color color}, Write a method Card[] GetUniqueElements(Card[] cards) which gives all the unique Card Objects .

For Example  (1,1,R), (1,2,G), (1,1,R), (2,2,R), (2,2,B) where parameters are ( card value, card suit, card color) respectively where R=1 & G=2 &B=3 (card color) etc.

Answer should be (1,1,R),(1,1,R), (2,2,R), (2,2,B)

Write a function to find the longest common prefix string amongst an array of strings



Simple Algorithm Will Go Like This:
Algorithm:Longest Common Prefix ( LCP)
1.Take a String From Array Whose length is Minimum else
  you might get exception if tries to access array element
  outside range.why this will work because if there exist 
  a common prefix then it will be the desired answer .
 Example like in case of "shash" ,"shank","shashank" LCP will be "sha"
 for this string "ab", "abc", "def" ,"defgh", "sha" LCP will be NULL
2.Keep Comparing reamining string character by character with 1st selected string  if mismatch occurs at any position i then append 1st string to output string.

Working Code
String findLongPrefix(String [] str) 
{
                StringBuilder strBuilder = new StringBuilder();
                
                char [] firstStr = str[0].toCharArray();
                for(int i=0; i< str[0].length(); i++ ) {
                        boolean found = true;
                        for(String str: str) {
                                if(str.charAt(i) != firstStr[i]) {
                                        found = false;
                                        break;
                                } 
                        }
                        
                        if(found) {
                                strBuilder.append(firstStr[i]);
                        } else 
                                break;
                        
                }
                
                return strBuilder.toString();
        }

Time Complexity O(N*M-1)=O( Where N is Length of 1st Smallest String 
and M is Number of remaining string in string array so it will run
upto length of array-1
Space Complexity O(1)

Tuesday, August 23, 2011

Write a function int interval_unfold_count(int n); that returns the length of the shortest sequence of operations resulting in either L or R being equal to N.

Two integer variables L and R are initially equal to 0 and 1 respectively (i.e. L = 0 and R = 1).
The values of these variables can be manipulated using the following operations: operation 'L' is the assignment L = 2*L-R, operation 'R' is the assignment R = 2*R-L.
Given an integer N we want to find what is the shortest sequence of such operations necessary to make either L or R equal to N. For example, given N = 21, the following sequence of operations:
(initially L = 0, R = 1),
L = 2*L-R (makes L = -1, R = 1),
L = 2*L-R (makes L = -3, R = 1),
R = 2*R-L (makes L = -3, R = 5),
L = 2*L-R (makes L = -11, R = 5),
R = 2*R-L (makes L = -11, R = 21)
makes one of the variables (namely R) equal to N (i.e. after the last operation N = R = 21). This sequence consists of 5 operations and there is no shorter sequence that would make either L or R equal 21.
Write a function int interval_unfold_count(int n);
that returns the length of the shortest sequence of operations resulting in either L or R being equal to N. For example, given N = 21 the function should return 5.

A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?
(a) A heap can be used but not a balanced binary search tree
(b) A balanced binary search tree can be used but not a heap
(c) Both balanced binary search tree and heap can be used
(d) Neither balanced binary search tree nor heap can be used
 
A self-balancing balancing binary search tree(Its *BST not BT )* containing 
n items allows the lookup, insertion, and removal of an item in O(log n) 
worst-case time. Since it’s a BST, we can easily find out minimum element 
in O(nlogn). please note that if it would have been simple BST not Balnced
BST then our complexity to lookup will changes to O(n) in worst case when
tree is skewed but as question say balanced BST (check out AVL/RB Tree) they 
gureentte that look-up will O(logn) only why its true & will work you need 
to go through tree rotation (thats used to make tree balanced & reduce 
height ).

Since Heap is a balanced binary tree (or almost complete binary tree but not 
balanced BST ), insertion complexity for heap is O(logn). Also complexity to 
get minimum in a min heap is O(logn) because removal of root node causes a 
call to Heapify (after removing the first element from the array) to maintain
the heap tree property. But a heap cannot be used for the above purpose as 
the question says – insert an element if it is not already present because of 
this constraint we can't use min-heap as well . For a heap, we cannot find out
in O(logn) if an element is present or not as its balanced Binary Tree(BT) , 
we have to search all the elements e.g.in both  left & right sub-tree up-to 
leaf so in worst case it will take O(n) time to search an element weather 
ist present or not , then its present leave it  else insert as a last node & 
call heapify (take O(logn)) so tottal time complexity will be O(n)+ O(logn) 
=O(n) 

      search+heapify =O(search) 

so why correct answer is only Balanced Binary Search Tree