Posts

DFS vs BFS

Image
  DFS vs BFS There are two ways to traverse the tree: DFS  depth first search  and BFS  breadth first search . Here is a small summary Let's use this problem to discuss the difference between  iterative BFS traversal with the queue  and  iterative DFS preorder traversal with the stack . Both start from the root and go down, both use additional structures, what's the difference? Here is how it looks at the big scale: BFS traverses level by level, and DFS first goes to the leaves. Now let's go down to the implementation. The idea is similar: Push root into queue (BFS) or stack (DFS). At each step pop out one node, and push its children into stack/queue. For BFS: pop out from the  left , first push the  left  child, and then the  right  one. For DFS: pop out from the  right , first push the  right  child, and then the  left  one.

Million, Billion, Trillion: A Breakdown

Image
Million, Billion, Trillion: A Breakdown 1,000,000 is a million,   1,000,000,000 is a billion,   1,000,000,000,000 is a trillion,   1,000,000,000,000,000 is a quadrillion , and so on.

Important Linux Commands

  ls -lrt → command lists the contents of the directory with all the details, in reverse order of their modification time (older files will be displayed first) ls -lrth → This will list the contents of the current directory showing more information and sorting them so the most recently modified file will be displayed last. The h flag makes the file sizes more human friendly! chmod 755 <name> → chmod 755 sets the 755 permission for a file. 755 means full permissions for the owner and read and execute permission for others. ln -s 14.9.0-SNAPSHOT current → Create a current tag and mapped to current version. To link files in the same directory Update Any File → sed -i 's/10.46.87.148/10.46.87.115/g' journal.sch textToFind → 10.46.87.148 replaceText → 10.46.87.115 FileName → journal.sch . SED is a text stream editor used on Unix systems to edit files quickly and efficiently Untar a tar file → tar -xvzf filename.tar Rmove a folder → rm -r folderName netstat -anpe | grep &q

B Tree

 B-Trees are a type of self-balancing, multi-way tree data structure that are optimized for systems that have slow or limited access to disk storage. Unlike binary trees, where each node has at most two children, a B-Tree node can have multiple children. This allows B-Trees to store large amounts of data efficiently while maintaining a relatively shallow height. In a B-Tree, each node has a specific number of keys and associated values, called "entries". The keys act as pointers to the values, and are used to determine which node to follow during a search. The entries in each node are sorted in ascending order, and the values are stored in the leaf nodes. The root node, internal nodes, and leaf nodes are all stored on disk, making B-Trees well-suited for large data sets that can't fit into memory. When a node becomes full and needs to be split, it is divided into two new nodes, with some of its entries being moved to the new node. When a node becomes under-full, it may me

TWO SUM

Given an array of integers   nums  and an integer   target , return   indices of the two numbers such that they add up to  target . You may assume that each input would have  exactly  one solution , and you may not use the  same  element twice. You can return the answer in any order. Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3: Input: nums = [3,3], target = 6 Output: [0,1]   Constraints: 2 <= nums.length <= 10 4 -10 9  <= nums[i] <= 10 9 -10 9  <= target <= 10 9 Only one valid answer exists. Solution 1: HashMap We need to find 2 numbers  a ,  b  so that  a + b = target . We need a HashMap datastructure to store elements in the past, let name it  seen . The idea is that we iterate  b  as each element in  nums , we check if we found  a  (where  a = target - b ) in the past. If  a  exists in  seen  then we already f

GIT Rebase vs Merge

Image
  How does Git Work? For understanding the working of git, we need to understand the two fundamental concepts in git which is git commit and git branch. Let’s understand these two terms respectively. What is a Commit? Commit is defined as the location where the code and its changes are stored.  In git merge, looking at the end diagram, one can make out Commit A and B came from the feature branch. However, in the git-rebase diagram, it is difficult to understand where commits A and B came from. Therefore, we do git merge when we want our team to understand logs in a way where they can identify where each commit is coming from. We use Git Rebase when the logs of the repository will not be referred by anyone else. To summarise, we can use Git Rebase, when we are working on branches, which cannot be seen by other developers. And we use Git Merge when the target and source branch can be viewed by other developers. How can Git Rebase and Git Merge be used together? Let us take an example if

What is Vendor lock-in in cloud computing

Image
Vendor lock-in refers to a situation where the cost of switching to a different vendor is so high that the customer is essentially stuck with the original vendor. Because of financial pressures, an insufficient workforce, or the need to avoid interruptions to business operations, the customer is "locked in" to what may be an inferior product or service. Imagine an office has coffee brought in by a coffee vendor, and this vendor requires specific coffee machines in the office that only the vendor sells. Now imagine there is a steep decline in the quality of the coffee that this vendor delivers. Switching to a new coffee vendor would mean the old machines they purchased become useless, as the switch likely requires the purchase of new coffee-making equipment. Given the hassle and added expense of replacing every coffee machine, the workers in the office would be effectively locked into their agreement with their old vendor and forced to drink inferior coffee. A real-world examp

SQL vs NOSQL

Select Nth Highest Salary

  select   min (salary)  from     ( select   distinct  salary  from  emp  order   by  salary  desc )    where  rownum < 3;   In   order   to  calculate the  second  highest salary use rownum < 3   In   order   to  calculate the third highest salary use rownum < 4  

Database Indexing

Image
 Database is divided into logical blocks and each block contains data. CPU works along with RAM. One by one Block loads into the RAM and CPU reads the block if the record is not found then another block will load into the memory. If we need to store 10000 records and 1 block can store 100 records. No. of blocks required = 10000/100->100 blocks. Indexing basically reduces the I/O cost means it reduces the number of blocks that get loaded in the RAM.    Block Size -> 1000 Bytes  Record Size -> 250 Bytes   Total No of records -> 10000   Records in a block -> 1000/250-> 4 records   Total No of blocks required -> 10000/4 -> 2500    Suppose it is taking 1 ms to read 1 block.    In best case it will take -> 1 ms    In worst case, it will be the last record -> 2500 ms   Average Case -> 2500/2 = 1250 (N/2)   If the data is sorted then we can implement binary search. Time Complexity will be log N Log2 2500 -> 12 The time complexity is very much reduced with so

Design a Flight Aggregator Service

Java 8 : Find the number starts with 1 from a list of integers

  List<Integer> list = List. of ( 12 , 32 , 14 , 15 , 56 ); //Result->12,14,15 List<String> listString = list.stream().map(String::valueOf).collect(Collectors.toList()); List<String> result1 = listString.stream().filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result1-->" +result1); List<String> result2 = list.stream().map(x->x+ "" ).filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result2-->" +result2);

Construct Binary Tree from Preorder and Inorder Traversal

Image
  Given two integer arrays   preorder   and   inorder   where   preorder   is the preorder traversal of a binary tree and   inorder   is the inorder traversal of the same tree, construct and return   the binary tree .   Example 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Example 2: Input: preorder = [-1], inorder = [-1] Output: [-1]