Skip to main content

Posts

MAY-20 2020 Challenge

Kth Smallest Element in a BST 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 3 / \ 1 4 \   2 Output: 1 Example 2: Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3 Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine? Solution in Java : class Solution {public int kthSmallest(TreeNode root, int k) {     Stack<TreeNode> stack = new Stack<TreeNode>();     TreeNode p = root;     while(p!=null){         stack.push(p);         p=p.left;     }     int i=0;     while(!stack.isEm...

MAY-19 2020 Challenge

Online stock Span Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day. The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price. For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].  Example 1: Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]] Output: [null,1,1,1,2,1,4,6] Explanation: First, S = StockSpanner() is initialized.  Then: S.next(100) is called and returns 1, S.next(80) is called and returns 1, S.next(60) is called and returns 1, S.next(70) is called and returns 2, S.next(60...

MAY-18 2020 Challenge

MAY-18 2020 Challenge :  Permutation in String Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1.  In other words, one of the first string's permutations is the substring of the second string . Example 1: Input:  s1 = "ab" s2 = "eidbaooo" Output: True Explanation:  s2 contains one permutation  of s1 ("ba") . Example 2: Input: s1= "ab" s2 = "eidboaoo" Output: False Note: - The input strings only contain lower  case letters. - The length of both given strings is in range [1, 10,000]. Solution in C++:  class Solution {     public boolean checkInclusion(String s1, String s2) {         int[] map = new int[128];         for (char c : s1.toCharArray()) {             map[c]++;         }     ...

MAY-17 2020 Challenge

17. Find All Anagrams in the String Given a string  s  and a  non-empty  string  p , find all the start indices of  p 's anagrams in  s . Strings consists of lowercase English letters only and the length of both strings  s  and  p  will not be larger than 20,100. The order of output does not matter. Example 1: Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc". Example 2: Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab". Solution in ...

MAY-16 2020 Challenge

16. Odd Even Linked List Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example 1: Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULL Example 2: Input: 2 ->1->3->5->6->4->7->NULL Output: 2->3->6->7->1->5->4->NULL Note: The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on ... Solution in Java : class Solution  { public ListNode oddEvenList(ListNode head) {     if(head == null)          return head;     ListNode result = head;     ListNode p1 = head;   ...

May-15 2020 Challenge

15. Maximum Sum Circular Subarray Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C. Here, a circular array means the end of the array connects to the beginning of the array.   (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.) Also, a subarray may only include each element of the fixed buffer A at most once.   (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.) Example 1: Input: [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3 Example 2: Input: [5,-3,5] Output: 10 Explanation:   Subarray [5,5] has maximum sum 5 + 5 = 10 Example 3: Input: [3,-1,2,-1] Output: 4 Explanation:   Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4 Example 4: Input: [3,-2,2,-3] Output: 3 Explanation:   Subarray [...

May-14 2020 Challenge

Implement Trie (Prifix Tree) Implement a trie with  insert ,  search , and  startsWith  methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true Note: You may assume that all inputs are consist of lowercase letters  a-z . All inputs are guaranteed to be non-empty strings. Solution in python: class Trie(object):    def __init__(self):       self.child = {}    def insert(self, word):       current = self.child       for l in word:          if l not in current:             current[l] = {}          current = current[l]       current['#']=1    def search(...