Amazon placement Round 2 August 2013
Student 1 - Round 2
Q1. Given a string find the length of longest substring which has none of its character repeated?
for eg:
i/p string:
abcabcbb
length of longest substring with no repeating charcters: 3 (abc)
Q2. Given a link list with right pointers and each element of the list has a down link containg another link list with down poitners as:
5 -> 7 -> 9 -> 18
| | | |
10 6 14 20
| | | |
11 8 19 22
| | |
12 13 24
|
15
each right and down list are sorted.
Write a function flatten() which flattens this link list to a single link list with all the elemnts in sorted order as:
5->6->7->8->9->10->11->12->13->14->15->18->19->20->22->24
where can i get solutions to these problems?
ReplyDelete@manmeet solution to question 1
Delete#include
#include
#define NO_OF_CHARS 256
int min(int a, int b);
int longestUniqueSubsttr(char *str)
{
int n = strlen(str);
int cur_len = 1; // To store the lenght of current substring
int max_len = 1; // To store the result
int prev_index; // To store the previous index
int i;
int *visited = (int *)malloc(sizeof(int)*NO_OF_CHARS);
/* Initialize the visited array as -1, -1 is used to indicate that
character has not been visited yet. */
for (i = 0; i < NO_OF_CHARS; i++)
visited[i] = -1;
/* Mark first character as visited by storing the index of first
character in visited array. */
visited[str[0]] = 0;
/* Start from the second character. First character is already processed
(cur_len and max_len are initialized as 1, and visited[str[0]] is set */
for (i = 1; i < n; i++)
{
prev_index = visited[str[i]];
/* If the currentt character is not present in the already processed
substring or it is not part of the current NRCS, then do cur_len++ */
if (prev_index == -1 || i - cur_len > prev_index)
cur_len++;
/* If the current character is present in currently considered NRCS,
then update NRCS to start from the next character of previous instance. */
else
{
/* Also, when we are changing the NRCS, we should also check whether
length of the previous NRCS was greater than max_len or not.*/
if (cur_len > max_len)
max_len = cur_len;
cur_len = i - prev_index;
}
visited[str[i]] = i; // update the index of current character
}
// Compare the length of last NRCS with max_len and update max_len if needed
if (cur_len > max_len)
max_len = cur_len;
free(visited); // free memory allocated for visited
return max_len;
}
/* A utility function to get the minimum of two integers */
int min(int a, int b)
{
return (a>b)?b:a;
}
/* Driver program to test above function */
int main()
{
char str[] = "ABDEFGABEF";
printf("The input string is %s \n", str);
int len = longestUniqueSubsttr(str);
printf("The length of the longest non-repeating character substring is %d", len);
getchar();
return 0;
}
here is the output of question number 1
Deletewith full code :)
http://ideone.com/ltzF7O
what about the second 1 ??
ReplyDeleteThe second one is a simple merge sort.
ReplyDeleteYeah right,consider two consecutive nodes as roots of 2 separate LL and then merge them.Keep doing this till you reach the last node horizontally.
DeleteFor Problem 1 , Here is a simple solution :
ReplyDeleteScan the characters of given string one by one and at the same time keep inserting them into a hash table and increment MAX_LENGTH by 1.As soon as you find a character which is already existing in the hash table,save the value of MAX_LENGTH and clear all the values of hash table.Repeat the above steps till you reach the end of string.The final value of MAX_LENGTH would be the length of the max substring with no repetition of characters.