solxget
BAN USERSimple Solution:
Team[4] = {T1, T2, T3, T4}. i will play index 0 to index 1 and index 2 to index 3 in all 3 games. but my team array have to change in some way. So
First game => Team[4] = {T1, T2, T3, T4}
Second game => Team[4] = {T1, T3, T2, T4}
Third game => Team[4] = {T1, T4, T2, T3}
if you look the above array carefully, you will see that index 1 value is swapped with index 1+loop counter value.
play index 0 to index 1 and index 2 to index 3, you get the correct output.
Algo:
int j = 1;
for(int i = 1 : 3) // 3 is total # of games{
swap(team[i], team[j]);
game<i-1, <team[0], team[1]>> // game should be a multi map
game<i-1, <team[2], team[3]>>
}
any comment is appreciated
- solxget January 11, 2016Simple solution,
The valid input ranges are ,since odd digits only, 0 - 9; 100 - 999, 10 - 99,999. there are the ranges that contribute to the total. the ranges in the middle are even digits. so ignore
to get how many in each range, just subtract lower range from upper range and divide it by 2.
the code is
int getCount(int n){
if(n < 0 || n >100,000) return -1
if(n < 10)
return (n/2);
else if (10 <= n < 1,000)
return ((998 - 100)/2 + 8/2 )
else if (1000 <= n < 100,000)
return ((99,999 - 1,000)/2 + (998 - 100)/2 + 8/2)
}
traverse the array online one time.
int i=1, j=length-2;
int Lsum=array[0], Rsum=array[length-1]
while(i<j-1){
while(Lsum<Rsum && i<j-1){
i++;
Lsum += array[i]
}
while(Lsum>Rsum && i<j-1){
j--
Rsum += array[j]
}
if(Lsum == Rsum && i= j-2)
return i+1;
}
return -1
run QuickSort O(nlogn) then check for even/odd
public void getEven(int array[], int max){
Sort(array, 0, max);
int checker = 1;
int val = array[0];
for(int i = 1; i<=max; i++){
if(array[i] == val){
checker = checker ^1;
}
else{
if(checker == 0)
System.out.println( array[i-1]);
val = array[i];
checker = 1;
}
}
if(checker == 0)
System.out.println( array[max]);
}
private void QuickSort(int array[], int left, int right){
int i = left, j = right;
int tmp;
int pivot = (right-left)/2 + left;
while (i <= j) {
while (array[i] < array[pivot])
i++;
while (array[j] > array[pivot])
j--;
if (i <= j) {
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}
}
if (left < j)
Sort(array, left, j);
if (i < right)
Sort(array, i, right);
}
- solxget August 01, 2015I liked your approach. but the code don't work for 2 reasons.
1. if (head->right == target)
return head->left; // head left is the right value to return but due to recursion when it pops the oldest stat from stack, you will lose the value and end up returning wrong answer (ancestor node). check my code below for this fix.
2. construct this tree and check it. tree input(7,4,10,5,3,8,14,9,13,16) where its post-order traversal out put is (3,5,4,9,8,13,16,14,10,7). try to get the predecessor of 9. your approach will fail. so does mine.
* Your function signature ???
void pred(node *root, node * &pre, node *nd){
if (root == NULL)
return;
if (nd->right != NULL){
pre = nd->right;
return;
}
if (nd->left != NULL){
pre = nd->left;
return;
}
getPostorder(root, NULL, nd, pre);
}
void find_pred_recurse(node *root, node *parent, node *nd, node *&pre){
if (root != NULL){
if (root->right == nd){
pre = root->left;
return;
}
find_pred_recurse(root->left, NULL, nd, pre);
find_pred_recurse(root->right, root->left, nd, pre);
if (root->left == nd){
pre = parent
return;
}
}
}
tested implementation of it. it takes int instead of byte array. its for C++ 11
#include "stdafx.h"
#include<iostream>
#include<thread>
#include<mutex>
#define defaultSize 50
using namespace std;
class CircullarArray{
private:
int *myQueue;
int top;
int tail;
int max;
mutex myMutex;
public:
void init(int size){
if (size < 0)
size = defaultSize;
myQueue = new int[size];
top = -1;
tail = -1;
max = size;
}
bool isFull(){
return ((tail == 0 && top == max - 1) || (tail == top + 1)) ? 1 : 0;
}
bool isEmpty(){
return (tail == -1) ? 1 : 0;
}
void push(int value){
myMutex.lock();
if (isFull())
cout << "Queue is Full!" << endl;
else{
top = (top + 1) % max;
myQueue[top] = value;
}
if (tail == -1)
tail = 0;
myMutex.unlock();
}
void pop(){
myMutex.lock();
int data;
if (isEmpty()){
cout<<"Queus is empty"<<endl;
myMutex.unlock();
return;
}
data = myQueue[tail];
if (tail == top){
top = -1;
tail = -1;
}
else
tail = (tail + 1) % max;
cout << data << endl;
myMutex.unlock();
}
};
int _tmain(int argc, _TCHAR* argv[])
{
CircullarArray *circullarArray = new CircullarArray();
// do staff here
thread thread1(&CircullarArray::pop, circullarArray);
thread thread2(&CircullarArray::pop, circullarArray);
// wait untill the threads finish their task in case the main thread finish early.
thread1.join();
thread2.join();
}
C++ implementation: create a third array iterate over each array and add the smallest element to the new array till the arrays are empty.
#include<iostream>
using namespace std;
class Merge{
public:
void mergeArrays(int *a, int *b, int *c, int as, int bs, int cs, int *final){
int k=0;
int j=0;
int l=0;
for (int i=0; i<(as+bs+cs); i++){
if(j<as && k<bs && l<cs){
if(a[j]<=b[k] && a[j]<=c[l]){
final[i] = a[j];
j++;
}
else if(b[k]<=a[j] && b[k]<=c[l]){
final[i] = b[k];
k++;
}
else if(c[l]<=a[j] && c[l]<=b[k]){
final[i] = c[l];
l++;
}
}
else if(j<as && k<bs){
if(a[j]<=b[k]){
final[i] = a[j];
j++;
}
else {
final[i] = b[k];
k++;
}
}
else if(j<as && l<cs){
if(a[j]<=c[l]){
final[i] = a[j];
j++;
}
else {
final[i] = c[l];
l++;
}
}
else if(k<bs && l<cs){
if(b[k]<=c[l]){
final[i] = b[k];
k++;
}
else {
final[i] = c[l];
l++;
}
}
else if(j<as){
final[i] = a[j];
j++;
}
else if(k<bs){
final[i] = b[k];
k++;
}
else if(l<cs){
final[i] = c[l];
l++;
}
}
}
};
int main(){
int a[] = {1,5,8};
int b[] = {2,6,7};
int c[] = {0,8,9,10};
int final[10];
int *ptra = a;
int *ptrb = b;
int *ptrc = c;
int *ptr = final;
Merge *merge = new Merge();
merge->mergeArrays(ptra,ptrb,ptrc,3,3,4,ptr);
for(int i=0;i<10;i++)
cout<<ptr[i];
cout<<endl;
system("pause");
}
Assuming its for every overlapping array, here is a simple order of N solution.
- solxget February 22, 2017