CareerCup

It is possible to optimize 2nd step to O(n).
Steps:
1. Assuming we have two array sorted in ascending order. say arr1 and arr2.
2. Traverse through both array,starting from index 0.
3. if arr1[i]==arr2[j] then found matching element.
else if arr1[i]<arr2[j] then i++
else j++;

In steps, I am putting only logic not boundary conditions.

In worst case,u need to try 99 times. Try to minimize number of trials. It is possible.

mention problem statement, what u r to achieve using this code.

it will help in understanding code and in finding problem, if you will write problem statement as well

@mani: calling arrange with second with 2nd largest number will reduce number of calls, but finding 2nd largest number everytime will increase computation cost. what u say ??

In Addition:
(Valid String,Valid String with dest doesn't exist without write permission) return false;
(Valid String,Valid String with dest doesn't exist with write permission) return true;
(Valid String, Valid String with dest already exists with Override permission) return true;
(Valid String, Valid String with dest already exists without Override permission) return false;

@ce: Yes you are right.
I did modification in code to now it should work.

public static String mapping(int n){
		
		if(n<=26) return ""+str.charAt(n);
		if(n%26==0){
			return mapping((n/26)-1)+"z";
		}else{
			return mapping(n/26)+str.charAt(n%26);
		}
	}

nice solution...

I doubt O(n)+O(nlogn) will be equivalent to O(n). It should be O(nlogn)

nice solution.

As I feel, given example in question is not a BST.
@sastry.soft: we can't keep BST according to definition. but if we don't have choice and we have to keep duplicates then either we should keep it as left child or right child but not both.

#include <stdio.h>
		int main(){
		    
		   unsigned int i = 1;
		   char *c = (char*)&i;
		   if (*c)   
		       printf("Little endian\n");
		   else
		       printf("Big endian\n");
		   getchar();
		   return 0;
		}

Java based recursive solution:

public static String  str="aabcdedfghijklmnopqrstuvwxyz";
	public static String mapping(int n){
		
		if(n==0) return "";		
		return mapping(n/26)+str.charAt(n%26);				
	}

11

Solution is correct.
But in question which angle they want , its not mentioned so better return angle <180 degree always.

In Question, It is asked to return end leaf nodes also.

@Rohit: This is simply brute-force method.
Using other available data structure, you can optimize this code upto O(n).

@JustCoding: Yes it make sense. Your point is valid.
But this case will arise only if sum is even and (sum/2) is present in array. So we can take care of this as a special case.

Good Solution.

You can do it in o(n) time complexity by using additional space.
Store all the elements in a hashmap as key-value pair, where key is number and value is index.(this will take O(n) time.)
traverse through the list and for each number see whether (sum-num) is present or not in hashmap.(searching in hashmap will take O(1) time)
if(num is present in hashmap){
print both number with indexes
}else{
do nothing.
}

@freeninza: you mean to say arr[i-1]>arr[i+1] right ?

Logic:
1. Array is given with n elements. and we have to search an element say x.
2. take the mid element.
Its for sure, one half of array will be in correct order.
find half array with correct order. You can find it by comparing mid element with either
first element or last element.
3. If x lies in half array with correct order, do the binary search on this half.
Otherwise, repeat step 2 and 3.
for ex: 7 8 9 0 1 2 3 4 5 6 and suppose we have to search element say 9.
here the correct half order is 2 3 4 5 6 and 9 is not part of it.
so again we will process first half array 7 8 9 0 1
here correct half order is 7 8 9 and element 9 lies in this.
so we will perform binary search on this.

This complete process will take log(n) time.

Good Solution.

Mean: keep track of sum and number of elements.
and print sum/no_of_element.
Median: Use linkedlist to store the items in sorted fashion.
keep track of number of elements stored in linked list
Whenever a new item comes, add it into list.
based on the count of elements find the median.
Any better idea is welcome...

You can use BackTracking to solve this problem.

Convert the string in postfix expression.
Evaluate postfix expression

@Nayak: Can you write your logic step by step ?

@eugene.yarovoi : Its my mistake. We can't do the same in-place.

my mistake, this logic won't work.

For a given array of length n , one can find Max element and 2nd Max Element in O(n) time.
The idea here is while traversing through the loop along with max and 2nd max element, keep track of their differences as well.

@bluesky: The good thing about this approach is, it is in-place.
We don't need any extra space.

@ eugene.yarovoi: u r right. it is O(n^2logn).

This function will return 1 if Equal otherwise it will return 0.

int strMatch(char str1[],char str2[]){
 
	int arr[256];
	for(int i=0;i<256;i++){	   
	     arr[i]=0;
	}
	for(int i=0;str1[i]!='\0';i++){
	      arr[str1[i]]++;
	}
	for(int i=0;str2[i]!='\0';i++){
		if(arr[str2[i]]<=0) return 0;
	    arr[str2[i]]--;
	}
	for(int i=0;i<256;i++){	
		if(arr[i]>0) return 0;
	}
	return 1;
 }

Good Solution. But I am still wondering is there possibility to optimize it further.

Yes, my mistake.
Output should be:
1, 2, 4, 8, 3, 5, 6 , 9, 10, 7

consider n=10. So according to output should be:
1,2,4,8,3,5,6,7,9,10 which is incorrect.
In this Case, Output should be
1,2,3,4,3,5,6,9,10,7

Yes you are correct. Time Complexity is O(n).

I am not understanding what interviewer is trying to test by mandating recursion.
We can solve this question very efficiently without recursion.

fibonacci series starts from 0. Refer to wikipedia.

This function won't work for num=0.

All integers that is power of 2, contains only one set bit in its bit-representation.
So idea is to check, only one bit is set or not in bit representation of a number.
Below is the code:

int isPowerOf2(int n){

  return  n && !(n&(n-1));
}

this function will return 1, if number n is power of 2.
Else it will return 0;