Just ran the code pasted above. Doesn't seem like it works right now. Can you please update?
simonzhu91
@simonzhu91
Posts made by simonzhu91

RE: Java: standard backtracking solution, 21ms

RE: Simple Recursive Java Solution With Explanation
@khaled_acmilan Absolutely! Thanks for pointing that out! I will update my solution now.

RE: Follow up questions discussion
In preparing for my Dropbox interview, I came across this problem and really wanted to find the ideas behind the follow up questions (as these were the questions that the interviewer was most interested in, not the code itself). Since this is the only post with the follow up discussion, i'll comment here! @yujun gave a great solution above and I just wanted to add a bit more to help future interviewees.
To find duplicate files, given input of String array is quite easy. Loop through each String and keep a HashMap of Strings to Set/Collection of Strings: mapping the contents of each file to a set of paths with filename concatenated.
For me, instead of given a list of paths, I was given a Directory and asked to return List of List of duplicate files for all under it. I chose to represent a Directory like:
class Directory{ List<Directory> subDirectories; List<File> files; }
Given a directory, you are asked how you can find duplicate files given very large files. The idea here is that you cannot store contents in memory, so you need to store the file contents in disk. So you can hash each file content and store the hash as a metadata field for each file. Then as you perform your search, store the hash instead the file's contents in memory. So the idea is you can do a DFS through the root directory and create a
HashMap<String, Set<String>>
mapping each hash to the Set of filepaths + filenames that correspond to that hash's content.(Note: You can choose BFS / DFS to traverse the Path. I chose DFS as it is more memory efficient and quicker to code up.)
Follow Up: This is great, but it requires you to compute the hash for every single file once, which can be expensive for large files. Is there anyway you can avoid computing the hash for a file?
One approach is to also maintain a metadata field for each file's size on disk. Then you can take a 2 pass approach:
 DFS to map each size to a set of paths that have that size
 For each size, if there are more than 2 files there, compute hash of every file, if any files with the same size have the same hash, then they are identical files.
This way, you only compute hashes if you have multiple files with the same size. So when you do a DFS, you can create a
HashMap<Integer, Set<String>>
, mapping each file's size to the list of file paths that have that size. Loop through each String in each set, get its hash, check if it exists in your set, if so, add it to yourList<String> res
otherwise add it into the set. In between each key (switching file sizes), you can add your res to yourList<List<String>>
.Will update with some code soon~~

RE: Java O(nuts) Explanation
Upvoted! Thanks for the explanation. First time solving problem, reading your solution really helps! :)
If possible, it would help if you explained your logic leading up to the solution a little more. Specifically, how did you arrive at your algorithm and why should we minimize (b  a)?

Simple Recursive Java Solution With Explanation
I used a simple recursive solution. After writing out many different numbers and tracing through each solution, you notice that you want to find the first digit that is greater than the digit to its right, decrease it by 1 and set the remaining digits to 9. The problem is that sometimes you have numbers for which this technique doesn't work.
Ex: 332 => 329, which isn't monotone increasing.
So I took a recursive approach. Each recursion, see if the number is monotone by looping through it once. If it is, return the solution. If not, find the first digit which is greater than digit to its right, decrease it by 1, and set remaining digit to 9. Then you recursively call the function again.
Note: It is O(n) per recursive call, so maybe I can consider a better approach, but seems to work for me and passes all the test cases :)
class Solution { public int monotoneIncreasingDigits(int N) { char[] num = Integer.toString(N).toCharArray(); calculateString(num); return Integer.parseInt(new String(num)); } public String calculateString(char[] num){ boolean flag = false; int index = 1; for(int i = 0; i < num.length  1; i++){ if(num[i] > num[i+1]){ flag = true; num[i]; index = i + 1; break; } } if(!flag){ return num.toString(); } while(index < num.length){ num[index++] = '9'; } return calculateString(num); } }
Thanks @khaled_acmilan for helping me provide a cleaner solution! :)

Sharing my Simple Straight Forward Java O(n) Solution  Explanation Included
The idea is a simple trick. First, you notice that at every single element in our original nums array, you have 2 choices: To earn or not to earn. Based on problem, whichever element you earn, you must delete any values of nums[i]1 and nums[i]+1. It helps to assume a sorted array so that you can place elements in ascending order to visualize the problem. You notice there that if you earn an element, you cannot earn its immediate unequal neighbors on both sides.
You also notice that if you have duplicate values in nums array, if you earn one of them, you end up earning all of them. This is because you have deleted its neighbors and therefore make its remaining duplicates "undeletable". This is important because you notice the problem simplifies to which values can earn you the largest total.
So I aggregated the sums into a sums array to map each value (array's index) with the total sum you can earn by deleting all elements of that value (array's value). Then write a for loop to compute the maximum sum ending at i At each step, your sum can either depend on your previous sum or the prior plus the current. You use a greedy algorithm to always pick the maximum value for each i.
*** Notice that when you create sums array, it naturally orders (sorts) the elements for you in ascending order so you can traverse it and get its immediate unequal neighbors on both sides in O(1).
sum[i] = Max(sum[i1], sum[i2] + sum[i])
class Solution { public int deleteAndEarn(int[] nums) { int[] sum = new int[10002]; for(int i = 0; i < nums.length; i++){ sum[nums[i]] += nums[i]; } for(int i = 2; i < sum.length; i++){ sum[i] = Math.max(sum[i1], sum[i2] + sum[i]); } return sum[10001]; } }

RE: [Java] Easy DP Solution
@luckman said in [Java] Easy DP Solution:
dp = new int[10003];
Kind of a silly question, but trying to understand the logic.
Can you explain the logic behind dp[i] and what it represents? 
RE: Java 20 lines very easy solution 7ms with explanation
What is the runtime of this algorithm? O(n^2)?