DD's Gibberish: August 2015

Monday, August 31, 2015

Pass by value Javascript

Problem

Correct the below code. It's simple—you click on one of three boxes to see what nice thing you've won. You always win something nice. Because we love you. Here's what we have so far. Something's going wrong though. Can you tell what it is?

<button id="btn-0">Button 1!</button>

<button id="btn-1">Button 2!</button>

<button id="btn-2">Button 3!</button>

<script type="text/javascript">

    var prizes = ['A Unicorn!', 'A Hug!', 'Fresh Laundry!'];

    for (var btnNum = 0; btnNum < prizes.length; btnNum++) {
        // for each of our buttons, when the user clicks it...
        document.getElementById('btn-' + btnNum).onclick = function() {
            // tell her what she's won!
            alert(prizes[btnNum]);
        };
    }
</script>

Solution

<!doctype html>
<html> 
<button id="btn-0">Button 1!</button>
<button id="btn-1">Button 2!</button>
<button id="btn-2">Button 3!</button>
</html>

<script type="text/javascript">
var prizes = ['A Unicorn!', 'A Hug!', 'Fresh Laundry!'];
for (var btnNum = 0; btnNum < prizes.length; btnNum++) {
// for each of our buttons, when the user clicks it...
        document.getElementById('btn-' + btnNum).onclick 
  = ((function(btnNUm){
    return function(){window.alert(prizes[btnNUm]);};
  })(btnNum));   
}
</script>

Add Spaces using Javascript

Problem

Create a textbox and a button. When button is clicked, replace the text in the textbox, with spaces between each character in the original text.

Note: window.alert was used to debug

Solution

<!doctype html>
<html>
 Input Text: <input id='inText' type='text'>
 <button onClick='addSpaces();'>Click to add spaces :)</button> 
</html>

<script language='javascript' type='text/javascript'>
function addSpaces() {
  var text = document.getElementById('inText');
  var newtext = text.value.split('').join(' ');
  //window.alert(newtext);
  text.value = newtext; 
}
</script>

Morris Tree Traversal (Pre & In order)

package Tree;

public class MorrisTraversal {
 //nlogn time complexity
 //but 1 space complexity => saves memory
 
 public void morrisPreorder(Tree t)
 {
  while(t!= null) 
  {
   if(t.left == null)
   {
    System.out.print(t.val + " ");
    t = t.right;
   }
   else
   {
    Tree pre =  t.left;
    while(pre.right != null && pre.right != t) 
     pre = pre.right;
    
    if(pre.right == null)
    {
     System.out.print(t.val + " ");
     pre.right = t;
     t = t.left;
    }
    else
    {
     pre.right  = null;
     t = t.right;
    }
   }
  }
 }
 
 public void morrisInorder(Tree t){
  while(t != null) 
  {
   if(t.left == null) 
   {
    System.out.print(t.val + " ");
    t = t.right;
   }
   else 
   {
    Tree temp = t.left;
    while(temp.right != null && temp.right != t)
    {
     temp = temp.right;
    }
    
    if(temp.right == null)
    {
     temp.right = t;
     t = t.left;
    }
    else 
    {
     temp.right = null;
     System.out.print(t.val + " ");
     t = t.right;
    }
   }
  }
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int[] pre = {10,5,1,2,7,50,100};
  BSTFromPre ob = new BSTFromPre();
  Tree t = ob.reContructTree(pre);
  TreeOperations.printTree(t);
  System.out.println("-------------------------");
  
  MorrisTraversal morris =  new MorrisTraversal();
//  morris.morrisInorder(t);
  morris.morrisPreorder(t);
  
 }
}

Strings are permutations?

Problem

Find out if 2 strings are permutations of each other.

Solution

 private HashMap convertStringToMap(String s)
 {
  HashMap map = new HashMap();
  Integer mapValue;
  Character c;
  for(int i=0; i< s.length(); i++)
  {
   c = s.charAt(i);
   mapValue = map.get(c);
   if(mapValue == null) map.put(c, 1);
   else map.put(c, mapValue+1);
  }
  return map;
 }

 private boolean permutation(String string1, String string2) {

  if(string1.length() != string2.length()) return false;

  HashMap map1 = convertStringToMap(string1);
  HashMap map2 = convertStringToMap(string2);

  return map1.equals(map2);
 }

Friday, August 28, 2015

Cryptography & Computer Security Intro

I recently started taking a course (CS 265 Cryptography & Computer Security) at SJSU as part of my part time masters. I intend to summarise what I learn each class at this tech blog.

Class 1:
1. CIA
Confidentiality - unauthorized access to data
Integrity - unauthorized data changes
Availability - as the name suggests (Denial of Service or DoS attacks)

2. Cryptography - authorization on a stand alone system
Cryptanalysis - breaking of secure systems
Access control - includes authentication and authorization
Protocols - authorization over a network
Software - buggy, complex => security concerns

3. ATM - Automatic Teller Machines

4. Two factor authentication => requires 2 out the 3 authentication methods

5. 3 authentication methods & examples:
what you know - passwords
what you have - smart cards
what you are - biometric authentication

6. war dialing - dialing many numbers serially to contact someone or to verify if your number exists

Build a simple regex function

Problem

Given a regular expression with characters a-z, ' * ', ' . '
the task was to find if that string could match another string with characters from: a-z
where ' * ' can delete the character before it, and ' . ' could match whatever character. ' * ' always appear after a a-z character.
Example:
isMatch("a*", "") = true;
isMatch(".", "") = false;
isMatch("ab*", "a") = true;
isMatch("a.", "ab") = true;
isMatch("a", "a") = true;

Solution


package myPackage;

public class Regex {

