Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1 Input: num1 = "2", num2 = "3" Output: "6" Example 2 Input: num1 = "123", num2 = "456" Output: "56088" Note The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note You may assume k is always valid, 1 ≤ k ≤ BST's total elements. Example 1 Input: root = [3,1,4,null,2], k = 1 Output: 1 Example 2 Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3 ``` ### Follow-up What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently?
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1 Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2 Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4 Note You may assume k is always valid, 1 ≤ k ≤ array's length. Solution Average time complexity: O(n) if we don’t need the sorted output, otherwise O(n+kLogk)
Given an array of strings, group anagrams together. Example Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note All inputs will be in lowercase. The order of your output does not matter. Solution (naive) Time: O(Nklogk), k: length of the longest word Space: O(Nk) sort each word and use it the sorted str as a key to the lookup dictionary class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: ans = collections.
Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space? Observation: Solution: /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if (head == null) return null; ListNode slow = head; ListNode fast = head; boolean hasCycle = false; while (slow.
Given a linked list, determine if it has a cycle in it. Follow-up Can you solve it without using extra space? Solution # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ slow = head fast = head while fast: # fast reaches the end, no cycle was detected if fast and not fast.
Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = "ABCCED", return true. Given word = "SEE", return true. Given word = "ABCB", return false.
Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Note If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns.
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack. Example MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.