babbupandey
BAN USER 0of 0 votes
AnswersGiven a string, find out whether the string contains any repeated characters or not. For example, 'abcd' does not contain any repeated character 'abcdaefgh' contains repeated character ('a' is repeated twice).
 babbupandey in United States for Big Data
As part B, I was asked if suppose it is given that string contains no more than 20 characters, will you change your algorithm in anyway to improve memory/time performance. Then he specifically added that there is a constraint on memory. Report Duplicate  Flag  PURGE
Knewton Computer Scientist Algorithm
I assumed all characters are ASCII, and then I created a bool array of 200, reading one character at a time and then marking the corresponding ASCII (numeric) value as true every time I encounter a character. When I see a character and its value in bool array has already been set to true, then I returned 'duplicate' otherwise 'correct'
For the second part, I said that since we know the upper limit of string length, we can follow the O(n^2) approach (check each character by all other characters). We will be repeating the loop at most 400 times (20x20). The interviewer, I guess, was not impressed
Length of string is less than 20 chars.
 babbupandey August 22, 2012This will work for the given input, I think you are getting confused by the fact that he is using j in the loop, that is only to counter the j++ in the for loop.
 babbupandey August 21, 2012I followed the exact 2pass approach, I dunno what happened and why wasn't I called for the next round.
 babbupandey August 21, 2012I gave the following answer (didn't get through, help me figure out if I did something wrong)
void group(int[] arr) {
int begin = 0, end = arr.length;
while(begin<end) {
/* group all positive together at the end*/
if(arr[begin]>0) {
int temp = arr[begin];
arr[begin] = arr[end];
arr[end] = temp;
end;
} else {
begin++;
}
}
/* At the end of previous loop, end will contain the first index of negative number */
end; //This will contain the endindex of subarray where +ve and zeros are mixed
begin = 0;
while(begin<end) {
/* group all zero together at the end*/
if(arr[begin]==0) {
int temp = arr[begin];
arr[begin] = arr[end];
arr[end] = temp;
end;
} else {
begin++;
}
}
}

babbupandey
August 20, 2012 Ashish: I may understood the question differently, but in your second output 'a' is coming before 'e', should't 'a' be the last character?
 babbupandey August 20, 2012I am thinking of the following approach, please correct me if I am wrong:
Input = (0,10^6] length string
Read characters one by one
Keep a bitmap of the read characters, if the character has been read, then discard it and move to next
Keep a maxheap of characters, put the incoming character in the maxheap
Remove the characters from maxheap onebyone and we will have the beautiful string
@rkt  each insert takes O(h) time, where 'h' is the height of the tree; therefore when we are inserting any node, we are making at most 'h' comparisons... which is what his algorithm seems to be doing.
 babbupandey August 19, 2012Why can't we follow this approach, and I know sorting has been discussed before but please bear with me:
1. Sort the array
2. Keep two variable, left_sum, right_sum
3. Keep two variable more variable, low, high
low = 0;
high = arr.length  1;
while (low < high) {
if (low_sum > right_sum) {
high;
right_sum = arr[high];
}
else if (low_sum < right_sum) {
low;
left_sum = arr[low];
}
else {
if(low>=high) break;
high;
right_sum = arr[high];
low;
left_sum = arr[low];
}
}
Should this not give a minimised partition? I also checked with the dynamic programming question, it looks better than O(n^2 k) solution, also, we do not need to have the numbers in the range of [0,k]  which means we can do it for negative numbers too.
Please let me know your thoughts
This looks the same to me as making the first element A[0] as root, then inserting the next elements into the BST like you do into ordinary BST. Correct me if I am wrong
 babbupandey August 16, 2012use A*
 babbupandey August 14, 2012Open Chat in New Window
I think we need to calculate the probability, rather than choosing from the given options. The options look like part of the question and we are not required (and should not) choose the given values.
 babbupandey August 26, 2012My answer:
Since there are three unique answers, each has 1/3 chance of being correct. Also (0.25) appears twice, so it has 1/2 probability of being chosen; the rest have 1/4 probability of being chosen. So,
P(0.25 is right answer and it is chosen) = P(0.25 is correct) x P(0.25 is chosen) = 1/3 x 1/2 = 1/6
P(0.6 is correct and it is chosen) = 1/3 x 1/4 = 1/12
P(0.5 is correct and it is chosen) = 1/12
P(choosing randomly and it being correct) = 1/4 x 1/3 = 1/12