k distinct integers [0, N) Select a random no [0,N) which is not in this k distinct list. Example: [4, 6, 9] Choose a random no between 0 - 9 which is not 4, or 6, or 9. Valid output: 2 Invalid output: 6

k distinct integers [0, N) Select a random no [0,N) which is not in this k distinct list. Example: [4, 6, 9] Choose a random no between 0 - 9 which is not 4, or 6, or 9. Valid output: 2 Invalid output: 6

You're given a string, and you want to split it into as few strings as possible such that each string is a palindrome.

A Good Discussion I Found here on The Same


https://groups.google.com/forum/#!topic/algogeeks/hUh_jRv8Ij8
https://groups.google.com/forum/#!topic/algogeeks/EQZFLZ4P3IA

How to generate random integer between A and B, using an unbiased coin. For ex. If A = 3 and B = 6 then your algorithm should generate 3, 4, 5, 6 with equal probabilities.

My Design Problem - 1 , A Man & Party Puzzle!!!! Tough One

A Man is Going to Party on Infinite length Road,So It Clear That You Don't know the starting point , ending point or length of the road he can start from any point in infinite length road & went to party & then came out from party,but her forgot where he parked the Car, Write an Efficient Algorithm that can solve his problem to find out the Car. Explain What data Structures You Will Use ?

Implement 3 Stack Using Single Array Efficiently

Approach 1:(Naive)
Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: “[“ means inclusive, while “(“ means exclusive of the end point).
»»for stack 1, we will use [0, n/3)
»»for stack 2, we will use [n/3, 2n/3)
»»for stack 3, we will use [2n/3, n)

This solution is based on the assumption that we do not have any extra information about the usage of space by individual stacks and that we can’t either modify or use any extra space. With these constraints, we are left with no other choice but to divide equally.
int stackSize = 300;
int[] buffer = new int [stackSize * 3];
int[] stackPointer = {0, 0, 0}; // stack pointers to track top elem

void push(int stackNum, int value) {
/* Find the index of the top element in the array + 1, and
* increment the stack pointer */
int index = stackNum * stackSize + stackPointer[stackNum] + 1;
stackPointer[stackNum]++;
buffer[index] = value;
}

int pop(int stackNum) {
int index = stackNum * stackSize + stackPointer[stackNum];
stackPointer[stackNum]--;
int value = buffer[index];
buffer[index]=0;
return value;
}

int peek(int stackNum) {
int index = stackNum * stackSize + stackPointer[stackNum];
return buffer[index];
}

boolean isEmpty(int stackNum) {
return stackPointer[stackNum] == stackNum*stackSize;
}

Approach 2:

In this approach, any stack can grow as long as there is any free space in the array.

We sequentially allocate space to the stacks and we link new blocks to the previous block. This means any new element in a stack keeps a pointer to the previous top element of that particular stack.
In this implementation, we face a problem of unused space. For example, if a stack deletes some of its elements, the deleted elements may not necessarily appear at the end of the array.
So, in that case, we would not be able to use those newly freed spaces.
To overcome this deficiency, we can maintain a free list and the whole array space would be given initially to the free list. For every insertion, we would delete an entry from the free list. In case of deletion, we would simply add the index of the free cell to the free list.
In this implementation we would be able to have flexibility in terms of variable pace utilization
but we would need to increase the space complexity.
int stackSize = 300;
int indexUsed = 0;
int[] stackPointer = {-1,-1,-1};
StackNode[] buffer = new StackNode[stackSize * 3];
void push(int stackNum, int value) {
int lastIndex = stackPointer[stackNum];
stackPointer[stackNum] = indexUsed;
indexUsed++;
buffer[stackPointer[stackNum]]=new StackNode(lastIndex,value);


}
int pop(int stackNum)
{
int value = buffer[stackPointer[stackNum]].value;
int lastIndex = stackPointer[stackNum];
stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
buffer[lastIndex] = null;
indexUsed--;
return value;
}
int peek(int stack) { return buffer[stackPointer[stack]].value; }
boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; }

class StackNode
{
public int previous;
public int value;
public StackNode(int p, int v)
{
value = v;
previous = p;
}

}

Taken from Cracking The Code By Gayle Laakmann Mcdowell !!!

How to Count Number of Set Bits e.g. Number of 1's efficiently ?

This Question is asked in almost all core s/w companies & most of we know logarithmic solution of this problem but there exist a constant time solution using bit manipulations stuck !!!!:) See 2nd Method to solve the same problem in O(1)

1st Brian Kernighan’s Algorithm:
Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
Beauty of the this solution is number of times it loops is equal to the number of set bits in a given integer.

1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count

#include

/* Function to get no of set bits in binary
representation of passed binary no. */
int countSetBits(int n)
{
unsigned int count = 0;
while (n)
{
n &= (n-1) ;
count++;
}
return count;
}

/* Program to test function countSetBits */
int main()
{
int i = 16;
printf("%d", countSetBits(i));
getchar();
return 0;
}

Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/2y2KJ

2nd Method is Most Efficient One !!!!!!

Assuming that the integer is 32 bits, this is pretty good:

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

