Spiral Order Traversal of Two Dimensional Matrix - 1

Problem:

Given a two dimensional array, print the elements in spiral order starting at the top left corner.

Example:

Output:

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Java Program:

public class SpiralOutToIn {
 public static void main(String[] args) {
  int [][] A = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}; //m x n, m=n, m and n even 
  //int [][] A = {{1,2,3},{5,6,7},{9,10,11}}; //m x n, m=n, m and n odd
  //int [][] A = {{1,2,3,4},{5,6,7,8},{9,10,11,12}}; //m x n, m < n, m odd and n even
  //int [][] A = {{1,2,3,4,17},{5,6,7,8,18},{9,10,11,12,19},{13,14,15,16,20}}; //m x n, m < n, m even and n odd
  //int [][] A = {{1,2,3},{5,6,7},{9,10,11},{13,14,15}}; //m x n, m > n, m even and n odd
  //int [][] A = {{1,2,3,19},{5,6,7,20},{9,10,11,21},{13,14,15,22},{16,17,18,23}}; //m x n, m > n, m odd and n even
  //Boundary Value Test Cases
  //int [][] A = {{}};
  //int [][] A = {{1}};

  int layer = 0;
  //Go till half the length of the array.
  int maxLayer = A.length % 2 == 0 ? A.length/2 - 1 : A.length/2;
  while(layer <= maxLayer) {
   int i=layer;
   int j=layer;
   //Left to Right
   for(j=layer; j<=A[i].length-1-layer;j++) {
    System.out.print(A[i][j] + " ");
   }
   j = A[i].length - 1 -layer;
   //Top to Down
   for(i=layer + 1; i <= A.length - 1 - layer; i++) {
    System.out.print(A[i][j] + " ");
   }
   i = A.length - 1 - layer;
   //Right to Left
   for(j=A[i].length - 2 - layer; j >= layer; j--) {
    System.out.print(A[i][j] + " ");
   }
   j = layer;
   //Down to Top
   for(i=A.length - 2 - layer; i>=layer + 1; i--) {
    System.out.print(A[i][j] + " ");
   }
   layer++;
  }
 }
}

Robot Steps

.Problem:
A robot can take 2, 3 or 5 steps at a time. Given the difference (total number of steps) between source and destination, find the number of ways the robot can reach from source to destination.

Sample Input:
1
2
3
4
5
6
7
8
9

Sample Output:
0
1 
1
1
3
2
5
6
8

Solution:
The solution to these problems can be generalized in the following manner:
If a robot can take a, b, c, ... steps to move from one position to another, then the total number of ways to traverse a particular number of steps n is:
A[n] = A[n-a] + A[n-b] + A[n-c] + ...

So in this case, the recurrence formula is:
A[n] = A[n-2] + A[n-3] + A[n-5]