 boolean match(String r, String in)
 {
  int j= 0;
  for(int i= 0; i< r.length(); i++)
  {
   if(j >= in.length()) return false;
   if(r.charAt(i) != '.' && r.charAt(i) != '+' 
     && r.charAt(i) != '*' 
     && r.charAt(i) != '?')
   {
    int k = i+1;
    if((k< r.length() && r.charAt(k) != '.' 
      && r.charAt(k) != '+' 
      && r.charAt(k) != '*' 
      && r.charAt(k) != '?') 
      || k == r.length())
    {
     if(j< in.length() 
      && in.charAt(j)==r.charAt(i)) 
      j++;
     else return false;
     i--;
    }
    else if(r.charAt(k) == '*') 
     while(j< in.length() 
      && r.charAt(i) == in.charAt(j))
     {j++;}
    else if(r.charAt(k) == '?') 
     if(r.charAt(i) == in.charAt(j)) 
     {j++;}
    else if(r.charAt(k) == '+') 
     if(r.charAt(i) == in.charAt(j)) 
     {j++;} 
     else return false;
    else if(r.charAt(k) == '.') {
      if(r.charAt(i) == in.charAt(j)) 
      {j++;} 
      else return false;
      while(j< in.length() 
          && (r.charAt(i) == in.charAt(j)))
      {j++;}
     }
    i++;
   }
   else {
    int k = i;
    if(r.charAt(k) == '*') 
     while(j< in.length())
     {j++;}
    else if(r.charAt(k) == '?') 
      if(j< in.length()) 
       j++;
    else if(r.charAt(k) == '+') 
    {
     if(j< in.length()) j++; 
     else return false;
    }
    else if(r.charAt(k) == '.') 
    {
     if(j< in.length()) j++; 
     else return false;
     while(j< in.length()){j++;}
    }
   }
  }
  if(j< in.length()) return false;
  return true;
 }


 public static void main(String[] args) {

  Regex ob = new Regex();
  System.out.println(ob.match("aab*d*c*a*b*aa*", "aabbbcbbbaa"));
 }

}

Wednesday, August 26, 2015

External CSS & JS Files

How would you reference a Javascript file or a CSS file in your html code? That is include the files in your code, such that you can reference them?

`HTML File:`

<!doctype html>
<html>
 <link rel='stylesheet' type='text/css' href='../styles.css'>
 <script type='text/javascript' src='byid.js'></script>
 <h1>What can javascript do?</h1>
 <button id='mybtn' onclick='changeText();'>Click Me!</button>
</html>

`JS file:`

function changeText() {
  var btn = document.getElementById('mybtn');
  btn.innerHTML = ('Hello Javascript' == btn.innerHTML) 
        ? 'Click Me!': 'Hello Javascript';
}

Whats important?

The src for script tag is mandatory for including the Javascript file. The parameter type, language for script tag are optional.

And <script> needs to be closed with a </script>. If you try to use <script type='text/javascript' src='byid.js'/>, then the code won't work.

For including the css file using the link tag, the rel parameter and href parameter are mandatory. The rest are optional.

Cake Thief

Problem

You are a cake thief, who wants to steal cakes from a shop.

Each cake has a weight and a value, stored in tuples with two indices:

An integer representing the weight of the cake in kilograms

An integer representing the monetary value of the cake in British pounds

For example:

Cake #1 weighs 7 kilograms and has a value of 160 pounds i.e. (7, 160)

Cake #2 weighs 3 kilograms and has a value of 90 pounds i.e. (3, 90)

You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible.Write a function that takes an array of cake type tuples and weight capacity, and returns the cakes to steal to get maximum profit.

What if there are unlimited cakes of each type? i.e. you can steal many cakes of a given weight 7 and price 160 and so on.

Solution

//Cake.java
public class Cake { 
 int price;
 int weight;

 public Cake(int weight, int price) {
  this.price = price;
  this.weight = weight;
 }
}

//CakeThief.java
import java.util.ArrayList;
import java.util.Comparator;

public class CakeThief {


 public ArrayList steal(ArrayList cakeList, int maxWt)
 {
  //Part 1: Sort the cakes according to their weights
  cakeList.sort(new Comparator(){
   @Override
   public int compare(Cake c1, Cake c2) {
    return c1.weight - c2.weight;
   }
  });

  //Part 2: Computer max value for a given number of items in an array
  int[][] sack = new int[cakeList.size()+1][maxWt+1];
  for(int i= 0; i< cakeList.size()+1; i++)
  {
   for(int j= 0; j < maxWt+1; j++)
   {
    if(i==0 || j==0) sack[i][j] = 0;
    else 
    {
     int wt = cakeList.get(i-1).weight;
     if(wt <= j)
     {
      int price = cakeList.get(i-1).price;
      sack[i][j] = Math.max(price + sack[i-1][j-wt], sack[i-1][j]);

      // if duplicate cakes allowed, this line should be

      // sack[i][j] = Math.max(price + sack[i][j-wt], sack[i-1][j]);

     }
     else sack[i][j] = sack[i-1][j];
    }
    System.out.print(sack[i][j]);
   }
   System.out.println();
  }

  //Part 3: see which cakes form the optimal solution
  ArrayList result = new ArrayList();
  int i = cakeList.size();
  int j = maxWt;
  while(i>= 1 && j>= 0)
  {
   if(sack[i][j] > sack[i-1][j])
   {
    result.add(cakeList.get(i-1));
    j = j - cakeList.get(i-1).weight;
   }
   i = i-1;

   //if duplicate cakes allowed, this line should be

   //else  i = i-1;
  }
  return result;
 }

 public void printCakeArray(ArrayList stolen)
 {
  for(int i= 0; i < stolen.size(); i++)
  {
   System.out.println("(" +  stolen.get(i).weight 
     + ", " + stolen.get(i).price + ")");
  }
 }

 public static void main(String[] args) {
  ArrayList cakeList = new ArrayList();
  cakeList.add(new Cake(1,1));
  cakeList.add(new Cake(3,4));
  cakeList.add(new Cake(5,7));
  cakeList.add(new Cake(4,5));

  CakeThief thief = new CakeThief();
  ArrayList stolen = thief.steal(cakeList, 7);
  thief.printCakeArray(stolen);
 }
}

Reference:

https://www.youtube.com/watch?v=8LusJS5-AGo

Monday, August 24, 2015

Bitwise Divisibility

Given a binary number a, how would you find if they are divisible by other numbers?

Divisibility by 2:
a & (a-1) = 0

