## Google Interview Question for Software Developers

Country: United States

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

This is 0-1 knapsack problem where the thief wants to steal maximum number of items. Max given is sack limit and the word lengths are items weight here.

``````for j from 1 to max:
for all i if array[i] < j:
sol[j] = max(sol[j], 1 + sol[j - array[i]])
return sol[max]``````

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

Based on this:
"Let's say I have a word "I love chicken", I can break the number of characters in each word, like so: [1] [4] [7] [1,4] [4,7], [1,4,7]."
we need to consider the provided ordering of the array in order to construct valid phrases. This suggests that we should NOT sort the input array.

We are looking for the longest phrase.. which means the longest continues sub-sequence in this array where the sum <= max.

``````public static int longestPhraseWith(int[] input, int max) {
if (input == null || input.length == 0 || max <= 0) {
return 0;
}

int i = 0;
while (input[i] > max) {
i++;
}

if (i >= input.length) {
return 0;
}

int words = 1, maxWords = 1;
int leftIndex = i;
int sum = input[i];

for (int j = i + 1; j < input.length; j++) {
sum += input[j];
words++;
if (sum <= max) {
maxWords = Math.max(maxWords, words);
}
else {
while (sum > max && leftIndex <= j) {
sum -= input[leftIndex++];
words--;
}
}
}

return maxWords;
}``````

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

This is the c++ implementation.
I think we can simply find the longest subsequence
whose sum is no greater than max.

``````int longestSubseqMaxSum(const vector<int> &arr, int maxSum)
{
int p1 =0, p2 = 0;
int S = arr[0];
int maxLen = 0;

if(S <= maxSum)
maxLen = 1;

while(p2 < arr.size() - 1){
if(S <= maxSum){
S += arr[++p2];
}
else {
S -= arr[p1++];
}

if(S <= maxSum && p2 - p1 + 1 > maxLen)
maxLen = p2 - p1 + 1;
}

return maxLen;
}``````

This is the test result

``````arr = {1, 4, 7, }, max = 5
result = 2

arr = {3, 1, 2, 3, }, max = 4
result = 2

arr = {3, 1, 1, 2, 5, 1, 2, 1, 2, }, max = 10
result = 5``````

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

``````def longest_phrase(a, n):
max_words = 0
start = 0
end = 1

while end < len(a):
sum_chars = sum(a[start:end])
print sum_chars, start, end
if sum_chars <= n:
end += 1
else:
max_words = max(max_words, end -1 - start)
start += 1
if sum(a[start:end]) <= n:
max_words = max(max_words, end - start)
else:
max_words = max(max_words, end -1 - start)

return max_words

a =  [1,4,7]
print longest_phrase(a, 5)``````

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

A C++ solution

This problem is neat because you naturally want to sort such a problem, but the words need to remain next to each other. The solution below uses the concept of a queue in that it pushes values onto a sum, and pops off the oldest value (found by "i - len"). Also this algorithm doesn't bother reducing the length ever as the length essentially "raises the bar" for the next max length.

Time: O(n)
Space: O(1)

``````int maxLen(int arr[], int max, int count)
{
// Corner cases and edge cases
if (count < 1 || max < 1) return 0;

int sum = 0;
int len = 0;

for (int i = 0; i < count; ++i)
{
sum += arr[i];

if (sum <= max)
++len;
else
sum -= arr[i - len];
}

return len;
}``````

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

what is output?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This solution takes O(n) time.

