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.
Workday HCM Course
ReplyDeleteGain expertise in Workday Human Capital Management, including Core HR, Payroll, Recruiting, and Talent Management. Get hands-on projects and certification preparation.