WAP to Calculate nth Prime Number Efficiently

java program

class nth
{

public static void main(String a[])
{
nthfindPrime(5);
}
static void nthfindPrime(int n)
{
int i=0,count=2;
if(n==1)
{
System.out.println("1st prime =2");
return;
}
if(n==2)
{
System.out.println("2nd prime =3");
return;
}

while(true)
{
for(int j=2;j<=i/2;j++)
{
if(i%j==0)
break;
else if(j==i/2)
{
count++;
}
}
if(count==n)
{
System.out.println(n+"th prime ="+i);
break;
}
i++;
}
}
}

Time Complexity O(n)
Space Complexity O(1)

Run Here https://ideone.com/OHmO9


A More Efficient Version

#include
#include
using namespace std;

int main()
{
int i=0,count=2;int n=60;
if(n==1)
{
cout << "1st Prime Number = 2\n";
return 1;
}
if(n==2)
{
cout << "2nd Prime Number = 3\n";
return 2;
}
i=5;
float root2 = sqrt(2);
int limit;
while(true)
{
limit = (int)(i/root2);
for(int j=2;j<=limit;j++)
{
if(i%j==0)
break;
else if(j==i/2)
{
count++;
}
}
if(count==n)
{
cout << n << "th Prime No. : " << i << endl;
break;
}
i++;
}
}

http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

But number of Instruction Reduced
Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/ncfzh

WAP to Convert it to a sorted array with minimum cost. You are given an array of positive integers.

You are given an array of positive integers. Convert it to a sorted
array with minimum cost. Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of
element
For example:
4,3,5,6, -> cost 1
10,3,11,12 -> cost 3


we can make the DP more efficient You don't need to scan the whole previous column when calculating costs of decrementing. Rather there are only two
possibilities.

Algorithm Given By Gene

DP is better for this problem.
Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing
sequence with the last element being no more than m. And we always
draw m from the set V of values in a.
So here is the new DP:
C(1, m) = max(a[1] - m, 0) // first row only decrement is possible
C(n, m) = min (
a[n] + C(n - 1, m), // delete
(a[n] <= m) ? C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement
)
In case you don't follow, the "//delete" line is saying that we
already know the cost of making everything up to element n-1 non-
decreasing and no more than m. This, by recursive assumption, is just
C(n-1,m). The additional cost of deleting a[n] is a[n].
The "//decrement" line is similar, but there are 2 cases. If a[n] is
more than m, we must decrement it. The cost here consists of making
everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m).
Plus we have the cost of chopping a[n] down to m, which is a[n]-m.
In the other case, a[n] is m or less. So there's no need to
decrement, but we must get the elements a[1..n-1] to be no more than
a[n]. Again by recursive assumption this cost is C(n-1,a[n]).
Here is an example. Suppose we have a = [5, 1, 1, 1, 3, 1]. The
least cost here is obtained by decrementing the 5 to 1 (cost 4) and
deleting the final 1 (cost 1) for a total cost of 5.
So let's try the algorithm. (You must view this with a fixed font.)
Table of C(n, m) values:
m = 1 3 5
n = 1 : 4 2 0
n = 2 : 4 3* 1*
n = 3 : 4 4 2*
n = 4 : 4 4 3*
n = 5 : 6m 4 4
n = 6 : 6 5* 5*
Here * means C resulted from decrementing and "m" means that a
decrement was based on the value of m rather than a[n].
We take the answer from C(6,5) = 5.
Implementing this is a little tricky because m values are drawn from
V. You could use a hash table for the m-axis. But it's more
efficient to store V in an array and convert all the values of m in
the DP into indices of V. Because all the indices lie in [ 1 .. |
V| ], we can use simple arrays rather than hash tables to represent
the rows of the table C.
We only need 2 rows at a time, so O(|V|) storage does the job.
For C, we also need to convert all the indices to origin 0.
So here's the final O(n^2) code. I think this is a correct
implementation. If anyone has an example that breaks it, I'd like to
see.
#include
#define NMAX 10000
int cost(int *a, int N)
{
int i, j, max, Nv;
int V[NMAX], A[NMAX], B[NMAX];
int *Cm = A, *Cn = B; // (n-1)'th and n'th rows of C
// Compute set V with no duplicates.
// Remember where max element is.
Nv = max = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < Nv; j++)
if (a[i] == V[j])
break;
if (j == Nv) {
V[Nv++] = a[i];
if (V[j] > V[max])
max = j;
}
a[i] = j; // Convert a to indices.
}
// Fill in first row of C.
for (i = 0; i < Nv; i++)
Cm[i] = (V[a[0]] >= V[i]) ? V[a[0]] - V[i] : 0;
// Fill in the rest of the rows of C.
for (i = 1; i < N; i++) {
for (j = 0; j < Nv; j++) {
int del = Cm[j] + V[a[i]];
int dec = (V[a[i]] <= V[j]) ? Cm[a[i]] : Cm[j] + V[a[i]] - V[j];
Cn[j] = (del < dec) ? del : dec;
}
// Swap row buffers so current becomes previous.
int *tmp = Cn; Cn = Cm; Cm = tmp;
}
return Cm[max];
}

