CareerCup

the merge step of merge sort can be used.

i guess we might need to use the longest common substring algorithm to extract the common fragments between multiple strings. doing it for multiple files might hurt the efficiency though because it has quadratic runtime..

couple of doubts though:
1. Will the fragments be of size 3 or 4 everytime? or can they be longer?

2. i dont think i understood this example 'a a a a a b c b c b c b c' very well. is this just one string in one file or does it mean that we have abt strlen("a a a a a b c b c b c b c") files each having 1 character in them? Kindly explain this input again.

the above code would work on inputs where the matrix sequence is strictly increasing across rows, columns and adjacent rows.

@sujith for your input, i'm not sure how to find a row and do a binary search in [O(n) + O(log(n))] time. lets say we're searching for the number 38, now as per your logic, you'll first loop over all the rows comparing the value of matrix[i][0] and matrix[i][n-1] with 38. For each such satisfying row, you will need to do a binary search to get the actual column of 38 (if it exists in that row). This will take you O(n*log(n)) time in the worst case. For example, if we search for 38, we'll have to do a binary search on Row 1(assuming the row count starts at Row 0), and Row 2 before we get the desired data.

@Annonymous very true dude.. the above algorithm is linear in O(m + n). but my point was that we can do better by using binary search which has O(log n)..

since the matrix contains sorted numbers, its more efficient to not look at every possible index of the matrix. Looking at every index will make the search O(n^2). but doing a binary search would eliminate rows and cols where our search term is not expected to be. Hence, the efficiency of this would be O(log n).. thats the advantage.

binarySearch on 2D matrix:


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

int rows = 50;
int cols = 50;

int** matrix = NULL;

int search_matrix(int start_row, int start_col, int end_row, int end_col,
int search_term) {

int returnValue = -1;

int mid_row = (start_row + end_row) / 2;
int mid_col = (start_col + end_col) / 2;

if (start_row > end_row || start_col > end_col || end_row < start_row
|| end_col < start_col || search_term < matrix[0][0])
return -1;

if (matrix[mid_row][mid_col] == search_term) {
printf("\nFound %d at Row = %d Column = %d\n", search_term, mid_row,
mid_col);
return mid_row;
}

if (matrix[mid_row][start_col] <= search_term
&& matrix[mid_row][cols] >= search_term) {
// we have found our row

if (matrix[mid_row][start_col] <= search_term
&& matrix[mid_row][mid_col] >= search_term) {
start_row = mid_row;
//start_col = 0;
end_row = mid_row;
end_col = mid_col;
}

else if (matrix[mid_row][mid_col] < search_term
&& matrix[mid_row][cols] >= search_term) {
start_row = mid_row;
start_col = mid_col;
end_row = mid_row;
end_col = cols;
}

returnValue = search_matrix(start_row, start_col, end_row, end_col,
search_term);

} else if (matrix[mid_row][0] > search_term) {
end_row = mid_row;
end_col = cols;

start_row = 0;
//start_col = 0;

returnValue = search_matrix(start_row, start_col, end_row, end_col,
search_term);

} else if (matrix[mid_row][0] < search_term) {

start_row = mid_row + 1;
//start_col = 0;

end_row = rows;
end_col = cols;

returnValue = search_matrix(start_row, start_col, end_row, end_col,
search_term);
}

return returnValue;
}

int main(int argc, char** argv) {

int i = 0, j = 0, counter = 0;

matrix = (int**) malloc(sizeof(int) * rows);
for (i = 0; i < rows; i++) {
matrix[i] = (int*) malloc(sizeof(int) * cols);
}

// initialize matrix
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++)
matrix[i][j] = counter + j;

counter = matrix[i][cols - 1] + 1;
}

for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++)
printf("%d ", matrix[i][j]);

printf("\n");
}

cols = cols - 1;
rows = rows - 1;
int searchTerm = 2423;

int index = search_matrix(0, 0, rows, cols, searchTerm);

if (index == -1)
printf("\n%d not present in matrix\n", searchTerm);

return EXIT_SUCCESS;
}

The first approach might lead to overflow if the list is too huge such that the sum of its elements is beyond the range of int/long.

The second approach is the only one that looks achievable. we can do something like this:

1. find the length of 2 lists => len_l1 and len_l2(lets say len_l1 > len_l2)
2. traverse the bigger list skipping (len_l1 - len_l2) nodes in l1.

3. now keep pushing teh current top of each list into the stack and call step 3 recursively passing (l1->next, l2->next).

4. in the recursive method implementing step 3, check if(nodeFromListOne->next == NULL && nodeFromListTwo->next == NULL). if so, this is the last node and we must start returning (popping from stack) after this instead of contuining with recusrion.

5. return the sum of digitList1 and digitList2 as well as the carryover value.

6. in the caller stack (to whom these values are returned), use the carry over value returned for summation again. also to store the sum, we can either create a new list or update either list1 or list 2 with the sum

public class dup_count {

public static int lastVal = Integer.MIN_VALUE;

public static void main(String[] args) {

// Testing with the following test data
int[] a = { 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 9, 9, 9,
10, 10 };

// int[] a = { 1, 2, 3, 4, 5 };

// int[] a = { 3, 3, 3 };

// int[] a = { 1, 1, 3 };

// int[] a = { 1, 1 };

new dup_count().count_dupicates(a, 0, a.length - 1);
}

void count_dupicates(int[] a, int start, int end) {

int mid = (start + end) / 2;

if (end <= start || mid == start && a.length > 2 || mid == end
&& a.length > 2)
return;

// if the mid element == start element, then the start element was
// repeated all
// the way through start to mid location

// a[start] > lastVal: This comparision is just to prevent
// printing the same number again and again

if (a[mid] == a[start] && a[start] > lastVal) {
System.out.println(a[start] + " , ");
lastVal = a[start];
}

else if (a[mid] > a[start]) {
count_dupicates(a, start, mid);
}

if (a[end] == a[mid] && a[end] > lastVal) {
System.out.println(a[end] + " , ");
lastVal = a[end];

return;
}

else if (a[end] > a[mid]) {
count_dupicates(a, mid, end);
}

}
}

Jave code for the above problem statement. Very similar to Binary Search algorithm. Additional ifs had to be put for the case when the array has only 2 and 3 elements.

malloc allocates contiguous blocks of memory. so lets say our original list contains nodes: { a, b, c, d, e}. Since we dont know the head, we dont know where the list begins. now we're asked to delete node 'e' (lets say) i.e. we've been given the address of the node 'e'. now if e->next == NULL, we can be certain that 'e' is the last node to be deleted. In this case, we must fix the address pointed to by the node 'd'. But how do we reach node 'd' given node 'e'?

Since malloc allocates memory in continuous chunks, cant we reach node 'd' by doing a pointer arithmetic i.e. Address of node 'd' = Address of node 'e' - sizeof(struct node). Now we can reach node 'd' and fix its next pointer to point to NULL.

the same logic can be used for any node but the first. imagine if we have only 1 node in the list and we're asked to delete this node?