Skip to main content

Posts

Recent posts

LeetCode 51 N Queens

The problem Input integer n Place n queens on n x n  board Q  means queen at cell .  Means empty space Queen can move in any direction Horizontally Up Down Diagonal neg + pos The Trick, let's say for 4x4 Understanding Notice that each and every queen has to be in a different row ! Notice that each and every queen has to be in a different column ! Notice that each and every queen has to be in a different positive diagonal ! Notice that each and every queen has to be in a different negative diagonal ! State - Set - is queen in column, posDiag (row-col), negDiag (row+col) Which rows have queen - do not have to store in state we just loop the rows Which columns have queen - store in state ! Which posDiag have queen - store in state! Which negDiag have queen - store in state! Trick posDiag -> row - column = constant Every time we increase row we increase column negDiag -> row + column = constant Every time we increase row we decrease column Loop 1st queen 1st row Can put first q

LeetCode 347. Top K Frequent Elements

Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order . Example 1: Input:  nums = [1,1,1,2,2,3], k = 2 Output:  [1,2] Example 2: Input:  nums = [1], k = 1 Output:  [1] Option 1 - Map to count + Sort to get top k - O(nlgn) We need to count what is the freq or how many times an item appeared. The obvious thing is  for each item  put it in a hashmap where Key is the item Value is the number of times it appeared Now the only thing that is left is to sort this hashtable. sorting is O(nlgn), placing everyting and counting is O(n) so this makes it overall O(nlgn) Option 2 - Improvement over option 1 - Instead of sorting use a Heap This is a common thing when you need to sort but the  core of the problem is not sorting  but as in this example only get top k then we could utilize a heap. We still build a  map  as in option 1 which takes O(n) this is the counting map. Building a heap  heapify  takes O(n) Remove  each

LeetCode 129 Sum Root to Leaf Number

  LeetCode 129 Sum Root to Leaf Numbers Given a root of binary tree containing digits from 0 to 9 only. Return the total sum of all root to leaf. The question is taken from the book “ Elements of Programming Interviews in Python ” page 125 https://amzn.to/3y84FHQ We see we have here these routes to path 495 +491 +40 Which in total is 1026 Now let’s see how to solve it in java /** * 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 { // This is an excellent trick to save us from passing params. int total = 0; public int sumNumbers(TreeNode root) { sumNumbers(root, 0); return total; } private void sumNumbers(Tr

Java ForkJoin Pool CheatSheet

Java ForkJoin Pool # Java ForkJoin Pool 1. As it sounds, assist distribute work 2. From java 7 3. Based on Doug Lea's work 4. As it sounds, break to simpler tasks    1.  Ideally, no worker thread idle        1.  Threads steal work 5. Classes you use    1.  ForkJoinPool        1.   Implements ExecutorService        2.   `ForkJoinPool = new ForkJoinPool(int parallelism)`             1.   With no arg by default, numProcessors        3.   Pool adjusts its size! (though you specified number)   1.   Send ForkJoinPool Tasks with        1.    Execute() - asynchronous        2.    invoke() - sync awaits        3.    submit() - Async get Future    2.  ForkJoinTask        1.  isDone() - true when complete        2.  isCompletedNormally() - finished without exception        3.  isCompletedAbnormally() - true cancelled / exception 6.  How to use     1. Create `RecursiveTask`     2. Implement `compute()` in RecursiveTask to do your work        1. You can create additional tasks inside it, that&#

DynamoDb Read Capacity Units - RCU

1. DynamoDb Max Item Size is 400KB 2. 1 RCU is ~1 Read request from the DB 3. Why is it only roughly 1 read request because we could have multiple types of read requests 4. We could have a consistent read request 5. We could have an eventual consistent read request 6. We could have a transactional read request 4. If the item we read is up to 4kb and we read with eventual consistent than we could actual make 2 such items read with 1 RCU 5. If the item i up to 8KB and we make an eventual consistent read than we could have a single read request per second with 1 RCU 6. If the item is larger than 4KB and we want to perform a consistent read request than this would require 2 read request at least. 7. If we need a transactional read request for an item up to 8KB then we would need even 4 RCU 8. If we need a transactional read request for an item up to 4KB then we would need 2 RCU that is because transactional read requires 2 phase commit the first RCU would be for prepare and the secon

4 Core Patterns for SEO

Relevance Your content is relevant to keywords On-page optimization In the past, could just repeat keywords Today, content keywords should be related Think TOPIC Not keywords Divide web pages by topics not by keywords Many pages same topic—google will get confused Aggregate keywords to topics Identify primary keyword within topic Topic in Url's Not good too deep – isn't that important  http://programminghacks.com/java/tips/interview/best-java-interview-tips.htmls http://programminghacks.com/java/java-interview-tips.html Title tag title  tag Header tags <h1>⁣ – Best  description of the web page <h2>⁣ – Synonyms  to topic <h3+>⁣ – You  don't have to optimize Keyword density copy from results 1 – 5 How many times your keyword appear vs your total words in your page Use tool tools.seobook.com/general/keyword-density LSI Latent Semantic indexing Prove you are on that topic if you discuss java interview tips, I guesstimate problem coding works would be in your p