Divisibility by 3:
Starting from MSB or LSB, add the first digit, subtract 2nd digit, add the 3rd, subtract the 4th...so on. If result = 0, then its divisible by 3.
+ - + - + - .... = 0

Divisibility by 4:
a & 3 = 0

Divisibility by 2^x:
a & (2^x - 1) = 0

Ascii values to remember

0 -> 48 +9 => 9 -> 57
A -> 65 +25 => Z -> 90
a -> 97 +25 => z- > 122

Friday, August 21, 2015

Regex

Problem

How to find if string has alphanumeric characters?

Solution

Pattern p = Pattern.compile("[^0-9a-z]", Pattern.CASE_INSENSITIVE);

boolean b = p.matcher("My String").find();

Regex Lookup table

^	Matches the starting position within the string. In line-based tools, it matches the starting position of any line.
*	Matches the preceding element zero or more times. For example, abc matches "ac", "abc", "abbbc", etc. [xyz] matches "", "x", "y", "z", "zx", "zyx", "xyzzy", and so on. (ab)* matches "", "ab", "abab", "ababab", and so on.
.	Matches any single character
?	Matches the preceding element zero or one time. For example, ab?c matches only "ac" or "abc".
+	Matches the preceding element one or more times. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac".
\|	The choice (also known as alternation or set union) operator matches either the expression before or the expression after the operator. For example,abc\|def matches "abc" or "def".
{m,n}	Matches the preceding element at least m and not more than n times. For example, a{3,5} matches only "aaa", "aaaa", and "aaaaa".
[ ]	A bracket expression. Matches a single character that is contained within the brackets. For example, [abc] matches "a", "b", or "c".

Thursday, August 20, 2015

Rotated Strings

Problem

Assume you have a method isSubstring which checks if one word is a substring
of another. Given two strings, s1 and s2, write code to check Ifs2 is a rotation of s1
using only onecalltoisSubstring (e.g., "waterbottLe" is a rotation of "erbottLewat").

Note: this is from Cracking the Coding Interview

Solution

 public boolean isRotation(String s1, String s2){
  if(s1.length() != s2.length() || s2.length() == 0) return false;
  return isSubString(s1 + s1, s2);
 }

Changing CSS stylesheets dynamically

How do you change a style sheet dynamically? Below is an example code that changes the css style sheet when you click on a text.

HTML Code

<!doctyle html>
<html>
  <link rel='stylesheet' type='text/css' href='styleGreen.css'>
<body>
  <h1>Magic #1</h1>
  <a href='#' onClick='changeBkgColor();'>Click to change background color</a>
</body>
</html>
<script>
function changeBkgColor() {
   var linkTags = document.getElementsByTagName('link');
   for(var i=0; i< linkTags.length; i++) {
      linkTags[i].temp =  ('styleBlue' == linkTags[i].temp)

                                  ? 'styleGreen' : 'styleBlue';
      linkTags[i].href = linkTags[i].temp + '.css';
   }
}
</script>

CSS File - styleGreen.css

body {
   background-color: green;
}
a:link{
 color: #00FFFF;
}
a:visited{
 color: white;
}
a:hover{
 color: yellow;
}

CSS File 2 - styleBlue.css

body {
   background-color: blue;
}
a:link{
 color: #CCCCFF;
}
a:visited{
 color: white;
}
a:hover{
 color: yellow;
}

Display HTML code in another HTML page

I previously wrote about how <pre><code></code></pre> would help to output a code to a webpage. But what if you want to embed and display a html code? It's not so straight forward.

In blogger, I paste the code from my html file in the compose mode first. Then I go to the HTML mode and surround my html code with <pre> , <code> tags.

What this does is convert the special characters of html namely
< into <
> into >
& into &

So it encodes the characters on the code and decodes them while displaying the page.
<pre> helps to keep the formatting (indentation, font, etc) the same as the setting in your text file or code editor file. <code> indicates to the web page that this is code.

This encoding decoding technique is useful when your client wants to display certain special characters, that interfere's with your code or overlaps with what are considered special characters by your code and cannot be used in your coding language.

This was one of my first UI exercises at my previous company. While it was a bank and many people complain that you don't get mainstream tech experience at such places, I say its the other way round. Getting to maintain legacy applications and old technology, you learn what you shouldn't be doing faster than if you wrote new code with latest technologies from scratch. My two cents - tech in banks is not so crazy or bad.

If you're building your own html page and want to embed some html code inside that page, copy the html code to embed into a notepad++ file and replace <, > and & with < > and &amp respectively.

HTML 101

In an attempt to prepare for UI interviews, I've decided to go back to coding UI on white paper and notepad, so I can refresh whatever I know about UI so far. Here's the first of those exercises.

The code below is the first ever hello world HTML code most UI developers would write. I first wrote this as a 10 year old, now I am back to the basics after 15 years.

Steps

Step 1: Copy the below code into a notepad file.
Step 2: Save the file as test.html
Step 3: Launch the file in the browser - basically copy the complete path of the file and paste it in browser & hit enter.

Code

<!doctype html>
<html>
<h1>Test 123</h1>
</html>

Wednesday, August 19, 2015

Least Possible Number After Removing k digits

Problem

Please get the least number after deleting k digits from the input number. For example, if the input number is 24635, the least number is 23 after deleting 3 digits.

Solution

public class GetLeastkdigits {

 int getLeast(int num, int k)
 {
  ArrayList a = new ArrayList();
  HashMap map = new HashMap();
  if(num == 0) {
   a.add(0); 
   map.put(0, 0);
  }
  int index=0;
  while(num > 0)
  {
   a.add(num%10);
   map.put(num%10, index++);
   num/=10;
  }

  int retainCnt = a.size() - k;
  if(retainCnt <= 0) return -1;
  
  ArrayList copy = new ArrayList(a);
  Collections.sort(a);
  
  int[] pos = new int[retainCnt];
  for(int i= 0; i< retainCnt; i++)
  {
   pos[i] = map.get(a.get(i));
  }
  Arrays.sort(pos);

  StringBuffer s = new StringBuffer();
  for(int i= retainCnt-1; i>= 0; i--)
  {
   s.append(copy.get(pos[i]));
  }
  
  return Integer.valueOf(s.toString());
 }
 
