Google Interview Question
Applications DevelopersCountry: United States
I think the question is as follows:
Example:
Input Number: 1993487443
Output Number: 199348743
Here we have 2 consecutive duplicates 99 and 44. Deleting one of the 4 would yield a greater result than deleting the 9. 199348743 vs 193487443
Another Example:
Input number:1100
Output Number: 110
Deleting the 0 would make the number larger than deleting the 1 would. 110 vs 100.
Here is code for max sum after deleting 2 consecutive integer
public class MaximumSumByRemoving1OfConsecutiveDigit {
public static int maxSum(int[] arr,int index){
if (index>=arr.length) {
return 0;
} else if (index==arr.length-1) {
return arr[index];
}
return Math.max(arr[index] + maxSum(arr, index + 2), arr[index + 1] + maxSum(arr, index + 3));
}
public static void main(String a[]){
System.out.println(maxSum(new int[]{1,2,3,4,5,6,7},0));
// output : 16
}
}
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
struct s_digit
{
int m_digit;
int m_right_digit;
s_digit():m_digit(-1), m_right_digit(-1){}
bool hasBiggerRight()
{
return m_right_digit > m_digit;
}
};
void loadAllDigits(int inVal, stack<struct s_digit> &outResult, int &indexOfLeftBigRight, int &indexOfRightDup)
{
int val1 = -1, val2 = -1;
indexOfLeftBigRight = -1;
indexOfRightDup = -1;
int loop = 0;
while(inVal > 0)
{
s_digit digit;
val1 = inVal % 10;
inVal /= 10;
digit.m_digit = val1;
digit.m_right_digit = val2;
if(val2 == val1)
{
s_digit tmp = outResult.top();
if(indexOfRightDup == -1)
{
indexOfRightDup = loop;
}
if(tmp.hasBiggerRight())
{
indexOfLeftBigRight = loop;
}
}
val2 = val1;
loop++;
outResult.push(digit);
}
}
int trimDigit(int inVal, int inIndex)
{
int tmp = 0, ret = 0, pw = 0;
if(inIndex < 0)
{
return inVal;
}
while(inVal > 0)
{
if(inIndex != 0)
{
tmp = inVal % 10 * pow(10, pw);
ret += tmp;
pw++;
}
inVal = inVal / 10;
inIndex--;
}
return ret;
}
int main(int argc, char** argv)
{
if(argc != 2)
{
printf("Usage: %s test_integer\n", argv[0]);
exit(1);
}
int val = atoi(argv[1]);
stack<struct s_digit> result;
int indexOfBig = -1, indexOfRight = -1;
loadAllDigits(val, result, indexOfBig, indexOfRight);
int index = (indexOfBig==-1)?indexOfRight:indexOfBig;
printf("%d delete index(%d) => %d\n", val, index, trimDigit(val, index));
return 0;
}
void checkLargest(string number, int k, long long& largest)
{
ostringstream ss;
for(int i = 0; i < number.length(); i++)
{
if(i == k || i == k+1)
continue;
ss << number[i];
}
string str = ss.str();
long long num = 0;
for(int i = 0; i < str.length(); i++)
{
num *= 10;
num += str[i] - '0';
}
if(num > largest)
largest = num;
}
long long deleteConsecutiveDigits(string number)
{
long long largest = -1;
for(int i = 0; i < number.length()-1; i++)
{
checkLargest(number, i, largest);
}
return largest;
}
void checkLargest(string number, int k, long long& largest)
{
ostringstream ss;
for(int i = 0; i < number.length(); i++)
{
if(i == k || i == k+1)
continue;
ss << number[i];
}
string str = ss.str();
long long num = 0;
for(int i = 0; i < str.length(); i++)
{
num *= 10;
num += str[i] - '0';
}
if(num > largest)
largest = num;
}
long long deleteConsecutiveDigits(string number)
{
long long largest = -1;
for(int i = 0; i < number.length()-1; i++)
{
checkLargest(number, i, largest);
}
return largest;
}
#include <iostream>
#include <vector>
#include <string>
int largestNum(int input) {
std::string str = std::to_string(input);
if (str.size()<2)
return;
std::vector<int> pos;
char prevChar = *(str.begin());
int repeatedPos = 1;
std::string::iterator it = str.begin() + 1;
for (;it!=str.end();++it) {
if (prevChar == (*it)) {
pos.push_back(repeatedPos);
}
prevChar = (*it);
repeatedPos++;
}
int maxNum = 0;
for (std::vector<int>::iterator it = pos.begin();it!=pos.end();++it) {
std::string tmp = str;
tmp.erase(*it,1);
std::string::size_type sz; // alias of size_t
maxNum = std::max(maxNum, stoi(tmp, &sz));
}
return maxNum;
}
int main () {
int num = largestNum(8888888);
std::cout << "Largest number is " << num;
return 0;
}
/*
Write program that takes integer, deletes one of two consecutive digits and return greatest of all results.
Assumption:
1) consecutive means, the same digit is repeated
2) only delete one digit of such a pair
Solution:
- straight forward
- runtime O(log(n)*log(n)) / where n is the value of the integer ...
Example:
994141 --> 99414
141465 --> 14165
*/
#include <iostream>
using namespace std;
int RemoveConsecutiveDigit(int v)
{
int ov = v / 10;
while (ov > 0)
{
int iv = v;
int ivc = 1;
while (iv != ov)
{
if (ov % 10 == iv % 10)
{
return (v / 10 / ivc * ivc) + (v % ivc); // looks wierd, just removes the digit
}
iv /= 10;
ivc *= 10;
}
ov /= 10;
}
return v;
}
int main()
{
cout << RemoveConsecutiveDigit(994141) << endl;
cout << RemoveConsecutiveDigit(141465) << endl;
getchar();
}
unsigned int greatest(unsigned int n) {
unsigned int result = 0, digit1 = n % 10, digit2, sum = 0, multiplier = 1, newresult;
n = n/10;
while (n > 0) {
digit2 = n % 10;
if (digit1 == digit2) {
newresult = n * multiplier + sum;
if (newresult > result)
result = newresult;
}
sum += digit1 * multiplier;
digit1 = digit2;
multiplier *= 10;
n /= 10;
}
if (result == 0)
printf("No consecutive digits");
return result;
}
public class Solution {
public static void main(String [] args) {
System.out.println(deleteConsecutiveDigit(1100));
}
public static int deleteConsecutiveDigit(int value) {
String str = String.valueOf(value);
for (int i = str.length()-2; i >= 0; i--) {
String first = str.substring(i, i+1);
String second = str.substring(i+1, i+2);
if (first.equals(second)) {
str = str.substring(0, i) + str.substring(i+1, str.length());
break;
}
}
return Integer.valueOf(str);
}
}
public class RemoveConsecutativeDigit {
public static void main(String[] args) {
//long num = Integer.parseInt(args[0]);
System.out.println("removed consucative digs " + consecutiveDig(416));
}
static long consecutiveDig(long num) {
if(num < 100)
return getMaxDig(num);
return getMaxDig(num %100) + 10 * consecutiveDig(num/100);
}
static long getMaxDig(long n) {
if (n<10)
return n;
return n/10 > n%10 ? n/10:n%10;
}
}
using System;
public class Program
{
public static void Main()
{
int number = 12234456, div = number, mod = number%10, prevmod = -1, sum = 0, multiply = 1;
while (div > 0) {
if (mod == prevmod) {
div = div / 10;
break;
}
sum += mod * multiply;
multiply = multiply * 10;
prevmod = mod;
div = div/10;
mod = div%10;
}
Console.WriteLine(div*multiply + sum);
}
}
Does this mean it waits for an integer of two digits only and return the greatest one, like call(95) -> return 9?
- Ahmed Refaey June 01, 2016