The Fellow Programmer

There are 2N people a company is planning to interview. The cost of flying the i -th person to city A is costs[i][0] , and the cost of flying the i -th person to city B is costs[i][1] . Return the minimum cost to fly every person to a city such that exactly N people arrive in each city. Example 1: Input: [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people  interviewing in each city. Note: 1 <= costs.length <= 100 It is guaranteed that costs.length is even. 1 <= costs[i][0], costs[i][1] <= 1000   class Solution {     public int twoCitySchedCost(int[][] costs) {         Arrays.sort(costs, (a, b...

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 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];     ...

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

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

Given a set of distinct positive integers, find the largest subset such that every pair (S i , S j ) of elements in this subset satisfies: S i % S j = 0 or S j % S i = 0. If there are multiple solutions, return any subset is fine. Example 1: Input: [1,2,3] Output: [1,2] (of course, [1,3] will also be ok) Example 2: Input: [1,2,4,8] Output: [1,2,4,8]   class Solution {     public List<Integer> largestDivisibleSubset(int[] nums) {     List<Integer> result = new ArrayList<Integer>();     if(nums==null||nums.length==0)         return result;       Arrays.sort(nums);       int[] arr = new int[nums.length];     int[] index = new int[nums.length];     Arrays.fill(arr, 1);     Arrays.fill(index, -1);       int max=0;     int maxIndex=-1;   ...

Design a data structure that supports all following operations in average O(1) time. insert(val) : Inserts an item val to the set if not already present. remove(val) : Removes an item val from the set if present. getRandom : Returns a random element from current set of elements. Each element must have the same probability of being returned. Example: // Init an empty set. RandomizedSet randomSet = new RandomizedSet(); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomSet.insert(1); // Returns false as 2 does not exist in the set. randomSet.remove(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomSet.insert(2); // getRandom should return either 1 or 2 randomly. randomSet.getRandom(); // Removes 1 from the set, returns true. Set now contains [2]. randomSet.remove(1); // 2 was already in the set, so return false. randomSet.insert(2); // Since 2 is the only number in the set, getRandom always return 2. randomSet.getRandom(); ...