Java program to find the common interval between the meeting intervals of two persons

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Meeting {
 private static List<Double> PS1; // Person 1's Meeting Start times.
 private static List<Double> PE1; // Person 1's Meeting End times.
 private static List<Double> PS2; // Person 2's Meeting Start times.
 private static List<Double> PE2; // Person 2's Meeting End times.
 private static Double maxTime;
 public static void main(String[] args) {
  //TC 1
//  PS1 = Arrays.asList(0D,8D);
//  PE1 = Arrays.asList(1D,23D);
//  PS2 = Arrays.asList(0D,3D,5D,9D);
//  PE2 = Arrays.asList(2D,4D,6D,23D);
  
  //TC 2
  PS1 = Arrays.asList(1D);
  PE1 = Arrays.asList(2D);
  PS2 = Arrays.asList(2D);
  PE2 = Arrays.asList(3D);
  
  //TC3
  PS1 = Arrays.asList(1D,10D,19D,21D,27D);
  PE1 = Arrays.asList(5D,14D,20D,23D,30D);
  PS2 = Arrays.asList(3D,12D,18D,23D);
  PE2 = Arrays.asList(5D,15D,21D,24D);
  
  maxTime = PE1.get(PE1.size() - 1) > PE2.get(PE2.size() - 1) ? PE1.get(PE1.size() - 1) : PE2.get(PE2.size() - 1); 
  
  FreeTimeSlot P1 = findFreeTimeSlot(PS1,PE1);
  System.out.println("Free time slots for person 1 :");
  printTimeSlot(P1);
  
  FreeTimeSlot P2 = findFreeTimeSlot(PS2,PE2);
  System.out.println("Free time slots for person 2 :");
  printTimeSlot(P2);

  FreeTimeSlot commonFreeTimeSlot = findCommonFreeTimeSlot(P1, P2);
  System.out.println("Common free time slots for person 1 and person 2 :");
  printTimeSlot(commonFreeTimeSlot);
 }
 
 public static void printTimeSlot(FreeTimeSlot timeSlot) {
  int i=0;
  for(Double time : timeSlot.S) {
   System.out.println(time + " " + timeSlot.E.get(i));
   i++;
  }
 }
 
 public static FreeTimeSlot findCommonFreeTimeSlot(FreeTimeSlot P1, FreeTimeSlot P2) {
  FreeTimeSlot commonFreeTimeSlot = new FreeTimeSlot();
  int a = 0; int b = 0;
  //a is the index for Person 1
  //b is the index for Person 2
  while (a < P1.S.size() && b < P2.S.size()) {
   //Person 1's time slot lies completely ahead of Person 2's time slot
   /*
    *        a                    b
    * +-----------------+   +----------------+
    */
   if(P1.S.get(a) < P2.S.get(b) && P1.E.get(a) <= P2.S.get(b)) {
    a++;
   }
   //Person 2's time slot lies completely ahead of Person 1's time slot
   /*
    *        b                    a
    * +-----------------+   +----------------+
    */
   else if(P1.S.get(a) > P2.S.get(b) && P1.S.get(a) >= P2.E.get(b)) {
    b++;
   }
   //Start of Person 1's time slot is before start of Person 2's time slot
   /*
    *        a        b
    * +-------------+---+-------+
    */
   else if(P1.S.get(a) <= P2.S.get(b)) {
    commonFreeTimeSlot.S.add(P2.S.get(b));
    Double time = P1.E.get(a) < P2.E.get(b) ? P1.E.get(a) : P2.E.get(b);
    commonFreeTimeSlot.E.add(time);
    if(P2.E.get(b) < P1.E.get(a)) {
     b++;
    }
    else {
     a++;
    }
   }
   //Start of Person 2's time slot is before start of Person 1's time slot
   /*
    *        b        a
    * +-------------+---+-------+
    */
   else if(P1.S.get(a) > P2.S.get(b)) {
    commonFreeTimeSlot.S.add(P1.S.get(a));
    Double time = P2.E.get(b) < P1.E.get(a) ? P2.E.get(b) :  P1.E.get(a);
    commonFreeTimeSlot.E.add(time);
    if(P1.E.get(a) < P2.E.get(b)) {
     a++;
    }
    else {
     b++;
    }
   }
  }
  return commonFreeTimeSlot;
 }
 
 public static FreeTimeSlot findFreeTimeSlot(List<Double> personStart, List<Double> personEnd) {
  double s=0;
  int a = 0;
  FreeTimeSlot freeTimeSlot = new FreeTimeSlot();
  while(a<personStart.size()) {
   if(s < personStart.get(a)) {
    freeTimeSlot.S.add(s);
    freeTimeSlot.E.add(personStart.get(a));
    s = personEnd.get(a);
    a++;
   }
   else if(s == personStart.get(a)) {
    s = personEnd.get(a);
    a++;
   }
  }
  // Adding the remaining time of the day as a free time slot.
  int length = freeTimeSlot.E.size();
  if(freeTimeSlot.E.get(length - 1) < maxTime && personEnd.get(personEnd.size() - 1) < maxTime) {
   freeTimeSlot.S.add(personEnd.get(personEnd.size() - 1));
   freeTimeSlot.E.add(maxTime);
  }
  return freeTimeSlot;
 }
}