 public static void main(String[] args) {
  GetLeastkdigits ob = new GetLeastkdigits();
  System.out.println(ob.getLeast(24635, 3));
 }

Light Bulbs

Problem

Given n light bulbs, write two methods.

isOn(i) to determine if a light bulb is on
toggle(start, end) to toggle all the light bulbs in the range

One caveat, write toggle so that it is less than O(n) complexity

Solution

public class LightBulbs {

 int lights=0b11010;
 boolean isOn(int i) {
  int temp = lights>>i & 1;
  if(temp == 1) return true;
  return false;
 }
 
 int toggle(int start, int end)
 {
  int temp = 1<<(end-start+1);
  temp = temp-1;
  temp <<= start;
  lights = lights^temp;
  
  return lights;
 }
 
 String convertToBinary(int i){
  return Integer.toString(i, 2);
 }
 
 public static void main(String[] args) {
   
  LightBulbs ob = new LightBulbs();
  System.out.println(ob.isOn(0)); 
  
  int newLight = ob.toggle(1,3);
  System.out.println(ob.convertToBinary(newLight));
 }
}

Tuesday, August 18, 2015

BST Biggest Subtree within a range

Problem

Given a binary search tree t and a range (a,b), find number of nodes in the largest subtree or tree, whose nodes are in the range of (a,b). a, b are exclusive for the range.

Solution

public class BSTRange {
 
 private int max = 0;
 private boolean valid(int val, int a, int b){
  if(val > a && val < b) return true;
  return false;
 }

 private Integer postOrder(Tree t, int a, int b){
  if(t== null) return 0;

  Integer leftCnt = postOrder(t.left, a, b);
  Integer rightCnt = postOrder(t.right, a, b);

  if(leftCnt == null || rightCnt == null) return null;
  if(!valid(t.node, a, b)) return null;

  int cnt = 1 + leftCnt + rightCnt;
  if(max < cnt) max = cnt;
  return cnt; 
 }

 public int getMaxNodesInRange(Tree t, int a, int b){
  max =0;
  postOrder(t, a, b);
  return max;
 }

 public static void main(String[] args) {

  int[] preOrderData = {10,5,1,2,7,50,100};
  BSTFromPre ob = new BSTFromPre();
  Tree t = ob.reContructTree(preOrderData);
  TreeOperations.printTree(t);

  BSTRange ob1 = new BSTRange();
  System.out.println(ob1.getMaxNodesInRange(t, 0, 101));
 }
}

Map & Lambda Expression

Problem

Given a HashMap<Character, Integer> map in Java 8, how would you remove the elements whose key > 's' or how would you remove elements with value > 1 (in a single line)?

Solution

  map.entrySet().removeIf(p->p.getKey()>'s');
  map.entrySet().removeIf(p->p.getValue()>1);

Leetcode - Add Two Numbers

Problem

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

What I learnt here? When you're creating a linkedlist, always remember to keep a copy of the start of the linkedlist and the a copy of the previous if necessary. Though this is obvious, its easy to forget this when you're doing while board coding or when you're in an interview.

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    
  public ListNode storeSum(int l1, int l2, ListNode result)
 {
  int sum = l1 + l2 + result.val;
  result.val = sum%10;
  if(sum > 9) result.next = new ListNode(sum/10); 
  else result.next = new ListNode(0);
  return result;
 }

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

  if(l1== null && l2== null) return null;
  if(l1== null) return l2;
  if(l2== null) return l1;

  ListNode sum = new ListNode(0);
  ListNode result = sum;
  ListNode prevRes;
  do {
   
   prevRes = storeSum(l1.val, l2.val, result);
   result = prevRes.next;
   l1 = l1.next;
   l2 = l2.next;
  }while(l1!=null && l2!=null);

  while(l1!=null)
  {
   prevRes = storeSum(l1.val, 0, result);
   result = prevRes.next;
   l1 = l1.next;
  }

  while(l2!=null)
  {
   prevRes = storeSum(l2.val, 0, result);
   result = prevRes.next;
   l2 = l2.next;
  }

  if(result.val == 0) prevRes.next = null;
  return sum;
 }

        //test functions
         static void printNode(ListNode l)
 {
  while(l!=null)
  {
   System.out.print(l.val);
   l = l.next;
  }
  System.out.println();
 }

 public static void main(String[] args) {

  ListNode l1 = new ListNode(2); 
  l1.next = new ListNode(4); 
  l1.next.next = new ListNode(3);
  Solution.printNode(l1);
  
  ListNode l2 = new ListNode(5); 
  l2.next = new ListNode(6); 
//  l2.next.next = new ListNode(4);
  AddTwoLists.printNode(l2);
  
  Solution ob = new Solution();
  ListNode res = ob.addTwoNumbers(l1, l2);
  Solution.printNode(res);
 }
}

Leetcode - Longest Substring Without Repeating Characters

Problem

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Accepted Solution

public class Solution {
     public int lengthOfLongestSubstring(String s) {

  int len=0; int start=0, pos=0, curLen=0, i=0;
  HashMap map = new HashMap();
  for(; i< s.length(); i++) 
                {
   if(map.containsKey(s.charAt(i)))
   {
    pos = map.get(s.charAt(i));
    curLen = i-start;
    if(curLen > len) len = curLen;
    if(pos >= start) start=pos+1;
   } 
   map.put(s.charAt(i),i);   
  }
  if(i== s.length() && i> 0) 
                {
          curLen = i-start;
   if(curLen > len) len = curLen;
  }
  return len;
 }
}

Reservoir Sampling - Tree

Problem

Get n random nodes from a binary tree, such that each node will be returned with equal probability.

Solution

import java.util.ArrayList;
import java.util.Random;


public class Tree {
 public int node;
 public Tree left;
 public Tree right;
}
public class NodesAtRandom {
 
 int index = 0;
 ArrayList getRandomNodes(Tree t, int n){
  ArrayList ret = new ArrayList();
  index =0;
  preOrder(ret, t, n);
  return ret;
 }
 
