CareerCup

Scala code for it using recursion.

object Encoder {
  def main(args: Array[String]): Unit = {
    allValidEncodedValues("12")
  }

  def toAlphabet(i : Int): String = (i+64).toChar.toString

  def allValidEncodedValues(ss : String): Any = {
    def loop(str : String, acc : String) : Unit = {
      if(str.isEmpty) print(acc)
      else if (str.length == 1) print(acc + toAlphabet(str.toInt))
      else{
        val secPart = str.substring(0,2)
        loop(str.substring(2,str.length), acc + toAlphabet(secPart.toInt))
        println
        val firstPart = str.substring(0,1)
        loop(str.substring(1,str.length), acc + toAlphabet(firstPart.toInt))
      }
    }
    loop(ss,"")
  }

}

Go to the k-1th element,save the next as head.
Point the next of k-th element to null.
Take the last k elements of the list and point the end of it to the original head
In Scala you can do it by drop and take

def rotateList(list : List[Int], k : Int) : List[Int] = list.drop(k)++list.take(k)

//Scala code for the above

def listIncreasingSubstring(str : String): List[String] = {
    def loop(start : Int, end : Int, result : List[String]) : List[String] = {
      val sub = str.substring(start,end+1)
      //See if this substring is strictly increasing
      val correctStart = everyCharIsGreaterThanLast(str,start,end)
      //Add the substring if it is increasing
      val newResult = if(correctStart) sub :: result else result
      //further loop conditions
      if(end == str.length - 1 && start == str.length - 2) newResult
      //checking correctStart here so that if a substring is not increasing from a fixed start there is no point in checking further from that start
      else if (end == str.length - 1 || !correctStart) loop(start+1,start+2,newResult)
      else loop(start,end+1,newResult)
    }
    loop(0,1,Nil)
  }

  def everyCharIsGreaterThanLast(str: String, start : Int, end: Int) : Boolean = {
    if (start == end) true
    else if(str.charAt(start) >= str.charAt(start+1)) false
    else everyCharIsGreaterThanLast(str,start+1,end)
  }

taking address of x in variable add_x
then modifying i's value by using ***add_x

#include <stdio.h>

int main()
{
	int i, j;
	int * p, * q;
	int ** x;
	int ***add_x; 
	
	i = 100;
	j = 200;
	p = &i;
	q = &j;
	x = &p;
	
	*p = *p + *q;
	*q = **x / 2;
	**x = *p + j;

	
	printf(" i = %d\n", i);
	printf("&i = %p\n", &i);
	printf(" j = %d\n", j);
	printf("&j = %p\n", &j);
	
	printf(" p = %p\n", p);
	printf("&p = %p\n", &p);
	printf("*p = %d\n", *p);
	printf(" q = %p\n", q);
	printf("&q = %p\n", &q);
	printf("*q = %d\n", *q);
	
	printf(" x = %p\n", x);
	printf("&x = %p\n", &x);
	printf("*x = %p\n", *x);
	printf("**x= %d\n", **x);
	
	//Modifying i:
	add_x = &x;
	***add_x = **x + j ; //Or any value you want to modify to  
	printf(" i = %d\n", i);
	printf("&i = %p\n", &i);
	
	return 0;
}

#include <stdio.h>

	float multiply(float x, float y){
		return x*y;	
	}
	float add(float x, float y){
		return x+y;
	}
	float divide(float x, float y){
		if(y==0){
			printf("Invalid input");
			return 0;
		}
		else
			return x/y;
	}
	float sub(float x, float y){
		return x-y;
	}
	float min(float x, float y){
		return x>y?y:x;
	}
	float max(float x, float y){
		return x>y?x:y;
	}
	
	int main(){
		float a,b,r;
		char op;
		do{
			printf("\nnumber op number?");
			scanf("%f %c %f", &a, &op, &b);
			switch(op){
				case '+' : 
					r = add(a,b);
					break;
				case '-':
					r = sub(a,b);
					break;
				case '*':
					r = multiply(a,b);
					break;
				case '/':
					r = divide(a,b);
					break;
				case 'm':
					r = min(a,b);
					break;
				case 'M':
					r = max(a,b);
					break;
				case 'q':
					break;
				default :
					op = '?';
			}
			if(op=='?'){
				printf("Unknown operator");
			}else if(op=='q'){
				printf("Bye\n");
			}else{
				printf("%f %c %f = %f", a,op,b,r);
			}
		}while(op != 'q');
		return 0;
	}

public static int sum(int x, int max){
		if(x==max)
		  return max;
		else 
			return x + sum(x+1,max);
	}

