Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”
Note: Review Needed
First, let’s start off by asking ourselves what a non-integer number in binary looks like. By analogy to a decimal number, the number n = 0.101 = 1 * (1/2^1) + 0 * (1/2^2) + 1 * (1/2^3).
Printing the int part of n is straight-forward (see below). To print the decimal part, we can multiply by 2 and check if the 2*n is greater than or equal to one. This is essentially “shifting” the fractional sum. That is:
r = 2*n = 2*0.101 = 1*(1 / 2^0) + 0*(1 / 2^1) + 1*(1 / 2^2) = 1.01
If r >= 1, then we know that n had a 1 right after the decimal point. By doing this continuously,we can check every digit.
class digit_prob
{
public static String printBinary(String n)
{
int intPart = Integer.parseInt(n.substring(0, n.indexOf('.')));
double decPart = Double.parseDouble(
n.substring(n.indexOf('.'), n.length()));
String int_string ="";
while (intPart > 0) {
int r = intPart % 2;
intPart >>= 1;
int_string = r + int_string;
}
StringBuffer dec_string = new StringBuffer();
while (decPart > 0) {
if (dec_string.length() > 32) return "ERROR";
if (decPart == 1) {
dec_string.append((int)decPart);
break;
}
double r = decPart * 2;
if (r >= 1) {
dec_string.append(1);
decPart = r - 1;
} else {
dec_string.append(0);
decPart = r;
}
}
return int_string + "." + dec_string.toString();
}
public static void main(String a[])
{
System.out.println(printBinary("3.5"));
}
}
TC O(K) k= length of number e.g digits in number
SC O(1)
Run Here https://ideone.com/7yjsH
Friday, May 27, 2011
WAP to Find a String in Sorted Array of String " Containing Large number of empty Strings in it Efficiently....Think of O(logn) ??
Given a sorted array of strings which is interspersed with empty strings, write a method
to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
TC O(n) when all array having empty string the 1st inner loop will run n time
SC O(1)
Run Here https://ideone.com/f9FcL
to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
class stringSearch
{
public static int search(String[] strings, String str,
int first, int last) { while (first <= last) { // Ensure there is something at the end while (first <= last && strings[last] =="") { --last; } if (last < first) { return -1;
// this block was empty, so fail } int mid = (last + first) >> 1; while (strings[mid] =="") { ++mid;
// will always find one } int r = strings[mid].compareTo(str); if (r == 0) return mid; if (r < 0) { first = mid + 1; } else { last = mid - 1; } } return -1; } public static int search(String[] strings, String str) { if (strings == null || str == null) return -1; if (str =="") { for (int i = 0; i < strings.length; i++) { if (strings[i] == "") return i; } return -1; } return search(strings, str, 0, strings.length - 1); } public static void main(String a[]) { String str_arr[]=new String[]{"at", "", "", "",
"ball", "", "", "car", "", "", "dad", "", ""}; String str="ball"; System.out.println(search(str_arr,str)); } }
TC O(n) when all array having empty string the 1st inner loop will run n time
SC O(1)
Run Here https://ideone.com/f9FcL
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
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++;
}
}
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
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.
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
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
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
}
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
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
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
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
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
Wednesday, May 25, 2011
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) :)
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) :)
Subscribe to:
Posts
(
Atom
)