``````int careercup(int[] array, int max){
if(max <= 0)
return 0;

int size = array.length;
int left = 0;
int sum = 0;

int count = 0;
int maxCount= 0;

for(int i = 0; i < size; i++){
int word = array[i];
if(sum + word <= max){
sum += word;
count++;
}else{
if(count > maxCount)
maxCount = count;

sum += word;
while(left <= i && sum > max){
sum -= array[left];
left++;
count--;
}
}

}

if(count > maxCount)
maxCount = count;

return maxCount;

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sort the array and iterate till we the sum is less than equal to max.
O(nlogn) sorting complexity

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The trick part is to sort the array, ones sorted becames into the problem of find a continius sequence that sums until max,every time we find a value <= max we update the maximum of words.

``````public int GetMaxNumberWords(int[] array, int max)
{
if (array == null || array.Length == 0)
return 0;

Array.Sort(array);

int i = 0;
int j = 0;
int maxWords = int.MinValue;
int sum = array[0];

while (i < array.Length)
{
if (a[i] > max)
break;

if (sum <= max)
{
int numWords = i - j + 1;
maxWords = Math.Max(maxWords, numWords);
}

Console.WriteLine("sum = " + sum + ", i = " + i + ", j = " + j + ", maxMords = " + maxWords);

if (i == j || sum < max)
{
i++;
if (i < array.Length)
sum += array[i];
}
else
{
sum -= array[j];
j++;
}
}

return maxWords == int.MinValue ? 0 : maxWords;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Algorithm: Please suggest whether we can solve in this way dont mind about the pseudocode i m practising to write it :)

1. take two stack S1 and S2.
2. fill S1 with items in the array from rear end.
3. initiate sum=0 count=0 and max=given value
4. while(!S1.empty()){
int val = s1.pop();
if((sum+val)<=max){
count++;
sum=sum+val;
s2.push(val);
}else{
s1.push(s2.pop());
sum=0;
}}
if(s2.pop()<=max){
count++;
}

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

package com.algo.clrs23;

import java.util.Stack;

public class LongestPhrase {

public static int longestPhrase(int[] inputs,int max) {

Stack<Integer> S1 = new Stack<>();
Stack<Integer> S2 = new Stack<>();
int sum = 0;
int count=0;
for (int i = inputs.length-1; i >=0; i--) {
S1.push(inputs[i]);
}
while(!S1.isEmpty()) {

int val = S1.peek();
++count;
sum=sum+val;
S2.push(S1.pop());
}else {
sum=0;
S1.push(S2.pop());
}
}
if(S2.peek()<=max){
++count;;
}
return count;
}
public static void main(String[] args) {

int[] inputs = {3,1,2,3};
int max=5;
int output = LongestPhrase.longestPhrase(inputs, max);
System.out.println(output);

}

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````1. Sort the array string by length
2. iterate over it and get longest and second longest string length
3. print it.
//-----Replace the string with any desired string and also key with any key.

import java.util.Arrays;
import java.util.Comparator;

public class LongestPhraseString
{
//~ Methods ----------------------------------------------------------------

public static void countString( String[] inp, int length )
{
Arrays.sort( inp, new Comparator<String>( )
{
public int compare( String s1, String s2 )
{
return s1.length( ) - s2.length( );
}
} );

int longestStringLen = 0;
String longestString = "";

int secondLongestStringLen = 0;
String secondLongestString = "";

int count = 0;
boolean flag = false;

for ( int i = inp.length - 1; i >= 0; i-- )
{
System.out.println( inp [i] );

if ( inp [i].length( ) <= length )
{
if ( count == 0 )
{
longestStringLen = inp [i].length( );
longestString = inp [i];
}
else if ( inp [i + 1].length( ) > inp [i].length( ) )
{
if ( flag == false )
{
secondLongestStringLen = inp [i].length( );
secondLongestString = inp [i];
flag = true;
}
}

count++;
}
}

System.out.println( "[" + secondLongestStringLen + " , " +
longestStringLen + "]" );
System.out.println( "[" + secondLongestString + " , " + longestString +
"]" );
}

public static void main( String[] args )
{
String inp = "I love chicken";

String[] inpStr = inp.split( " " );

countString( inpStr, 5 );
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Couldn't you just use a min-heap and then pull from the top of the heap until you reach the max?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````int findLongest(vector<int> v, int max)
{
int soFar = 0, best = 0, p1 = 0, p2 = 0, nWords = 0;
int start = 0, end = 0;

while (p2 < v.size()) {
soFar += v[p2];

if (soFar > max) {
while (p1 < p2 && soFar > max) {
soFar -= v[p1];
p1++;
}
while (p2 < v.size() && v[p2] > max) {
p2++;
p1 = p2;
soFar = 0;
}
}

if (p2 - p1 + 1 > best) {
best = p2 - p1  + 1;
start = p1;
end = p2;
}
p2++;
}

cout << "start = " << start << endl;
cout << "end = " << end << endl;
return best;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````/**
Optimized by remembering previous length and previous sum

*/

public class WordLengthFunction {

public static void main(String args[]) {
int input[] = {3, 1, 2, 3};
int max = 4;

System.out.println(findLength(input, max));

}

private static int findLength(int[] input, int max) {
int maxLength = 0;

int psum = 0;
int plength = 0;

for(int i=0; i< input.length; i++) {
int sum = 0;

if(psum != 0) {
sum = sum - input[i -1];
}

int ci = (plength <= 1) ? i : i + plength + 1;

for(int j = ci; j < input.length; j++) {
if(sum + input[j] <= max) {
sum = sum + input[j];
ci = j;
} else {
break;
}
}
int clength = (ci == i) ? 0 : ci - i + 1;
maxLength = Math.max(maxLength, clength);
}
return maxLength;
}
}``````

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.