 private void preOrder(ArrayList ret, Tree t, int n) {
  if(t==null) return;
  index++;
  if(ret.size() < n) ret.add(t.node);
  else {
   Random r = new Random();
   int rVal = r.nextInt(index);
   if(rVal < n) ret.set(rVal, t.node);
  }
  preOrder(ret, t.left, n);
  preOrder(ret, t.right, n);
 }

 public static void main(String[] args){
  Tree t = TreeTestData.getSampleTree1();
  TreeOperations.printTree(t);
  NodesAtRandom ob = new NodesAtRandom();
  ArrayList output = ob.getRandomNodes(t, 2);
  System.out.println(output);
 }
}

Monday, August 17, 2015

Construct Tree from PreOrder & InOrder

Problem

Construct a tree from pre-order and in-order traversal arrays.
What I learnt here? - Arrays.copyOfRange(int[], int start, int end) copies from start (included) till end-1 (i.e. exclusive of end)

Solution

import java.util.Arrays;
public class TreeProblem2 {
 class Tree {
  int node;
  Tree left;
  Tree right;
 }
 
 int preIndex = 0;
 Tree construct(int[] pre, int[] in) {
  if(preIndex >= pre.length  || in.length==0) return null;

  Tree t= new Tree();
  t.node = pre[preIndex++]; //first element in preorder is the root

  //Get pos of root in the inorder. 
  //Elements left of that will be the left tree
  //Elements to the right of that will be the right tree
  int i =0;
  for(;i< in.length; i++){
   if(in[i] == t.node) break;
  }

  int[] leftIn = Arrays.copyOfRange(in, 0, i);
  int[] rightIn = Arrays.copyOfRange(in, i+1, in.length);

  t.left = construct(pre, leftIn);
  t.right = construct(pre, rightIn);
  return t;
 }

 public static void main(String[] args) {
  int[] pre = {10,5,80,9,2,6};
  int[] in = {80,5,9,10,6,2};
  TreeProblem2 ob = new TreeProblem2();
  Tree t = ob.construct(pre, in);
  TreeOperations.printTree(t);
 }
}

Construct BST from PreOrder traversal array

Problem

Given an preorder traversal array as input, reconstruct a binary search tree.

Solution

public class Tree {
 public int node;
 public Tree left;
 public Tree right; 
}

public class TreeProblem1 extends Tree{
 int index = 0;
 Tree construct(int[] pre, int min, int max)
 {
  if(index>=pre.length) return null;
  if(pre[index]>max || pre[index] < min) return null;
  Tree t = new Tree();
  t.node = pre[index++];
  t.left = construct(pre,min, t.node);
  t.right = construct(pre, t.node, max);
  return t;
 }
 
 Tree reContructTree(int[] preorder)
 {
  index = 0;
  return construct(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
 }
 
 public static void main(String[] args) {
  
  int[] pre = {10,5,1,2,7,50,100};
  TreeProblem1 ob = new TreeProblem1();
  Tree t = ob.reContructTree(pre);
  TreeOperations.printTree(t);
 }

}

Strings replace spaces

Problem

Write a method to replace all spaces in a string with '%20'. You may assume that the
string has sufficient space at the end of the string to hold the additional characters,
and that you are given the "true" length of the string. (Note: if implementing in Java,
please use a character array so that you can perform this operation in place.)

Note: This is a problem from Cracking the Coding Interview Edition 5 Book.
Interesting part here: using Arrays.copy function

Solution

 private String replaceSpaces1(char[] s)
 {
  int count=0, i;
  int oldlen = s.length;

  for(i=0; i< oldlen; i++)
  {
   if(s[i] == ' ') count++;
  }


  int newlen = oldlen + count*2;
  s =  Arrays.copyOf(s, newlen);
  int pos = newlen-1;

  for(i= oldlen-1; i>= 0; i--)
  {
   if(s[i]==' ')
   {
    s[pos--] = '0';
    s[pos--] = '2';
    s[pos--] = '%';
   }
   else s[pos--] = s[i];
  }
  return Arrays.toString(s);
 }

Max & Min Heaps in Java

Part 1 provides a base class with functions common to max heap and min heap.

Part 2 below provides code for Min Heap construction, removal of an element and finding the kth smallest element from the heap.

Part 3 below provide code for Max heap construction, removal of an element and finding the kth largest element from the heap.

Part 1: Class with common functions of heap (get parent, printing etc)

import java.util.ArrayList;
public class Heap {

 ArrayList heap = new ArrayList(); 
 
 int parentIndex(int index) {
  return (index-1)/2;
 } 
 int getParent(int index)  {
  return heap.get(parentIndex(index));
 }
 int getLeftIndex(int index) {
  return (2*index + 1);
 }
 int getRightIndex(int index) {
  return (2*index + 2);
 }
 boolean validIndex(int index){
  return (index>= 0 && index< heap.size()) ? true: false;
 }
 void swap(int index1, int index2)  {
  int temp = heap.get(index1);
  heap.set(index1, heap.get(index2));
  heap.set(index2, temp);
 }
 
 void printHeap(){
  System.out.println(heap);
 }
}

Part 2: Min Heap & Getting kth smallest element

public class MinHeap extends Heap{

 int minHeapify(int index) {
  while(index!= 0 && getParent(index) > heap.get(index)){
   swap(parentIndex(index), index);
   index = parentIndex(index);
  }
  return index;
 }

 void insert(int[] input) {
  int index=heap.size() -1;
  for(int i=0; i< input.length; i++){
   heap.add(input[i]); index++;
   minHeapify(index);
  }
 }

 void siftDown(int pos)
 {
  int minIndex, rightIndex;
  while(validIndex(getLeftIndex(pos)))
  {
   minIndex = getLeftIndex(pos);
   rightIndex = getRightIndex(pos);
   if(validIndex(rightIndex) && heap.get(rightIndex) < heap.get(minIndex))
   {
    minIndex = rightIndex;
   }
   if(heap.get(pos) > heap.get(minIndex))
   {
    swap(pos, minIndex);
    pos = minIndex;
   }
   else break;
  }
 }

