Lab126 Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Hmm, seems to be a good application case for UnionFind.
en.m.wikipedia.org/wiki/Disjoint-set_data_structure
Find all connected components of the graph where nodes are all the distinct characters, here (A,B,C,D,E,F,G,H) and edges are the given pairs. Here A-B , C-D ... are edges.
Union-find seems to be bad variant as it has the api "are two points connected" and "connect two points". So this would lead to O(n^2) algorigthm, where N is the number of pairs.
For ASCI string we can use a simple graph that can be checked for connectivity using DFS. And although the implementation is a bit massive, it's very simple:
1. create graph as adjacency list
2. dfs through it, all dfs cycle discovers the connected elements
This is effectively O(n) implementation
public static void clusterize(char[][] pairs) {
// build graph
List<Character>[] graph = buildGraph(pairs);
char[] marked = new char[255];
for (int i = 0; i < graph.length; i++) {
if (marked[i] == 0 && graph[i] != null) {
// we have not come to this letter yet
dfsAndPrint(i, graph, marked);
System.out.println();
}
}
}
private static void dfsAndPrint(int i, List<Character>[] graph, char[] marked) {
if (marked[i] > 0) {
return;
}
System.out.printf("%s, ", (char)i);
marked[i] = 1;
if (graph[i] != null) {
for (Character c : graph[i]) {
dfsAndPrint(c, graph, marked);
}
}
}
private static List<Character>[] buildGraph(char[][] pairs) {
List<Character>[] graph = new ArrayList[255];
for (final char[] pair : pairs) {
addToGraph(graph, pair[0], pair[1]);
addToGraph(graph, pair[1], pair[0]);
}
return graph;
}
public static void addToGraph(List<Character>[] graph, char v1, char v2) {
List<Character> characters = graph[v1];
if (characters == null) {
characters = new ArrayList<>();
graph[v1] = characters;
}
characters.add(v2);
}
public static void main(String[] args) {
char[][] input = {
{'a', 'b'},
{'c', 'd'},
{'e', 'f'},
{'g', 'h'},
{'a', 'd'},
{'f', 'g'}
};
clusterize(input);
}
Union find approach would be a O(n) and should be relatively simple:
public static ArrayList<char[]> getSets(char[][] pairs){
HashMap<Character, Character> unionFindMap = new HashMap<Character, Character>();
//add the mappings of left to right
for(char[] pair : pairs){
union(unionFindMap, pair[0], pair[1]);
}
//organize group the mapped content
HashMap<Character, ArrayList<Character>> resultCollator = new HashMap<Character, ArrayList<Character>>();
for(Entry<Character, Character> entry : unionFindMap.entrySet()){
Character val = entry.getValue();
Character key = entry.getKey();
if(val == null){
val = key;
}
ArrayList<Character> list = resultCollator.get(val);
if(list == null){
list = new ArrayList<Character>();
resultCollator.put(val, list);
}
list.add(key);
}
//make the output
ArrayList<char[]> results = new ArrayList<char[]>(resultCollator.size());
for(ArrayList<Character> list : resultCollator.getValue()){
char[] set = new char[list.size()];
for(int i = 0; i < list.size(); i++){
set[i] = list.get(i);
}
results.add(set);
}
return results;
}
private void union(HashMap<Character, Character> unionFindMap, char c1, char c2){
if(!unionFindMap.contains(c2)){
unionFindMap.put(c2, null);
}
char dest = find(unionFindMap, c2);
unionFindMap.put(c1, c2);
}
private char find(HashMap<Character, Character> unionFindMap, char c){
Character dest = unionFindMap.get(c);
if(dest == null){
return c;
}
char newDest = find(unionFindMap, dest);
unionFindMap.put(c, newDest);
return newDest;
}
Implemented a few things incorrectly including collating the results:
public static ArrayList<char[]> getSets(char[][] pairs){
HashMap<Character, Character> unionFindMap = new HashMap<Character, Character>();
//add the mappings of left to right
for(char[] pair : pairs){
union(unionFindMap, pair[0], pair[1]);
}
//organize group the mapped content
HashMap<Character, ArrayList<Character>> resultCollator = new HashMap<Character, ArrayList<Character>>();
for(Character key : unionFindMap.keySet()){
Character val = find(unionFindMap,key);
if(val == null){
val = key;
}
ArrayList<Character> list = resultCollator.get(val);
if(list == null){
list = new ArrayList<Character>();
resultCollator.put(val, list);
}
list.add(key);
}
//make the output
ArrayList<char[]> results = new ArrayList<char[]>(resultCollator.size());
for(ArrayList<Character> list : resultCollator.values()){
char[] set = new char[list.size()];
for(int i = 0; i < list.size(); i++){
set[i] = list.get(i);
}
results.add(set);
}
return results;
}
private static void union(HashMap<Character, Character> unionFindMap, char c1, char c2){
if(!unionFindMap.containsKey(c2)){
unionFindMap.put(c2, null);
}
if(!unionFindMap.containsKey(c1)){
unionFindMap.put(c1, null);
}
char dest1 = find(unionFindMap, c1);
char dest2 = find(unionFindMap, c2);
unionFindMap.put(dest2, dest1);
}
private static char find(HashMap<Character, Character> unionFindMap, char c){
Character dest = unionFindMap.get(c);
if(dest == null){
return c;
}
char newDest = find(unionFindMap, dest);
unionFindMap.put(c, newDest);
return newDest;
}
How about using double linked list.
like this :
(find right end of first and left end of second then connect them.)
a<->b, c<->d, e<->f, g<->h
a-d
(right end of 'a' is 'b' and left end of 'd' is 'c' so connect 'b' and 'c')
a<->b<->c<->d
:
:
Here's the code :
(In fact the code has a problem :
if you add pairs in same group alreday, the code will make cirular link
so need to add the code checking the case)
import java.util.HashMap;
import java.util.Map;
public class Main {
public static class DoubleLink {
Character left;
Character right;
}
static Map <Character, DoubleLink> map = new HashMap<Character, DoubleLink>();
static void addLink(Character a, Character b) {
Character LeftEndB = getLeftEnd(b);
Character RightEndA = getRightEnd(a);
map.get(LeftEndB).left = RightEndA;
map.get(RightEndA).right = LeftEndB;
}
static Character getLeftEnd(Character a) {
if (!map.containsKey(a)) {
map.put(a, new DoubleLink());
return a;
}
Character end = a;
while (map.get(end).left != null) {
end = map.get(end).left;
}
return end;
}
static Character getRightEnd(Character a) {
if (!map.containsKey(a)) {
map.put(a, new DoubleLink());
return a;
}
Character end = a;
while (map.get(end).right != null) {
end = map.get(end).right;
}
return end;
}
public static void main(String[] args) {
addLink('a','b');
addLink('c','d');
addLink('e','f');
addLink('g','h');
addLink('a','d');
addLink('f','g');
for (Character key : map.keySet()) {
if (map.get(key).left == null) {
System.out.print(key);
while (true) {
key = map.get(key).right;
if (key == null) {
break;
}
System.out.print(key);
}
System.out.println();
}
}
}
}
There are two algorithms here : quickunion and quickfind.
- vishal.cs.bits October 13, 2014If we use quickfind, it will be kind of slow, if we have to add the pairs.
it will be a better choice if we use quickunion!