A rooted tree is a free tree in which one of the vertices is distinguished from the others. We call the distinguished vertex the root of the tree. We often refer to a vertex of a rooted tree as a node5 of the tree. Given figure shows a rooted tree on a set of 12 … Read more
Question Implement strstr(). Returns the index of the first occurrence of needle in haystack, or –1 if needle is not part of haystack. Solution: O(nm) runtime, O(1) space – Brute force: There are known efficient algorithms such as Rabin-Karp algorithm, KMP algorithm, orthe Boyer-Moore algorithm. Since these algorithms are usually studied in an advancedalgorithms class, … Read more
Question: Given a string, determine if it is a palindrome, considering only alphanumeric charactersand ignoring cases.For example,“A man, a plan, a canal: Panama” is a palindrome.“race a car” is not a palindrome Example Questions Candidate Might Ask: Q: What about an empty string? Is it a valid palindrome?A: For the purpose of this problem, we … Read more
Solution of LeetCode Two Sum III – Data structure design using java add – O(n) runtime, find – O(1) runtime, O(n 2 ) space – Store pair sums in hash table: We could store all possible pair sums into a hash table. The extra space needed is in the order of O(n2 ). You would … Read more
Solution of Leetcode Two Sum II – Input array is sorted using java O(n log n) runtime, O(1) space – Binary search: For each element x, we could look up if target – x exists in O(log n) time by applying binary search over the sorted array. Total runtime complexity is O(n log n). O(n) … Read more
Condition: The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution Solution: O(n2 ) runtime, O(1) … Read more