 boolean remove(int pos)
 {
  if(!validIndex(pos)) return false;
  if(pos == (heap.size()-1)) {
   heap.remove(pos);
   return true;
  }
  swap(pos, heap.size() -1);
  heap.remove(heap.size()-1);
  pos = minHeapify(pos);
  siftDown(pos);
  return true;
 }
 
 int getKthMin(int k)
 {
  if(k > heap.size()) return -1;
  if(k == 1) return heap.get(0);
  remove(0);
  return getKthMin(k-1);
 }

 public static void main(String[] args) {

  int[] input = {4,6,10,9,8,1,0};
  MinHeap obj = new MinHeap();
  obj.insert(input);
  obj.printHeap();
//  obj.remove(6);
  System.out.println(obj.getKthMin(4));
 }

Part 3: Max heap & get the kth largest element

public class MinHeap extends Heap{
 int minHeapify(int index)
 {
  while(index!=0 && getParent(index) > heap.get(index))
  {
   swap(parentIndex(index), index);
   index = parentIndex(index);
  }
  return index;
 }

 void insert(int[] input)
 {
  int index=heap.size() -1;
  for(int i=0; i< input.length; i++)
  {
   heap.add(input[i]); index++;
   minHeapify(index);
  }
 }

 void siftDown(int pos)
 {
  int minIndex, rightIndex;
  while(validIndex(getLeftIndex(pos)))
  {
   minIndex = getLeftIndex(pos);
   rightIndex = getRightIndex(pos);
   if(validIndex(rightIndex) && heap.get(rightIndex) < heap.get(minIndex))
   {
    minIndex = rightIndex;
   }
   if(heap.get(pos) > heap.get(minIndex))
   {
    swap(pos, minIndex);
    pos = minIndex;
   }
   else break;
  }
 }

 boolean remove(int pos)
 {
  if(!validIndex(pos)) return false;
  if(pos == (heap.size()-1)) {
   heap.remove(pos);
   return true;
  }
  swap(pos, heap.size() -1);
  heap.remove(heap.size()-1);
  pos = minHeapify(pos);
  siftDown(pos);
  return true;
 }
 
 int getKthMin(int k)
 {
  if(k > heap.size()) return -1;
  if(k == 1) return heap.get(0);
  remove(0);
  return getKthMin(k-1);
 }

 public static void main(String[] args) {

  int[] input = {4,6,10,9,8,1,0};
  MinHeap obj = new MinHeap();
  obj.insert(input);
  obj.printHeap();
//  obj.remove(6);
  System.out.println(obj.getKthMin(4));
 }

Matrix Rotation by 90 degrees clockwise

 public int[][] rotate90(int[][] matrix)
 {
  
  int rowLength = matrix.length;
  int colLength = matrix[0].length;
  int [][] res = new int[colLength][rowLength];
  int col=0;
  for(int i=rowLength-1; i>= 0; i--, col++)
  {
   for(int j=0, row=0; j< colLength; j++, row++)
   {
    res[row][col] = matrix[i][j];
   }
  }
  return res;
 }

Convert Between Bases

Convert an integer from base 10 to base 16

String x = Integer.toString(10, 16); 
System.out.println(x);//prints a

Convert an integer from base 16 to base 10

int y = Integer.valueOf("a", 16);
System.out.println(y); //prints 10

Matrix - Moving from one cell to another

Problem

Given an nxm matrix, filled with either 1 or 0. If a cell has value 1, then you cannot move into it. If it has 0, then you can move into it. You're given a starting position (sx, sy), where sx indicates a row on the matrix, and sy a column on the matrix. Check if a move is possible from (sx, sy) to another position (ex, ey). Return true if possible, otherwise return false.

Solution


public class MatrixMove {

 boolean valid(int[][]m, int x, int y)
 {
  if(x < m.length && y< m[0].length && x >= 0 && y>= 0 ) return true;
  return false;
 }

 boolean move(int[][] m, int sx, int sy, int ex, int ey)
 {
  if(!valid(m,sx, sy) ||  !valid(m,ex, ey)) return false;
  if(m[sx][sy] == 1 || m[ex][ey]==1) return false;
  if(sx == ex && sy == ey) return true;
  
  m[sx][sy] = 1;
  
  return  move(m,sx-1,sy,ex,ey) || move(m,sx+1,sy,ex,ey) 
    || move(m, sx, sy-1, ex,ey) || move(m,sx,sy+1, ex, ey);
 }
 
 public static void main(String[] args) {
  int[][] m = {{0,0,1,0,1}, {0,0,0,0,0}, {0,1,1,1,1}, {0,0,0,0,0}, {0,1,1,1,0}};
  int sx=1, sy =1, ex=4, ey=4;
  MatrixMove ob = new MatrixMove();
  System.out.println(ob.move(m, sx, sy, ex, ey));
  
 }

}

BigInteger - Storing Infinitely long numbers

Say you need to take an input number that is really huge. So huge that it won't fit into a long or even a double. Then how do you do it?

Method 1: ArrayList

Take in each digit in an array list and then compute the length of the array.

Now what if you need to add 2 such huge numbers? Or say you want to count the number of sets of numbers you can get from a given set of digits - 1234 can be {1,2,3,4} or {1,23,4} or {12,34} so on. And if you have infinite such digits, how can you store your count?

This is where Method 2 comes

Method 2: BigInteger & BigDecimal

From what I understand, BigInteger & BigDecimal classes can hold a number/ decimal or any length, as long as the JVM has heap memory available to store the number.

Here are useful functions of BigInteger that I learnt today:

1. Initializing using numbers zero, one and ten

BigInteger cnt = BigInteger.ZERO;
BigInteger cnt = BigInteger.ONE;
BigInteger cnt = BigInteger.TEN;

2. Initializing using Other numbers

BigInteger cnt = BigInteger.valueOf(15);

3. Operations such as mod, divide, add

BigInteger modTen = cnt.mod(BigInteger.TEN);
BigInteger modTen = cnt.mod(BigInteger.valueOf(10));
cnt  = cnt.add(BigInteger.valueOf(1));
BigInteger divTen = cnt.divide(BigInteger.TEN);

4. Comparisons between 2 BigIntegers

//a,b are BigIntegers
int output = a.compareTo(b);
a<b, then output = -1
a=b, then output = 0
a>b, then output = 1

5. Converting to primitive data types & displaying on console for debugging

BigInteger modTen = big.mod(BigInteger.TEN);
if(modTen.intValue() > 0) System.out.println(modTen);

Sample Code


//helper functions 
 private BigInteger bigInt(int smallVal)
 {
  return BigInteger.valueOf(smallVal);
 }

