Remove nodes in Linked List


Node* RemoveNodesWithValue(Node* head, int k) {
if (!head) {
return head;
}

Node dummy;
dummy.next = head;
Node* prev = &dummy;
Node* current = head;

while (current) {
if (current->data == k) {
prev->next = current->next;
delete current;
current = prev->next;
}
else {
prev = current;
current = current->next;
}
}

return dummy.next;
}

Posted in Algorithm Brews.. | 1 Comment

All Combinations Without Repetitions

+-------+------------+-----------+
| Binary | Position  |  Selected |
| Count  | Set       |  String   |
+-------+------------+-----------+
| 0000   | {}        |  ""       |
| 0001   | {0}       |  "a"      |
| 0010   | {1}       |  "b"      |
| 0011   | {0,1}     |  "ab"     |
| 0100   | {2}       |  "c"      |
| 0101   | {0,2}     |  "ac"     |
| 0110   | {1,2}     |  "bc"     |
| 0111   | {0,1,2}   |  "abc"    |
| 1000   | {3}       |  "d"      |
| 1001   | {0,3}     |  "ad"     |
| 1010   | {1,3}     |  "bd"     |
| 1011   | {0,1,3}   |  "abd"    |
| 1100   | {2,3}     |  "cd"     |
| 1101   | {0,2,3}   |  "acd"    |
| 1110   | {1,2,3}   |  "bcd"    |
| 1111   | {0,1,2,3} |  "abcd"   |
+-------+------------+-----------+ 


/* Program to generate all r-Combinations of a set with distinct element
* This code is a part of http://phoxis.wordpress.com/2009/10/13/allcombgen/
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100
#define TRUE 1
#define FALSE 0

int generate_combination (const char *source_string,char *combination_string);

unsigned int comb_mask = 0x00000001;
unsigned int max_mask_length;

/* Main Function, driving generate_combination() */
int
main (void)
{
char source_string[MAX], combination_string[MAX];
int len;

printf ("Enter the Source String:");
scanf ("%s", source_string);

len = strlen (source_string);
max_mask_length = ~(0x00000001 << len);

printf ("\nPrinting Combinatins:\n");
while (1)
{
if (generate_combination (source_string, combination_string) == FALSE)
break;
printf ("%s\n", combination_string);
}
printf ("\nfinished\n");
return 0;
}

/*
* File Name : combination.c
* Function Name : generate_combination
* Parameters :
* @ (const char *) source_string
* @ (char *) combination_string
* Return Type : (int)
* # return FALSE if no more mermutations, else return TRUE
* Globals :
* @ (unsigned int) comb_mask
* # A bitmask. Used to select unique combinations from source
* string. This function increments and updates this mask
* in each iteration. Each call results in a new permutation.
* @ (unsigned int) max_mask_length
* # A bitmask. Used to control the length of masking of
* comb_mask variable. This is not modified in this function.
* Initilized in function main()
* Description : Each call to this function generated a new combination from
* the source_string and then places into combination_string
* The combination is done based upon comb_mask variable. The
* positions, in which comb_mask has a '1' , are only selected
* from the source_string to make a combination.
* Note : The combination generation is comb_mask dependent. To generate
* unique combinations in each call comb_mask should not be modified
* any where else, if some explicit customized combinination is to be
* generated. Each bit field has a fixed length (32bit) , the combintaion
* can be generated is limited to this length, in this version of code.
* This function does not return the null set.
*/

int
generate_combination (const char *source_string, char *combination_string)
{
unsigned int mask = 0x00000001;
int s_pos = 0, c_pos = 0;

/* Main logic */
while ((mask & max_mask_length))
{
if ((comb_mask & mask))
{
combination_string[c_pos] = source_string[s_pos];
c_pos++;
}
s_pos++;
mask <<= 1;
}

/*update permutation mask */
comb_mask++;

/* Terminate the combination_string with NULL character */
combination_string[c_pos] = 0;

/* If combination_string is empty, ie. c_pos == 0 , return FALSE else return TRUE */
return (c_pos == 0 ? FALSE : TRUE);
}

Code Description

