Microsoft Interview Question
Country: United States
Interview Type: In-Person
class Program
{
static void Main(string[] args)
{
String[] inputArray = { "0110000", "1010000", "1100000", "0000001", "0001000", "0000100", "0000010" /*"0110000", "1010000", "1100000", "0000100", "1000001", "0001000", "0000010"*/ };
IdentifyGroups.FindGroups(inputArray);
}
}
public class IdentifyGroups
{
private static int[] groups; // groupNumber of the node(employee)
private static Dictionary<int, List<EmployeeGroup>> employeeGroups = new Dictionary<int, List<EmployeeGroup>>();
public static void FindGroups(String[] employeeInformation)
{
int totalEmployees = employeeInformation.Length;
groups = new int[totalEmployees];
for (int i = 0; i < totalEmployees; i++)
{
groups[i] = i;
employeeGroups[i] = new List<EmployeeGroup>(new[] { new EmployeeGroup { Id = i, Employee = employeeInformation[i] } });
}
// Mapping each employee to its group
for (int i = 0; i < totalEmployees; i++)
{
int currentEmployeeGroup = groups[i];
char[] empId = employeeInformation[i].ToCharArray();
for (int j = 0; j < empId.Length; j++)
{
if (empId[j] == '1')
{
int relatedGroupKey = groups[j];
if (relatedGroupKey != currentEmployeeGroup)
{
employeeGroups[currentEmployeeGroup].AddRange(employeeGroups[relatedGroupKey]);
foreach (EmployeeGroup group in employeeGroups[relatedGroupKey])
{
groups[group.Id] = currentEmployeeGroup;
}
employeeGroups.Remove(relatedGroupKey);
}
}
}
}
//Printing the group
foreach (KeyValuePair<int, List<EmployeeGroup>> m in employeeGroups)
{
Console.Write(m.Key + " : ");
foreach (EmployeeGroup value in m.Value)
{
Console.Write(value.Employee + ", ");
}
Console.WriteLine();
}
}
}
public class EmployeeGroup
{
public int Id;
public string Employee;
}
The solution I am providing is the solution to find the connected components using DFS in an UnDirected Graph. Here each employee is considered as a Node and the other employees he/she works with are the adjacentNodes. The code gives correct solution to me. Please try and let me know if it fails on some conditions..
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class EmployeeEmployeeRelation
{
private static boolean[] marked; // to check is a node(employee) is visited
private static int[] groupNumber; // groupNumber of the node(employee)
private static int count = 1; // count assigns the groupNumber
public static void findGroups(String[] employeeInformation)
{
int totalEmployees = employeeInformation.length;
marked = new boolean[totalEmployees];
groupNumber = new int[totalEmployees];
for(int i = 0 ; i < totalEmployees ; i++)
{
if(!marked[i])
{
findAdjacentEmployees(employeeInformation, employeeInformation[i], i); // calling DFS
count++;
}
}
// Mapping each employee to its group
Map<Integer, List<String>> employeeGroups = new HashMap<Integer, List<String>>();
for(int i = 0 ; i < totalEmployees ; i++)
{
List<String> group = employeeGroups.get(groupNumber[i]);
if(group == null)
employeeGroups.put(groupNumber[i], group = new ArrayList<String>());
group.add(employeeInformation[i]);
}
//Printing the group
for(Map.Entry<Integer, List<String>> m : employeeGroups.entrySet())
System.out.println(m.getKey() + " : " + m.getValue());
}
// Applying DFS sort of technique to find the adjacent nodes. The method is nothing but DFS.
public static void findAdjacentEmployees(String[] employeeInformation, String currentEmployee, int id)
{
marked[id] = true;
groupNumber[id] = count;
char[] empId = currentEmployee.toCharArray();
for(int i = 0 ; i < empId.length ; i++)
if(empId[i] == '1')
if(!marked[i])
findAdjacentEmployees(employeeInformation, employeeInformation[i], i);
}
public static void main(String[] args)
{
String[] inputArray = {"0110000", "1010000", "1100000", "0000001", "0001000", "0000100", "0000010"};
findGroups(inputArray);
}
}
I went with a Depth-First Search using an iterative Stack.
GroupId and Visited Information has been rolled up into a single int array which is returned to the caller.
vector<int> FindGroups(vector<string> employees)
{
vector<int> groups(employees.size());
stack<int> group;
int groupId = 0;
for (size_t i = 0; i < employees.size(); i++)
{
if (groups[i])
continue;
groupId++;
group.push(i);
while (!group.empty())
{
int employeeId = group.top();
group.pop();
groups[employeeId] = groupId;
string coworkers = employees[employeeId];
for (size_t i = 0; i < coworkers.length(); i++)
{
if (coworkers[i] == '1' && groups[i] == 0)
{
group.push(i);
}
}
}
}
return groups;
}
Treat the array of bits as a matrix (Use Bit rotation to achieve this). The matrix is a symmetric matrix with diagonal elements being zero.Now traverse the upper half of the matrix using bitwise right rotation and check for values of 1 and put the ones in their group. YOu can either use graphs or labels depeding on your inclination.
Complexity roughly O(N^2)/2. If you use graph with the matrix, it will be even lesser.
My proposal starts with setting the bit of worker in his own bipmap. Ex: worker 0 has bit 0 = 1.
After that, gonna iterate forward doing binary OR with all other workers presented in the bitmap.
As I have to iterate through array changing the bit set, I'm not sure about running complexity.
Follow my code:
/*
Output:
Before:
0011
0010
1100
1000
After:
0011
0011
1100
1100
*/
#include <iostream>
#include <vector>
#include <bitset>
int main() {
const int bits = 4;
const int elements = 4;
std::vector<std::bitset<bits>> workers(elements);
workers[0].set(0, 1).set(1, 1);
workers[1].set(1, 1);
workers[2].set(2, 1).set(3, 1);
workers[3].set(3, 1);
std::cout << "before:" << std::endl;
for(auto worker: workers)
std::cout << worker << std::endl;
std::cout << std::endl << std::endl;
for(int i = 0; i < workers.size(); i++) {
if(workers[i].any() == false) {
// Working alone
continue;
}
// Looking for partners
for(int b = 0; b < workers[i].size(); ++b) {
if(workers[i].test(b)) {
// Bit b of worker [i] is set
workers[i] |= workers[b];
workers[b] = workers[i];
}
}
}
std::cout << "after:" << std::endl;
for(auto worker: workers)
std::cout << worker << std::endl;
return 0;
}
As it was mentioned above - it is a simple graph problem. You need to find strongly connected components of the graph. Subsets of vertexes, where each u is reachable from each v, both belongs to the subset. This can be solved yousing double DFS.
vector < vector<int> > g, gr;
vector<char> used;
vector<int> order, component;
void dfs1 (int v) {
used[v] = true;
for (size_t i=0; i<g[v].size(); ++i)
if (!used[ g[v][i] ])
dfs1 (g[v][i]);
order.push_back (v);
}
void dfs2 (int v) {
used[v] = true;
component.push_back (v);
for (size_t i=0; i<gr[v].size(); ++i)
if (!used[ gr[v][i] ])
dfs2 (gr[v][i]);
}
int main() {
int n;
read n from file
for (;;) {
int a, b;
read from file edge
g[a].push_back (b);
gr[b].push_back (a);
}
used.assign (n, false);
for (int i=0; i<n; ++i)
if (!used[i])
dfs1 (i);
used.assign (n, false);
for (int i=0; i<n; ++i) {
int v = order[n-1-i];
if (!used[v]) {
dfs2 (v);
output component
component.clear();
}
}
}
the number of groups will be equal to the number of different values of the array.
Thus,we can find the number of different groups by counting the number of unique values in the n size array.
we can further reduce the time complexity by searching for unique values in the array only until the number of 1's in the bit values of the unique element(eg if element 1=0010110 then here 3 1's are there) is less than n.
algorithm
1 group1 will contain all employee whose bit is 1 in element 0
2 val=value of element 0
3 for next group
2.1 find the first bit which is zero in the val say d
2.2 all employee whose bit is 1 in element d is included in the group
2.3 val=val OR element d(bitwise or)
4 continue step 3 until val=111...(all bits are1)
algorithm
1 group1 will contain all employee whose bit is 1 in element 0
2 val=value of element 0
3 for next group
3.1 find the first bit which is zero in the val say d
3.2 all employee whose bit is 1 in element d is included in the group
3.3 val=val OR element d(bitwise or)
4 continue step 3 until val=111...(all bits are1)
Straightforward way:
- the matrix is a symmetric, so will check only half of it;
- get co-workers of current element and try to merge them with existing groups.
public class MatrixGroups
{
public static HashSet<int>[] GetGroups(BitMatrix matrix)
{
List<HashSet<int>> groups = new List<HashSet<int>>();
HashSet<int> set = null;
for (int y = 0; y < matrix.Size - 1; y++)
{
for (int x = 1 + y; x < matrix.Size; x++)
{
if (matrix[x, y] == false)
continue;
if (set == null)
{
set = new HashSet<int>();
set.Add(y);
}
set.Add(x);
}
if (set != null && TryMerge(groups, set) == false)
groups.Add(set);
set = null;
}
return groups.ToArray();
}
private static bool TryMerge(List<HashSet<int>> groups, HashSet<int> set)
{
Stack<int> indexes = new Stack<int>();
for (int i = 0; i < groups.Count; i++)
if (groups[i].Overlaps(set))
indexes.Push(i);
if (indexes.Count == 0)
return false;
while (indexes.Count > 1)
{
int i = indexes.Pop();
groups[indexes.Peek()].UnionWith(groups[i]);
groups.RemoveAt(i);
}
groups[indexes.Pop()].UnionWith(set);
return true;
}
}
static void DoubleLink(bool[][] T, int N)
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
T[j][i] = true;
}
static int[] Grouping(bool[][] T, int N)
{
int[] groups = new int[N];
int curgroup = 0;
Queue<int> nodes = new Queue<int>();
for (int i = 0; i < N; i++)
{
if (groups[i] == 0)
{
groups[i] = ++curgroup;
nodes.Enqueue(i);
while (nodes.Count != 0)
{
int j = nodes.Dequeue();
for (int k = 0; k < N; k++)
{
if (T[j][k] == true && groups[k] == 0)
{
groups[k] = curgroup;
nodes.Enqueue(k);
}
}
}
}
}
return groups;
}
Used C# and Linq:
class Employee
{
public Guid EmployeeId { get; set; }
public Guid GroupId { get; set; }
public UInt64 RelationNumber { get; set; }
public string Name { get; set; }
public Employee()
{
EmployeeId = Guid.NewGuid();
GroupId = Guid.Empty;
}
public Employee(string name, UInt64 relationNumber) : this()
{
Name = name;
RelationNumber = relationNumber;
}
public static Hashtable GetGroups(Employee[] employeeList)
{
Guid currentGroupId = Guid.Empty;
UInt64 relationNumber = 0;
int j = -1;
List<Employee> currentGroup = null;
List<Employee> otherGroup = null;
Hashtable groups = new Hashtable();
for (int i = 0; i < employeeList.Length; i++)
{
currentGroupId = employeeList[i].GroupId;
if (currentGroupId == Guid.Empty)
{
// start new Group
currentGroupId = Guid.NewGuid();
currentGroup = new List<Employee>();
employeeList[i].GroupId = currentGroupId;
currentGroup.Add(employeeList[i]);
}
else
{
currentGroup = (List<Employee>)groups[currentGroupId];
groups.Remove(currentGroupId);
}
relationNumber = employeeList[i].RelationNumber;
j = employeeList.Length - 1;
while (relationNumber > 0)
{
if ((relationNumber & 1) != 0)
{
if (employeeList[j].GroupId == Guid.Empty)
{
// group isn't assigned yet
employeeList[j].GroupId = currentGroupId;
currentGroup.Add(employeeList[j]);
}
else
{
// group is assigned, so merge it with current group
if (employeeList[j].GroupId != currentGroupId)
{
otherGroup = (List<Employee>)groups[employeeList[j].GroupId];
groups.Remove(employeeList[j].GroupId);
otherGroup.ForEach(delegate(Employee employee)
{
employee.GroupId = currentGroupId;
});
currentGroup.AddRange(otherGroup);
}
}
}
relationNumber >>= 1;
j--;
}
groups.Add(currentGroupId, currentGroup);
}
return groups;
}
}
DFS solution:
class Employee
{
public Guid EmployeeId { get; set; }
public Guid GroupId { get; set; }
public UInt64 RelationNumber { get; set; }
public string Name { get; set; }
public Employee()
{
EmployeeId = Guid.NewGuid();
GroupId = Guid.Empty;
}
public Employee(string name, UInt64 relationNumber) : this()
{
Name = name;
RelationNumber = relationNumber;
}
/// <summary>
/// DFS approach helper
/// </summary>
/// <param name="groupId"></param>
/// <param name="employeeList"></param>
/// <param name="currentEmployeeNumber"></param>
/// <param name="group"></param>
private static void GetGroupDfsHelper(Guid groupId,
Employee[] employeeList,
int currentEmployeeNumber,
ref List<Employee> group)
{
UInt64 relationNumber = employeeList[currentEmployeeNumber].RelationNumber;
int j = employeeList.Length - 1;
employeeList[currentEmployeeNumber].GroupId = groupId;
group.Add(employeeList[currentEmployeeNumber]);
while (relationNumber > 0)
{
if ((relationNumber & 1) != 0)
{
if (employeeList[j].GroupId == Guid.Empty)
{
GetGroupDfsHelper(groupId, employeeList, j, ref group);
}
}
relationNumber >>= 1;
j--;
}
}
/// <summary>
/// DFS approach
/// </summary>
/// <param name="employeeList"></param>
/// <returns></returns>
public static Hashtable GetGroupsDfs(Employee[] employeeList)
{
Guid currentGroupId = Guid.Empty;
List<Employee> group = null;
Hashtable groups = new Hashtable();
for (int i = 0; i < employeeList.Length; i++)
{
if (employeeList[i].GroupId == Guid.Empty)
{
currentGroupId = Guid.NewGuid();
group = new List<Employee>();
GetGroupDfsHelper(currentGroupId, employeeList, i, ref group);
groups.Add(currentGroupId, group);
}
}
return groups;
}
}
I would go for a graph solution.
Construct a graph and connect all employees who work together e.g if A works with B and B works with C then the connection is as follows A-B-C. For each node perform search and create its team. Skip nodes which has been already assigned to teams. In this way transitive property will be handled quite well.
Union-Find Set might work.
- uuuouou January 04, 2014(1)at first everybody himself/herself forms a set.
(2)scan every element's bits, if the kth bit of element[i] is 1, which means i work with k, then find k's set and i's set, and merge them if they are not in the same sets.
(3)as the average time complexity of find and merge is O(1), the total time complexity is O(N*N), while space complexity is O(N)