## Google Interview Question for Software Developers

Country: India
Interview Type: In-Person

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

Question seems incomplete. Are you asking for all possible(over-lapping) sub-arrays of size k? And minimum of what? Do we need to sum them? or min element in them?

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

Actually I hate this is a very defficult problem to solve in O(n).
I was doing similar exercise of implement a queue with a Max() function from the book "Elements of Programming Interviews" which has a O(n) 'Ninja' level solution which I could not get as it required a another 'ninja' solution from another problem.

This is a variation of implementing a Queue which had a Max function which used a Stack which maintained the max but in this case it maintains the minimum.

This is a very hard solution to perform this in O(n) taking O(n) space as well.

``````class Stack<T>()
{
List<StackNode<T>> buffer = new List<StackNode<T>>();
private class StackNode<T>
{
T Value;
T Min;
}

public void Push(T val)
{
var node = new StackNode<T>();
node.Value = val;
if(buffer.Count == 0 || buffer[buffer.Count - 1].Min > val)
{
node.Min = val;
}
else
{
node.Min = buffer[buffer.Count - 1].Min;
}

}

void T Pop()
{
var node = buffer[buffer.Count - 1];
buffer.RemoveAt(buffer.Count - 1);

return node.Value;
}

public bool IsEmpty()
{
return buffer.Count == 0;
}

public T Min()
{
if(buffer.Count > 0)
return buffer[Count - 1].Min;

return default(T);
}
}

public class Queue<T>
{
Stack<T> A = new Stack<T>();
Stack<T> B = new Stack<T>();

public void Enqueue(T val)
{
A.Push(val);
}

public T Dequeue()
{
if(B.IsEmpty())
{
while(!A.Empty())
{
B.Push(A.Pop());
}
}

return B.Pop();
}

public T Min()
{
wile(!A.Empty())
{
B.Push(A.Pop());
}

return B.Min();
}
}

public IEnumerable<int> FindMinOfSubArray(int[] A, int k)
{
if(A.Length < k) throw ArgumentOutOfRangeException("k");
Queue q = new Queue();

for(int i = 0; i < k; i++)
{
q.Enqueue(A[i]);
}

int min =	q.Min();
for(int j = k; j < A.Length; j++)
{
q.Enqueue(A[j]);
q.Dequeue();

var temp = q.Min();
if(min > temp)
min = temp;

yield return min;
}
}``````

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

In order to keep time-complexity at O(n), only one loop can be used. So, to avoid a second loop, the first has to repeat itself to iterate thru each subarray.

``````import java.util.*;

public class Careercup5 {
public static ArrayList findMin(ArrayList<ArrayList<Integer>> main){
ArrayList<Integer> result = new ArrayList<Integer>();
int smallestValue = Integer.MAX_VALUE;
int j = 0;
int n = main.size(); //size of array
int k; //size of each subarray

for (int i = 0; i < n; i++){
k = main.get(i).size();

if (j < k){
smallestValue = Math.min(smallestValue, main.get(i).get(j)); //find new minimum value
j++;	//helps iterate thru subarrays
i--;	//helps keep the loop at current subarray
}
else {
j = 0;
smallestValue = Integer.MAX_VALUE;
}
}
return result;
}
}``````

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

Main{}

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

``````for (int i=0; i<n; i++) {
if (i>=k) {
cout << q.front() << " ";
if (q.front() == a[i-k]) {
q.pop();
}
}
while (!q.empty() && a[i] < q.front()) {
q.pop();
}
q.push(a[i]);
}
cout << q.front() << endl;
return 0;``````

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

Assuming its for every overlapping array, here is a simple order of N solution.

``````int min = array[0]
for(int i=0: k-1){
if(array[I] < min)
min = array[i];
}
cout<<"Min so far" << min;
for(int j = k : j<n-1){
if(array[j] < min){
min = array[j];
//display min
}
}``````

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.