SDE - 1

You are given a Singly Linked List of integers. You have to return true if the linked list is palindrome, else return false.

A Linked List is a palindrome if it reads the same from left to right and from right to left.

Example:

The lists (1 -> 2 -> 1), (3 -> 4 -> 4-> 3), and (1) are palindromes, while the lists (1 -> 2 -> 3) and (3 -> 4) are not.

You have been given string 'S' of length 'N' that may contain duplicate alphabets. Your task is to return the count of distinct subsequences of it.

For example:

For the given string “deed” :
The possible subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“d”}, {“dd”}, {“ed”}, {“ded”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}.

As, {“d”}, {“e”}, {“de”}, {“ed”} and {“ded”} are repeated. 

The distinct subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“dd”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}

Thus, the output will be 11. 

Note:

As the answer can be large, return your answer modulo 10^9  + 7.  

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

Can you solve this problem in O(N) time and O(1) space complexity?

You have been given two strings ‘STR1’ and ‘STR2’.

Your task is to find if ‘STR1’ is a subsequence of ‘STR2’.

A subsequence of a string is a new string that can be derived from the original string by deleting some characters (can be none) without changing the relative ordering of other characters.

Example:

‘ACE’ is a subsequence of ‘ABCDE’ because ‘ACE’ can be formed by deleting ‘B’ and ‘D’ without changing the relative order of characters. ‘ADB’ is not a subsequence of ‘ABCDE’ because we can get ‘ABD’ from ‘ABCDE’ but not ‘ADB’ and in ‘ADB’ relative order of ‘B’ and ‘D’ are different from original strings.

Note:

1.Strings ‘STR1’ and ‘STR2’ consists only of English uppercases.

2.Length of string ‘STR2’ will always be greater than or equal to the length of string ‘STR1’.

Example:

For example, the given ‘STR1’ is ‘BAE’ and ‘STR2’ is ‘ABADE’. 
String ‘STR1’ is a subsequence of string ‘STR2’ because ‘BAE’ can be formed by deleting ‘A’ and ‘D’ from ‘ABADE’ and the relative ordering of the characters of the string ‘ABADE’ persists.