You have already explained the logic..... This is java implementation of the same

public static void countAlphabet(String str){
		char[] charr = str.toCharArray();
		int[] alphaCount = new int[26];
		for(int i=0;i<charr.length;i++){
			if(charr[i]>=97 && charr[i]<=122){
				alphaCount[charr[i]-97]++;
			}else if(charr[i]>=65 && charr[i]<=90){
				alphaCount[charr[i]-65]++;
			}
		}
		for(int i=0;i<26;i++){
			System.out.println(Character.toString ((char) (i+97))+": "+alphaCount[i]);
		}
	}

Just find the max element for consecutive 3 elements and place it at even position.

static void weirdSorting(int[] arr){
		int max = 0;
		int temp = 0;
		for(int i=1;i<arr.length;i+=2){
			max = Ideone.findMax(arr,i);
			temp = arr[max];
			arr[max] = arr[i];
			arr[i] = temp;
		}
 
	}
	static int findMax(int[] arr, int i){
		int max = 0;
		if(i<arr.length-1){
				max = arr[i]>arr[i-1]? i:i-1;
				max = arr[i+1]>arr[max]? i+1:max;
		}else{
			max = arr[i]>arr[i-1]? i:i-1;
		}
			System.out.println(max +"max	");
		return max;
	}

I dont think you can say that. What about, if i create object of Integer class.

Integer i = new Integer(4);

and pass this to a function??

1. Iterate over the 1000 words.
Create a multivalue hashmap, put the sorted form of that word as key and actual order as value. So all 'act', 'tca', 'cat' will come under key 'act'.
2. Sort the string to compare i.e. sort 'tca' -> 'act'.
3. Use 'act' as key to find all the values from hashmap.

code :

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;


public class Anagrams {
	public static void main(String[] args) {
		String[] source = {"cat","act","tca", "good", "dogo", "waste", "read", "dear"};
		printSameKind(source, "good");
		printSameKind(source, "read");
		printSameKind(source, "act");
	}
	public static void printSameKind(String[] source, String str){
		Hashtable<String, List<String>> ht = new Hashtable<String, List<String>>();
		MergeSort sorter = new MergeSort();
		List<String> values;
		char[] chr;
		
		for(int i=0;i<source.length;i++){
			chr = source[i].toCharArray();
			sorter.sort(chr);			
			String sortedString = String.valueOf(chr);
			if(ht.get(sortedString)==null){
				values = new ArrayList<String>();
			}else{
				values = ht.get(sortedString);
			}
			values.add(source[i]);
			ht.put(sortedString, values);
		}
		
		
		chr = str.toCharArray();
		sorter.sort(chr);
		str = String.valueOf(chr);
		List<String> result = ht.get(str);
		System.out.println(result);
	}
	
}

(I have used mergesort to sort the string)

public class MergeSort {
	private char[] c; 
	private char[] helper;

	private int number;

	public void sort(char[] chr){
		this.c = chr;
		this.number = chr.length;
		this.helper = new char[number];
		mergesort(0,number-1);
	}

	private void mergesort(int first, int last){
		
		if(first<last){
			int mid = first + (last-first)/2;
			mergesort(first,mid);
			mergesort(mid+1,last);
			merge(first,mid,last);
		}		
	}

	public void merge(int start,int mid, int end){

		//Copy both parts to helper array
		for(int i=start;i<=end;i++){
			helper[i] = c[i];
		}
		
		int i = start;
		int j = mid+1;
		int k = start;
		while(i<=mid && j<=end){
			if(helper[i]<=helper[j]){
				c[k] = helper[i];
				i++;
			}else{
				c[k] = helper[j];
				j++;
			}
			k++;
		}
		while (i <= mid) {
			c[k] = helper[i];
			k++;
			i++;
		}
		while (j <= end) {
			c[k] = helper[j];
			k++;
			j++;
		}

	}
}

Hey,
I am assuming the phone numbers are in some file.
I used a hash map to add names as keys and phone numbers as ArrayList.
Here is the code:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.List;