where
0x55555555 = 01010101 01010101 01010101 01010101
0x33333333 = 00110011 00110011 00110011 00110011
0x0F0F0F0F = 00001111 00001111 00001111 00001111
0x00FF00FF = 00000000 11111111 00000000 11111111
0x0000FFFF = 00000000 00000000 11111111 11111111


Notice that the hex constants are respectively alternate bits,
alternate pairs of bits, alternate groups of four bits, alternate
bytes, and the low-order half of the int.

The first statement determines the number of one-bits in each pair of
bits. The second statement adds adjacent pairs of bits to get the
number of bits in each group of four bits. Then these are added to get
the number of bits in each byte, short int, and finally in the whole
int.

but it works at low level ??

Suppose that the first four bits of x from the left are abcd. Lets separate the bits into pairs with a comma: ab,cd. The first four bits of the hex constant0x55... are 0101, or separated into pairs: 01,01. The logical product of x with this constant is 0b,0d. The first four bits of x>>1 are 0abc, or separated into pairs are 0a,bc. The logical product of this with the constant is 0a,0c. The sum 0b,0d + 0a,0c is a+b,c+d, where a+b = 00, 01, or 10, and b+c = 00, 01, or 10. Thus we have replaced each pair of bits in x with the sum of the two bits originally in the pair.

The next statement uses the constant 0x333.... The first four bits of this are 0011, split into pairs as 00,11. The logical product of the first four bits of x with this constant gives 00,c+d. Furthermore (a+b,c+d)>>2 = 00,a+b. Then 00,c+d + 00,a+b gives the four-bit quantity a+b+c+d, i.e., the number of one bits set in the first four bits of the original x.

The next statements continue to double the number of bits included in each sum.
& so on

#include
using namespace std;

int main()
{
int x=0x00000016;
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

cout<> 2) & 0x33333333);

cout<> 4) & 0x0F0F0F0F);

cout<> 8) & 0x00FF00FF);

cout<> 16) & 0x0000FFFF);

cout< return 0;

}

Time Complexity O(1)
Space Complexity O(1)
Run Here https://ideone.com/uDKGK
More Info http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

You are provided with a bit generator which generates 1 and 0 with equal probabilities i.e. (1/2). You are required to design a function which generates numbers form 1-1000 with equal probabilities i.e. (1/1000).

Given two sorted arrays a[]={1,3,77,78,90} and b[]={2,5,79,81}. Merge these two arrays, no extra spaces are allowed. Output has to be a[]={1,2,3,5,77} and b[]={78,79,81,90}.

Data Structure Used: Array

Algorithm: Question is really tricky if we don't think smartly !!!! :)
use two pointer & points l to 1st & r to 2nd array
if elementb in 1st is smaller trhen 2nd arraye elemnt at index i then increment 1st pointer
else
swap element at index i in both array &b incerment 1st pointer & sort 2nd
array its not necessary only if we need sorted output in each array

Solution:

size of a=m size of b =n
a[]={1,3,77,78,90} and b[]={2,5,79,81}
l r


while(l<=m && r<=n)
{
if(b[r] {
swap(a[l],b[r]);
l++;
sort(b[]);
}
elseif(a[l] l++;



}

Time Complexity O(mlogm) sorting to 2nd array
Space Complexity O(1)

Given a word, convert it into a palindrome with minimum addition of letters to it. letters can be added anywhere in the word. for eg if yahoo is given result shud be yahoohay.

e.g

ABBA : 0 (already a palindrome)
ABB: 1
FAE: 2
FOO: 1


Simple Algorithm Will be

You need to find the longest palindrome at the end of the string. An algorithm to see if a string is a palindrome can be created by simply running one pointer from the start of the string and one from the end, checking that the characters they refer to are identical, until they meet in the middle. Something like:

function isPalindrome(s):
i1 = 0
i2 = s.length() - 1
while i2 > i1:
if s.char_at(i1) not equal to s.char_at(i2):
return false
increment i1
decrement i2
return true

Try that with the full string. If that doesn't work, save the first character on a stack then see if the remaining characters form a palindrome. If that doesn't work, save the second character as well and check again from the third character onwards.

Eventually you'll end up with a series of saved characters and the remaining string which is a palindrome.

Best case is if the original string was a palindrome in which case the stack will be empty. Worst case is one character left (a one-character string is automatically a palindrome) and all the others on the stack.

The number of characters you need to add to the end of the original string is the number of characters on the stack.

To actually make the palindrome, pop the characters off the stack one-by-one and put them at the start and the end of the palindromic string.

Examples:

String Palindrome Stack Notes
------ ---------- ----- -----
ABBA Y - no characters needed.

String Palindrome Stack Notes
------ ---------- ----- -----
ABB N -
BB Y A one character needed.
ABBA Y - start popping, finished.

String Palindrome Stack Notes
------ ---------- ----- -----
FAE N -
AE N F
E Y AF two characters needed.
AEA Y F start popping.
FAEAF Y - finished.

String Palindrome Stack Notes
------ ---------- ----- -----
FOO N -
OO Y F one character needed.
FOOF Y - start popping, finished.

String Palindrome Stack Notes
------ ---------- ----- -----
HAVANNA N -
AVANNA N H
VANNA N AH
ANNA Y VAH three characters needed.
VANNAV Y AH start popping.
AVANNAVA Y H
HAVANNAVAH Y - finished.