ps
BAN USERJava version
public class reverseStringRecursive {
private static void reverse(char[] s,int start,int end){
if(start > end){
System.out.println("Reversed String " + String.valueOf(s));
return;
}
if(start == end)
return;
char temp = s[start];
s[start] = s[end];
s[end] = temp;
reverse(s,start+1,end-1);
}
public static void main(String args[]){
String s = "This is a test";
char []temp = s.toCharArray();
reverse(temp,0,temp.length-1);
System.out.println(s);
}
}
How about you iterate over the given string character by character and have an inner loop which runs from current index to the string length you are interested in finding out ( say 3) ( constant work) . Put each string of length 3 in a hashmap<Word, WordFrequencey> and update the frequency if the same string occurs again. At the end just iterate over the hashmap and return all those keys which have values > 1.
Time Complexity - O(n) , Space Complexity - No of words in the hashmap *( 2 bytes * (length of each word))
public class Solution {
public int search(int[] a, int target) {
int start = 0;
int end = a.length-1;
while(start <= end){
int mid = (start + end)/2;
if(a[mid] == target){
//System.out.println(mid);
return mid;
}
else if(a[start] <= a[mid] ){
if(target < a[start] || target > a[mid]){
start = mid +1;
}
else
end = mid;
}
else if(a[start] > a[mid] ){
if(target > a[mid] && target < a[start]){
start = mid +1;
}
else
end = mid;
}
}
return -1;
}
}
Complexity - O(log N) , modified binary search
- ps July 05, 2014public class secondHighest {
private static int findSecondMax(int count[]){
int i=0;
int MAX = count[0];
int index=0;
int maxindex=0;
int secondMax = 0;
for(i=1;i< count.length;i++){
if(count[i] > MAX ){
if(i!=1){
secondMax = MAX;
index = maxindex;
}
MAX = count[i];
maxindex = i;
}
else{
if(count[i] < MAX && count[i] > secondMax){
secondMax = count[i];
index = i;
}
}
}
return index;
}
public static void main(String args[]){
String s = "aab";
if(s.length() <= 1){
System.out.println(s);
}
int count[] = new int[256];
for(int i=0;i<s.length();i++){
count[(int)s.charAt(i) -97]++;
}
int c= findSecondMax(count);
System.out.println("second highest frequency " + (char)(c+97));
}
}
Working C code. Seems to pass the test cases which have been discussed.
void findDepth(char * str){
int i=0,depth =0,counter =0;
int len = strlen(str);
if(len < 4){
printf("\n Malformed String \n");
}
else{
for(i=0;i<len;i++){
if(str[i] == '('){
depth++;
if(str[i+1]=='0' && str[i+2]=='0');
if(str[i+1]=='0' && str[i+2]==')'){
printf("\n Malformed String \n");
break;
}
if(str[i+1]== '0' && str[i+2]=='(')
counter++;
}
else if(str[i] == ')' && depth == 0){
printf("\n Malformed String \n");
break;
}
else if( str[i] == ')' && depth > 0){
depth --;
}
else if(str[i]!='0' || str[i] !='(' || str[i] != ')'){
// printf("\n Malformed String");
break;
}
}
if(depth == 0)
printf("\n The depth of the given tree is %d", counter == 0? counter:counter +1);
else
printf("\n Malformed String");
}
}
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
void reverseString(char *str){
if(*str == '\0')
return ;
reverseString(str+1);
printf("%c", *str);
}
int main()
{
printf("Reverse a string recursively\n");
printf("\n Please enter a string to reverse \n");
char *str= malloc(sizeof(100*sizeof(char)));
scanf("%[^\n]s", str);
reverseString(str);
return 0;
}
Fully working Java code - handles all the cases
public class Solution {
public int maxSubArray(int[] A) {
int i=0;
int max=0;
int sum =0;
int flag = 0;
for(i=0;i< A.length;i++){
sum = sum + A[i];
if(sum < 0) {
int j=0;
if(A.length == 1)
max = A[0];
else {
for(j=0;j< A.length;j++)
{
if(A[j] > 0 ){
flag = 0;
break;
}
else flag = 1;
}
if(flag == 1){
max = A[0];
for(j=0;j< A.length-1;j++) {
if(A[j+1] >= max)
max = A[j+1];
}
}
else{
sum= 0;
}
}
}
else if(sum > max){
max = sum;
}
}
return max;
}
}
This doesn't work for many cases.
- ps October 20, 2014Example -
For this case
( ( (00) 0 ) ) , output should be 1 , while your logic will increment count 3 times.