Longest Substring Of Two Unique Characters (Java)

Question is from here.

Today’s exercise comes from our unending list of interview questions:

Find the longest run of consecutive characters in a string that contains only two unique characters; if there is a tie, return the rightmost. For instance, given input string abcabcabcbcbc, the longest run of two characters is the 6-character run of bcbcbc that ends the string.

Your task is to write the requested program.

Solution:

public class Longest_Substring_Two_Unique_Characters {
	public static void main(String[] args) {
		findLongest("abcabcbcbc");
		findLongest("abababcabc");
		findLongest("abcacacabc");
	}

	public static void findLongest(String s) {
		String res = "";

		for (int i = 0; i + 1 < s.length(); i++) {
			String sub = s.substring(i, i + 2);
			String temp_sub = sub;

			while(s.replaceFirst(temp_sub, "").length() < s.length()) {
				if(res.length() < temp_sub.length())
					res = temp_sub;
				temp_sub = temp_sub + sub;
			}

		}
		System.out.println(res);
	}
}

Output:

bcbcbc
ababab
cacaca

Three List Exercises (Java)

Question is from here.

Today’s exercise provides three little exercises on linked lists, designed to help beginning programmers learn more about how lists work; there is also a special invitation for more experienced programmers.

  1.  Write a function that takes an input list and an interval n and returns a new list with all the elements of the original list, in order, except that every nth item has been removed. For instance, given the input list (1 2 3 4 5 6 7 8 9 10) and n = 4, the function should return the list (1 2 3 5 6 7 9 10).
  2. Write a function that takes an input list and returns a new list with all the elements of the original list, in order, except that in the case of duplicate elements all of the duplicates except the first has been removed. For instance, all of the following lists should be transformed into the list (1 2 3 4 5): (1 2 3 4 5), (1 1 2 3 4 5), (1 2 1 3 1 4 1 5 1), and (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5).
  3. Write a function that takes an input list and splits the list in half; for instance, given the input list (1 2 3 4 5) the two outputs are the lists (1 2) and (3 4 5). If the list has odd length the middle element can be placed in either half, at your option, so the lists (1 2 3) and (4 5) are an alternate acceptable solution for the example problem.

Solution – Exercise 1:

import java.util.*;

public class Three_List_Exercises_1 {
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9));

		System.out.println(reShape(list, 4));
	}

	private static List<Integer> reShape(List<Integer> list, int n) {
		int count = 1;
		Iterator<Integer> it = list.iterator();
		List<Integer> res = new ArrayList<Integer>();
		int current_n = n;

		while(it.hasNext()) {
			int c = it.next();
			if(count < current_n)
				res.add(c);
			else if(count == current_n)
				current_n += n;
			count++;
		}

		return res;
	}
}

Output:

[1, 2, 3, 5, 6, 7, 9]

Solution – Exercise 2:

import java.util.*;

public class Three_List_Exercises_2 {
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>(Arrays.asList(1,2,1,3,1,4,1,5,1));
		System.out.println(removeDuplicate(list));
	}
	
	private static List<Integer> removeDuplicate(List<Integer> list) {
		Set<Integer> set = new LinkedHashSet<Integer>();
		List<Integer> res = new ArrayList<Integer>();
		
		Iterator<Integer> it = list.iterator();
		
		while(it.hasNext()) {
			set.add(it.next());
		}
		
		res.addAll(set);
		
		return res;
	}
}

Output:

[1, 2, 3, 4, 5]

Solution – Exercise 3:

import java.util.*;

public class Three_List_Exercises_3 {
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5));
		split(list);
	}
	
	private static void split(List<Integer> list) {
		int mid = list.size()/2;
		List<Integer> first = new ArrayList<Integer>();
		List<Integer> second = new ArrayList<Integer>();
		int count = 0;
		
		Iterator<Integer> it = list.iterator();
		
		while(it.hasNext()) {
			
			if(count++ < mid)
				first.add(it.next());
			else
				second.add(it.next());
		}
		
		System.out.println("f: " + first);
		System.out.println("s: " + second);
	}
}

Output:

f: [1, 2]
s: [3, 4, 5]

Pairing Students (Java)

Question is from here:

