pranaymahajan
BAN USER@mr i think you are right
- pranaymahajan August 28, 2012Here is the code for Kadane's algorithm
int Kadane(int* A,int n,int& startIndex,int& endIndex)
{
startIndex = 0;
endIndex = 0;
int maxSubTotal=1<<31; // -INFINITY
int currSubTotal=0;
int j=0;
for(int i=0; i<n ;i++)
{
currSubTotal=currSubTotal+A[i];
if(currSubTotal>maxSubTotal)
{
startIndex=j;
endIndex=i;
maxSubTotal=currSubTotal;
}
if(currSubTotal<0)
{
currSubTotal=0;
j=i+1;
}
}
return maxSubTotal;
}
inplace menas that no extra memory should be allocated for doing the substring comparison. For Rabin-Karp, memory would be required for hashing purpose. Hence, it cant work in this case.
One approach might be to use the naive approach for this. But I am sure the interviewer might be looking for something smarter.
we have to do this in-place. So Rabin-Karp cant be applied
- pranaymahajan August 28, 2012The application of the above 3 steps is not enough to check the interleaving of two string. Consider the following example-
str1 = "acb", str2 = "def", str3 = "abcdef"
Although the above string combinations satisfies all the three conditions mentioned above, still, str3 is not the interleaved string combination for str1 and str2
int sumCount(int* arr, int len, int total)
{
int count = 0;
for (int i = 0; i < len; ++i)
{
sumCountHelper(arr, i, len, total - arr[i], count);
}
return count;
}
void sumCountHelper(int* arr, int start, int len, int total, int& count)
{
if (total == 0)
{
++count;
return;
}
if (total < 0)
return;
for (int i = start + 1; i < len; ++i)
{
sumCountHelper(arr, i, len, total - arr[i], count) ;
}
}
One change: Find all the numbers in A which are between x and y (including x and y) and call the list C
- pranaymahajan August 27, 2012In that case we can add this code snippet in the beginning of
definition of interleavedStrings function
if (result)
return;
bool interleavedStrings(char* str1, char* str2, char* str3)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
int len = len1 + len2;
char* str = new char[len + 1];
bool result = false;
interleavedStringsHelper(str1, str2, str, len, str3, result);
return result;
}
void interleavedStringsHelper(char* str1, char * str2, char* str, int len, char* str3, bool& result)
{
if (!(*str1) && !(*str2))
{
str[0] = NULL;
if (!strcmp(str3, str - len))
result = true;
return;
}
if (*str1)
{
str[0] = *str1;
interleavedStringsHelper(str1 + 1, str2, str + 1, len, str3, result);
}
if(*str2)
{
str[0] = *str2;
interleavedStringsHelper(str1, str2 + 1, str + 1, len, str3, result);
}
}
The above algo is for in-place modification
- pranaymahajan August 27, 2012void removeDoubleZero(char* ptr)
{
char* iter = ptr;
char* copyToIter = ptr;
char* zeroStart = NULL;
int zeroCount = 0;
while(*iter)
{
if ('0' == *iter)
{
++zeroCount;
if (!zeroStart)
{
zeroStart = iter;
}
}
else
{
if ( zeroStart && (2 != zeroCount) )
{
while ( zeroStart != iter )
{
*copyToIter = *zeroStart;
++zeroStart;
++copyToIter;
}
}
*copyToIter = *iter;
++copyToIter;
zeroCount = 0;
zeroStart = NULL;
}
++iter;
}
*copyToIter = NULL;
}
Solution 1:
void swap(int* a, int i, int j)
{
if (i >= j)
return;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void print(int * a, int len)
{
for (int i = 0; i < len; ++i)
printf("%3d ", a[i]);
}
int main()
{
int arr[] = {-12, -11, 12, 0, 11, -10, 10, 9, 8, -8, 7, 0, 0 , -9, -7};
int start = 0;
int mid = 0;
int len = sizeof(arr) / sizeof(arr[0]);
int end = len - 1;
print(arr, len);
printf("\n");
while (mid <= end)
{
if (arr[mid] < 0)
swap(arr, start++, mid++);
else if (arr[mid] == 0)
mid++;
else
swap(arr, mid, end--);
}
print(arr, len);
printf("\n");
return 0;
}
Solution 2:
void swap(int* a, int i, int j)
{
if (i >= j)
return;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void print(int * a, int len)
{
for (int i = 0; i < len; ++i)
printf("%3d ", a[i]);
}
int main()
{
int arr[] = {-12, -11, 12, 0, 11, -10, 10, 9, 8, -8, 7, 0, 0 , -9, -7};
int start = 0;
int len = sizeof(arr) / sizeof(arr[0]);
int end = len - 1;
print(arr, len);
printf("\n");
while (start < end)
{
while (arr[start] < 0)
++start;
while (arr[end] >= 0)
--end;
swap(arr, start, end);
}
print(arr, len);
printf("\n");
while (arr[start] >= 0)
--start;
++start;
end = len - 1;
while (start < end)
{
while (!arr[start])
++start;
while (arr[end] > 0)
--end;
swap(arr, start, end);
}
print(arr, len);
return 0;
}
1) Take (m = n % 3).
2) If m != 0
you make the first move and pick m number of stones
else
ask other person to make the first move, else
3) Now if other person picks up k( k = 1 or 2) stones. Then you should pick 3 - k stones, to always move on a multiple of three boundary after eliminating the first m stones
slight modification in the algo
#include <stdio.h>
#define MASK 0x1
int _tmain(int argc, _TCHAR* argv[])
{
unsigned int arr[] = {1, 4, 5, 6, 4, 6, 2};
//unsigned int arr[] = {1, 2, 3};
// set[i] contains the xor of all the numbers whose (i+1)th LSB is set
unsigned int set[32] = {0};
// unset[i] contains the xor of all the numbers whose (i+1)th LSB is unset
unsigned int unset[32] = {0};
unsigned int xorNum = 0;
unsigned int numOne = 0;
unsigned int numTwo = 0;
unsigned int numThree = 0;
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len; ++i)
{
unsigned int& val = arr[i];
xorNum ^= val;
for (int j = 0; j < 32; ++j)
{
( val & (MASK << j) ) ? ( set[j] ^= val ) : ( unset[j] ^= val );
}
}
unsigned int temp = 0;
int j = 0;
for ( int j = 0; j < 32; ++j )
{
temp = ( (xorNum >> j) & MASK ) ? set[j] : unset[j];
if ( (temp != xorNum) )
{
numOne = temp;
break;
}
}
//xorNum ^= numOne;
for ( int k = j + 1; k < 32; ++k )
{
temp = ( (xorNum >> k) & MASK ) ? set[k] : unset[k];
if ( (temp != xorNum) && (temp != numOne) )
{
numTwo = temp;
break;
}
}
numThree = xorNum ^ numTwo ^ numOne;
printf("Required Numbers : %d, %d, %d\n", numOne, numTwo, numThree);
return 0;
}
set[i] contains the xor of all the numbers whose (i+1)th LSB is set
unset[i] contains the xor of all the numbers whose (i+1)th LSB is unset
I have been thinking about a solution to this problem for quiet some time now.
Before I propose my solution, here is some points that my code will use
1 = 1^1^1 or 1^0^0
0 = 0^0^0 or 0^1^1
ie, if we calculate the xor of all the numbers (xorNum), then
1) if a particular bit is set in the xorNum, then
a) either it is set in all the 3 numbers,
b) or it is set in only one of them
2) Similarly, if a particular bit is unset in the xorNum, then
a) either it is unset in all the 3 numbers
b) or it is unset in only one of them
Though my code I will try to find 1b and 2b condition mentioned above to find a solution to this problem.
Here is my solution
#include <stdio.h>
#define MASK 0x1
int _tmain(int argc, _TCHAR* argv[])
{
// this is the input array, modify it to change this
unsigned int arr[] = {1, 4, 5, 6, 4, 6, 2};
unsigned int set[32] = {0};
unsigned int unset[32] = {0};
unsigned int xorNum = 0;
unsigned int numOne = 0;
unsigned int numTwo = 0;
unsigned int numThree = 0;
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len; ++i)
{
unsigned int& val = arr[i];
xorNum ^= val;
for (int j = 0; j < 32; ++j)
{
( val & (MASK << j) ) ? ( set[j] ^= val ) : ( unset[j] ^= val );
}
}
unsigned int temp = 0;
for ( int j = 0; j < 32; ++j )
{
temp = ( (xorNum >> j) & MASK ) ? set[j] : unset[j];
if ( (temp != xorNum) )
{
numOne = temp;
break;
}
}
xorNum ^= numOne;
for ( int j = 0; j < 32; ++j )
{
temp = ( (xorNum >> j) & MASK ) ? set[j] : unset[j];
if ( (temp != xorNum) && (temp != numOne) )
{
numTwo = temp;
break;
}
}
numThree = xorNum ^ numTwo;
printf("Required Numbers : %d, %d, %d\n", numOne, numTwo, numThree);
return 0;
}
@jane: Let me explain you this with an example:
For n = 5,
Upper Triangle:
------------------------------
0: arr[0][0]
1: arr[0][1] arr[1][0]
2: arr[2][0] arr[1][1] arr[0][2]
3: arr[0][3] arr[1][2] arr[2][1] arr[3][0]
4: arr[4][0] arr[3][1] arr[2][2] arr[1][3] arr[0][4]
Lower Triangle:
------------------------
5: arr[1][4] arr[2][3] arr[3][2] arr[4][1]
6: arr[4][2] arr[3][3] arr[2][4]
7: arr[3][4] arr[4][3]
8:arr[4][4]
so for n = 5, the lop iterates from 0 to 8(ie 0 to 2n-2)
#include <stdio.h>
int main()
{
int n = 0;
scanf("%d", &n);
if (n < 3)
return 0;
int x, y;
bool bStartFromLeft = true;
int limit = 0;
for (int i = 0; i < 2*n-1 ; ++i)
{
if (i < n)
{
limit = i + 1;
if (bStartFromLeft)
{
x = 0;
y = i - x;
}
else
{
y = 0;
x = i - y;
}
}
else
{
limit = 2*n - i - 1;
if (!bStartFromLeft)
{
x = n - 1;
y = i - x;
}
else
{
y = n - 1;
x = i - y;
}
}
for (int j = 0; j < limit; ++j)
{
printf("%d ", y*n + x + 1);
if (bStartFromLeft)
{
--y;
++x;
}
else
{
++y;
--x;
}
}
bStartFromLeft = !bStartFromLeft;
}
return 0;
}
Mat[n][n]
int row = 0;
int i;
for (i = n- 1; (i >= 0) && (!Mat[0][i]); --i);
int column = i;
if (i == n - 1)
return row;
int tryingColumn = i + 1;
for (j = 1; j < n; ++j)
{
if (Mat[j][tryingColumn])
{
++tryingColumn;
while (tryingColumn < n)
{
if (Mat[j][tryingColumn])
++tryingColumn;
}
row = j;
if (tryingColumn == n)
return row;
}
}
return row;
- pranaymahajan August 28, 2012