The variable comb_mask here is the bit field which we use to count up the binary sequence and make the selection set. The comb_mask variable is set to 0x00000001 , that is the upper 31 bits are set to ’0′ and the LSB is set to ’1′, and counted upwards. The max_mask_length is used to limit the masking of variable mask and comb_mask up-to the length of the source string. Its is set to ~(0x00000001 << len) . If the length of the source string is 'n' then the '(n+1)'th position of the max_mask_length will be ’0′, which determines the loop’s termination. The mask variable is initialized to 0x00000001 . It is left bit shifted in each iteration to shift the ’1′ from right most to left positions. In each iteration it is checked with the max_mask_length to see if the max bit field length is exceeded and if the iteration should stop as all combinations are generated.
The loop termination is as follows: The mask has only one ’1′ in a certain position. It is AND-ed with max_mask_length. If the length is 4 then max_mask_length will have a ’0′ in the 5th position. The loop will be true till mask has the ’1′ at positions less than 5th. Whenever mask will have the ’1′ in the 5th position the bitwise operation (mask & max_mask_length) would be false , (both are complements of each other), and the loop will terminate. Thus length of the count is bound inside a limit.
For example if the length of the source string is 4 then max_mask_length is ~(0x00000001 << 4) = ~(0x00000010) = 0xffffffef = 11111111111111111111111111101111 in binary. in the while loop this value is masked with mask, when ever the mask’s 4th bit would get 1 it would mean that it has counted from 00000 to 01111 and generated all the combinations and now has become 10000 so we would stop. Thus the loop is terminated after all the combinations are generated.

In the loop the if statement tests each bit position of the comb_mask with the help of mask variable which scans from the rightmost bit to leftmost bit and checks if a certain bit position is a ’1′, if it is then the character of the corresponding position of the source string is selected. The bit position being checked currently is tracked by s_pos counter. If a a bit position of comb_mask is ’1′ then the position of that bit (recorded by s_pos) is used to select the corresponding character from the source_string and assign to combination_string . The c_pos variable points to the last character of the combination_string.
For example, comb_mask is 0x0000000a whose binary equivalent is 00000000000000000000000000001010 . Now mask is 00000000000000000000000000000001 . (mask & comb_mask) evaluates to 0, so the 0th character is not selected. next iteration mask is equal to 00000000000000000000000000000010 . (mask & comb_mask) evaluates to 1, so the 1st character is selected, and so on.

The mask is left shifted by 1 bit and updated in each iteration, so it can check the next bit. The comb_mask is incremented in each iteration to make select new combinations.
Notes

The null set is not selected by the above code.

The above code does not select the input string for repeat characters in it. So a string “aaaa” is allowed and each ‘a’ is considered as different entity.

This is not a process with which permutation without repetitions can be made, that permuting elements by changing their order within themselves cannot be made.

This is a good process to generate a bruteforce password generator, which can be used to input into an appropriate hash function and stored, or matched with the target hash.

Source: http://phoxis.org/2009/10/13/allcombgen/

Posted in Algorithm Brews.. | Leave a comment

Number of bits set in an integer.

Going by the brute force approach, it would be easy to come up with the following solution. If the least significant bit of a number is 1, it will return a result of 1 when we AND it with 1. Using this logic, we can shift bits in the number to the right and keep testing if the least significant bit is 1. When there are no 1′s left in the number, it will become zero. Here’s some code to illustrate this simple logic.

int numOnesInInteger( int num )
{
int numOnes = 0;
while( num != 0 )
{
if( ( num & 1 ) == 1 ) {
numOnes++;
}
num = num >> 1;
}
return numOnes;
}

Think we can do better? The above algorithm runs in O(n) where n in the number of bits in the integer. Maybe we can make this a tad better. But this would need some real creative bit manipulation skills. So let’s think, what happens to a number when it we AND it with (number – 1). Let’s take 7 (0111) as an example.

7 & 6 = 0111 & 0110 = 0110 = 6
6 & 5 = 0110 & 0101 = 0100 = 4
4 & 3 = 0100 & 0011 = 0000 = 0

Do you see a pattern yet? Essentially, when you AND a number with (number – 1), the last 1 bit in the number gets set to zero. So if we continue to set every 1 bit in the number to zero, the number will eventually become zero. If we use this logic to count the number of 1s, we have an algorithm that runs in O(m) where m is the number of bits set to 1 in the number. Here’s some code.

