Google Interview Question Software Engineers
Country: India
Interview Type: Phone Interview
def readRow(inputStr, startPos, num):
row=[]
pos=0
for valNr in range(num):
numStr=''
if len(inputStr)<(pos+startPos) or not (inputStr[pos+startPos]).isdigit():
return None
while (startPos+pos)<len(inputStr) and inputStr[startPos+pos]!='#':
if len(inputStr)<pos+startPos:
return None
numStr+=inputStr[pos+startPos]
pos+=1
row.append(int(numStr))
pos+=1
return (row, pos+startPos)
def maxOfRowInTriangle(inputStr):
rowMaxValues=[]
pos=0
rowCnt=1
while len(inputStr)>=pos:
r = readRow(inputStr, pos, rowCnt)
if r==None:
return "Invalid"
else:
rowMax=max(r[0])
pos = r[1]
rowCnt+=1
rowMaxValues.append(rowMax)
return str(sum(rowMaxValues))
c++ implementation.
#include <iostream>
#include <string>
using namespace std;
string GetSumOfBiggest( char *str_pointer ) {
int length = 4;
int sum = (int)*str_pointer - '0';
if ( sum == -13 || str_pointer[ 0 ] == '\0' ) {
return "Invalid";
}
str_pointer++;
while ( str_pointer[ 0 ] != '\0' ) {
int maxVal = 0;
for ( int i = 0; i < length; i++ ) {
if ( i % 2 == 0 ) {
str_pointer++; continue;
}
int val = (int)*str_pointer - '0';
if ( val == -13 || str_pointer[ 0 ] == '\0' ) {
return "Invalid";
}
maxVal = val > maxVal ? val : maxVal;
str_pointer++;
}
sum += maxVal;
length += 2;
}
return to_string( sum );
}
int main() {
//5#9##4#6#8#0#7#1
//5#9#6#4#6#8#0#7#1
//5#9#6#4#6#8#0#7#1#5
//5#9#6#4#6#8#0#7#1#5#0#7#1#5#6
//5#9#6#4#6#8#0#7#1#5#0#7#1#5#6#0#7#1#5#6#2
char *str_pointer = "5#9#6#4#6#8#0#7#1#5";
cout<< GetSumOfBiggest( str_pointer );
str_pointer = (char *)0xDEADBEEF;
getchar();
return 0;
}
Java solution
public class TriangleMaxSum {
public static void main(String[] args) {
String triangle = "5#9#6#4#6#8#0#7#1#5";
System.out.println(TriangleMaxSum.maxSum(triangle));
}
public static String maxSum(String triangle) {
String[] nums = triangle.split("#");
int start, sum, diff, end = 1;
start = sum = diff = 0;
for (;;) {
sum += maxVal(nums, start, end);
if (end == nums.length) return sum+"";
diff = end - start;
start = end;
end += diff + 1;
if (end > nums.length) return "Invalid";
}
}
public static int maxVal(String[] array, int start, int end) {
int intValue, max = Integer.MIN_VALUE;
for (int i = start; i < end; i++) {
intValue = Integer.parseInt(array[i]);
if (intValue > max) max = intValue;
}
return max;
}
}
I emulated the case when the method receives a very very very long string, such that the loop "for" will be executed 6.000.000 times. After the loop finished I watched the value of the variable "end": is was "-198937535" (negative). So, it means that starting from some moment during execution negative values were being passed to method Arrays.copyOfRange(nums, start, end)".
using namespace::std;
void main()
{
string str = "5#9#6#4#6#8#0#7#1";
int curLenght = 1, curPosInRow = 0, curValue = 0, curMax = 0;
long long sum = 0;
for (char &c : str)
{
if (c == '#')
continue;
curValue = c - '0';
if (curValue > curMax)
curMax = curValue;
if (curLenght == (++curPosInRow))
{
++curLenght;
sum += curMax;
curMax = 0;
curPosInRow = 0;
}
}
if (curPosInRow)
cout << "invalid input";
else
cout << sum;
}
ProcessTokens(@"15#9#6#4#6#8#0#7#1#5".ToCharArray());
ProcessTokens(@"5#9#6#4#6#8#0#7#1".ToCharArray());
ProcessTokens(@"5#9##4#6#8#0#7#1".ToCharArray());
private static void ProcessTokens(char[] tokens)
{
int maxPerRowSoFar=0, rowCount = 1, unprocessedElementsPerRow;
int? num;
int streamIndex = 0, overallSum = 0;
unprocessedElementsPerRow = rowCount;
while ((num = GetToken(tokens, ref streamIndex)) != null)
{
// row break condition
if (unprocessedElementsPerRow == 0)
{
rowCount++;
unprocessedElementsPerRow = rowCount;
overallSum += maxPerRowSoFar;
}
maxPerRowSoFar = (rowCount == unprocessedElementsPerRow) ? num.Value : Math.Max(maxPerRowSoFar, num.Value);
unprocessedElementsPerRow--;
}
if (unprocessedElementsPerRow == 0 && streamIndex == tokens.Length)
{
overallSum += maxPerRowSoFar;
Console.WriteLine(overallSum);
}
else
{
Console.WriteLine("Invalid");
}
}
private static int? GetToken(char[] tokens, ref int i)
{
int? number = null;
while (i < tokens.Length && tokens[i] != '#')
{
if (tokens[i] < '0' && tokens[i] > '9')
throw new ArgumentException("Invalid");
number = (number ?? 0) * 10 + (tokens[i] - '0');
i++;
}
if (i < tokens.Length)
{
i++;
}
return number;
}
split string with delimeter #, lets say result arrays size is x, if 8*x + 1 is not perfect square then output "invalid", if any array element is empty then output "invalid", else
get biggest element from M element and add to SUM, where M is initially 1, after finding max value among M elements increase M by 1 (M++), return SUM.
public class TriangleSum {
public static void main(String... args) {
String str = "1#2#30#5#6#1#4#5#8#3#98#24#12#1#9";
String[] a = str.split("#");
int n = a.length;
int sqrt = (int) Math.sqrt(8 * n + 1);
double sqrt2 = (double) sqrt;
double sqrt3 = Math.sqrt(8 * n + 1);
if (Math.abs(sqrt2 - sqrt3) > 0.000001) {
System.out.println("Invalid");
return;
}
int next = 1;
int count = 0;
int ind = 0;
int max = 0;
int sum = 0;
int val;
while (ind < n) {
if (a[ind].equals("")) {
System.out.println("Invalid");
return;
}
val = Integer.parseInt(a[ind]);
if (val > max) {
max = val;
}
ind++;
count++;
if (count == next) {
next++;
count = 0;
sum += max;
max = 0;
}
}
System.out.println(sum);
}
}
Just a comment. I am very curious how would you expect to load 20GB string in main memory? Given solutions above takes as assumption that memory is enough to satisfy requirements.
#include <iostream>
using namespace std;
int Tokenize(const string &str, int idx, const char ch, int &val)
{
int i = idx;
int v = 0;
while(i < str.size() && str[i] != ch)
{
v = v * 10 + str[i] - '0';
i++;
}
val = v;
return i;
}
int Sum(const string &str)
{
int maxSum = 0;
int i = -1;
int len = 0;
int size = str.size();
while(i < size)
{
++len;
int count = len;
int localMax = 0;
bool isInvalid = false;
while((count != 0) && (++i < size))
{
int val = 0;
int idx = Tokenize(str, i, '#', val);
if(idx == i)
{
isInvalid = true;
break;
}
localMax = max(localMax, val);
count--;
i = idx;
}
if(count == 0)
{
maxSum += localMax;
}
else
{
throw "Invalid";
}
}
return maxSum;
}
int main()
{
try
{
cout << Sum("15#9#6#4#6#8#0#7#1#5");
}
catch(const char *pEx)
{
cout << pEx;
}
getchar();
return 0;
}
My solution in C# without using string.split() and int parse() methods
public int? GetMaxSum(string s)
{
int maxValue = int.MinValue;
int sum = 0;
int count = 0;
int row = 1;
int? value = null;
foreach (var c in s)
{
if (c == '#')
{
if (!value.HasValue)
return null;
if (row == count)
{
count = 0;
row++;
}
if (value > maxValue)
maxValue = value.Value;
value = null;
count++;
if (row == count)
{
sum += maxValue;
maxValue = int.MinValue;
}
}
else if (c >= '0' && c <= '9')
{
if (!value.HasValue)
value = 0;
value = value * 10 + (int)(c - '0');
}
else
return null;
}
if (value > maxValue)
maxValue = value.Value;
count++;
if (row == count)
sum += maxValue;
return (count == row) ? (int?)sum : null;
}
foreach loop copies the current array to a new one for the operation.
According to the task the string may have length up to 20 GB. Let's assume, that your total space is 25 GB. Your solution will crash.
Moreover, generally foreach loop does not ensure the order of of collection' elements processing.
public class Triangles {
public static void main( String args[] ) {
Triangles t = new Triangles();
//String tri = "5#9#6#4#6#8#0#7#1#5";
System.out.println( t.getMaxSum( args[0] ));
} // end main
public int getMaxSum( String tri ) {
String[] nums = tri.split( "#" );
int rowSize = 1;
int rowStop = 1;
int maxInRow = 0;
int maxSum = 0;
int i;
try {
for( i = 0; i < nums.length; i++ ) {
if( i == rowStop ) {
maxSum += maxInRow;
maxInRow = 0;
rowSize++;
rowStop += rowSize;
} // end if
if( Integer.parseInt( nums[i] ) > maxInRow ) {
maxInRow = Integer.parseInt( nums[i] );
} // end if
} // end for
if( i == rowStop ) {
maxSum += maxInRow;
return maxSum;
} else {
return -1;
} // end if/else
} catch( NumberFormatException nfe ) {
return -1;
} // end try/catch
} // end getMaxSum
} // end Triangles
All answers that posted before are wrong. Problem is in great size of problem, not in just finding max value.
You should implement stream algorithm which can handle any size problem.
Here is my "stream" solution in C#:
private static bool IsNumber(char ch)
{
return '0' <= ch && ch <= '9';
}
private static string GetMax(IEnumerable<char> ds, char delim)
{
if (ds == null) throw new ArgumentNullException();
using (var en = ds.GetEnumerator())
{
var sb = new StringBuilder(int.MaxValue.ToString().Length);
var curDelimCnt = 0;
var lastDelimCnt = 0;
var lastLineLength = int.MinValue;
var curLineLength = 0;
long sum = 0;
var max = long.MinValue;
bool hasNext;
long value;
var ch = char.MinValue;
do
{
hasNext = en.MoveNext();
if (!hasNext) continue;
ch = en.Current;
curLineLength++;
if (IsNumber(ch))
sb.Append(ch);
else if (ch == delim)
{
var s = sb.ToString();
value = s.Length == 0 ? 0 : long.Parse(s);
max = value > max ? value : max;
sb.Clear();
curDelimCnt++;
if (curDelimCnt == lastDelimCnt + 1)
{
if (curLineLength <= lastLineLength)
return "Invalid";
sum += max;
max = long.MinValue;
lastDelimCnt = curDelimCnt;
curDelimCnt = 0;
lastLineLength = curLineLength;
curLineLength = 0;
}
}
} while (hasNext);
// check that last line length more that previous
if (curLineLength <= lastLineLength)
return "Invalid";
//check last char
if (ch != char.MinValue && !IsNumber(ch)) return "Invalid";
value = long.Parse(sb.ToString());
sum += value > max ? value : max;
return sum.ToString();
}
}
Testing on some samples:
private static IEnumerable<char> GetDataSource(string s)
{
if (string.IsNullOrEmpty(s)) yield break;
using (var reader = new StringReader(s))
{
int ch;
while ((ch = reader.Read()) != -1)
yield return (char)ch;
}
}
[TestCase]
public void MainTest()
{
var dictionary = new Dictionary<string, string>
{
{"1#1#2", "3"},
{"1#1#2#", "Invalid"},
{"1#1#2#1#2#3", "6"},
{"1#1#2#1#2#3#", "Invalid"},
{"1#1#2#1#2#3#1#2#3", "Invalid"},
{"1#1#2#1#2#3#1#2#3#1", "9"},
{"1", "1"},
{"11", "11"},
{";", "Invalid"},
{"#", "Invalid"},
{"1#2", "Invalid"},
{"1##", "Invalid"},
{"1##2", "Invalid"},
{"1#2#3#7#4#8", "12"},
{"7#3#7#1#7#5#6#1#9#7", "30"},
{"7#3#7#1#7#5#6#1#9#7\0", "30"}
};
foreach (var pair in dictionary)
Assert.AreEqual(pair.Value, GetMax(GetDataSource(pair.Key), '#'));
}
Code to generate Biggest files with triangle
private static double SolveQuadratic(double a, double b, double c)
{
var d = b*b - 4*a*c;
if (d > 0)
{
var x1 = (-b + Math.Sqrt(d))/(2*a);
var x2 = (-b - Math.Sqrt(d))/(2*a);
return x1 > x2 ? x1 : x2;
}
var x = (-b + Math.Sqrt(d))/(2*a);
return Math.Abs(x);
}
// compute interation count
// size_of_file = encoding_len * cnt_of_chars
// cnt_of_chars = (len(digit) + len(delim)) * (n*(n+1)/2) = (len(digit) + len(delim)) * ( (n^2 + n)/2 )
// len(digit) = length of digit returned by Random Generator
// So encoding_len * ( (len(digit) + len(delim)) * (n^2 + n)/2 ) = size_of_file
// n^2 + n = 2*size_of_file / (encoding_len *(len(digit) + len(delim)))
// For instance:
// generate 1 Mb file in ASCII encoding consinst of 3 digits number with 1 char delimeter
// size of file = len(ascii) * (len(digit)+len(delim)) * ( (n^2+n)/2 )
// 1e6 = 1 * (3+1)*(n^2+n)/2 = 2(n^2+n)
// n^2 + n - 5*1e5 = 0
// n = 706.61
// 1GB
// n^2 + n - 5*1e8 = 0
private static int GetN(double size, int digitLen, int delimLen, Encoding enc)
{
var encodingLen = 1; // FOR ASCII
if (Equals(enc, Encoding.ASCII))
encodingLen = 1;
else return 0;
//n ^ 2 + n
var rp = 2*size/(encodingLen*(digitLen + delimLen));
var solveQuadratic = SolveQuadratic(1, 1, -rp);
return (int) Math.Floor(solveQuadratic);
}
/// <summary>
/// Method generate triangle file with random 3-digits numbers
/// </summary>
[TestCase((int)1e2, TestName = "Test")]
//[TestCase((int)1e6, TestName = "MB1")]
//[TestCase((int)1e9, TestName = "GB1")]
//[TestCase((int)2e9, TestName = "GB2")]
//[TestCase((int)4e9, TestName = "GB4")]
//[TestCase((int)200e6, TestName = "MB200")]
public void GenerateData(int sizeInBytes)
{
const string path = DataFilePath;
const char delim = '#';
var rnd = new Random((int) DateTime.Now.Ticks);
long n = GetN(sizeInBytes, 3, 1, Encoding.ASCII);
var chunkSize = (int)Math.Min(100, n);
var j = 0;
var prevLen = 0;
var prevCnt = int.MinValue;
var curCnt = 0;
var sb = new StringBuilder();
using (
var writer =
new StreamWriter(new FileStream(path, FileMode.Create), Encoding.ASCII, 1024*1024)
)
{
writer.AutoFlush = true;
while (j < n)
{
var curLen = 0;
while (curLen < prevLen || curCnt < prevCnt)
{
curCnt++;
var value = rnd.Next(100, 1000).ToString(); // 3 - digit chars
sb.Append(value);
curLen += value.Length + 1;
if (j + 1 != n || curLen < prevLen) sb.Append(delim);
// ReSharper disable once InvertIf
if ((curLen + 1) % chunkSize == 0)
{
writer.Write(sb.ToString());
sb.Clear();
}
}
prevLen = curLen + 1;
prevCnt = curCnt;
j++;
writer.Write(sb.ToString());
// if (j < n) writer.Write(Environment.NewLine);
sb.Clear();
}
}
}
Code to test this solution
private static IEnumerable<char> GetDataSourceFromFile(string path)
{
if (string.IsNullOrEmpty(path)) yield break;
using (var reader = new StreamReader(path, Encoding.ASCII, false, 1024 * 1024))
{
int ch;
while ((ch = reader.Read()) != -1)
yield return (char)ch;
}
}
[TestCase]
public void Test2FromFile()
{
var dataSource = GetDataSourceFromFile(DataFilePath);
var m = GetMax(dataSource, '#');
Console.WriteLine(m);
}
javascript
function getMaxNumber(input,lineNumber){
var split = input.split("#");
var totalLineNum = lineNumber * (lineNumber + 1) / 2;
if(totalLineNum > split.length){
return "not valid";
}
var start = totalLineNum - lineNumber;
var end = totalLineNum - 1;
var temp = 0;
for(var a = start;a<=end;a++){
var num = parseInt(split[a]);
if(isNaN(num)){
return "not valid";
}
if( num > temp){
temp = num;
}
}
if(totalLineNum == split.length){
return temp;
}
else{
var next = getMaxNumber(input,++lineNumber);
if(next == "not valid"){
return "not valid";
}
return temp + next;
}
}
console.log("result = " + getMaxNumber("3#7#6#9#8#6#6#9#8#0##",1));
#include <ctime>
#include <iostream>
#include <list>
#include <string>
void sumNumber(std::string randomNumberString) {
int sum;
bool status;
size_t preIndexOfSharpSign, postIndexOfSharpSign;
std::list<int> listOfInteger;
sum = 0;
status = true;
preIndexOfSharpSign = 0;
postIndexOfSharpSign = 0;
for (int i = 1; postIndexOfSharpSign != std::string::npos; i++) {
for (int j = 0; j < i; j++) {
postIndexOfSharpSign = randomNumberString.find('#', preIndexOfSharpSign);
if (postIndexOfSharpSign == std::string::npos) {
listOfInteger.push_back(std::stoi(randomNumberString.substr(preIndexOfSharpSign, randomNumberString.length() - preIndexOfSharpSign)));
break;
} else {
listOfInteger.push_back(std::stoi(randomNumberString.substr(preIndexOfSharpSign, postIndexOfSharpSign - preIndexOfSharpSign)));
}
preIndexOfSharpSign = postIndexOfSharpSign + 1;
}
for (std::list<int>::iterator listOfIntegerOfIterator = listOfInteger.begin(); listOfIntegerOfIterator != listOfInteger.end(); listOfIntegerOfIterator++) {
std::cout << *listOfIntegerOfIterator << " ";
}
std::cout << std::endl;
if (listOfInteger.size() == i) {
listOfInteger.sort(std::greater<int>());
sum += listOfInteger.front();
listOfInteger.clear();
} else {
listOfInteger.clear();
status = false;
break;
}
}
if (status) {
std::cout << "Sum: " << sum << std::endl;
} else {
std::cout << "Invalid" << std::endl;
}
}
void makeRandomNumberString(std::string & randomNumberString) {
int randomNumber;
std::srand((unsigned int)std::time(nullptr));
randomNumber = std::rand() % 500 + 1;
for (int i = 0; i < randomNumber; i++) {
randomNumberString.append(std::to_string(std::rand() % 10));
if (i < randomNumber - 1) {
randomNumberString.append(1, '#');
}
}
std::cout << randomNumberString << std::endl;
}
int main(int argc, const char * argv[]) {
std::string randomNumberString;
makeRandomNumberString(randomNumberString);
sumNumber(randomNumberString);
return 0;
}
-(int)maxOfTriangleString:(NSString*)str {
int total = 0, row = 1;
for (int i = 0; i< str.length;) {
int max = INT_MIN;
for (int j = 0; j<row; j++) {
if (i+j*2 > str.length) {
NSLog(@"Invalid input %@", str);
return -1;
}
int value = [str characterAtIndex:i+j*2]-48;
if (value > max) {
max = value;
}
}
i = i + row*2;
row++;
total+=max;
}
return total;
}
package com.problems;
import java.util.Comparator;
import java.util.PriorityQueue;
public class numTriangle {
public static void main(String[] args) {
PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
int startIndex = 0;
int endIndex = 0;
int moveIndex = 0;
int index = 1;
String input = "1#2#3#4#5#6#7#8#9#10";
String[] data = input.split("#");
// Clear the string as it wont be used anymore.
input = "";
int currVal = 0;
int triangleSum = 0;
for (startIndex = 0; startIndex <= endIndex; startIndex++) {
if (startIndex >= data.length)
break;
// If the input is not in triangle format, throw exception
if (endIndex > data.length) {
throw new RuntimeException("Invalid triangle");
}
currVal = Integer.parseInt(data[startIndex]);
if (startIndex == endIndex) {
moveIndex += (index += 1);
maxheap.add(currVal);
triangleSum += maxheap.remove();
endIndex = moveIndex;
maxheap.clear();
} else
maxheap.add(currVal);
}
System.out.println(triangleSum);
}
}
public static String sumTriangle(String s) {
String[] stream = s.split("#");
int sum = 0;
int rowLength = 1;
int index = 0;
try {
int largest = Integer.MIN_VALUE;
int endOfRowIndex = rowLength++;
while (index < stream.length) {
largest = Math.max(largest, Integer.valueOf(stream[index++]));
if (index == endOfRowIndex || index == stream.length) {
endOfRowIndex += rowLength++;
sum += largest;
largest = Integer.MIN_VALUE;
}
}
return "" + sum;
} catch (NumberFormatException nfe) {
return "Invalid";
}
}
Here is the solution for objective C
- Jay December 09, 2015-(int)maxOfTriangleString:(NSString*)str { int total = 0, row = 1; for (int i = 0; i< str.length;) { int max = INT_MIN; for (int j = 0; j<row; j++) { if (i+j*2 > str.length) { NSLog(@"Invalid input %@", str); return -1; } int value = [str characterAtIndex:i+j*2]-48; if (value > max) { max = value; } } i = i + row*2; row++; total+=max; } return total; }