 private boolean valid(BigInteger big) {

  if(big.compareTo(bigInt(0)) == 1 && big.compareTo(bigInt(27)) == -1)
   return true;
  return false;
 }

 BigInteger perm(BigInteger big)
 {
  BigInteger cnt = BigInteger.ZERO;
  if(big.equals(BigInteger.ZERO)) return cnt;
  BigInteger modTen = big.mod(BigInteger.TEN);
  BigInteger divTen = big.divide(BigInteger.TEN);

  if(modTen.intValue() > 0 && divTen.equals(BigInteger.ZERO)  )
  {
   return valid(modTen)? BigInteger.ONE: BigInteger.ZERO; 
  }

  BigInteger mod100 = big.mod(bigInt(100));
  BigInteger div100 = big.divide(bigInt(100));

  if(mod100.intValue() > 0 && div100.equals(bigInt(0)))
  {
   if(valid(big)) cnt  = cnt.add(bigInt(1));
   if(valid(modTen) && valid(divTen)) cnt = cnt.add(bigInt(1));
      
   return cnt;
  }

  if(valid(modTen)) cnt = cnt.add(perm(divTen));
  if(valid(mod100)) cnt = cnt.add(perm(div100));
  return cnt;
 }

Wednesday, August 12, 2015

Codility Perm Check

Problem

A non-empty zero-indexed array A consisting of N integers is given.
A permutation is a sequence containing each element from 1 to N once, and only once.
For example, array A such that:

A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2
is a permutation, but array A such that:

A[0] = 4
A[1] = 1
A[2] = 3
is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation. Write a function:

int solution(int A[], int N);
that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2
the function should return 1.

Given array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
the function should return 0.

Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].

Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Solution

public class PermCheck {

	public int solution(int[] A) 
	{
		int invalid = 0, valid =1;
		int n = A.length;
		boolean[] perm = new boolean[n+1];
		int numbers = n;
		
		for(int i=0; i< n; i++)
		{
			if(A[i]> 0 && A[i]<= n)
			{
				if(perm[A[i]] == false) {
					perm[A[i]] = true;
					numbers--;
					if(numbers == 0) return valid;
				}
				else return invalid;
			}
		}
		
		return invalid;
	}

	public static void main(String[] args) {

		int[] A = new int[1000000];//= {0};

		for(int i=1; i<= 1000000; i++)
		{
			A[i-1] =i; 
		}
		int output = new PermCheck().solution(A);
		System.out.println(output);

	}

Codility Frog River One

Problem

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river.

You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.

For example, you are given integer X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In minute 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

class Solution { public int solution(int X, int[] A); }
that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

the function should return 6, as explained above. Assume that:

N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].

Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(X), beyond input storage (not counting the storage required for input arguments).

Solution

import java.util.Arrays;
public class FrogRiverOne {

	public int solution(int X, int[] A) {
        
		 int cantCross = -1;
	        if(X==0) return cantCross;
	        int len = A.length;
			
			int[] timeAtPos = new int[X];
			int[] timeAtposX = new int[len]; 
			Arrays.fill(timeAtPos, -1);
			int j=0, biggest = Integer.MIN_VALUE;
			
			for(int i=0; i< len; i++)
			{
				if(A[i]>= 0 && A[i]< X && timeAtPos[A[i]] == -1)
				{
					timeAtPos[A[i]] = i;
				}
				if(X == A[i])
				{
					timeAtposX[j++] = i;
				}
			}
			
			for(int i=1; i< X; i++)
			{
				if(timeAtPos[i] == cantCross) return cantCross;
				if(biggest < timeAtPos[i])
					biggest = timeAtPos[i];
			}
			
			System.out.println(Arrays.toString(timeAtposX));
			for(int k=0; k< j; k++)
			{
				
				if(biggest < timeAtposX[k])
					return timeAtposX[k];
			}
			return cantCross;
}
	
	 public int frog(int X, int[] A) {
	        int steps = X;
	        boolean[] bitmap = new boolean[steps+1];
	        for(int i = 0; i < A.length; i++){
	            if(!bitmap[A[i]]){
	                bitmap[A[i]] = true;
	                steps--;
	            }
	            if(steps == 0) return i;
	        }
	        return -1;
	    }
	 
	public static void main(String[] args) {
		
		int[] A = {1,3,1,1,2,3,5,4,5};
		
		int output =  new FrogRiverOne().frog(5, A);
		System.out.print(output);
	}
}

Tuesday, August 11, 2015

Tree Depth First Searches


public class Tree {
 public int nodeValue;
 public Tree leftNode;
 public Tree rightNode; 
}

public class TreeOperations {

 public void preorderSearch(Tree t)
 {
  if(t == null) return;
  System.out.print(t.nodeValue + " ");
  preorderSearch(t.leftNode);
  preorderSearch(t.rightNode);
 }
 
 public void inorderSearch(Tree t)
 {
  if(t == null) return;
  inorderSearch(t.leftNode);
  System.out.print(t.nodeValue + " ");
  inorderSearch(t.rightNode);
 }
 
 public void postorderSearch(Tree t)
 {
  if(t==null) return;
  postorderSearch(t.leftNode);
  postorderSearch(t.rightNode);
  System.out.print(t.nodeValue + " " );
 }

 public static void main(String[] args) {

  Tree t = TreeTestData.getSampleTree1();
  TreeOperations  treeOps = new TreeOperations();
  treeOps.preorderSearch(t);
  treeOps.inorderSearch(t);
  treeOps.postorderSearch(t);
 }

}

Note: For the TreeTestData Class look at post Tree part 1 step 2.

Display Tree (Breadth First Search Output)

Step1: Write Tree class

public class Tree {
 public int nodeValue;
 public Tree leftNode;
 public Tree rightNode;
}

Note: You can write get set functions, instead of declaring the tree members as public

Step 2: Write a sample test input & functions for it

public class TreeTestData {

