sp!de?
BAN USERpublic int indexFun(int[] arr, int start, int end, int number)
{
if(arr[start] == number)
{
return start;
}
if(arr[end] == number)
{
return end;
}
if(start == end)
{
return -1;
}
int mid = ( start + end ) / 2;
if((arr[mid]<=arr[start] && (number<=arr[mid]|| number>=arr[start]))||
(arr[mid]>=arr[start] && number>=arr[start] && number <=arr[mid]))
{
return indexFun(arr, start, mid, number);
}
else
{
return indexFun(arr, mid+1, end, number);
}
}
public static void main(String args[]) {
int[] arr = {10,2,5,40,15,3,2};
int index = 0;
TreeSet<Integer> ts = new TreeSet<Integer>();
for(int i=0; i<arr.length; i++)
{
ts.add(arr[i]);
if(ts.size()>=4)
{
System.out.println(ts.first());
ts.remove(arr[index++]);
}
}
}
public static void main(String args[]) {
int[] arr = {10,2,5,40,15,3,2};
int index = 0;
TreeSet<Integer> ts = new TreeSet<Integer>();
for(int i=0; i<arr.length; i++)
{
ts.add(arr[i]);
if(ts.size()>=4)
{
System.out.println(ts.first());
ts.remove(arr[index++]);
}
}
}
#include <stdio.h>
#include "iostream"
#include <conio.h>
using namespace std;
struct node
{
int data;
node* leftChild;
node* rightChild;
node* rightNeighbour;
};
class SetRightChild
{
public:node* root;
public:SetRightChild()
{
root = new node();
}
public:node* SetTree()
{
root->data = 2;
node* leftNode = new node();
node* rightNode = new node();
leftNode->data = 1;
leftNode->leftChild = NULL;
leftNode->rightChild = NULL;
leftNode->rightNeighbour = NULL;
root->leftChild = leftNode;
rightNode->data = 3;
rightNode->leftChild = NULL;
rightNode->rightChild = NULL;
rightNode->rightNeighbour = NULL;
root->rightChild = rightNode;
return root;
}
public:void SetRightNeighbour(node* rootNode)
{
if(rootNode == NULL)
{
return;
}
if(rootNode->leftChild != NULL && rootNode->rightChild != NULL)
{
rootNode->leftChild->rightNeighbour = rootNode->rightChild;
}
SetRightNeighbour(rootNode->leftChild);
SetRightNeighbour(rootNode->rightChild);
}
public:void printTree(node* rootNode)
{
if(rootNode != NULL)
{
cout<<"Node: "<<rootNode->data<<endl;
if(rootNode->leftChild != NULL)
{
cout<<"LeftChild: "<<rootNode->leftChild->data<<endl;
}
if(rootNode->rightChild != NULL)
{
cout<<"RightChild: "<<rootNode->rightChild->data<<endl;
}
if(rootNode->rightNeighbour != NULL)
{
cout<<"RightNeighbour: "<<rootNode->rightNeighbour->data<<endl;
}
if(rootNode->leftChild != NULL)
{
printTree(rootNode->leftChild);
}
if(rootNode->rightChild != NULL)
{
printTree(rootNode->rightChild);
}
}
}
};
void main()
{
SetRightChild* tree = new SetRightChild();
tree->root = tree->SetTree();
cout<<"before setting rightneighbour: "<<endl;
tree->printTree(tree->root);
tree->SetRightNeighbour(tree->root);
cout<<"after setting rightneighbour: "<<endl;
tree->printTree(tree->root);
_getch();
}
import java.util.LinkedList;
import java.util.Queue;
import javax.swing.tree.TreeNode;
/**
* copy tree with unlimited number of children with breadth fist search...
*/
public class CopyTreeBFSeg {
/**
* @param args
*/
int data;
CopyTreeBFSeg leftChild, rightChild;
public CopyTreeBFSeg(int data){
this.data = data;
leftChild = null;
rightChild = null;
}
public CopyTreeBFSeg(){}
public CopyTreeBFSeg(CopyTreeBFSeg node){
this.data = node.data;
this.leftChild = null;
this.rightChild = null;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
CopyTreeBFSeg obj = new CopyTreeBFSeg();
CopyTreeBFSeg root = new CopyTreeBFSeg(5);
CopyTreeBFSeg lc = new CopyTreeBFSeg(6);
CopyTreeBFSeg rc = new CopyTreeBFSeg(7);
root.leftChild = lc;
root.rightChild = rc;
CopyTreeBFSeg newRoot = obj.copyTree(root);
System.out.println("new tree: ");
System.out.println(newRoot.data + " ");
System.out.println(newRoot.leftChild.data + " ");
System.out.println(newRoot.rightChild.data + " ");
}
public CopyTreeBFSeg copyTree(CopyTreeBFSeg root){
Queue<CopyTreeBFSeg> nodeQueue = new LinkedList<CopyTreeBFSeg>();
CopyTreeBFSeg newRoot=null;
CopyTreeBFSeg newNode=null, tempNode = null;
CopyTreeBFSeg markerNode= new CopyTreeBFSeg(0);
if(root==null){
return root; //nothing to copy
}
nodeQueue.add(root);
CopyTreeBFSeg newTreeNode = null;
CopyTreeBFSeg parentNode = null;
int lc=0,rc=0;
while(!nodeQueue.isEmpty()){
if(parentNode==null){
parentNode = newTreeNode;
}
tempNode = nodeQueue.remove();
if((tempNode.data==0)&&(lc==0)){
lc=1;
rc=0;
parentNode=parentNode.leftChild;
continue;
}
else if((tempNode.data==0)&&(rc==0)){
lc=0;
rc=1;
parentNode=parentNode.leftChild;
continue;
}
if((parentNode!=null)&&(tempNode.data!=0)){
if(parentNode.leftChild== null){
parentNode.leftChild = tempNode;
}
else{
parentNode.rightChild = tempNode;
}
}
if(tempNode.leftChild!=null){
nodeQueue.add(tempNode.leftChild);
}
if(tempNode.rightChild!=null){
nodeQueue.add(tempNode.rightChild);
nodeQueue.add(markerNode);
}
newTreeNode = new CopyTreeBFSeg(tempNode);
if(newRoot==null){
newRoot = newTreeNode;
}
}
return newRoot;
}
}
Hi Vikas,
Since we have all n arrays already sorted, the next step i.e. n-way merge sort, won't take any extra space (except the resultant array).
In fact, external sorting, which is used in case of memory restriction also uses this technique.
in this sorting,
1>>we will read 1st number from each sorted array, and put the least number in the resultant array.
2>>increament the index for this array from which least number is taken
3>>read next numbers and write least number of this cycle to resultant array
4>>continue till we are out of numbers from all the arrays
:)
/*
find the sub array of sum K from the the given unsorted array
*/
#include <iostream>
#include <conio.h>
#include <array>
using namespace std;
void getSubArray(int arr[],int arraySize,int * start, int * end, int desiredSum){
int sum = 0;
cout<<"initial values of start and end pointer elements: "<<*start<<" "<<*end<<endl;
if(arraySize==1){return;}
start = arr;
end = arr+1;
int count = 1;
sum = sum + *start + *end;
while(count < arraySize){
if(desiredSum == sum){
cout<<"Final subarray is: ";
while(start<=end){
cout<<*start<<" ";
start++;
}
return;
}
if(sum<desiredSum){
end++;
sum += *end;
}
if(sum>desiredSum){
sum -= *start;
start++;
}
count++;
}
cout<<"No sub array found with desired sum"<<endl;
}
int main(){
int arr[5]={2,2,4,1,5};
int * start= arr;
int * end= arr + 1;
int arraySize = sizeof(arr)/sizeof(*arr);
getSubArray(arr,arraySize,start,end,6);
getch();
return 0;
}
o/p:
initial values of start and end pointer elements: 2 2
Final subarray is: 2 4
Very nice solution.
may be we could change last few lines to make it work for- path starting from any node and ending at any node:
if ( leftSubtreeSum > rightSubtreeSum )
return (leftSubtreeSum + node->data) > leftSubtreeSum ? (leftSubtreeSum + node->data) : leftSubtreeSum ;
else
return (rightSubtreeSum + node->data) > rightSubtreeSum ? (rightSubtreeSum + node->data) : rightSubtreeSum ;
one more difference between mutex and semaphore is:
in mutex, only the process which locked the resource can unlock it.
while in semaphore, one process can put lock(decrements value) and other can unlock
e.g.: producer consumer problem
The semaphore type mentioned by JD is known as counting semaphore, where semaphore variable can have value greater than one.
semaphore variable which can have only 0 or 1 is known as binary semaphore.
say ptr1 points to start of linked list,
if(ptr1==null) return false;
node * ptr2;
ptr2=ptr1->next;
if(ptr1->data==number){
ptr1=ptr2;
return true;
}
while(ptr2){
if(ptr2->data==number){
ptr1->next=ptr2->next;
return true;
}
ptr1=ptr2;
ptr2=ptr2->next;
}
return false;
pure virtual function is the function that provides only prototype and not the implementation. This forces derived class to override this function and provide implementation.
e.g. mathclass can have pure vitual function --> mathoperation()
but no implementation for it.
and its derived classes add and subtract can override this mathoperation() function
and can provide implementations.
- sp!de? August 11, 2014