class FreeTimeSlot
{
 List<Double> S = new ArrayList<Double>();
 List<Double> E = new ArrayList<Double>();
}

Print combinations of strings from List of List of Strings

Print combinations of strings from List of List of Strings.
Example input: [[abc, def], [ghi, jkl, mno], [pqr]]
Example output:

abc ghi pqr 
abc jkl pqr 
abc mno pqr 
def ghi pqr 
def jkl pqr 
def mno pqr 

Java Program

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Combinations {
 public static void main(String[] args) {
  int num = 0;
  ArrayList<List<String>> input = new ArrayList<List<String>>();
  input.add(Arrays.asList("abc","def"));
  input.add(Arrays.asList("ghi","jkl","mno"));
  input.add(Arrays.asList("pqr"));
  ArrayList<String> output = new ArrayList<String>();
  combine(num, input, output);
 }
 
 public static void combine(int num, ArrayList<List<String>> input, ArrayList<String> output) {
  if(num == input.size()) {
   for(String string : output) {
    System.out.print(string + " ");
   }
   System.out.println();
  }
  else {
   List<String> current = input.get(num);
   for(String string : current) {
    output.add(string);
    combine(num + 1, input, output);
    output.remove(num);
   }
  }
 }
}

Match the columns problem

Problem:
Find the number of intersections of the lines matching the two columns. The first line contains an integer T denoting the number of test-cases.
First line of each test-case contains an integer N denoting the number of elements in each column. N lines follow each containing a character c separated from a number n by a space character.

Sample Input:
1
8
A 3
B 2
C 8
D 1
E 6
F 7
G 4
H 5

Sample Output:
10 

Explanation:

Solution: To come in following days.

Switching between tabs in same browser window using Selenium WebDriver

Recently I was supposed to automate a test-case which needed me to perform the following steps:

1. Open a browser window
2. Navigate to a URL
3. Perform some operations
4. Open a new tab in the "same" browser window
5. Perform some operations in the newly opened tab
6. Switch back to the previously opened tab
7. Perform some operations in this tab

Most of the resources I have come across while I was dealing with this particular problem talked about opening a new browser window (not a new tab in the same window), using windowHandles to switch between the windows.

The typical catch in this problem is:
When you open a new browser window, you get two window handles. Then they can be used to switch between them.
But when you open a new tab, there is a single window handle. So switching between tabs is not achieved by calling driver.switchTo().window(<windowHandle>)

So I used the following work-around:
1. Open a new tab using Ctrl + t
2. Driver control automatically switches to the newly opened tab
3. Perform the required operations here.
4. Next switch back to the old tab using Ctrl + Tab. You need to keep pressing this unless you reach the desired tab.
5. Once the desired tab is reached, then perform the operations in that tab.

Sample Code:
Get the current window handle and open a new tab using Ctrl + t

        driver.get("http://google.com");
        String windowHandle = driver.getWindowHandle();
        driver.findElement(By.cssSelector("body")).sendKeys(Keys.CONTROL +"t");

The size of the output of getWindowHandles() is 1 which means that there is one single window handle

        ArrayList tabs = new ArrayList (driver.getWindowHandles());
        System.out.println(tabs.size());
        driver.switchTo().window(tabs.get(0)); 

The control is now in the new tab

        driver.get("http://bing.com");
        //perform other operations.

Switch to the old tab using Ctrl + Tab

        driver.switchTo().window(mainWindowHandle);
        driver.findElement(By.cssSelector("body")).sendKeys(Keys.CONTROL +"\t");
        driver.switchTo().defaultContent();

String Problems asked in Programming Interviews

Problem 1:
Find the longest anagram substring of a given string S2 in another string S1.
S1: ascfg
S2: acs
Output: asc



Problem 2:
Find all the anagram substrings of a given string S2 in another string S1.
S1: ascfgsa
S2: cas
Output: {asc, sa}