A teacher wants to create several sets of pairs of her students to work together on class projects; over the several sets, each student should be paired with each other student only once. For instance, with four students, there are three sets of pairings:

{Anne, Beth}, {Chet, Dirk}
{Anne, Chet}, {Beth, Dirk}
{Anne, Dirk}, {Beth, Chet}

Your task is to write a program that, given a list of students, produces a list of all possible sets of pairings, without duplicates.

Solution:

public class Pairing_Students {
	public static void main(String[] args) {
		String [] students = {"Anne", "Beth", "Chet", "Dirk"};
		pairThem(students);
	}
	
	private static void pairThem(String[] s) {
		for (int i = 0; i < s.length; i++) {
			for (int j = i + 1; j < s.length; j++) {
				System.out.println(s[i] + " " + s[j] + " ");
			}
		}
	}
}

Output:

Anne Beth 
Anne Chet 
Anne Dirk 
Beth Chet 
Beth Dirk 
Chet Dirk 

First Unrepeated Character In A String (Java)

Question is from here.

We have today another exercise from our never-ending supply of interview questions:

Given a string, find the first character that appears only once in the string. For instance, given the string “aabbcddd”, the first character that appears only once is the “c” found at the 4th character in the string, counting from 0. Be sure that your program properly handles the case that all characters appear more than once.

Your task is to write a program that finds the first unrepeated character in a string, and its index in the string.

My Solution:

import java.util.*;

public class First_Unrepeated_Character_In_A_String {
	public static void main(String[] args) {
		firstUnrepeated("aabbcdddee");
		firstUnrepeated("a");
		firstUnrepeated("aa");
	}

	private static void firstUnrepeated(String s) {
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		ArrayList<Character> ans = new ArrayList<Character>();

		for (int i = 0; i < s.length(); i++) {
			Integer freq = map.get(s.charAt(i));

			map.put(s.charAt(i), (freq == null) ? 1 : freq + 1);

			if(freq == null)
				ans.add(s.charAt(i));
			else
				ans.remove(new Character(s.charAt(i)));
		}
		if(ans.size() == 0)
			System.out.println("all characters appear more than once");
		else
			System.out.println(ans.get(0) + "  index: " + s.indexOf(ans.get(0)));
	}
}

Output:

c  index: 4
a  index: 0
all characters appear more than once

Reverse Groups (Java)

Question:

Challenge Description:

Given a list of numbers and a positive integer k, reverse the elements of the list, k items at a time. If the number of elements is not a multiple of k, then the remaining items in the end should be left as is.

Input sample:

Your program should accept as its first argument a path to a filename. Each line in this file contains a list of numbers and the number k, separated by a semicolon. The list of numbers are comma delimited. e.g.

1,2,3,4,5;2
1,2,3,4,5;3

Output sample:

Print out the new comma separated list of numbers obtained after reversing. e.g.

2,1,4,3,5
3,2,1,4,5

Solution:

public class Valid_parentheses {
	public static void main(String[] args) {
		isWellFormed("()");
		isWellFormed("([)]");
		isWellFormed("([{({})}])");
	}
	
	private static void isWellFormed(String s) {
		int len = s.length();
		int len2 = 0;
		
		while(s.length() > 0 && len != len2) {
			len = s.length();
			s = s.replace("()", "");
			s = s.replace("[]", "");
			s = s.replace("{}", "");
			len2 = s.length();
		}
		if(s.length() == 0)
			System.out.println("True");
		else
			System.out.println("False");
	}
}

Output:

True
False
True

Pascals Triangle (Java)

Question:

Your program should accept a positive integer which indicates the depth of the triangle e.g.

6

Output sample:

Print out the resulting pascal triangle up to the requested depth in row major form e.g.

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1

Solution:

import java.util.ArrayList;

public class Pascals_Triangle {
	public static void main(String[] args) {
		String s = args[0];
		pascalTri(Integer.parseInt(s));
	}

