Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
In the example you give, aren't the last 6 values the longest contiguous subarray?
How does this algorithm handle a case like this?
################################*#
The answer here should be 2 (the last two characters).
#,#,#,#,#....,#,*,#
0,-1,-2,-3,....,-N,-N+1,-N,
So you have -N on two positions. You calculate the distance - 1, you get it.
You could store both first and last occurrence in maps ( and keep updating last if more than one occurrence ) for each number at step 1.
then at step 2, just iterate the map, and find max of (last - first). Also no need array for sums, since it's only 1 pass.
I was just keeping diff between # and * from the begining, same thing basically:
public static int sub(byte[] bytes) {
int[] diffs = new int[bytes.length + 1];
diffs[0] = 0;
for (int i = 0; i < bytes.length; i ++) diffs[i+1] = diffs[i] + ((bytes[i]=='#')?-1:1);
HashMap<Integer,Integer> difToStart = new HashMap<Integer,Integer>();
int max = 0;
for (int i = 0; i < diffs.length; i ++) {
Integer start = difToStart.get(diffs[i]);
if (start == null) difToStart.put(diffs[i], i);
else max = Math.max(max, i - start);
}
return max;
}
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
int main()
{
const char* str = "****##**#**##";
int s = strlen(str);
//sum used to know where the same sum last time seen at what index
int* sum = new int[2*s+1];
for(int i = 0; i < 2*s+1; i++)
{
sum[i] = INT_MIN;//mean it seen never earlier
}
int max = 0;
int sMax = -1;
int eMax = -1;
//
int sumUpto = 0;
sum[0] = -1;
sumUpto = (str[0] == '*' ? 1 : -1);
sum[sumUpto] = 0;
for(int i = 1; i < s; i++)
{
sumUpto = sumUpto + (str[i] == '*' ? 1 : -1);
if(sum[sumUpto] == INT_MIN)
{
sum[sumUpto] = i;
}
else
{
int indexLastSeen = sum[sumUpto];//the same sumUpto first time seen what index
if((i-indexLastSeen) > max)
{
max = (i-indexLastSeen);
sMax = indexLastSeen +1;
eMax = i;
}
}//else
}//forloop
cout<<max<<" "<<"Start Index = "<<sMax<<" "<<"End Index = "<<eMax;
return 0;
}
Try with sample input : **#*##
O/P : 1 and 4.
1. I dont get what is the max length its matching
2. I dont see correct starting position too
Can you provide few example to support your code?
Hi
Max represent longest substring that have equal * & #
sMax is starting point of that substring which have equal * & #
eMax is starting point of that substring which have equal * & #
And for your information i execute your sample "**#*##"
Output was - 6 Start Index = 0 End Index = 5
So longest substring which have equal * # is length of 6
start point is 0 and end point is 5
In the second step you need to find the maximum distance. Consider using hash_map for storing the first occurence of every number. Calculate the size.
"joe kidd": can you explain what this means?
Sure. Imagine you have a hash table, that is empty at the moment. You also have the maximum distance max_dist = -1. Scan the result array ([1 0 -1 0 -1 -2 -3 -2 -1]) from left to one.
1) if 0, then max_dist = i
2) else
---- if(hash_map.contains(arr[i]) then max_dist = max(max_dist, i - hash_map.get(arr[i] - 1)
--- else hash_map.set(arr[i], i)
So the hash map is used to store, minimum index, that a value arr[i] was met and is then used to calculate maximum distance. 0 is considered in a special way, as it stands for: equal amount from the beginining.
Lets say you have an array A = **###***#**##*###*#* and you have another array B.
Step 1: What you can do is go through array A and where a sequence of either * or # starts at index i, place how many are in that sequence at the index i in array B. In this case you'd have something like 20300300120201300111, where each non-zero value is the number of * or # in a sequence starting at that index i in array A.
Step 2: Now go through B using two pointers: x and y. You are only comparing non-zero values. make x point to the first non-zero value and have y be the next one over. if they are equal, save the index and value of x. Now make x point to y and iterate y again to the next one. if that value isn't greater than the one you saved, don't overwrite your saved index and value. keep going to the end. you'll have the index of the start of the sequence and the length / 2 (just double it)
It takes O(N) for Step 1, and O(N) for Step 2, which is O(2N) = O(N) runtime overall. You have O(N) space as well for the array you make.
SubsetCount(string input )
{
string result = "";
char current = input[0];
Dictionary<char,int> count = new Dictionary<char,int>();
int maxCount = 0;
int subsetIndex= 0;
if (current == '*')
{
count.Add('*', 1);
count.Add('#', 0);
}
else
{
count.Add('#', 1);
count.Add('*', 0);
}
subsetIndex =0;
for (int i = 1; i < input.Length;i++ )
{
if (input[i] == current)//counting this series
{
count[current]++;
}
else
{
current = input[i];
if (count[current] > 0)//we have a subset of both
{
if ((count['#'] == count['*']) && (count['*'] > maxCount))//balanced and largest subset
{
maxCount = count['*'];
result = "Start Index = " + (subsetIndex - maxCount) + " End index = " + (subsetIndex + maxCount-1);
}
//start a new series
if (current == '*')
{
count['*'] = 1;
subsetIndex = i;
}
else
{
count['#'] = 1;
subsetIndex = i;
}
}
else//adding series to current subset
{
count[current]++;
}
}
}
if (count[current] > 0)//we have a subset of both
{
if ((count['#'] == count['*']) && (count['*'] > maxCount))//balanced and largest subset
{
maxCount = count['*'];
textBoxO.Text = "Start Index = " + (subsetIndex - maxCount) + " End index = " + (subsetIndex + maxCount-1);
}
}
}
I have below solution, it can be optimised:
int subArray(char* array,int size){
vector<int> indexes;
vector<int> lengths;
int n_sstring = -1;
bool counting = false;
for(int i = 0;i<size;i++){
if(array[i] == '*'){
if(array[i+1] == '#'){
if(counting == false){
n_sstring++;
counting = true;
indexes.push_back(i);
lengths.push_back(2);
}else{
lengths.at(n_sstring) += 2;
}
i++;
}else{
counting = false;
}
}else{
if(array[i+1] == '*'){
if(counting == false){
n_sstring++;
counting = true;
indexes.push_back(i);
lengths.push_back(2);
}else{
lengths.at(n_sstring) += 2;
}
i++;
}else{
counting = false;
}
}
}
int index = 0;
int max = 0;
if(!lengths.size()){
return -1;
}else{
index = indexes.at(0);
max = lengths.at(0);
}
for(int i = 1;i<lengths.size();i++){
if(max < lengths.at(i)){
max = lengths.at(i);
index = i;
}
}
return indexes.at(index);
}
/*
* for a given array of either hashes or stars, find the (first) longest inner array
* containing an equal number of hashes and stars
*/
static char[] getMostSameChars(char[] array) {
//sanity check
if (array.length == 0) return array;
//assign +1 to stars, and -1 to hashes.
//Starting from the beginning, begin totalizing hashes +1 and stars -1
//whenever a 0 occurs, we have an equal number of stars and hashes.
//Do this starting at 0, then 1... until the length of the longest inner array
//is greater than the rest of the source array
int maxZeroLen = -1; //This is the longest valid inner array we have found so far
int maxZeroIndex = -1;//the beginning index of the longest valid array
for (int i = 0; i < array.length && (array.length - i) > maxZeroLen; i++) {
//find the longest valid inner array starting at index i
int maxZero = findMaxZero(array, i);
if (maxZero > maxZeroLen)
{
//found a new hero, store the details
maxZeroLen = maxZero;
maxZeroIndex = i;
}
}
//nothing found...
if (maxZeroLen == -1) return new char[0];
//whole array is valid
if (maxZeroLen == array.length) return array;
//return new array
char[] ret = new char[maxZeroLen];
System.arraycopy(array, maxZeroIndex, ret, 0, maxZeroLen);
return ret;
}
/*
Given an array of hashes and stars, find the longest inner array
where the number of stars = the number of hashes, starting from
the given start index
*/
static int findMaxZero(char[] array, int startIndex)
{
int len = 0; //this is the len thus far.
int maxZero = -1; //the maximum length found thus far
int total = 0; //the running total (*'s add 1, #'s subtract 1)
//TODO ultra fancy optimization so we don't iterate when iterations left < Math.abs(total)
for (int i = startIndex; i < array.length; i++) {
char c = array[i];
len++;
//add for stars, subtract for hashes
if (c == '*') total++;
else total--;
//if total is 0, we've found a valid inner array
if (total == 0) maxZero = len;
}
return maxZero;
}
Hi Peter i updated my code ya thanks ofr pointing the bug in my code i fixed it and now i work fine it think
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
int main()
{
//const char* str = "################################*#";
const char* str = "###########**#****######";
int s = strlen(str);
//sum used to know where the same sum last time seen at what index
int* sum = new int[2*s+1];
for(int i = 0; i < 2*s+1; i++)
{
sum[i] = INT_MIN;//mean it seen never earlier
}
int max = 0;
int sMax = -1;
int eMax = -1;
int offset = s;
//
int sumUpto = 0;
sum[offset] = -1;
sumUpto = (str[0] == '*' ? 1 : -1);
sum[sumUpto+offset] = 0;
for(int i = 1; i < s; i++)
{
sumUpto = sumUpto + (str[i] == '*' ? 1 : -1);
cout<<sumUpto<<" ";
if(sum[sumUpto + offset] == INT_MIN)
{
sum[sumUpto+offset] = i;
}
else
{
int indexLastSeen = sum[sumUpto+offset];//the same sumUpto first time seen what index
if((i-indexLastSeen) > max)
{
max = (i-indexLastSeen);
sMax = indexLastSeen +1;
eMax = i;
}
}//else
}//forloop
cout<<max<<" "<<"Start Index = "<<sMax<<" "<<"End Index = "<<eMax<<endl;
for(int p = sMax; p <= eMax; p++)cout<<str[p];
return 0;
}
public class LongestString {
public String searchLongest(String str) {
// The first char in the inoput
char startChar = str.charAt(0);
//Count of the first char
int total1 = 0;
// Count of the second char
int total2 = 0;
// Array that tell me the groups of symbols and how many symbols in each group
ArrayList<Integer> dataNumber = new ArrayList<Integer>();
// Array that tell me the order of the symbols
ArrayList<String> dataChars = new ArrayList<String>();
char curChar = str.charAt(0);
int index = 0;
dataNumber.add(new Integer(0));
dataChars.add(str.charAt(0) + "");
// analize data an complete the arrays and the counts of symbols
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == startChar) {
total1++;
} else {
total2++;
}
if (curChar == str.charAt(i)) {
dataNumber.set(index, dataNumber.get(index) + 1);
} else {
index++;
dataNumber.add(new Integer(1));
curChar = str.charAt(i);
dataChars.add(curChar + "");
}
}
// The last index of the dataNumbers and dataChars
int lastIndexNumbers = dataNumber.size() - 1;
// We iterate untils total1 == total2 are the same or the start position is the same as tha last
for (int start = 0, last = str.length() - 1; start < last;) {
// When the counts of symbols are equals
if (total1 == total2) {
return str.substring(start, last+1);
}
// Number of the current symbol at the left in the str(start, last) substring
int numberLeft = dataNumber.get(0);
// Number of the current symbol at the rigth in the str(start, last) substring
int numberRight = dataNumber.get(lastIndexNumbers);
// When in my current str (substring) my start position and the last position are the same symbol
if (str.charAt(start) == str.charAt(last)) {
// I prefer start to remove from the side where I have the smallest group
if (numberLeft < numberRight) {
numberLeft--;
start++;
} else {
numberRight--;
last--;
}
// I know that the str(start) position is the current symbol, if it fits with the original startChar, I discount from total1
if(startChar == str.charAt(start)){
total1--;
}else{
total2--;
}
} else {
// The case wuen the current substring has different symbols on the sides
if(total1 > total2 && str.charAt(0) == str.charAt(start)){
numberLeft--;
start++;
total1--;
}else if(total1 > total2 && str.charAt(0) == str.charAt(last)){
numberRight--;
last--;
total1--;
}else if(total2 > total1 && str.charAt(0) != str.charAt(start)){
numberLeft--;
start++;
total2--;
}else if(total2 > total1 && str.charAt(0) != str.charAt(last)){
numberRight--;
last--;
total2--;
}
}
// Update the dataChars and dataNumbers
if(numberLeft == 0){
dataChars.remove(0);
dataNumber.remove(0);
}
if(numberRight == 0){
dataChars.remove(lastIndexNumbers);
dataNumber.remove(lastIndexNumbers);
lastIndexNumbers--;
}
}
return null;
}
public static void main(String[] args) {
LongestString lg = new LongestString();
String result = lg.searchLongest("###****#**#");
System.out.println("result" + result);
}
}
public class LongestString {
public String searchLongest(String str) {
// The first char in the inoput
char startChar = str.charAt(0);
//Count of the first char
int total1 = 0;
// Count of the second char
int total2 = 0;
// Array that tell me the groups of symbols and how many symbols in each group
ArrayList<Integer> dataNumber = new ArrayList<Integer>();
// Array that tell me the order of the symbols
ArrayList<String> dataChars = new ArrayList<String>();
char curChar = str.charAt(0);
int index = 0;
dataNumber.add(new Integer(0));
dataChars.add(str.charAt(0) + "");
// analize data an complete the arrays and the counts of symbols
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == startChar) {
total1++;
} else {
total2++;
}
if (curChar == str.charAt(i)) {
dataNumber.set(index, dataNumber.get(index) + 1);
} else {
index++;
dataNumber.add(new Integer(1));
curChar = str.charAt(i);
dataChars.add(curChar + "");
}
}
// The last index of the dataNumbers and dataChars
int lastIndexNumbers = dataNumber.size() - 1;
// We iterate untils total1 == total2 are the same or the start position is the same as tha last
for (int start = 0, last = str.length() - 1; start < last;) {
// When the counts of symbols are equals
if (total1 == total2) {
return str.substring(start, last+1);
}
// Number of the current symbol at the left in the str(start, last) substring
int numberLeft = dataNumber.get(0);
// Number of the current symbol at the rigth in the str(start, last) substring
int numberRight = dataNumber.get(lastIndexNumbers);
// When in my current str (substring) my start position and the last position are the same symbol
if (str.charAt(start) == str.charAt(last)) {
// I prefer start to remove from the side where I have the smallest group
if (numberLeft < numberRight) {
numberLeft--;
start++;
} else {
numberRight--;
last--;
}
// I know that the str(start) position is the current symbol, if it fits with the original startChar, I discount from total1
if(startChar == str.charAt(start)){
total1--;
}else{
total2--;
}
} else {
// The case wuen the current substring has different symbols on the sides
if(total1 > total2 && str.charAt(0) == str.charAt(start)){
numberLeft--;
start++;
total1--;
}else if(total1 > total2 && str.charAt(0) == str.charAt(last)){
numberRight--;
last--;
total1--;
}else if(total2 > total1 && str.charAt(0) != str.charAt(start)){
numberLeft--;
start++;
total2--;
}else if(total2 > total1 && str.charAt(0) != str.charAt(last)){
numberRight--;
last--;
total2--;
}
}
// Update the dataChars and dataNumbers
if(numberLeft == 0){
dataChars.remove(0);
dataNumber.remove(0);
}
if(numberRight == 0){
dataChars.remove(lastIndexNumbers);
dataNumber.remove(lastIndexNumbers);
lastIndexNumbers--;
}
}
return null;
}
public static void main(String[] args) {
LongestString lg = new LongestString();
String result = lg.searchLongest("###****#**#");
System.out.println("result" + result);
}
}
This code has O(n) complexity in the best case and O(2n) in the worst case.
public static int sub(byte[] bytes) {
int[] diffs = new int[bytes.length + 1];
diffs[0] = 0;
for (int i = 0; i < bytes.length; i ++) diffs[i+1] = diffs[i] + ((bytes[i]=='#')?-1:1);
HashMap<Integer,Integer> difToStart = new HashMap<Integer,Integer>();
int max = 0;
for (int i = 0; i < diffs.length; i ++) {
Integer start = difToStart.get(diffs[i]);
if (start == null) difToStart.put(diffs[i], i);
else max = Math.max(max, i - start);
}
return max;
}
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
void find();
char *input;
int n,ns,nh,ns1=-1,nh1=-1;
int main()
{
printf("Enter the size of array : ");
scanf("%d",&n);
input = (char*)malloc(n*sizeof(char));
printf("Enter the array : ");
fflush(stdin);
gets(input);
find();
return 0;
}
void find()
{
int i;
ns = nh = 0;
for(i=0;i<n;i++)
{
if(input[i] == '*')
{
if(input[i-1] == '#')
ns = 0;
ns++;
}
if(input[i] == '#')
{
if(input[i-1]=='*')
nh = 0;
nh++;
}
if(nh>nh1)
nh1 = nh;
if(ns>ns1)
ns1 = ns;
}
if(ns1 == nh1)
printf("Such longest substring is of length : %d", ns1);
else
printf("No such substring");
}
I wrote a simpler program that takes a pointer to middle of an integer array instead of map.
char arr[]="*##*###*****####*#*###*";
int len=strlen(arr);
cout<<"len="<<len<<endl;
int *newarr=new int[2*len+1];
int newdistance[2*len+1]; //distance between pair with same number
int *arrpos=newarr+len-1; //allow negative positions also
int *distance=newdistance+len-1; //distance for negative positions
for(int i=-len;i<=len; i++)
arrpos[i]=-100,distance[i]=0;
int pos=0; //universal position of each character
for(int i=0;i<len;i++)
{
if(arr[i]=='*') //* is +1
pos++;
else
pos--; //# is -1
if(arrpos[pos]!=-100) //this number was encountered before
distance[pos]=i-arrpos[pos];
else //first time pos found
arrpos[pos]=i; //save position of number
}
int max=0;
int maxpos=0;
for(int i=-len;i<=len;i++)
{
if(arrpos[i]!=-100)
{
cout<<"Largest distance for number "<<i<<" is "<<distance[i]<<" ,1st occr="<<arrpos[i]<<endl;
//now find largest of all distances, that is the largest subarray.
if(max<distance[i])
{
max=distance[i];
maxpos=arrpos[i];
}
}
}
cout<<"max subarray of equal number of * and # is of length "<<max<<" and starts at pos "<<maxpos+1<<endl;
return 0;
Output is
len=23
Largest distance for number -4 is 0 ,1st occr=21
Largest distance for number -3 is 16 ,1st occr=6
Largest distance for number -2 is 14 ,1st occr=5
Largest distance for number -1 is 16 ,1st occr=2
Largest distance for number 0 is 12 ,1st occr=1
Largest distance for number 1 is 12 ,1st occr=0
Largest distance for number 2 is 0 ,1st occr=11
max subarray of equal number of * and # is of length 16 and starts at pos 7
static void Main(string[] args)
{
Console.WriteLine(FindLongestSubstring("################################*#"));
Console.WriteLine(FindLongestSubstring("**#*##"));
Console.WriteLine(FindLongestSubstring("****##**#**##"));
Console.WriteLine(FindLongestSubstring("*##*###*****####*#*###*"));
Console.ReadKey();
}
// Given an array containing only stars '*' and hashes '#' . Find longest contiguous sub array that will
// contain equal no. of stars '*' and hashes '#'.
// Order (n) solution required
public static string FindLongestSubstring(string s)
{
if (s.Length == 0)
return "";
List<int> lengths = new List<int>();
char prev = s[0];
int count = 0;
foreach (char c in s)
{
if (prev != c)
{
lengths.Add(count);
count = 0;
}
count++;
prev = c;
}
lengths.Add(count);
int index = 0;
int longestIndex = -1;
int maxOfMin = -1;
for (int i = 0; i < lengths.Count - 1; i++)
{
int min;
min = (lengths[i] < lengths[i + 1]) ? lengths[i] : lengths[i + 1];
index += lengths[i];
if (min > maxOfMin)
{
maxOfMin = min;
longestIndex = index;
}
}
Console.Write("Index: {0}, Length: {1}, Orig: {2}, ", longestIndex, maxOfMin, s);
return s.Substring(longestIndex - maxOfMin, 2 * maxOfMin);
}
#include<stdio.h>
#include<string.h>
#include<conio.h>
int compare(char input[],int star[],int hash[],int low,int high,int *start)
{
int no_star,no_hash;
int max;
int max1,max2;
int start1,start2;
if(input[low]=='*')
{
no_star=star[high]-star[low]+1;
no_hash=hash[high]-hash[low];
}
else
{
no_star=star[high]-star[low];
no_hash=hash[high]-hash[low]+1;
}
if(no_star == no_hash)
{
*start=low;
max=no_hash;
}
else
{
max1=compare(input,star,hash,low+1,high,&start1);
max2=compare(input,star,hash,low,high-1,&start2);
if(max1 > max2)
{
max=max1;
*start=start1;
}
else
{
max=max2;
*start=start2;
}
}
return max;
}
int main()
{
char input[]="*##*###**##**###*";
int *star;
int *hash;
int length;
int i,j,k;
int start;
int no_of_char;
length=strlen(input);
star = (int *)malloc(length*sizeof(int));
hash = (int *)malloc(length*sizeof(int));
if(input[0]=='*')
{
star[0]=1;
hash[0]=0;
}
else
{
hash[0]=1;
star[0]=0;
}
for(i=1;i<length;i++)
{
if(input[i]=='*')
{
star[i]=star[i-1]+1;
hash[i]=hash[i-1];
}
else
{
hash[i]=hash[i-1]+1;
star[i]=star[i-1];
}
}
no_of_char=compare(input,star,hash,0,length-1,&start);
printf("Sub array is ");
no_of_char *= 2;
while(no_of_char > 0)
{
printf("%c",input[start++]);
no_of_char--;
}
getch();
}
Using PHP:
function findLongestSubarray($in_array){
$arr_len = count($in_array);
$longest = '';
$stars = '';
$hashes = '';
$previous_char = '';
for($i=0;$i<$arr_len;$i++){
$current_char = $in_array[$i];
if($current_char!=$previous_char){
if($current_char=='#') $hashes = ''; else $stars = '';
}
${($current_char=='*'?'stars':'hashes')} .= $current_char;
if(strlen($stars)==strlen($hashes))
if((strlen($stars) + strlen($hashes))>strlen($longest))
$longest = ($current_char=='*')?$hashes.$stars:$stars.$hashes;
$previous_char = $current_char;
}
return $longest;
}
echo "the longest substring is: ". findLongestSubarray(['#','*','#','#','#','*','*','#','*','#','#','#','#','*','*','*','*','*','#','#','*','#','#','*','*','*','#','#','*','*','*','#','#','#']);
1a. Define a block as one that has equal number of *s and #s. A block will have a starting position and an ending position. The block(s) that has the maximum difference between these numbers is/are the answer.
1b. Create an empty linked list to hold the blocks.
2. Start reading the array.
3. When you encounter a "change" (* followed by # or vice-versa), add a block to the linked list.
4. When you are done reading the array, the linked list will have only blocks. If the linked list is empty, it means the array consists of only one kind of symbol and we could not find any contiguous blocks.
5. Now read the linked list. Pick the first block. Look at the next block and see if they 'touch' each other (ending position of first one is one less than starting position of the next). If they are throw out both the blocks, coalesce them, and insert the new block in its place.
6. If the next block is not contiguous, go back to the original array and check if there is a * and # combination with one on left or one on right of the current block. If so, expand the current block (by changing start and end). Then go back to step 5 and see if we have hit another block. If we don't hit another block and the left and right symbols don't 'cancel' each other out, we move on to the next block in the list.
7. Repeat this process for each block in the linked list.
8. Once reading the linked list is done, we are ready to make a call. By this time, we have blocks and we have symbols that could not make it into any blocks. These symbols are 'unbalanced' and do not have a counter symbol. Our problem now is to examine each of these blocks and identify the one with the longest length.
9. Read the linked list again, this time picking up the block that has maximum width. This is your answer.
The code runs in O(n) since we read the array twice and the linked list twice. The linked list will have n/2 elements in the worst case and the coalescing operation will be O(n).
private static String largeSubString (String str){
int hashCount = 0, starCount = 0, start = 0, end = -1 ;
String maxString ="";
int maxLen = 0;
if(str.length() > 2){
for(int index = 0; index < str.length(); index ++){
for (int count = index +1; count < str.length(); count ++){
String string = str.substring(index, count+1);
if (isBalancedString (string)){
if (maxLen < string.length())
{
System.out.println(string);
maxLen = string.length();
maxString = string;
}
}
}
}
}
return maxString;
}
private static boolean isBalancedString(String string) {
int starCount = 0, hashCount = 0;
if(string.length() == 1)
return false;
for (int index = 0; index < string.length(); index ++) {
if(string.charAt(index) == '*')
starCount ++;
else
hashCount++;
}
return hashCount == starCount? true : false;
}
char* findLongestBalancedRun( const char *str )
{
int len = strlen( str );
char *run = str;
int hashes = 0;
int stars = 0;
for( int i = 0; i < len; i++ )
{
if( '*' == str[i] ) stars++;
else hashes++; // since we only have * and # skip a test
int balance = hashes - stars;
if( 0 == balance ) continue;
if( 0 > balance ) balance = -balance; // get the absolute value
// if we don't have enough remaining characters to balance, move the target
if( ( len - 1 - i ) < balance )
{
// adjust the counts for the character we're going to skip
if( '*' == *run ) stars --;
else hashes--;
run++;
}
}
return run;
}
Working code:
public class MaxSubArrayOfCommonElement {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "***##**#*#*####";
char charArr[] = str.toCharArray();
int countOfStar = 0;
int countOfHash = 0;
int maxCountOfStar = 0;
int maxCountOfHash = 0;
boolean charMisMatch = false;
char preChar = charArr[0];
for (char ch : charArr) {
if ( preChar != ch) {
charMisMatch = true;
} else {
charMisMatch = false;
}
if (countOfStar > maxCountOfStar && charMisMatch) {
maxCountOfStar = countOfStar;
}
if (countOfHash > maxCountOfHash && charMisMatch) {
maxCountOfHash = countOfHash;
}
if (charMisMatch) {
countOfStar = 0;
countOfHash = 0;
}
if ((ch == '*' && countOfStar == 0) || (ch == '*' && preChar == ch)) {
countOfStar++;
}
else if ((ch == '#' && countOfHash == 0) || (ch == '#' && preChar == ch)) {
countOfHash++;
}
preChar = ch;
}
if (countOfStar > maxCountOfStar) {
maxCountOfStar = countOfStar;
}
if (countOfHash > maxCountOfHash) {
maxCountOfHash = countOfHash;
}
if (maxCountOfStar > maxCountOfHash) {
System.out.println("max count of common char subArray is " + maxCountOfHash);
}
else {
System.out.println("max count of common char subArray is " + maxCountOfStar);
}
}
}
Have Counter for Star and Hash. lets say if arr[i] is "*", then check if there is any hash available. If yes, then increment sum by 2 and decrement "#" counter by one. If No then increment "*" counter by one. At the end, you will have total sequence. (optionally you can store start and end index also)
Code will look like this. For int arr interatiion I am taking 0 and 1 instead of * and #.
public static void findMaxSeq1(int[] arr)
{
int sum = 0, zeroCount = 0, oneCount = 0;
for(int i : arr)
{
if(i == 0)
{
if(oneCount >= 1)
{
sum+=2;
oneCount--;
}
else
zeroCount++;
}
else
{
if(zeroCount >= 1)
{
sum+=2;
zeroCount--;
}
else
oneCount++;
}
}
System.out.println("Max Seq is :: "+sum);
}
public static int LongestStarAndHashMatch(string StarAndHash)
{
string[] str = StarAndHash.Split(new char[] { '#' });
int largest = 0;
Dictionary<int, int> startDictionary = new Dictionary<int, int>();
for (int i = 0; i < str.Length; i++)
{
if (!startDictionary.ContainsKey(str[i].Length))
{
startDictionary.Add(str[i].Length, 0);
}
}
string[] strs = StarAndHash.Split(new char[] { '*' });
for (int j = 0; j < strs.Length; j++)
{
if (startDictionary.ContainsKey(strs[j].Length))
{
largest = (strs[j].Length > largest) ? strs[j].Length : largest;
}
}
return largest;
}
As mentioned above, the 2 steps solution works fine.
1. get the diff array
2. use a hash map to save the first occurrence of a diff number
package careercup;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class LongestSubString {
// Given an array containing only stars '*' and hashes '#' . Find longest contiguous sub array that will contain
// equal no. of stars '*' and hashes '#'.
// Order (n) solution required
private static final String input1 = "##*#**"; // 6
private static final String input2 = "##############*#"; // 2
public static void main(String[] args) {
System.out.println(get(input1));
System.out.println(get(input2));
}
public static int get(String input) {
if (null == input)
return -1;
int[] arr = new int[input.length()];
char[] str = input.toCharArray();
// * = 1, # = -1
int sum = 0;
for (int i = 0; i < str.length; i++) {
if (str[i] == '*')
sum += 1;
else if (str[i] == '#') {
sum -= 1;
} else {
System.out.println("invalid input: " + str[i]);
}
arr[i] = sum;
}
System.out.println("arr = " + Arrays.toString(arr));
int max = -1;
Map<Integer, Integer> pos = new HashMap<Integer, Integer>();
pos.put(0, -1);
for (int i = 0; i < arr.length; i++) {
int value = arr[i];
Integer first = pos.get(value);
if (null == first) {
pos.put(value, i);
continue;
} else {
int diff = i - first;
if (diff > max)
max = diff;
}
}
return max;
}
}
#include <iostream>
using namespace std;
int findSubArray(char arr[],int size)
{
int starcount = 0;
int hashcount = 0;
int s=0,e=-1,max1 = -1;
for(int i=0;i<size;i++)
{
if(arr[i] == '#') hashcount++;
if(arr[i] == '*') starcount++;
if(starcount == hashcount)
max1 = starcount+hashcount , s = 0, e = i;
else
{
int temp = 2 * min ( starcount , hashcount);
if(temp > max1)
max1 = temp, s = i -temp + 1,e = i;
}
}
cout<<"start : "<<s<<"\t"<<", end : "<<e<<endl;
cout<<"subarray : " <<endl;
for(int i=s;i<=e;i++)
cout<<arr[i]<<"\t";
cout<<endl;
return max1;
}
/* Driver program to test above functions */
int main()
{
char arr[] = {'#', '#', '#', '#', '#', '#', '*','*','#','#','*'};
int size = sizeof(arr)/sizeof(arr[0]);
int m = findSubArray(arr, size);
cout<<"count : "<<m<<endl;
return 0;
}
public class EqualNumberSymbols
{
private static boolean checkEquality(String s)
{
Deque<Character> dq1 = new ArrayDeque<Character>();
Deque<Character> dq2 = new ArrayDeque<Character>();
for(int i = 0; i < s.length(); i++)
{
if(s.charAt(i) == '#')
{
dq1.push('#');
}
else
{
dq2.push('*');
}
}
return dq1.size() == dq2.size();
}
public static void main(String a[])
{
String s = "###**##*##*#**#";
String temp = null;
int max = 0;
String result = null;
for(int i = 0; i < s.length(); i++)
{
for(int j = i+1; j < s.length()+1; j++)
{
temp = s.substring(i, j);
if(temp.length()%2 == 0)
{
if(checkEquality(temp))
{
if(max < temp.length())
{
max = temp.length();
result = temp;
}
}
}
}
}
System.out.println(result);
}
char current;
int currentCount;
int currentStart;
char previous;
int previousCount;
int previousStart;
int contiguousStart;
int contiguousLength;
public void find(char[] arr){
current = arr[0];
for(int i=0; i<arr.length; i++){
if(arr[i] != current || i==arr.length-1){
if(previous != '\0'){
int length = 2 * Math.min(currentCount, previousCount);
if(length > contiguousLength){
contiguousLength = length;
if(previousCount <= currentCount){
contiguousStart = previousStart;
}else{
contiguousStart = currentStart - currentCount -1;
}
}
}
previous = current;
previousCount = currentCount;
previousStart = currentStart;
current = arr[i];
currentCount=1;
currentStart = i;
}else{
currentCount++;
}
}
}
Consider * and # as 1 and -1. Then calculate the sum starting from left, and store it in the array.
- joe kidd August 03, 2014Example: *##*###** becomes 1 -1 -1 1 -1 -1 -1 1 1 and the sums = [1 0 -1 0 -1 -2 -3 -2 -1].
As you can see the places where 0 appearance says that there is an equal amount of zeros and one,
starting from the beginning of the array. In the places where the number matches, let's say at
index i and j, the sum between i + 1, and j was equal 0.
In the second step you need to find the maximum distance. Consider using hash_map for storing
the first occurence of every number. Calculate the size.