public class PhoneNumbers {
	public static void main (String[] s)  throws IOException{	
		getPhone("resources/Directory_phone.txt");
	}
	public static void getPhone(String str)  throws IOException{
		FileReader fr = new FileReader(str);	
		BufferedReader br = new BufferedReader(fr);
		String  thisLine = null;
		Hashtable<String,List<String>> ht = new Hashtable<String,List<String>>();
		while((thisLine = br.readLine()) != null){
			//System.out.println(thisLine);
			String[] nameNum = thisLine.split("--");		
			List<String> values;// = new ArrayList<String>();
			if(ht.get(nameNum[0].toLowerCase())==null){
				values = new ArrayList<String>();				
			}else{
				values = ht.get(nameNum[0].toLowerCase());				
			}
			values.add(nameNum[1]);
			ht.put(nameNum[0].toLowerCase(), values);
		}
		
		Enumeration<String> enumKey = ht.keys();
		while(enumKey.hasMoreElements()){
			String s = enumKey.nextElement();
			List<String> values  = ht.get(s);
			System.out.println(s + " -- "+ values);
		}
		
		br.close();
	}
}

The text file :

abc--123
AbC--432
des--212
des--433
Home--322

Use a hash table.
-key word in lower case.
-value its frequency.
--Increase the value when the word is already there in hash otherwise just put it in hash table.

Here is the code.

import java.util.Enumeration;
import java.util.Hashtable;


public class FrequencyWords {
	public static void main(String[] args) {
		String[] arr = {"Good", "bad", "good", "word", "woRd"};
		countFrequency(arr);
	}
	public static void countFrequency(String[] arr){
		Hashtable<String, Integer> ht = new Hashtable<String, Integer>();
		for(int i=0;i<arr.length;i++){
			if(ht.get(arr[i].toLowerCase())==null){
				ht.put(arr[i].toLowerCase(), 1);
			}else{
				ht.put(arr[i].toLowerCase(), ht.get(arr[i].toLowerCase()) + 1);
			}
		}
		Enumeration<String> enumKey = ht.keys();
		while(enumKey.hasMoreElements()){
			String str = enumKey.nextElement();
			Integer value = ht.get(str);
			System.out.println(str + " -- "+ value);
		}
		
	}
}

public class stringToInteger {

	public static void main(String[] args) {
		int y=1;
		int number = 0;
		int start = 0;
		int sign =1;
		String str = "9000";
		
		if(str.charAt(0) == '+'){
			start++;
			sign = 1;
		}
		else if(str.charAt(0) == '-'){
			start++;
			sign = -1;
		}
		for(int i=str.length()-1; i>=start;i--){
			char c = str.charAt(i);
			number = number + ((c-48)*y);
			y*=10;
			
		}
		number *= sign;
		
		System.out.println(number);
	}
}

void printrev(struct node *head)
{
    struct node *q=NULL,*p=head;
    while(q!=head)
    {
        p=head;
        while(p->next!=q)
            p=p->next;
        printf("%d  ",p->data);
        q=p;
    }

}

i didnt get your question what is the capacity of Y containers? and what is fixed cost C is it directly proportional to something??

nyc algo :) can u tell me the complexity?

i thought of a optimization
if (target ==-1 || start > 7) {
return ;
}
should be better written as
if (target <=-1 || start > 7) {
return ;
}

how will u "print" that path?? can u please explain

i thought something like that too... but it was also mentioned that. The range of output can be large that cant fit in integer or double. Sorry i forgot to mention that

Nyc :)
I have a doubt though... why have u taken only 5 next conditions why not 8..such as

printMatrixPaths(matrix, row+1, column-1, path, word, tempWord);
		printMatrixPaths(matrix, row, column-1, path, word, tempWord);
		printMatrixPaths(matrix, row-1, column-1, path, word, tempWord);

char * DecodeURL(char *a,int n)
{
int i,j;
for(i=0,j=0;i<n && j<n; i++,j++)
{
if(a[i]=='%')
{
if(a[i+1]=='2' &&a[i+2]=='0')
a[i]=' ';
if(a[i+1]=='3' && a[i+2]=='A')
a[i]='?';
if(a[i+1]=='3' && a[i+2]=='D')
a[i]=':';

j=j+2;
}
else
{
a[i]=a[j];
}
}
a[i]='\0';
return *a;
}
#include<stdio.h>
int main()
{
char s[]="kitten%20.jpg";
int n=sizeof(s)-1;
DecodeURL(s,n);
printf("%s",s);
}

Nyc... I also thought of the same solution. I have a doubt though.
Will this solution or the one suggested by - ashot madatyan will give less number of comparisons?

Sorry i made a mistake the val array would be....
4 3 5 2 4 4 6 1
(i wrote the sorted one by mistake)