	private static void pascalTri(int n) {
		ArrayList<ArrayList<Integer>> tri = new ArrayList<ArrayList<Integer>>();
		tri.add(new ArrayList<Integer>());
		tri.get(0).add(1);

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i + 1; j++) {
				if(j == 0) {
					tri.add(new ArrayList<Integer>());
					tri.get(i).add(1);
				} else if(j == i) {
					tri.get(i).add(1);
				} else {
					int temp = tri.get(i - 1).get(j - 1) + tri.get(i - 1).get(j);
					tri.get(i).add(temp);
				}
			}
		}
		System.out.println(tri);
	}
}

Output:

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Cyclic Equality (Java)

Question is from here.

Two cyclic lists are equal if they have the same number of elements in the same order. For instance, the cyclic lists (1 2 3 4 5) and (3 4 5 1 2) are equal. So are the cyclic lists (1 1 2 2) and (2 1 1 2), and also the cyclic lists (1 1 1 1) and (1 1 1 1). The two cyclic lists (1 2 3 4) and (1 2 3 5) are not equal because they have different elements, and the cyclic lists (1 1 1) and (1 1 1 1) are not equal because they have different lengths.

Your task is to write a function that takes two cyclic lists and determines if they are equal.

Solution:

public class Cyclic_Equality {
	public static void main(String[] args) {
		System.out.println(isEqual("1 2 3 4 5", "3 4 5 1 2"));
		System.out.println(isEqual("1 1 2 2", "2 1 1 2"));
		System.out.println(isEqual("1 1 1", "1 1 1"));
		System.out.println(isEqual("1 2 3 4", "1 2 3 5"));
		System.out.println(isEqual("1 1 1", "1 1 1 1"));
	}
	
	private static boolean isEqual(String list1, String list2) {
		list1 = list1.replace(" ", ""); list2 = list2.replace(" ", "");
		
		StringBuilder l1 = new StringBuilder(list1);
		StringBuilder l2 = new StringBuilder(list2);
		
		if(l1.length() != l2.length())
			return false;
		
		int index = l2.indexOf("" + l1.charAt(0));
		String l2S = l2.substring(index, l2.length());
		String l2F = l2.substring(0, index);
		String l1F = l1.substring(0, l2S.length());
		String l1S = l1.substring(l2S.length(), l2.length());
			
		return l1F.equals(l2S) && l1S.equals(l2F);
	}
}

Output:

true
true
true
false
false

Pass Triangle – CodeEval – Java

Question is from here.

Challenge Description:

By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27.

   5
  9 6
 4 6 8
0 7 1 5

5 + 9 + 6 + 7 = 27

 

Input sample:

Your program should accept as its first argument a path to a filename. Input example is the following

5
9 6
4 6 8
0 7 1 5

You make also check full input file which will be used for your code evaluation.

 

Output sample:

The correct output is the maximum sum for the triangle. So for the given example the correct answer would be

27

Solution:

import java.io.*;
import java.util.*;

public class Pass_Triangle {
	private static List<ArrayList<Integer>> tree;
	public static void main(String[] args) {
		try {
			File file = new File(args[0]);
			BufferedReader in = new BufferedReader(new FileReader(file));
			tree = new ArrayList<ArrayList<Integer>>();
			String s;
			while ((s = in.readLine()) != null) {
				String[] values = s.split(" ");
				//temp is used to store each row
				ArrayList<Integer> temp = new ArrayList<Integer>();
				for (int j = 0; j < values.length; j++) {
					temp.add(Integer.parseInt(values[j]));
				}
				tree.add(temp);
			}
			System.out.println(tree);
			maxValue(tree.size());
			in.close();
		} catch (IOException e) {
			System.out.println("File Read Error: " + e.getMessage());
		}
	}
	
	
	public static void maxValue(int n) {
		//n is the size of the tree
		for (int i = n - 2; i >= 0; i--) {
			for (int j = 0; j <= i; j++) {
				if(tree.get(i + 1).get(j) > tree.get(i + 1).get(j + 1)) 
					tree.get(i).set(j, tree.get(i + 1).get(j) + tree.get(i).get(j));
				else
					tree.get(i).set(j, tree.get(i + 1).get(j + 1) + tree.get(i).get(j));
			}
		}
		System.out.println(tree.get(0).get(0));
	}
}

Output:

[[5], [9, 6], [4, 6, 8], [0, 7, 1, 5]]
27