Posts

Dynamic Programming

Image
What is dynamic programming? It is a way of making your algorithm more efficient by storing some of the intermediate results and it works really well when your algorithm has a lot of repetitive computations. So that you don't have to repeat those computations over and over again.  I'm gonna give you a concrete example of how it works with Fibonacci Sequence (1, 1, 2, 3, 5, 8, ....). Let see how we can solve the problem using dynamic programming. There are typically three steps you can take: 1. Recursion. 2. Store (Memoize). 3. Bottom-up. Recursion solution   public static  int fibSeq (int n)   {       // this function return the value of Fibonacci Sequence at n position              if(n ==1 || n==2)            return 1;       else            return (fibSeq(n-1) + fibSeq(n-2));             } // Let call this function return value 5 fastly fibSeq(5); // Return 6765 value pretty quickly on my computer fibSeq(20); // Return  value 9227

Code Jam 2020 Qualification Round

Image
Problem: Vestigium  Vestigium means "trace" in Latin. In this problem we work with Latin squares and matrix traces. The  trace  of a square matrix is the sum of the values on the main diagonal (which runs from the upper left to the lower right). An  N -by- N  square matrix is a  Latin square  if each cell contains one of  N  different values, and no value is repeated within a row or a column. In this problem, we will deal only with "natural Latin squares" in which the  N  values are the integers between 1 and  N . Given a matrix that contains only integers between 1 and  N , we want to compute its trace and check whether it is a natural Latin square. To give some additional information, instead of simply telling us whether the matrix is a natural Latin square or not, please compute the number of rows and the number of columns that contain repeated values. Input The first line of the input gives the number of test cases,  T .  T  test cases follo

AVL Tree Rotations

Image
Rotations When the tree structure changes, we need to modify the tree to restore the AVL tree property. This can be done using single or double rotations. Types of Violations Let us assume the node that must be rebalanced in X. Violations might occur in four cases: Insertion into the left subtree of the left child of X. Insertion into the right subtree of the right child of X.  Insertion into the right subtree of the left child of X. Insertion into the left subtree of the right child of X. Single Rotation Left Left Rotation (LL Rotation) [Case 1]: Rotation does not have to be done at the root of a tree. In general, we start at the node inserted and travel up the tree, updating the balance information at every node on the path. public AVLTree rotateLeft (AVLTree x) {        AVLTree  y = x.right;        // Perform rotation            y.left = x;        x.right =  y.left ;        // Update heights        x.height = max(height(x.left), hei

AVL (Adelson-Velskii and Landis) Trees

Image
What is AVL Tress? A binary tree is said to be an AVL Tree if: It is a binary search tree. For any node, the height of left subtree of node and height of right subtree of node differ by at most 1. Minimum/Maximum number of Nodes in AVL Tree Let the height of an AVL Tree is h and N(h) indicate the number of nodes in AVL Tree. Minimum number of nodes with height h is: N(h) = N(h-1) + N(h-2) + 1 N(h-1) indicates the minimum number of nodes with height h-1 . N(h-2) indicates the minimum number of nodes with height h-2 .   AVL Tree Declaration The declaration of AVL is similar to that of BST (Binary Search Tree). We include the height sldo as a part of a declaration. public class AVLTree {          int key, height;           AVLTree  left, right;           AVLTree  (int data) {                 key = d;                 height = 1;          }                 public int findHight( AVLTree  root ) {                 if(root

What is the difference between the add and offer methods in a Queue in Java?

If a collection refuses to add a particular element for any reason other than that it already contains the element, it  must throw  an exception (rather than returning false). This preserves the invariant that a collection always contains the specified element after this call returns. offer  method - tries to add an element to a queue, and returns  false  if the element can't be added (like in case when a queue is full), or  true  if the element was added, and doesn't throw any specific exception. add  method - tries to add an element to a queue, returns  true  if the element was added, or throws an IllegalStateException if no space is currently available. There is no difference for the implementation of  PriorityQueue.add : public boolean add ( E e ) { return offer ( e ); } For  AbstractQueue  there actually is a difference: public boolean add ( E e ) { if ( offer ( e )) return true ; else throw new IllegalStateE

Tree

Image
What is Tree? A tree is a data structure, each node points to a number of nodes. A tree is an example of non-linear data structures. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. The root of a tree is the node with no parents. A node with no children is called a leaf node . Children of the same parent are called siblings . A node "p" is an ancestor of node "q" if there exists a path from "root" to "q" and "p" appears on the path. The node "q" is called descendant of p. Set of all node at a given depth is called the level of the tree. The root node is at level zero. The height of the tree is the maximum height among all the nodes in the tree and depth of the tree is the maximum depth among all the nodes in the tree. Binary Tree A tree is called a binary tree if each node has zero child, one child or two children. Types of binary tree Stric

Capgemini Salesforce Hackathon Oct-2018

Image
Description: Salesforce application which covers the following scenarios with the tools and technologies given below: List of records in first of the page, upon selecting a record, the details of it needs to be shown in the lower half using Lightning. List of records shown, with the new edit and delete functionality in Lightning. List of records, Functionality to select multiple records and update with a single value and delete multiple records at a time in lightning. Tools/Technology Usages: SFDC, APEX, Salesforce Lightning, CSS. I secure 27 rank in Capgemini Salesforce Hackathon 2018 in Round 2. Prerequisites:   Salesforce provides free developer account where you can develop force.com applications for free. Salesforce.com free developer account will be created through the URL http://developer.force.com.  Steps to create a free developer account in salesforce.com (Salesforce login) 1. First, you have a valid email Id.  2. Login to http://develope