Psycho
BAN USERSimple guy. Loves Programming.
- 0of 0 votes
AnswersState the difference between this two statement.
- Psycho in India
char str[] = "/root//foo/bar" ;
char *str = "/root//foo/bar" ;
Now, you have given an assignment str[in1] = str[in2]
where in1 and in2 both initialize with 0.
In first type of declaration no problem. But in second type of declaration 'Segmentation fault' is there. Why this happens?| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer C - 0of 0 votes
AnswersJust Example : "Given 8 cue balls , one is weighing lesser than other 7. Find that(light weight) ball using just 2 chances on balance weight."
- Psycho in India
How to find a general solution to these kind of question? How to divide this set of balls? Is there any finer method or general formula?| Report Duplicate | Flag | PURGE
Software Engineer / Developer Brain Teasers - 0of 0 votes
AnswersAn unsorted array is given, where there is no specific range in which the elements occur. There is only one duplicate element present in it. Let it is a[i]. It should be within the half of the size of the array from where it appears for first time. i.e. the duplicate element should be within (i+(arr_size/2)), at ith index it appears for 1st time. Find the duplicate element with minimum number comparisons.
- Psycho in United States| Report Duplicate | Flag | PURGE
Microsoft
- 0 Answers C++ Topic : Related to 'Multiset' functionality
Consider this sample piece of code!
multiset<int> iends; multiset<int>::iterator et1; while(et1!=iends.end()){ multiset<int>::iterator te=et1; et1++; iends.erase(te); } while(et1!=iends.end()){ multiset<int>::iterator te=et1; iends.erase(te); et1++; }
What is the difference between this two pieces of code?
- Psycho December 09, 2012| Flag | PURGE
This is greedy approach. It won't lead you to the correct answer.
The idea of posting it is to show the sorting won't lead you to the actual solution.
You can try yoursef with different inputs. The array given here is the apt example. Why the sorting will not work!
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std ;
int getDifference (int *arr, int size) {
int i, start = 0, end = size-1 ;
int sum1 = 0, sum2 = 0;
vector<int> set1, set2 ;
printf ("\n%d\n", size );
while (start <= end) {
if ( sum1 > sum2 ) {
sum2 += arr[end] ;
set2.push_back (arr[end]) ;
end --;
} else {
sum1 += arr[start] ;
set1.push_back (arr[start]) ;
start ++ ;
}
}
vector<int>::iterator it1, it2 ;
printf ( "\nFirst set contains : " ) ;
for ( it1 = set1.begin(); it1 < set1.end() ; it1++ )
printf ( " %d", *it1 ) ;
printf ( "\nSecond set contains : " ) ;
for ( it2 = set2.begin(); it2 < set2.end() ; it2++ )
printf ( " %d", *it2 ) ;
return abs(sum1-sum2) ;
}
int main () {
int ptr[] = {12,4,7,1,6,3,3} ;
int len = sizeof(ptr) / sizeof(ptr[0]) ;
sort (ptr, ptr+len) ;
printf ( "\nMinimum difference is: %d", getDifference (ptr, len) ) ;
getchar ();
return 0;
}
Very similar concept as told by shondik
#include <stdio.h>
#include <limits.h>
int main () {
int arr[] = {20, 5, 10}, i;
int len = sizeof(arr) / sizeof(arr[0]) ;
int maxProfit = INT_MIN, min = 0, max = 0 ;
for ( i = 0 ; i < len ; i++ ) {
if ( arr[i] > arr[min] ) {
if ( (arr[i] - arr[min]) > maxProfit )
maxProfit = arr[i] - arr[min] ;
}
else min = i ;
}
( maxProfit < 0)? printf ("\nNo profit") : printf ( "\nMax Profit = %d", maxProfit) ;
getchar() ;
return 0;
}
int getKthMagicNumber (int k) {
queue<int> q2, q3, q5 ;
int val = 1, minVal ;
if (k <= 0)
return 0 ;
q2.push (2) ;
q3.push (3) ;
q5.push (5) ;
for ( --k ; k > 0 ; -- k ) {
minVal = min (q2.front(), min (q3.front(), q5.front())) ;
if ( minVal == q5.front() ) {
q5.pop () ;
} else {
if ( minVal == q3.front() ) {
q3.pop () ;
} else {
q2.pop () ;
q2.push (minVal*2) ;
}
q3.push (minVal*3) ;
}
q5.push (minVal*5);
}
return minVal ;
}
As per given direction : I think it is the best one!
"There is an O(n) solution based on mathematics, the iterative equation is the following:
f[1]=0;
f[i]=(f[i-1]+k)%i; (i>1)
and f[n]+1 is the your final answer."
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int value;
struct node* next;
}node;
node* getNode (int val) {
node *element ;
element = (node *) malloc (sizeof(node)) ;
element->value = val ;
element->next = NULL ;
return element ;
}
node* addNode (node* head, node *element) {
node *temp = head ;
if ( head == NULL ) {
head = element ;
head->next = head ;
return head ;
}
while (temp->next != head)
temp = temp->next ;
temp->next = element ;
element->next = head ;
return head ;
}
void printList(node *head) {
node *temp = head ;
if (head) {
while ( temp->next != head ) {
printf ( "%d ", temp->value ) ;
temp = temp->next ;
}
printf ( "%d", temp->value ) ;
}
}
node* getKthNode (node *list, int k, int size) {
int oldVal = 0, i, newVal ;
node *temp = NULL, *element ;
for ( i = 2 ; i <= size ; i ++ ) {
newVal = (oldVal + k) % i ;
oldVal = newVal ;
}
newVal ++ ;
temp = list ;
if ( size == 1 )
return list ;
for ( i = 1 ; i < newVal; i++ ) {
list = list->next ;
free (temp) ;
temp = list ;
}
element = list ;
element->next = NULL ;
list = list->next ;
for ( i = newVal+1 ; i < size ; i++ ) {
list = list->next ;
free (temp) ;
list = list->next ;
}
free (list) ;
return element ;
}
int main() {
node *head = NULL, *temp ;
int size, i, val, k;
printf ( "\nEnter the sie :\t" ) ;
scanf ( "%d", &size ) ;
for ( i = 0 ; i < size ; i ++ ) {
printf ( "\nEnter the value :\t" ) ;
scanf ( "%d", &val ) ;
head = addNode (head, getNode(val)) ;
}
printf ( "\n" );
printList(head);
printf ( "\nEnter the k :\t" ) ;
scanf ( "%d", &k ) ;
temp = getKthNode (head, k, size) ;
if ( temp != NULL )
printf ( "\nLast node :\t%d\n", temp->value ) ;
return 0;
}
#include <stdio.h>
void swap (char* ch1, char *ch2) {
char ch = *ch1 ;
*ch1 = *ch2 ;
*ch2 = ch ;
}
void rotate (char *str, int first, int middle, int end) {
int next = middle ;
while ( first != next ) {
swap ( &str[first++], &str[next++] ) ;
if ( next == end )
next = middle ;
else if ( first == middle )
middle = next ;
}
}
int main () {
char arr[] = {'1', '2', '3', '4', '5', 'a', 'b', 'c'} ;
int i ;
rotate (arr, 0, 5, 8) ;
printf ( "\n" ) ;
for ( i = 0; i < 8; i ++ )
printf ( "%c ", arr[i] ) ;
printf ( "\n" ) ;
return 0;
}
Simple implementation as written in std::rotate
- Psycho August 02, 2012Trying to avoid checking conditions and multiplications and divisions!
But one more extra space is wasted!! Tried hard to find some another soln. without wasting the space! But failed any helped will be appreciated.
#include <stdio.h>
#include <stdlib.h>
int next[] = {1,2,3,4,5,6,7,8,9,0};
int* getPlusPlus (int arr[], int len, int* res_len) {
int i, carry = 1, nextnum ;
int *result = (int *) malloc (sizeof(int) * (*res_len=(len+1))) ;
for ( i = len-1, nextnum = i+1 ; i >= 0 ; i -- ) {
if ( arr[i] != 9 ) {
carry = 0 ;
break ;
}
result[nextnum] = next[arr[i]] ;
nextnum = i ;
}
if ( carry )
result[0] = 1 ;
else {
result[nextnum] = next[arr[i]] ;
for ( nextnum = i , i-- ; i >= 0 ; nextnum = i, i -- )
result[nextnum] = arr[i] ;
(*res_len) -- ;
return ++result ;
}
return result ;
}
int main () {
int arr[] = {9, 9, 8, 7};
int i, *result, len ;
result = getPlusPlus (arr, 4, &len) ;
for ( i = 0 ; i < len ; i ++ )
printf ( "%d ", result[i] ) ;
printf ( "\n" ) ;
return 0 ;
}
O(n) complexity.
#include <stdio.h>
void printPattern (char* str, int len) {
int row = (len%3 == 0) ? (len/3) : ((len/3)+1) ;
int i ;
for ( i = 0 ; i < row ; i ++ ) {
printf ( "%c", str[i] ) ;
printf ( " %c", str[i+row] ) ;
if ( (i+(row<<1)) < len )
printf ( " %c", str[i+(row<<1)] ) ;
printf ("\n") ;
}
}
int main () {
char str[] = {'a','b', 'c', 'd', 'e', 'f' , 'g', 'h', 'i', 'j'} ;
printPattern (str, sizeof(str)/sizeof(str[0])) ;
return 0;
}
Code for printing the pascal triangle for nth row. Optimized space and computation.
#include <stdio.h>
#include <stdlib.h>
int main () {
int row , i, limit ;
int *arr ;
printf ("Enter row number :(Starting from 1)\t" );
scanf ( "%d", &row ) ;
if ( row < 0 )
printf ( "\nInvalid Input\n" ) ;
else {
limit = row >> 1 ;
if ( row&1 )
limit ++ ;
arr = (int *) malloc (sizeof(int) * limit) ;
arr[0] = 1 ;
for ( i = 1 ; i < limit ; i ++ )
arr[i] = (arr[i-1] * (row-i)) / i ;
printf ( "\n" ) ;
for ( i = 0 ; i < limit ; i ++ )
printf ( "%d ", arr[i] ) ;
if ( row&1 )
limit -- ;
for ( i = --limit ; i >= 0 ; i -- )
printf ( "%d ", arr[i] ) ;
printf ( "\n" ) ;
free (arr) ;
}
return 0 ;
}
Double linked list as said by Tintin.
#include <stdio.h>
#include <stdlib.h>
/* Structures */
typedef struct node {
int val ;
struct node *prev;
struct node *next ;
}node ;
typedef struct dlist {
int count ;
int midpos ;
node* start ;
node* end ;
node* middle ;
}dlist ;
dlist* init () {
dlist *head ;
head = (dlist *) malloc (sizeof(dlist)) ;
head->count = 0 ;
head->midpos = 0 ;
head->start = NULL ;
head->end = NULL ;
head->middle = NULL ;
return head ;
}
node* createNode (int val) {
node *ele ;
ele = (node *) malloc (sizeof(node)) ;
ele->val = val ;
ele->prev = NULL ;
ele->next = NULL ;
return ele ;
}
/* PUSH Operation */
dlist* push (dlist *head, int val) {
node* ele = createNode (val) ;
head->count ++ ;
if ( head->start == NULL ) {
head->start = ele ;
head->end = ele ;
head->middle = ele ;
} else {
head->end->next = ele ;
ele->prev = head->end ;
head->end = ele ;
if ( (head->count) & 1 )
head->middle = head->middle->next ;
}
return head ;
}
/* Pop Operation */
int pop (dlist **head) {
int val ;
node *temp ;
if ( (*head)->count == 0 ) {
printf ( "\nPopping can be performed!\n" );
return -1 ;
}
val = (*head)->end->val ;
(*head)->count -- ;
if ( (*head)->count == 0 ) {
(*head)->start = NULL ;
(*head)->end = NULL ;
(*head)->middle = NULL ;
return val ;
}
temp = (*head)->end ;
(*head)->end = (*head)->end->prev ;
(*head)->end->next = NULL ;
temp->prev = NULL ;
if ( (((*head)->count) & 1) == 0 )
(*head)->middle = (*head)->middle->prev ;
free ( temp ) ;
return val ;
}
void visit (dlist *head) {
node *temp ;
if ( head->count > 0 ) {
printf ( "\nStarting from bottom :\n" ) ;
for ( temp = head->start ; temp ; temp = temp->next )
printf ( "%d\t", temp->val ) ;
}
}
int menu () {
int opt ;
printf ( "\n1. push" ) ;
printf ( "\n2. pop" ) ;
printf ( "\n3. middle" ) ;
printf ( "\n4. Exit" ) ;
printf ( "\nEnter choice : \t" ) ;
scanf ( "%d", &opt );
if ( opt > 4 || opt < 1 )
return menu() ;
return opt ;
}
/* Get MIDDLE node */
void getMid (dlist *head) {
if ( head->count == 0 )
return ;
printf ( "\nMin element is :\t%d", head->middle->val ) ;
}
int main () {
dlist *head = init() ;
int opt , num ;
do {
opt = menu ();
switch ( opt ) {
case 1 : printf ( "\nEnter val :\t" ) ;
scanf ( "%d", &num );
push (head, num );
visit (head) ;
break ;
case 2 :
if ( (num = pop(&head)) != -1 )
printf ( "\nPopped val is :\t", num );
visit (head) ;
break ;
case 3 :
getMid (head) ;
break ;
}
} while ( opt != 4 ) ;
free ( head ) ;
return 0;
}
This is a O(k logk) solution written in c++
#include <cstdio>
#include <queue>
#include <cstdlib>
#include <climits>
using namespace std ;
#define SIZE 4
int matrix[SIZE][SIZE] = {
{1, 2, 6, 10},
{3, 4, 7, 13},
{5, 9, 11, 14},
{8, 12, 15, 16}
};
typedef struct node {
int x, y ;
int val ;
bool operator < (const node& obj) const {
return (val > obj.val) ;
}
}node ;
int findKthMin (int mat[SIZE][SIZE], int k) {
int count = 0 ;
node n ;
int row, col ;
priority_queue <node> elements ;
n.x = 0 ; n.y = 0 ; n.val = mat[0][0] ;
mat[0][0] = INT_MAX ;
elements.push (n) ;
while (count <= k) {
n = elements.top() ;
elements.pop () ;
printf ( "%d\n", n.val ) ;
count ++ ;
node temp ;
if ( n.x < SIZE-1 ) {
temp.x = n.x + 1 ;
temp.y = n.y ;
if ( mat[temp.x][temp.y] != INT_MAX ) {
temp.val = mat[temp.x][temp.y] ;
mat[temp.x][temp.y] = INT_MAX ;
elements.push (temp) ;
}
}
if ( n.y < SIZE-1 ) {
temp.x = n.x ;
temp.y = n.y + 1 ;
if ( mat[temp.x][temp.y] != INT_MAX ) {
temp.val = mat[temp.x][temp.y] ;
mat[temp.x][temp.y] = INT_MAX ;
elements.push ( temp ) ;
}
}
}
}
int main () {
int k ;
printf ( "\nEnter the k (0 index) :\t" ) ;
scanf ( "%d", &k ) ;
findKthMin (matrix, k) ;
return 0 ;
}
node* deleteNode (node* head, int val ) {
node *ptr1, *ptr2 ;
if ( head == NULL )
return head ;
else if ( head->data == val ) {
head = head->next ;
return head ;
}
ptr1 = head ;
ptr2 = head->next ;
while ( ptr2 ) {
if ( ptr2->data == val ) {
ptr1->next = ptr2->next ;
return head ;
}
ptr1 = ptr2 ;
}
return head ;
}
node* deleteNode (node* head, int val ) {
node *ptr1, *ptr2 ;
if ( head == NULL )
return head ;
else if ( head->data == val ) {
head = head->next ;
return head ;
}
ptr1 = head ;
ptr2 = head->next ;
while ( ptr2 ) {
if ( ptr2->data == val ) {
ptr1->next = ptr2->next ;
return head ;
}
ptr1 = ptr2 ;
}
return head ;
}
RepOliviaJBlack, Consultant at Apkudo
I am Olivia from San Diego. I am working as a checker in the Thom McAn Store company. My strong ...
RepShirleyCWest, Software Engineer at Agilent Technologies
Hello, me Shirley and I from Savage. I am an artist and I love to doing art and I am ...
your solution will not work for this input :
- Psycho August 11, 2012