Lab126 Interview Question for Software Engineer / Developers


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!

- vishal.cs.bits October 13, 2014 | Flag Reply
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

- gameboy1024 October 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- alisovenko October 14, 2014 | Flag
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.

- khunima October 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 13, 2014 | Flag
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.

- Soulslayer October 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Hashset

- Soulslayer October 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Read about disjoint set data structure

- Rahul Sharma October 13, 2014 | Flag Reply
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[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);
    }

- alisovenko October 14, 2014 | Flag Reply
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[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;
}

- Zortlord October 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- alisovenko October 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Zortlord October 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- curiosus October 20, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More