Google Interview Question for SDE-2s


Country: India




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

Second question is to find the diameter of a tree and return the mid vertex of diameter.

- madi.sagimbekov November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes.

- little December 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Graveton November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- madi.sagimbekov November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- madi.sagimbekov November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- Anonymous November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- peisi November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry for the duplicate replies.......couldn't remove.....

- lepeisi November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- YoMrWhite November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you can only find an approximate median in O(N) using medians of medians algorithm. Can you please let me know how to find exact median in O(N) time?

- Stanley November 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

maybe then we should conclude that luck also play imp role :)

- sameer November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

so what was your question ?

- sameer November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Potato November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes this is what I suggested but this will have O(n^2) complexity...interviewer was expecting O(n) solution (which can be solved using queue...by iteratively deleting current leaf nodes)

- sameer November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- madi.sagimbekov November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- lepeisi November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sameer November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi ,
if the graph has Tree characteristics, can we say the question is asking to find the root node of the graph ?

Thanks

- Scott November 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 :(

- damien5314 November 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- emb November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

careercup won't let me edit comments,
>and 1 + height of its parent
fix

- emb November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]+",");

}

- Nandhinee November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- zr.roman November 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just sort it and arrange in form: a4a5a3a6a2a7a1a8

- sameer November 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Punit November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- damien5314 November 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- hankm2004 December 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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])

- daniel March 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Q1 can be done in O(n) time. You don't have to sort the array. You only need to split it into two halves. First find the median, and then use that as a pivot to rearrange. Then alternate your picks among the two halves.

- kefeilei87 September 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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]+",");

}

- Anonymous November 18, 2015 | 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