Problem Given two sequences, return the longest subsequence present in both of them. Examples Example 1: Input: text1 = "abcde", text2 = "ace" Output: "ace" Explanation: The longest common subsequence is "ace". Example 2: Input: text1 = "abc", text2 = "abc" Output: "abc" Explanation: The longest common subsequence is "abc". ...
Problem Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space. Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces. ...
Problem Given two strings s and t, return true if s is a subsequence of t, or false otherwise. OR Given two strings str1 and str2, find if str1 is a subsequence of str2. Subarrays vs Subsequences vs Subsets Definition Follow up Expected time complexity is linear. Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code? Examples Example 1: ...
Problem Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Please implement encode and decode Examples Example1 Input: ["lint","code","love","you"] Output: ["lint","code","love","you"] Explanation: One possible encode method is: "lint:;code:;love:;you" ...
Problem The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file. By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file. Examples Example 1 Input: "filetestbuffer" read(6) read(5) read(4) read(3) read(2) read(1) read(10) Output: 6, buf = "filete" 5, buf = "stbuf" 3, buf = "fer" 0, buf = "" 0, buf = "" 0, buf = "" 0, buf = "" ...
Problem Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters. Method read4: The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf. The return value is the number of actual characters read. Note that read4() has its own file pointer, much like FILE *fp in C. ...
Problem Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace or substitute a character Examples Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') ...
Problem Write a function that takes a string as input and returns the string reversed. Examples Example 1: Given s = "hello", return "olleh". Given s = “kodeknight” , return “thginkedok“. Solution Method 0 - Iterative, Not in Place In Java, string is immutable. So, cannot do in place!. public String reverseString(String s) { int n = s.length; char[] reversed = s.toCharArray(); return reverse(reversed); } ...
Problem Write an algorithm to find Whether Given String is palindrome or Not. Definition Palindrome Definition Examples Example 1: Input: str = "malayalam" Output: true Example 2: Input: str = "abc" Output: false Solution Method 1 - Recursion Algorithm If the first and last characters don’t match, return false (not a palindrome). If they match, remove the first and last characters and call the function recursively with the remaining substring. This continues until the entire string is checked. Code Java public Boolean isPalindrome(String s) { if (s.length()<2) { return true; } if (s.charAt(0) == s.charAt(s.length() - 1)) { return isPalindrome(s.substring(1, s.length() - 1)); } else { return false; } } ...
Problem Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Palindrome Definition Examples Example 1: Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. Example 2: Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome. ...