 public static Tree createNode(int nodeVal, int left, Tree right)
 {
  Tree t = new Tree();
  t.nodeValue = nodeVal;
  t.leftNode = createNode(left, null, null);
  t.rightNode = right;
  return t;
 }
 
 public static Tree createNode(int nodeVal, int left, int right)
 {
  Tree t = new Tree();
  t.nodeValue = nodeVal;
  t.leftNode = createNode(left, null, null);
  t.rightNode = createNode(right, null, null);
  return t;
 }
 public static Tree createNode(int nodeVal, Tree left, Tree right)
 {
  Tree t = new Tree();
  t.nodeValue = nodeVal;
  t.leftNode = left;
  t.rightNode = right;
  return t;
 }
 
 public static Tree getSampleTree1()
 {
  Tree right = createNode(3, 2, 4);
  Tree currentLeftTree = createNode(1, 0, right);
  right = createNode(8,7,null);
  Tree currentRightTree = createNode(6, null, right);
  Tree t = createNode(5, currentLeftTree, currentRightTree);
  return t;
 }
}

Step 3: Construct an array of arrays using depth first search pre-order to store the nodes at each level. Go through the array using breadth first search and print the tree. If a node doesn't have a particular child, -1 is printed in this code.


import java.util.ArrayList;

public class TreeOperations {

 public void printNodeRecursively(Tree t, int level, 
              ArrayList<ArrayList<Integer>> levelNodes)
 {
  if(levelNodes.size() == level)
  {
   levelNodes.add(new ArrayList());
  }
  ArrayList nodes = levelNodes.get(level);
  if(t == null)
  {
   nodes.add(-1);
   return;
  }
  nodes.add(t.nodeValue);
  printNodeRecursively(t.leftNode, level+1, levelNodes);
  printNodeRecursively(t.rightNode, level+1, levelNodes);
 }

 public void printTree(Tree t)
 {
  final ArrayList<ArrayList<Integer>> levelNodes = new ArrayList<ArrayList<Integer>>();

  printNodeRecursively(t, 0, levelNodes);

  for(int level=0; level < levelNodes.size(); level++)
  {
   for(int nodeIndex = 0; nodeIndex < levelNodes.get(level).size(); nodeIndex++)
   {
    System.out.print(levelNodes.get(level).get(nodeIndex));
    System.out.print(" ");
   }
   System.out.println();
  }
 }

 public static void main(String[] args) {
  Tree t = TreeTestData.getSampleTree1();
  TreeOperations  treeOps = new TreeOperations();
  treeOps.printTree(t);
 }
}

Codility Max Counters

Problem

You are given N counters, initially set to 0, and you have two possible operations on them:

    increase(X) − counter X is increased by 1,
    max_counter − all counters are set to the maximum value of any counter.

A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:

    if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
    if A[K] = N + 1 then operation K is max_counter.

For example, given integer N = 5 and array A such that:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

struct Results {
  int * C;
  int L;
};

Write a function:

struct Results solution(int N, int A[], int M);

that, given an integer N and a non-empty zero-indexed array A consisting of M integers, returns a sequence of integers representing the values of the counters.

The sequence should be returned as:

    a structure Results (in C), or
    a vector of integers (in C++), or
    a record Results (in Pascal), or
    an array of integers (in any other programming language).

For example, given:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Assume that:

    N and M are integers within the range [1..100,000];
    each element of array A is an integer within the range [1..N + 1].

Complexity:

    expected worst-case time complexity is O(N+M);
    expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Solution

 public int[] solution(int N, int[] A) 
 {
  int[] counters = new int[N];
  int maxValue = 0, lastUpdatedValue= 0;
  int index=0;

  for(int i=0; i< A.length; i++)
  {
   if(A[i] == (N+1))
   {
    lastUpdatedValue = maxValue;
   }
   else 
   {
    index = (A[i]-1);
    if(counters[index] < lastUpdatedValue)
     counters[index] = lastUpdatedValue;
    counters[index]++;
    if(maxValue < counters[index]) maxValue = counters[index];
   }
  }
  for(index=0; index< N; index++)
  {
   if(counters[index]< lastUpdatedValue) counters[index] = lastUpdatedValue;
  }
  return counters;
 }

Pages

Monday, August 31, 2015

Problem

Solution

Problem

Solution

Problem

Solution

Friday, August 28, 2015

Problem

Solution

Wednesday, August 26, 2015

HTML File:

JS file:

Whats important?

Problem

Solution

Reference:

Monday, August 24, 2015

Friday, August 21, 2015

Problem

Solution

Regex Lookup table

Thursday, August 20, 2015

Problem

Solution

HTML Code

CSS File - styleGreen.css

CSS File 2 - styleBlue.css

Steps

Code

Wednesday, August 19, 2015

Problem

Solution

Problem

Solution

Tuesday, August 18, 2015

Problem

Solution

Problem

Solution

Problem

Solution

Problem

Accepted Solution

Problem

Solution

Monday, August 17, 2015

Problem

Solution

Problem

Solution

Problem

Solution

Part 1: Class with common functions of heap (get parent, printing etc)

Part 2: Min Heap & Getting kth smallest element

Part 3: Max heap & get the kth largest element

Convert an integer from base 10 to base 16

Convert an integer from base 16 to base 10

Problem

Solution

Method 1: ArrayList

Method 2: BigInteger & BigDecimal

1. Initializing using numbers zero, one and ten

2. Initializing using Other numbers

3. Operations such as mod, divide, add

4. Comparisons between 2 BigIntegers

5. Converting to primitive data types & displaying on console for debugging

Sample Code

Wednesday, August 12, 2015

Problem

Solution

Problem

Solution

Tuesday, August 11, 2015

Step1: Write Tree class

Step 2: Write a sample test input & functions for it

Step 3: Construct an array of arrays using depth first search pre-order to store the nodes at each level. Go through the array using breadth first search and print the tree. If a node doesn't have a particular child, -1 is printed in this code.

Problem

Solution

`HTML File:`

`JS file:`