This can be done by using an extra array. Say the array is val[].
1. Give the root index of original array(a[]) i.e. 0 in val array value =(Number of nodes)/2.
(The number of nodes I am assuming are given).
2. Set root left child index i.e. val[2i+1]=val[0]-1 and right child index i.e. val[2i+2]=val[0]+1.
Do this for whole array.
for example if given array is
1 2 3 9 4 6 5 8
val array will have
1 2 3 4 4 4 5 6
Sort val array(using counting sort(O(n)) and as u sort val array keep changing original array too correspondingly.

Sorry i cant make out what is the complexity for it. :(

I learned about newtons method by a video in youtube. This site doesnt allow to post the link it is : Finding Roots with Newton's Method.
now as for ur questions:
Why do you pick x0 = 1? Aren't you supposed to choose x0 = n as your initial guess?
This is just because in the video that guy said to take is as 1 not sure why.

What is the significance of choosing 0.00000000000009 as the precision?
The basic idea behind this algo was result was accurate when dx=x(i+1)-x(i) was minimum. So I tried to take some random minimum possible difference. But that was stupid of me better would be if we take run the loop till x1-x0!=0. I was in doubt that it would result in infinite loop but i checked it it works fine.
Here is it with change:

double squareroot(double num)
{
    double x0,x1=1;
    if(num<0)
    {
        printf("Negative Input not valid");
    }
    do
    {
        x0=x1;
        x1=(1/2.0)*( x0 + num/x0);
    }while(x1-x0);

    return x1;

}

This is based on Newtons method.

double squareroot(double num)
{
    double x0,x1=1;
    if(num<0)
    {
        printf("Negative Input not valid");
    }
    do
    {
        x0=x1;
        x1=(1/2.0)*( x0 + num/x0);
    }while((x1-x0)>0.00000000000009 || x0-x1>.00000000000009);

    return x1;

}

If structurally similar means : in binary tree the alignment of tree is same but values can be different then...

int strSimilar(struct node *root1,struct node *root2)
{
    if(root1==NULL && root2==NULL)
        return 1;
    if(root1==NULL || root2== NULL)
        return 0;
    return strSimilar(root1->left,root2->left) && strSimilar(root1->right,root2->right);

}

void printSpiral(int **a,int m,int n)
{
    int i=0,j=0,p,q;
    p=m;
    q=n;
    while(p>0 && q>0)
    {
        while(j<q)
        {
            printf("%d ",a[i][j]);
            j++;
        }
    j--;
    i++;
    while(i<p)
        {
            printf("%d ",a[i][j]);
            i++;
        }
    i--;
    j--;
    while(j>=(n-q))
    {
        printf("%d ",a[i][j]);
        j--;
    }
    j++;
    i--;
    while(i>m-p)
    {
        printf("%d ",a[i][j]);
        i--;
    }
    i++;
    j++;
    p--;
    q--;

}

I found the first non 9 number and incremented it.
Decremented the digit after it.
But it doesnt solve the 999->doesnt exist case. Please help me will that :\

int Next(int a)
{
   int b,f,c,level=1;
   f=a;
   b=a;
   while(f!=0)
   {
       c=f%10;
       f=f/10;
       if((f%10)+1<10)
        {
            b=b+pow(10,level);
            b=b-pow(10,level-1);
            break;
        }
       else
        level++;
   }
   return b;

}

ohhh sorry then i guess ur answer seems correct :/

int mul(int a,int b)
{
int c=0;
if(abs(b)>abs(a))
{swap(a,b,c);}
printf("a=%d b=%d\n ",a,b);
if(b==1)
return a;
if(b==0 || a==0)
return 0;
if(b<0)
{
b=-b;
return -(a + mul(a,b-1));
}

return (a + mul(a,b-1));
}

For all positive a condition at start to check the least element

#include<stdio.h>
void maxSum(int *a,int n)
{
    int SumSoFar=0,sumEndingHere=0,i;
    int start=0,end=0;
    for(i=0;i<n;i++)
    {
        sumEndingHere+=a[i];
        if(sumEndingHere<0)
        {
            sumEndingHere=0;
            start=i+1;
            continue;
        }
        if(sumEndingHere>SumSoFar)
            {
                SumSoFar=sumEndingHere;
                end=i;
            }
    }
    printf("%d\n",SumSoFar);
    for(i=start;i<=end;i++)
        printf("%d ",a[i]);
}
void minSum(int *a,int n)
{
    int SumSoFar=0,sumEndingHere=0,i,min=99;
    int start=0,end=0;
    for(i=0;(a[i]>0 && i<n);i++)
    {
         if(a[i]<min)
            min=a[i];
    }
    if(i==n)
        printf("%d",min);

    else{
    for(i=0;i<n;i++)
    {
        sumEndingHere+=a[i];
        if(sumEndingHere>0)
        {
            sumEndingHere=0;
            start=i+1;
            continue;
        }
        if(sumEndingHere<=SumSoFar)
            {
                SumSoFar=sumEndingHere;
                end=i;
            }
    }
    printf("%d\n",SumSoFar);
    for(i=start;i<=end;i++)
        printf("%d ",a[i]);
    }
}
int main()
{
    int *a,n,i;
    scanf("%d",&n);
    a=(int *)malloc(sizeof(int)*n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    minSum(a,n);
}

By comparing both trees together at each step of inorder

#include<stdio.h>
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct stack
{
    int top;
    int capacity;
    struct node **array;
};

struct stack * CreateStack()
{
    struct stack *s=malloc(sizeof(struct stack));
    if(!s)
        return 0;
    s->top=-1;
    s->capacity=10;
    s->array=malloc(s->capacity*sizeof(struct node *));
    if(!s->array)
        return 0;

    return s;
}
int isEmptyStack(struct stack *s)
{
    return(s->top==-1);
}
void DoubleStack(struct stack *s)
{
    s->capacity*=2;
    s->array=realloc(s->array,s->capacity);
}
int isFullStack(struct stack *s)
{
     return(s->top==s->capacity-1);
}
void push(struct stack *s, struct node *root)
{
    if(isFullStack(s))
        DoubleStack(s);
    s->array[++s->top]=root;
}
struct node * pop(struct stack *s)
{
    if(isEmptyStack(s))
        return 0;
    else
        return s->array[s->top--];

}

struct node * newNode(int data)
{
        struct node *root;
        root=(struct node*)malloc(sizeof(struct node));
        root->data=data;
        root->left=NULL;
        root->right=NULL;
        return root;
}
int equalTrees(struct node *root1,struct node *root2)
{
    int count1=0,count2=0;
    struct stack *s1=CreateStack();
    struct stack *s2=CreateStack();
   int x=3,y=3;

    while(1)
    {
        while(root2)
    {
                push(s2,root2);
                root2=root2->left;
                count2++;
    }
    while(root1)
    {
                push(s1,root1);
                root1=root1->left;
                count1++;
    }
    if(isEmptyStack(s1) && isEmptyStack(s2))
    {
            return 1;
    }
    if(isEmptyStack(s1)|| isEmptyStack(s1) )
    {
              return 0;
    }
    if(count1!=count2)
        return 0;
               root1=pop(s1);
                root2=pop(s2);
                if(root1->data!=root2->data)
                    return 0;
                root1=root1->right;
                root2=root2->right;
    }


}
int main()
{
    struct node *root1 =newNode(1);
    root1->left        = newNode(3);
    root1->left->right  = newNode(2);
    struct node *root2 = newNode(1);
    root2->left        = newNode(2);
    root2->left->left  = newNode(3);
    printf("%d",equalTrees(root1,root2));
    return 0;
}

int find_maxsum(int *a,int n)
{
    int i=0;
    int prev_sum=0,sum=0,t;
    while(i<n)
    {
         if(prev_sum+a[i]<a[i])
        {
            //printf("helloo");
            sum=a[i];
        }
        else if(prev_sum+a[i]>sum)
        {
            //printf("hii");
            t=sum;
            sum=prev_sum+a[i];
            prev_sum=t;
            i++;
            continue;
        }

        i++;
        prev_sum=sum;
    }
    return sum;
}
int find_maxsum(int *a,int n)
{
    int i=0;
    int prev_sum=0,sum=0,t;
    while(i<n)
    {
         if(prev_sum+a[i]<a[i])
        {
            //printf("helloo");
            sum=a[i];
        }
        else if(prev_sum+a[i]>sum)
        {
            //printf("hii");
            t=sum;
            sum=prev_sum+a[i];
            prev_sum=t;
            i++;
            continue;
        }

        i++;
        prev_sum=sum;
    }
    return sum;
}
int find_maxsum(int *a,int n)
{
    int i=0;
    int prev_sum=0,sum=0,t;
    while(i<n)
    {
         if(prev_sum+a[i]<a[i])
        {
            //printf("helloo");
            sum=a[i];
        }
        else if(prev_sum+a[i]>sum)
        {
            //printf("hii");
            t=sum;
            sum=prev_sum+a[i];
            prev_sum=t;
            i++;
            continue;
        }

        i++;
        prev_sum=sum;
    }
    return sum;
}

I tried to keep previous sum...and current sum. this is working as far as i have tested.