The Fellow Programmer

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 call...

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 Constraints: The input strings only contain lower case letters. The length of both given strings is in range [1, 10,000].   public class Solution {     public boolean checkInclusion(String s1, String s2) {         if (s1.length() > s2.length())             return false;         int[] s1Arr = new int[26];         int s1Length = s1.length(), s2Length = s2.length();         for (int ...

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 ...   /**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode() {}  *     ListNode(int val) { this.val = val; }  *...

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 [3] and [3,-2...

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.   class TrieNode {         private TrieNode[] nodeLinks;     public boolean isEnd;     public TrieNode() {         nodeLinks = new TrieNode[26];     }     public boolean containsKey(char ch) {         return nodeLinks[ch -'a'] != null;     }     public TrieNode get(char ch) {         return nodeLinks[ch -'a'];  ...

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. Note: The length of num is less than 10002 and will be ≥ k . The given num does not contain any leading zero. Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes. Example 3: Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0.   class Solution {     public String removeKdigits(String num, int k) {         for (int i = 1; i <= k; i++)             num = toRemoveOneDigit(num);     ...

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once. Example 1: Input: [1,1,2,3,3,4,4,8,8] Output: 2 Example 2: Input: [3,3,7,7,10,11,11] Output: 10 Note: Your solution should run in O(log n) time and O(1) space. METHOD 1:   class Solution {     public int singleNonDuplicate(int[] nums) {         int result = 0;         for(int num:nums)             result ^= num;         return result;     } } Try it on Leetcode Here we are going to do XOR operation. Because, in the problem itself they mentioned that each number in array repeated twice and only one number occurs once. Also XOR of same number is 0 and i...

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535). Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor , "flood fill" the image. To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor. At the end, return the modified image. Example 1: Input: image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Explanation: From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected by a path of the same color as the starting pixel are colored with the new color. ...

In a town, there are N people labelled from  1 to N .  There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town judge trusts nobody. Everybody (except for the town judge) trusts the town judge. There is exactly one person that satisfies properties 1 and 2. You are given trust , an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b . If the town judge exists and can be identified, return the label of the town judge.  Otherwise, return -1 .   Example 1: Input: N = 2 , trust = [[1,2]] Output: 2 Example 2: Input: N = 3 , trust = [[1,3],[2,3]] Output: 3 Example 3: Input: N = 3 , trust = [[1,3],[2,3],[3,1]] Output: -1 Example 4: Input: N = 3 , trust = [[1,2],[2,3]] Output: -1 Example 5: Input: N = 4 , trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] Output: 3   Note: 1 <= N <= 1000 trust.length <= 10000 ...

Given a positive integer num , write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt . Example 1: Input: 16 Output: true Example 2: Input: 14 Output: false   class Solution {     public boolean isPerfectSquare(int num) {        for (long i = 1; i * i <= num; i++) {                if ((i)*(i) == num) {                 return true;             }         }         return false;             } } Try it on Leetcode Here, they mentioned in problem not to use in-build methods. We are going to use basic idea to solve this...

You are given an array  coordinates , coordinates[i] = [x, y] , where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane. Example 1: Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true Example 2: Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: false   Constraints: 2 <= coordinates.length <= 1000 coordinates[i].length == 2 -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4 coordinates  contains no duplicate point.   class Solution {     public boolean checkStraightLine(int[][] coordinates) {             double tSlope = 0;         int length = coordinates.length - 1, i;                  double slope = (double)(coordinates[1][1] - coordinates[0][1])...

In a binary tree, the root node is at depth 0 , and children of each depth k node are at depth k+1 . Two nodes of a binary tree are cousins if they have the same depth, but have different parents . We are given the root of a binary tree with unique values, and the values x  and y  of two different nodes in the tree. Return  true  if and only if the nodes corresponding to the values x and y are cousins.   Example 1: Input: root = [1,2,3,4] , x = 4 , y = 3 Output: false Example 2: Input: root = [1,2,3,null,4,null,5] , x = 5 , y = 4 Output: true Example 3: Input: root = [1,2,3,null,4] , x = 2, y = 3 Output: false   Note: The number of nodes in the tree will be between 2 and 100 . Each node has a unique integer value from 1 to 100 .   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *...

Given an array of size n , find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2   class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } } Here, we are sorting the entire array using sort() of Arrays class. Then, number at index position n/2 would be a majority element. There is no chance of wrong values in odd or even length.   Below is another method using HashMap. METHOD 2: class Solution { public int majorityElement(int[] nums) { HashMap<Integer, Integer>list = new HashMap<Integer, Integer>(); int ...

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1. Examples: s = "leetcode" return 0. s = "loveleetcode", return 2. Note: You may assume the string contain only lowercase letters. class Solution {     public int firstUniqChar(String s) {         int length = s.length();         String str;         for(int i=0;i<length;i++){             if(i==length-1){                 str = s.substring(0, i);             }             else{                 str = s.substring(0,i)+s.sub...

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation. Example 1: Input: 5 Output: 2 Explanation: The binary representation of 5 is 101  (no leading zero bits), and its complement is 010.  So you need to output 2. Example 2: Input: 1 Output: 0 Explanation: The binary representation of 1 is 1  (no leading zero bits), and its complement is 0.  So you need to output 0. Note: The given integer is guaranteed to fit within the range of a 32-bit signed integer. You could assume no leading zero bit in the integer’s binary representation. This question is the same as 1009:  https://leetcode.com/problems/complement-of-base-10-integer/ class Solution {     public int findComplement(int num) {                 int totalBits = (int)(Math.floor(Math.log(num) / Math.log(2))) + 1; ...

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false. Each letter in the magazine string can only be used once in your ransom note. Note: You may assume that both strings contain only lowercase letters. canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true   class Solution { public boolean canConstruct(String ransomNote, String magazine) { StringBuilder sb = new StringBuilder(); sb.append(magazine); int length = ransomNote.length(), count = 0; for(int i=0;i<length;i++){ int index = sb.indexOf(ransomNote.charAt(i)+""); if(index != -1){ sb.delete(index, index+1); count++; ...

You're given strings J representing the types of stones that are jewels, and S representing the stones you have.  Each character in S is a type of stone you have.  You want to know how many of the stones you have are also jewels. The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A" . Example 1: Input: J = "aA", S = "aAAbbbb" Output: 3   Example 2: Input: J = "z", S = "ZZ" Output: 0   Note: S and J will consist of letters and have length at most 50. The characters in J are distinct. METHOD 1: class Solution {     public int numJewelsInStones(String J, String S) {        int res=0;        for(char c : S.toCharArray()){            if(J.indexOf(c) != -1){       ...

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.   Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API. Example: Given n = 5, and version = 4 is the first bad version. call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version.      METHOD 1:     /* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */...