Forum Posts
- 0 Answers how this code convert to java? please .....
// Dynamic Programming implementation of edit distance
- omarhidayat1 May 10, 2013
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// Change these strings to test the program
#define STRING_X "SUNDAY"
#define STRING_Y "SATURDAY"
#define SENTINEL (-1)
#define EDIT_COST (1)
inline
int min(int a, int b) {
return a < b ? a : b;
}
// Returns Minimum among a, b, c
int Minimum(int a, int b, int c)
{
return min(min(a, b), c);
}
// Strings of size m and n are passed.
// Construct the Table for X[0...m, m+1], Y[0...n, n+1]
int EditDistanceDP(char X[], char Y[])
{
// Cost of alignment
int cost = 0;
int leftCell, topCell, cornerCell;
int m = strlen(X)+1;
int n = strlen(Y)+1;
// T[m][n]
int *T = (int *)malloc(m * n * sizeof(int));
// Initialize table
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
*(T + i * n + j) = SENTINEL;
// Set up base cases
// T[i][0] = i
for(int i = 0; i < m; i++)
*(T + i * n) = i;
// T[0][j] = j
for(int j = 0; j < n; j++)
*(T + j) = j;
// Build the T in top-down fashion
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
{
// T[i][j-1]
leftCell = *(T + i*n + j-1);
leftCell += EDIT_COST; // deletion
// T[i-1][j]
topCell = *(T + (i-1)*n + j);
topCell += EDIT_COST; // insertion
// Top-left (corner) cell
// T[i-1][j-1]
cornerCell = *(T + (i-1)*n + (j-1) );
// edit[(i-1), (j-1)] = 0 if X[i] == Y[j], 1 otherwise
cornerCell += (X[i-1] != Y[j-1]); // may be replace
// Minimum cost of current cell
// Fill in the next cell T[i][j]
*(T + (i)*n + (j)) = Minimum(leftCell, topCell, cornerCell);
}
}
// Cost is in the cell T[m][n]
cost = *(T + m*n - 1);
free(T);
return cost;
}
// Recursive implementation
int EditDistanceRecursion( char *X, char *Y, int m, int n )
{
// Base cases
if( m == 0 && n == 0 )
return 0;
if( m == 0 )
return n;
if( n == 0 )
return m;
// Recurse
int left = EditDistanceRecursion(X, Y, m-1, n) + 1;
int right = EditDistanceRecursion(X, Y, m, n-1) + 1;
int corner = EditDistanceRecursion(X, Y, m-1, n-1) + (X[m] != Y[n]);
return Minimum(left, right, corner);
}
int main()
{
char X[] = STRING_X; // vertical
char Y[] = STRING_Y; // horizontal
printf("Minimum edits required to convert %s into %s is %d\n",
X, Y, EditDistanceDP(X, Y) );
printf("Minimum edits required to convert %s into %s is %d by recursion\n",
X, Y, EditDistanceRecursion(X, Y, strlen(X), strlen(Y)));
return 0;
}| Flag | PURGE - 0 Answers how to convert to java?
#include<stdio.h>
- omarhidayat1 May 10, 2013
#include<stdlib.h>
// Structure for a pair
struct pair
{
int a;
int b;
};
// This function assumes that arr[] is sorted in increasing order
// according the first (or smaller) values in pairs.
int maxChainLength( struct pair arr[], int n)
{
int i, j, max = 0;
int *mcl = (int*) malloc ( sizeof( int ) * n );
/* Initialize MCL (max chain length) values for all indexes */
for ( i = 0; i < n; i++ )
mcl[i] = 1;
/* Compute optimized chain length values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i].a > arr[j].b && mcl[i] < mcl[j] + 1)
mcl[i] = mcl[j] + 1;
// mcl[i] now stores the maximum chain length ending with pair i
/* Pick maximum of all MCL values */
for ( i = 0; i < n; i++ )
if ( max < mcl[i] )
max = mcl[i];
/* Free memory to avoid memory leak */
free( mcl );
return max;
}
/* Driver program to test above function */
int main()
{
struct pair arr[] = { {5, 24}, {15, 25},
{27, 40}, {50, 60} };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of maximum size chain is %d\n",
maxChainLength( arr, n ));
return 0;
}| Flag | PURGE - 2 Answers Regarding "return i == t.length() - 1" in Anagram Program in Cracking the Coding Interview
I was going through Cracking the Coding Interview 4th edition.
- kanishk.dudeja May 09, 2013
I was going through a program which checked if two strings are anagrams, by checking if the two strings have identical counts for each unique character.
I could not understand the condition checked in this line.
return i == t.length() - 1;
After understanding the whole algorithm properly, and trying out various test cases, i found that 'return true' would also work in place of this line.
Could anybody please give me any scenario where writing 'return true' instead of the above line would cause the program to fail?| Flag | PURGE - 0 Answers send me project about .....
queue sort using divide and conquer or dynamic
- omarhidayat1 May 06, 2013
programing approach with time complexity)with code java to show run and algorithm?
and
queue search using divide and conquer or dynamic
programing approach with time complexity)with code java to show run and algorithm?
please.......please......think you .................| Flag | PURGE - 1 Answer Subscription Mail Cancellation .
Hi ,
- hprem991 May 06, 2013
I am not sure if this is with me or with everyone else as I am getting a lot of mails into my private and registered mail id regarding the question / discussion after every user comments from here.
I may have put comment of my own on the same question sometimes back and may becoz of that I am getting the same but the question here is the is no way to unsubscribe those subscriptions.
Although , C C does have the checkbox at the bottom of the question under discussion but I am not sure why it is "Checked" by default and always gets redirected to mail account.
Gayle, Could you please provide the single point of subscription / UnSubscription button which will help user to regulate this mail forwarding option.
Thanks
Prem| Flag | PURGE - 2 Answers please write the logic to this program
You are given a set of positive integers. your task is to solve partition problem.
- embedded.naveen May 06, 2013
Lets define the partition problem.
Partition problem is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the elements in S1 equals the sum of the elements in S2.
Ex:
Example 1:
array[] = {1, 5, 11, 5}
Output: Yes
This array can be divided into to subsets {1, 5, 5} and {11} these two have equal sum.
array[] = {1, 5, 3}
Output: No
This array cant be divided into two subsets of equal sum.| Flag | PURGE - 1 Answer java for loop i++ versus i=i++
Hi ,
- itsvivekshetty May 02, 2013
What is the logic behind this behaviour?
int i=0;
for(int k=0;k<10;k++){
i++;
}
System.out.println("i="+i);
Output=10; //Exepcted
int i=0;
for(int k=0;k<10;k++){
i=i++;
}
System.out.println("i="+i);
Output=0; //Surprised :)| Flag | PURGE - 1 Answer Follow-up tech interview
Hi!
- mexibec April 30, 2013
I'd like some feedback on this. Got approached by a top company, got a coding phone interview, then an on-site interview, where all coding/tech questions really went well but one. On that one, I solved the problem in 30 sec. but the interviewer wanted an optimized solution. Let's say that I eventually got there but with too many hints. That was somewhat of a red flag because they'd like a follow-up phone tech interview to determine the final outcome.
So I will naturally prepare (I was a little rusty on algo, but I reviewed them as much as I could prior to the interviews - Gayle's book was very effective at that), but I wanted to get some thoughts about this situation.
It can at least two different things:
1) I have to do exceptionally well, not just good, to get an offer
2) They mostly agree that I can deliver, but want to make sure the questions I properly answered were not just luck. So answering good would be enough.
Either way, I will fully prepare and aim for an A+ on this, but I'd like to know if anyone got into that situation, how they prepared, how it went, etc.
I've been developing for many years, got some apps to be very popular across multiple platforms, no problems at all coding in C/Obj-C/C++/Java, very comfy with any data structures, but not the smartest / brightest / quickest when it comes to algo (although I usually always find a way, not necessarily the best way).
Thanks!
Jack| Flag | PURGE - 6 Answers In C language..
int i = 10;
- jain.saurabh241990 April 30, 2013
printf("%d" , main || i)| Flag | PURGE - 1 Answer character array question
Write a java Program such that Given two character arrays a[] and b[], remove from b[] all occurrences of all characters that occur in array a[]. You need to do this in-place i.e. without using an extra array of characters. E.g.:
- dum April 29, 2013
Input: char a[] = {'G', 'O'}
Input char b[] = {'G', 'O', 'O', 'G', 'L', 'E'}
Output: char b[] = {'L', 'E'}
Please provide me with the java code for the same.| Flag | PURGE - 6 Answers Samsung Interview question
You have given one array (Cell) with 100 blocks and in these block you can have 10 colors. Write a program to manage these colors in sorting order by using following conditions.
- venkatakarthik April 29, 2013
1. Colors will be pick from {a, b, c,........,z}.
2. No sorting algorithm .
3. Here you can swap maximum color as per the color type.
like:
Color Maximum Swap
a 1
b 2
... ....
z 26| Flag | PURGE - 2 Answers Deleting a linked list from the beginning
Hello,
- becky5868 April 29, 2013
I am trying the delete all the elements in a linked list in the beginning.
I used the following code, it seems like that it complied fine with ./a.out,
however, when I use valgrind ./a.out, it says there are memory errors.
Could you help me to fix the problem please?
Thank you!
void List::emptyTheList()
{
cout << "inside function emptyTheList() ";
cout <<"starting to traverse list to delete nodes"<<endl;
if (head==NULL)
{
cout<<"there is no elements in the list" <<endl;
}
else
{
DR *temp1;//DR is a class
temp1=head->getNext();
while(temp1!=NULL)
{
free(head);
head=temp1;
temp1=head->getNext();
}
}
} //END function emptyTheList()| Flag | PURGE - 2 Answers Amazon interview process: Do they consider a rejected candidate for a different role or a team?
If I interview for an SDE role with a team(say AWS) and fail. Can I apply for same(SDE) role at Lab126(part of Amazon) in next few weeks and still get a interview call if they think I am a good fit ? Or does the failing in previous interview means no interview calls for next 6 months ?
- seibroski April 25, 2013
Similarly what if I fail interviewing for SDE and apply for TPM role in next few weeks may be with same or different division .| Flag | PURGE