The Fellow Programmer

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to] , reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK . Thus, the itinerary must begin with JFK . Note: If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"] . All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary. One must use all the tickets once and only once. Example 1: Input: [["MUC", "LHR...

Given a positive integer n , find the least number of perfect square numbers (for example, 1, 4, 9, 16, ... ) which sum to n . Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.   class Solution {     public int numSquares(int n) {    int[] dp = new int[n + 1];     int near, min;     for (int i = 1; i <= n; i++) {         near = (int) Math.sqrt(i);          min = dp[i - 1];         for (int j = near; j > 0; j--) {                 min = Math.min(dp[i - j * j], min);         }         dp[i] = min + 1;     }     return dp[n]; } } Try it on Leetcode Here, we are going to solv...

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123 . Find the total sum of all root-to-leaf numbers. Note:  A leaf is a node with no children. Example: Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12 . The root-to-leaf path 1->3 represents the number 13 . Therefore, sum = 12 + 13 = 25 . Example 2: Input: [4,9,0,5,1] 4 / \ 9 0  / \ 5 1 Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026 .   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *   ...

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3 Note: You must not modify the array (assume the array is read only). You must use only constant, O (1) extra space. Your runtime complexity should be less than O ( n 2 ). There is only one duplicate number in the array, but it could be repeated more than once. METHOD 1:   class Solution {     public int findDuplicate(int[] nums) {         ArrayList<Integer>list = new ArrayList<Integer>();                 for(int num:nums){             if(list.contains(num)){   ...

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". METHOD 1:   class Solution { public List<Intege...

Given n , how many structurally unique BST's (binary search trees) that store values 1 ...  n ? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3   class Solution {     public int numTrees(int n) {          int countUniqueTrees[] = new int[n + 1];         countUniqueTrees[0] = 1;     countUniqueTrees[1] = 1;       for (int i = 2; i <= n; i++)      {         for (int j = 1; j <= i; j++)          {             countUniqueTrees[i] = countUniqueTrees[i] + (countUniqueTrees[...

Given a complete binary tree, count the number of nodes. Note: Definition of a complete binary tree from Wikipedia : In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2 h nodes inclusive at the last level h. Example: Input: 1 / \ 2 3 / \ / 4 5 6 Output: 6   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  * ...

Given an integer n and an integer start . Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length . Return the bitwise XOR of all elements of nums . Example 1: Input: n = 5, start = 0 Output: 8 Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8. Where "^" corresponds to bitwise XOR operator. Example 2: Input: n = 4, start = 3 Output: 8 Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8. Example 3: Input: n = 1, start = 7 Output: 7 Example 4: Input: n = 10, start = 5 Output: 2   Constraints: 1 <= n <= 1000 0 <= start <= 1000 n == nums.length   class Solution {     public int xorOperation(int n, int start) {         int i = 1, result = 0;         while(i<=n){             result ^= start;  ...

Given a non-empty  array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1: Input: [2,2,3,2] Output: 3 Example 2: Input: [0,1,0,1,0,1,99] Output: 99 METHOD 1:   class Solution {     public int singleNumber(int[] nums) {         Arrays.sort(nums);         int i, length = nums.length, result=0;         for(i=0;i<length;){             if(i==length-1){                 result = nums[i];                 break;        ...

The demons had captured the princess ( P ) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight ( K ) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons, so the knight loses health ( negative integers) upon entering these rooms; other rooms are either empty ( 0's ) or contain magic orbs that increase the knight's health ( positive integers). In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. For example, given the dungeon below, the initial health o...

The set [1,2,3,..., n ] contains a total of n ! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" "231" "312" "321" Given n and k , return the k th permutation sequence. Note: Given n will be between 1 and 9 inclusive. Given  k  will be between 1 and n ! inclusive. Example 1: Input: n = 3, k = 3 Output: "213" Example 2: Input: n = 4, k = 9 Output: "2314"   class Solution {     public String getPermutation(int n, int k) {     int[] factorial = new int[n];     int i;     StringBuilder sb = new StringBuilder();     ArrayList<Integer> num = new ArrayList<Integer>();     for (i = 0; i < n; i++) {         num.add(i + 1);         factorial[i] = i == 0 ? 1 : i * factorial[i - 1];     ...

Given a string S , consider all duplicated substrings : (contiguous) substrings of S that occur 2 or more times.  (The occurrences may overlap.) Return any duplicated substring that has the longest possible length.  (If S does not have a duplicated substring, the answer is "" .) Example 1: Input: "banana" Output: "ana" Example 2: Input: "abcd" Output: "" Note: 2 <= S.length <= 10^5 S consists of lowercase English letters.   class Solution {     public int search(int L, int a, long modulus, int n, int[] nums) {   long h = 0;   for(int i = 0; i < L; ++i) h = (h * a + nums[i]) % modulus;   HashSet<Long> seen = new HashSet();   seen.add(h);   long aL = 1;   for (int i = 1; i <= L; ++i) aL = (aL * a) % modulus;   for(int start = 1; start < n - L + 1; ++start) {     h = (h * a - nums[start - 1] * aL % modulus + modulus) % modulus;     h ...

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Given linked list -- head = [4,5,1,9], which looks like following: Example 1: Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function. Example 2: Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function. Note: The linked list will have at least two elements. All of the nodes' values will be unique. The given node will not be the tail and it will always be a valid node of the linked list.   /**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ...

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index. According to the  definition of h-index on Wikipedia : "A scientist has index  h  if  h  of his/her  N  papers have  at least   h  citations each, and the other  N − h  papers have  no more than   h  citations each." Example: Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0 , 1, 3, 5, 6 citations respectively.   Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, her h-index is 3 . Note: If there are several possible values for  h , the maximum one is taken as the h-index.   class Solution { ...

Write a function that reverses a string. The input string is given as an array of characters char[] . Do not allocate extra space for another array, you must do this by modifying the input array  in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters .   Example 1: Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Example 2: Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]   class Solution {     public void reverseString(char[] s) {        int start = 0, end = s.length-1;         while(start  < end){             char temp = s[end];             s[end] = s[start];             s[start] = temp;      ...

Problem Statement: Write a program to find a perfect square between 1 and 500 in C using while loop. HINT: A number is said to be perfect square if multiples of a number are same. eg., 16 is perfect square because it's multiples are 4 * 4.   #include <stdio.h> #include <math.h> int main() {     int start=1;    while(start<500){ //change 500 to any n        if (sqrt(start) == (int)sqrt(start)) {            printf("%d ",start);        }        start++;    }     return 0; } Run above code now Here we are going to solve using sqrt() in <math.h>. sqrt() returns double value. (int)sqrt() returns int value. If both float and int are same, then it is a perfect square. [i.e., 4.0 == 4] and print that number. You can also incre...

Given a 2D board containing 'X' and 'O' ( the letter O ), capture all regions surrounded by 'X' . A region is captured by flipping all 'O' s into 'X' s in that surrounded region. Example: X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X Explanation: Surrounded regions shouldn’t be on the border, which means that any 'O'  on the border of the board are not flipped to 'X' . Any 'O'  that is not on the border and it is not connected to an 'O'  on the border will be flipped to 'X' . Two cells are connected if they are adjacent cells connected horizontally or vertically.   class Solution {     static int rows, cols;     public void solve(char[][] board) {     if (board == null || board.length == 0) return ;          rows = board.length;     cols = board[0].length;      ...

Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither. IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots ("."), e.g., 172.16.254.1 ; Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid. IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (":"). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases). However, we don't replace a consecutive group of zero value with a single empty group using two...

Invert a binary tree. Example: Input: 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *         this.right = right;  *     }  * }  */ class Solution {     public TreeNode invertTree(TreeNode root) {     if (root == null) {     ...

There are n cities connected by  m flights. Each flight starts from city  u and arrives at  v with a price w . Now given all the cities and flights, together with starting city src and the destination  dst , your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1 . Example 1: Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 Output: 200 Explanation: The graph looks like this: The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture. Example 2: Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 Output: 500 Explanation: The graph looks like this: The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture. Constraints: The number of nodes  n will be in range [1, 100] , with nodes labeled from 0 to n - 1 . The size of...