int main(void)
{
static int a[] = { 5, 1, 1, 1, 3, 1 };
printf("Min cost = %d\n", cost(a, sizeof a / sizeof a[0]));
return 0;
}
TC O(N^2)
Sc O(n)
Run Here https://ideone.com/VdsC0

WAP to Find a Word in Dictionary at ith Position Efficiently

If you have a dictionary (sorted list of words) of unknown size and given a function which returns the word in the dictionary at a specified 'i'th location. Suggest an algorithm for finding a word.

We can think of finding the size of dictionary by exponentially getting (2^i)th element (incrementing i each time till the word is lexicographically higher than the given word) and then simply applying binary search from 0 to 2^i.

WAP a Program By Choosing Best Data structure which is supposed to log number of user requests per second.

Make a data structure which is supposed to log number of user requests per second. At any point of time your boss can ask you the number of hits for the last 60 seconds. It can be at any time for example he will say at 71st second that tell me how many hits for past 30 seconds or something, but this window can go maximum upto 60 seconds to in the previous example 11 to 71.

WAP to Generate The Series of Ugly or Lucky Number

Question:Generate The Series of Lucky/Ugly Number or Find the First K Ugly/Lucky Number



eg. 1 2 4 8 10 16 20 25 32 64 100 125 128

Algorithm

Answer: Consider an array of first 10 ugly numbers: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, , , , }

Next ugly number can be calculated by just multiplying one of all these numbers with 2 or 3 or 5.

The least number whose double is not present in the list is 8 (any number before this has its double present in the list). So one of the candidates for next ugly number is 8*2=16

The least number whose multiple by 3 is not present in the list is 5 (any number before this has its multiplied by 3 present in the list). So other candidate for next ugly number is 5*3 = 15.

The least number whose multiple by 5 is not present in the list is 3 (any number before this has its multiplied by 5 present in the list). So other candidate for next ugly number is 3*5 = 15.

Least of these three numbers (15) is our next ugly number.

Now how to choose next ugly number is pretty simple. Since our ugly number is 15 it means now 3*5 and 5*3 are present in the list. So next numbers whose multiple by 3 and 5 respectively are not present in the list are 6 and 4 respectively. The least number whose double is not present in the list remains unchanged at 8. So next candidates are 8*2, 6*3 and 4*5. We will continue in this manner for further list.
Lucky numbers are numbers whose prime factors are just 2, 3, 5. Find the first k lucky numbers.


Algorithm: Keep 3 pointers with you and keep track whose multiple by 2,3 and 5 are present and whose are not. Choose the least number of next candidates and increase the pointer by 1 for the chosen one. If 2 candidates are same, and we chose that number, increment both the pointers as in example above.


#include
#include
using namespace std;
#define k 20 //modify it

int Lucky[k], ptr2, ptr3, ptr5;

int minimum(int x,int y,int z)
{
if (x return (y}

int nextLucky(int num)
{
int num2,num3,num5;
if(num==0)
{
Lucky[num]=1;
ptr2=ptr3=ptr5=0;
return Lucky[num];
}

num2=Lucky[ptr2]*2;
num3=Lucky[ptr3]*3;
num5=Lucky[ptr5]*5;

Lucky[num]=minimum(num2,num3,num5);

if(Lucky[num]==num2) ptr2++;
if(Lucky[num]==num3) ptr3++;
if(Lucky[num]==num5) ptr5++;

return Lucky[num];
}

int main()
{
int i;

for(i=0; i printf("Lucky number no. %d is %d\n", i+1,nextLucky(i));
}

Dynamic Programming
TC O(n)
SC O(n)
Run Here https://ideone.com/B8rCN


Variation
Google Interview Question in different Way:
Given expression E=(2^i * 5^j), increment i and j to ensure the output is sorted.
so above logic will remain same except we need multiples of 2's & 5's thats it

TC O(n)
SC O(n)
Run Here https://ideone.com/M2Bmz

Given integer n decide if it is possible to represent it.SPOJ Prob. 91 as a sum of two squares of integers.

In number theory, Pierre de Fermat's theorem on sums of two squares states that an odd prime p is expressible as
x^2+y^2=c
with x and y integers, if and only if

For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and they can be expressed as sums of two squares in the following ways:

On the other hand, the primes 3, 7, 11, 19, 23 and 31 are all congruent to 3 modulo 4, and none of them can be expressed as the sum of two squares.

More Info http://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares


I used Above Fact to Solve the Question(to Solve SPOJ problem You have to Modify the program )

#include
#include

int isSquare(int c)
{
int a=0;int b=sqrt(c);
if(c%4==1)//remove this to solve spoj probelm
{
while(a<=sqrt(c))
{ int pows=pow(a,2)+pow(b,2);
if(a!=b && pows==c ) //a!=b means 1^1+1^1=2 not allowed
{ printf(" yes Possible \t %d %d ", a,b);
return 1;
}
else if(pows a++;
else b--;

printf( " %d %d %d \n", a,b,pows);
}

}
else
{ printf( "not Possible");
return 0;
}
return 0;
}

int main()
{
printf(" %d ", isSquare(29));
}


TC O(sqrt(n))
SC O(1)
Run Here https://ideone.com/nLGDs

WAP to design an efficient algorithm to find whether String s3 is formed from the interleaving of String s1 and String s2

Design an algorithm to find whether a given string is formed by the
interleaving of two given strings or not.
s1= aabccabc
s2= dbbabc
s3= aabdbbccababcc

If I am Correct a Similer Iterative Approahc can be written as

bool test(A,B,C)
{
i=j=k=0;
while(k < C.size()) { if(i < A.size() && C[k]==A[i]) {i++,k++; } else if(j < B.size() && C[k]==B[j]) { j++,k++; } else return false } return (i == A.size() && j == B.size()); } Similer Recursive Apparoahc in Which Interviewer Show More Interest bool interleaved(char *s1, char *s2, char *s3) { // Base case, all strings are empty return (!s1[0] && !s2[0] && !s3[0]) || // First character of s1 is next in s3 (s1[0] && (s1[0] == s3[0]) && interleaved(s1+1,s2,s3+1)) || // First character of s2 is next in s3 (s2[0] && (s2[0] == s3[0]) && interleaved(s1,s2+1,s3+1)); } No Doubt This Problem Requires DP (Top-Down memozation will be Best )Approach & I had Solved It Using the Same. Below is one of The Possible Approach. I found A Good Discussion Here AlgoGeek


TC O(N) length of Bigger String thats S3 Need to Check
SC O(1)
Run Here http://ideone.com/n6RLc

WAP to Check That Binary Representation of Given Number is Palindrome of NOt

Here i Found an Algorithm for This

Algorithm
take two varible i -0 & j=N (number)
keep storing bits of number from lsb in reverse order (e.g. shift i left & do or operation with j&1 (mind shud click this the way to extract right most set bit from number :)
keep shifting j right while j is not equals to 0

Explaintion

The first while loop reverses the rightmost bits of the number, stopping after the leftmost 1-bit. It does this by anding out the low-order bit of the number j and oring it into a new number, i. Then j is shifted right. E.g., the number j = 01101 becomes 01011. If the number j matches the input number, then the input number is a palindrome, and the procedure returns TRUE. If the reversed number is less than the input number, it may be that the input number has trailing zeros. E.g., 0110 has reversal 0011. Since this is less than the input number, we shift it left until it is no longer less, giving 0110. Since this equals the input number, we call the number a palindrome. If you don't want to consider the leading zeros, then you leave out the second while loop and say that the number 0110 is not a palindrome.


#include

bool isPalindrome(int N)
{
int i = 0, j = N;
while(j)
{
i = (i << 1) | (j & 1); j >>= 1;
}
return(i == N);
}

int main()
{
printf( " %d ", isPalindrome(9));

}


TC O(logn) as You Know that n=logk(base 2)
Sc O(1)
Run Here http://ideone.com/ddovS


Most Optimized Way can Be Find Here http://www-graphics.stanford.edu/~seander/bithacks.html#BitReverseTable in O(1) :)

WAP Search An Element in N-Ary Tree Efficiently

Given an n-ary tree , you have to search for an element in the tree without using recursion.
int FindNum(node *head, int num)
{

}

Note: Review Needed...??

Using BFS is Absolutely Efficient Way to Solve it..kep in Mind Recursion(DFS) is not good because it needs memory stack.

#include
#include
#define MAX_Q_SIZE 500
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node *child[];
   
};
 
/* frunction prototypes */
struct node** createQueue(int *, int *);
void enQueue(struct node **, int *, struct node *);
struct node *deQueue(struct node **, int *);
 
/* Given a binary tree, print its nodes in level order
   using array for implementing queue */
void printLevelOrder(struct node* root,int val)
{
  int rear, front;
  struct node **queue = createQueue(&front, &rear);
  struct node *temp_node = root;
  int i=0;
  while(temp_node)
  {
     if(temp_node->data==val)
printf("item found");
else
printf(" Item DNE");

  i=0;
    /*Enqueue left child */
if(temp_node->child[i])
{
     while(temp_node->child[i)
{
       enQueue(queue, &rear, temp_node->left);
i++;
}
 
    
 
    /*Dequeue node and make it temp_node*/
    temp_node = deQueue(queue, &front);
  }
}
 
/*UTILITY FUNCTIONS*/
struct node** createQueue(int *front, int *rear)
{
  struct node **queue =
   (struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE); 
 
  *front = *rear = 0;
  return queue;
}
 
void enQueue(struct node **queue, int *rear, struct node *new_node)
{
  queue[*rear] = new_node;
  (*rear)++;
}    
 
struct node *deQueue(struct node **queue, int *front)
{
  (*front)++;
  return queue[*front - 1];
}    
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
 
  return(node);
}
 
/* Driver program to test above functions*/
int main()
{
  struct node *root = newNode(11);
int i=0,j=0;int k=1;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
   root->child[i]= newNode(k);
k++;
}
k++;
root=root->child[i];
}
  
  printf("Level Order traversal of binary tree is \n");
  printLevelOrder(root);
 
  getchar();
  return 0;
}

TC O(nlogn)
SC O(1)
Run Here

WAP to convert a given string to its palindrome string by appending min chars at the right side of string.

Example
e.g. i/p is abc , o/p should be abcba
i/p is aaba , o/p should be aabaa.

aaba is not a palindrome

aaaa is a palindorme (so it does not require anything)

aabaa is also a palindrome (so it does not require anything)

Example 1:
-------------
str = abcbad;
revStr = dabcba;
output = abcbadabcba

Example 2:
----------------
str = abcb;
revStr = bcba;
output = abcba;

Ecample 3
str = rrrr
revstr=rrrr
output=rrrr