int numOnesInInteger( int num )
{
int numOnes = 0;
while( num != 0 ){
num = num & (num – 1);
numOnes++;
}
return numOnes;
}

Interesting right? Please Digg or Stumble this post! As usual, comments are always welcome.

Source: http://www.mytechinterviews.com/number-of-ones

Posted in Algorithm Brews.. | Leave a comment

Reverse a link list in chunks of k.


/* Reverses the linked list in groups of size k and returns the pointer to the new head node */
struct node *reverse (struct node *head, int k)
{
struct node* current = head;
struct node* next;
struct node* prev = NULL;
int count = 0;

/*reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}

/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if(next != NULL)
{ head->next = reverse(next, k); }

/* prev is new head of the input list */
return prev;
}

Source : geeksforgeeks.org

Posted in Algorithm Brews..

Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

Examples:

Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
Output: 6 (j = 7, i = 1)

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Output: 8 ( j = 8, i = 0)

Input: {1, 2, 3, 4, 5, 6}
Output: 5 (j = 5, i = 0)

Input: {6, 5, 4, 3, 2, 1}
Output: -1

Method 1 (Simple but Inefficient)
Run two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.


#include
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff = -1;
int i, j;

for (i = 0; i i; --j)
{
if(arr[j] > arr[i] && maxDiff < (j - i))
maxDiff = j - i;
}
}

return maxDiff;
}

int main()
{
int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
int n = sizeof(arr)/sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
printf("\n %d", maxDiff);
getchar();
return 0;
}

Time Complexity: O(n^2)

Method 2 (Efficient)
To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index. So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.

Thanks to celicom for suggesting the algorithm for this method.

#include

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
return x > y? x : y;
}

int min(int x, int y)
{
return x arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff;
int i, j;

int *LMin = (int *)malloc(sizeof(int)*n);
int *RMax = (int *)malloc(sizeof(int)*n);

/* Construct LMin[] such that LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for (i = 1; i = 0; --j)
RMax[j] = max(arr[j], RMax[j+1]);

/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while (j < n && i < n)
{
if (LMin[i] < RMax[j])
{
maxDiff = max(maxDiff, j-i);
j = j + 1;
}
else
i = i+1;
}

return maxDiff;
}

/* Driver program to test above functions */
int main()
{
int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
int n = sizeof(arr)/sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
printf("\n %d", maxDiff);
getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(n)

Source: geeksforgeeks.org

Posted in Algorithm Brews.. | Leave a comment

Total different combination of the lower and upper case of a single string.

Given a string, write all the possible upper case and lower case strings of it. eg. given a string THE print tHE,ThE,THe,thE,The,tHe,the.


#include
#include
#include
#include

int count = 0;

void toggler(char* x, int pos)
{

if(pos==0)
{
printf("%s\n",x);
printf("count %d\n",++count);
return;
}

printf("\nString is now: %s , pos = %d\n",x,pos);

x[pos-1] = toupper(x[pos-1]);
printf("upper -String is now: %s\n",x);
toggler(x, pos-1);

x[pos-1] = tolower(x[pos-1]);
printf("lower- String is now: %s\n",x);
toggler(x, pos-1);

return;
}

int main(void)
{

char str[500] = "THE";

toggler(str, strlen(str));

return 0;
}

Posted in Algorithm Brews.. | Leave a comment

Product of all the elements of an array except element at current Index, without using Division.

Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator and in O(n).


#include<iostream>

using namespace std;

void printArray(int A[], int n)
{
int i ;
cout << "Printing Array: \n";
for (i = 0 ; i < n; i++)
cout<< A[i] << "\t";
cout<< endl;
}

int main()
{
int arr[5] = {1,2,3,4,5};
int prod[5];
int n = 5;
int i;
int left_partial = 1;
int right_partial = 1;

printArray(arr,n);

for (i = 0 ; i < n; i++)
{
prod[i] = left_partial;

left_partial *= arr[i];
cout<< "leftPartial = "<<left_partial<<"\t prod[i]= "<<prod[i]<<endl;
}

printArray(prod,n);

for (i = n - 1; i >= 0; i--)
{
prod[i] *= right_partial;
cout<< "right_Partial = "<<right_partial<<"\t prod[i]= "<<prod[i]<<endl;
}
printArray(prod,n);

}

Posted in Algorithm Brews.. | Leave a comment