Google Interview Question
SDE-2sCountry: India
Wave: sort it, add half of the array when creating waves to avoid equal values close
public class WaveArrange {
public static int[] waveArrange(int[] input)
{
int[] result=new int[input.length];
int[] copiedInput=input.clone();
Arrays.sort(copiedInput);
int offset=input.length/2;
for (int i=0;i<input.length/2;i++)
{
result[2*i]=copiedInput[i+offset];
result[2*i+1]=copiedInput[i];
}
if (input.length%2==1)
{
result[input.length-1]=copiedInput[input.length-1];
}
return result;
}
}
@Test
public void testWaveArrange() throws Exception {
int[] input=new int[]{1,2,3};
int[] expected=new int[]{2,1,3};
assertArrayEquals(expected, WaveArrange.waveArrange(input));
input=new int[]{3,3,3,3,4,4,4,4};
expected=new int[]{4,3,4,3,4,3,4,3};
assertArrayEquals(expected, WaveArrange.waveArrange(input));
}
Your solution needs O(nlogn) time and O(n) extra space, can be solved with constant space complexity, just swap elements in place, see code below.
O(nlogn) time complexity, O(1) space complexity
import java.util.*;
public class WaveArray {
public static void main(String... args) {
int n = args.length;
if (n == 0) {
return;
}
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(args[i]);
}
Arrays.sort(a);
int half = n / 2;
for (int i = half; i < n; i++) {
int t = a[i];
a[i] = a[(i - half) * 2];
a[(i - half) * 2] = t;
}
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
Try this case {0, 1, 2, 3, 3, 3, 3, 3, 8, 9}
Expected answer is {3, 0, 3, 1, 3, 2, 8, 3, 9, 3}
Your code gives {3, 1, 3, 3, 3, 0, 8, 3, 9, 2}
Try this {0, 1, 2, 3, 3, 3, 3, 3, 8, 9}
Expected {3, 0, 3, 1, 3, 2, 8, 3, 9, 3}
Your code gives {3, 1, 3, 3, 3, 0, 8, 3, 9, 2}
For q1 : find median of the tree (there is a linear time algo). Partitions the array in two halts. To create a wave, pick one from the first array next from the second and you will be done in ear time.
Sorry to dissapoint, but I interviewed recently for Google Europe and got a graph question, and it was harder than the one you were given.
I think your graph question narrows down to finding the middle of the longest path in the tree.
Simple solution to the second question: do a DFS starting from every node of the graph, storing the maximum height found from that node. Choose the one with the minimum height as the node.
O(nlogn) time complexity, O(1) space complexity
import java.util.*;
public class WaveArray {
public static void main(String... args) {
int n = args.length;
if (n == 0) {
return;
}
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(args[i]);
}
Arrays.sort(a);
int half = n / 2;
for (int i = half; i < n; i++) {
int t = a[i];
a[i] = a[(i - half) * 2];
a[(i - half) * 2] = t;
}
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
2nd Q... finding largest path and middle of that path...this is what I suggested but how to find that path ?
1) I suggested separate dfs from each node -> O(n^2)
interviewer expecting O(n)
2) iteratively delete all current leaf nodes (using queue-reverse level order traversal) till u get single node and thats root node
Hi ,
if the graph has Tree characteristics, can we say the question is asking to find the root node of the graph ?
Thanks
@Scott: That is one way to put it, but assuming this is an undirected graph you don't really get specific pointers to the parent and children like you would in a real tree data structure. Just an adjacency list or matrix for each node and you have to find which node would best serve as the root to reduce the height of a depth-first search to a minimum.
Approach 2 is pretty interesting, I will definitely try to implement this and post my solution as graphs are my weakness :(
2) this is a variation of "find tree height" problem
class Node(object):
def __init__(self, name, *children):
self.name = name
self.children = children
self.height = None
def __repr__(self):
return "Node(%s, %r, height=%d)" % (self.name, self.children, self.height)
def find_height(node):
height = 1
for child in node.children:
find_height(child)
height = max(height, child.height + 1)
node.height = height
def find_min_height(node, height_from_parent=0):
if not node.children:
return height_from_parent
n = len(node.children)
lmax = [0] * n
rmax = [0] * n
for i in xrange(1, n):
lmax[i] = max(lmax[i - 1], node.children[i - 1].height)
rmax[n - i - 1] = max(rmax[n - i], node.children[n - i].height)
return min(
find_min_height(child, max(lm, rm, height_from_parent) + 1)
for (lm, rm, child) in zip(lmax, rmax, node.children)
)
N = Node
tree = N(1, N(2, N(3, N(4))))
find_height(tree)
assert find_min_height(tree) == 3
So basically for each node we find height, leafs have height 1, parents 2 and so on.
Then we need to query each node "what would be your height if you were root?"
That's maximum amongs heights of all of its children and one plus height of its parent if the parent was root and didn't have that particular node as a child.
Time O(n) since we visit each node 1 time when finding height and 1 time when finding minimum height.
private void waveArrangement(int[] intArray) {
// TODO Auto-generated method stub
int[] waveArray = new int[intArray.length];
waveArray=intArray;
Arrays.sort(waveArray);
for (int i=1;i<waveArray.length-1;i=i+2){
int temp= waveArray[i];
waveArray[i]=waveArray[i+1];
waveArray[i+1]=temp;
waveArray[i]=waveArray[i];
}
for(int i=0;i<waveArray.length;i++)
System.out.print(waveArray[i]+",");
}
Q#1.
I created the solution that works on all the variants, including {0, 1, 2, 3, 3, 3, 3, 3, 8, 9},
but it is quite long (200 lines) and cannot be an interview question. Why do they ask such questions?
If needed, I can post the code.
Regarding the 2nd question,
The efficiency of algo is O(n). The idea is to do DFS from every node of the graph and return the minimum height. But this approach would take O(n^2). One important thing to node here is that once the height is calculated using any node as reference, the height of tree wrt other node can be easily calculated. Follow the below steps..
1. Find the height of each node picking any one node as root.. It takes walking the nodes in DFS.. Takes O(n).
2. Foreach brach from that root
h = max (height from remaining branch)
foreach node in that branch {
height(node) = max(height(node), (h + height of node from the root))
min_height = min(min_height, height(node))
}
return min_height;
}
Java solution for minimum height tree question.
private static <T> Node<T> getBalancedRoot(Node<T> node) {
// Variables to cache the longest and second longest adjacent paths
Stack<Node<T>> longest = new Stack<>();
Stack<Node<T>> longest2 = new Stack<>();
// Loop through each adjacent node
for (Node<T> connection : node.adjacent) {
// Get the longest path for that child node
Stack<Node<T>> childPath = getLongestPath(connection, node);
// Adjust cached longest paths accordingly
if (childPath.size() > longest.size()) {
longest2 = longest;
longest = childPath;
} else if (childPath.size() > longest2.size()) {
longest2 = childPath;
}
}
// Set the returned root node to our originating node, for now
Node<T> root = node;
int diff = longest.size() - longest2.size();
// If the difference in size between the adjacent paths is more than 1 node, we need to rebalance
while (diff > 1) {
// This is equivalent to moving one node over, e.g.
// 5 3 9 1 (7) 4 2 --- Difference = 4 - 2 = 2
// becomes
// 5 3 9 (1) 7 4 2 --- Difference = 3 - 3 = 0
root = longest.pop();
diff -= 2;
}
// The node at the start of the longest path is now the root, return it
return root;
}
private static <T> Stack<Node<T>> getLongestPath(Node<T> node, Node<T> previous) {
Stack<Node<T>> longestPath = new Stack<>();
if (!node.adjacent.isEmpty()) {
for (Node<T> adjacent : node.adjacent) {
if (adjacent == previous) continue; // Prevent circular loop
Stack<Node<T>> thisLongest = getLongestPath(adjacent, node);
if (thisLongest.size() > longestPath.size()) {
longestPath = thisLongest;
}
}
}
longestPath.add(node);
return longestPath;
}
Here is C++ solution to the first question running in O(n log n).
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool compare(int prev, int next)
{
return prev >= next;
}
void swap(vector<int>& list, int prev, int next)
{
int tmp = list[prev];
list[prev] = list[next];
list[next] = tmp;
}
void sort_to_waveform(vector<int>& input)
{
sort(input.begin(), input.end(), compare);
int pos = 1;
while(pos < input.size()-1)
{
swap(input, pos, pos+1);
pos+=2;
}
}
void print(vector<int>& list)
{
for(int i =0; i <list.size(); i++)
cout<<list[i]<<" -> ";
cout<<endl;
}
int main ()
{
vector<int> input;
input.push_back(1);
input.push_back(6);
input.push_back(3);
input.push_back(7);
input.push_back(2);
input.push_back(10);
input.push_back(9);
input.push_back(4);
input.push_back(5);
input.push_back(11);
print(input);
sort_to_waveform(input);
print(input);
return 1;
}
python solution for #1
import itertools
def wave_sort(arr):
arr.sort()
mid = len(arr) // 2
L = arr[0:mid]
R = arr[mid:]
result = []
for i in itertools.izip_longest(L, R):
if None not in i:
result.extend([i[1], i[0]])
else:
result.extend([val for val in i if val is not None])
return result
print wave_sort([0, 1, 2, 3, 3, 3, 3, 3, 8, 9])
private void waveArrangement(int[] intArray) {
// TODO Auto-generated method stub
int[] waveArray = new int[intArray.length];
waveArray=intArray;
Arrays.sort(waveArray);
for (int i=1;i<waveArray.length-1;i=i+2){
int temp= waveArray[i];
waveArray[i]=waveArray[i+1];
waveArray[i+1]=temp;
waveArray[i]=waveArray[i];
}
for(int i=0;i<waveArray.length;i++)
System.out.print(waveArray[i]+",");
}
Second question is to find the diameter of a tree and return the mid vertex of diameter.
- madi.sagimbekov November 17, 2015