## Lab126 Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
9
of 9 vote

There are two algorithms here : quickunion and quickfind.
If 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!

Comment hidden because of low score. Click to expand.
4
of 6 vote

Hmm, seems to be a good application case for UnionFind.
en.m.wikipedia.org/wiki/Disjoint-set_data_structure

Comment hidden because of low score. Click to expand.
0

Could you provide the solution? What complexity will it have?
I see a lot of pluses, though it does not seem to be the linear solution. Check my O(n) solution with graphs and DFS below

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

That is a nice approach but maintaining Graph just for evaluating this. Will it not be expensive ? I am asking.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it is just bucket printing. Create bucket and do the rest.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Hashset

Comment hidden because of low score. Click to expand.
0

HashSet can have only unique entries. Here we have mapping A-B and A-D..

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

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;

for (final char[] pair : pairs) {
}
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;
}
}

public static void main(String[] args) {
char[][] input = {
{'a', 'b'},
{'c', 'd'},
{'e', 'f'},
{'g', 'h'},
{'a', 'd'},
{'f', 'g'}
};
clusterize(input);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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, pair);
}

//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);
}
}

//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);
}
}
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;
}``````

Comment hidden because of low score. Click to expand.
0

Your code output for example input:
[b]
[a, c, d]
[e]
[f]
[g, h]

Comment hidden because of low score. Click to expand.
0

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, pair);
}

//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);
}
}

//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);
}
}
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)) {
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)) {
return a;
}
Character end = a;
while (map.get(end).right != null) {
end = map.get(end).right;
}
return end;
}

public static void main(String[] args) {

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();
}
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.