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
Use dutch national flag algorithm. One thing is that it destroys the original array.
#include <stdio.h>
#include <limits.h>
void swap (int *a, int *b) {
int temp = *a ;
*a = *b ;
*b = temp ;
}
int maxSubSequence (int a[], int size) {
int i, high = size-1, start = 0, mid = 0;
int sum = 0, mid_flag = 0, max_min = INT_MIN;
/* Similar to dutch national flag */
while ( mid < high ) {
if ( a[mid] < 0 ) {
swap (&a[start], &a[mid]);
/* check for maximum of minimum */
if ( max_min < a[start] )
max_min = a[start] ;
start ++ ;
mid ++ ;
} else if ( a[mid] == 0 ) {
mid_flag = 1 ; /* denotes there is atleast one zero */
mid ++ ;
}
else {
swap (&a[mid], &a[high]) ;
sum += a[high] ; /* adds the sum */
high -- ;
}
}
if ( sum )
return sum ;
if ( mid_flag )
return 0 ;
return max_min ; // returns the maximum of all negative numbers
}
int main () {
int a[] = {-4, -9, 0, -3, -1, -2, 0, -2, -8} ;
int size = sizeof(a) / sizeof(a[0]) ;
printf ( "\nMaximum sum sub-sequence : %d\n", maxSubSequence(a,size)) ;
return 0 ;
}
Circular Kadane.
#include <stdio.h>
#include <stdlib.h>
/* Circular kadane with limited size */
int maxSum ( int arr[], int size ) {
int i, tSize = (size<<1) - 1 ;
int maxsum, sumsofar, ti ;
int *dup_arr = (int *) malloc (sizeof(int)*tSize) ;
if ( size == 0 )
return 0 ;
for ( i = 0 ; i < size ; i ++ )
dup_arr[i] = arr[i] ;
for ( ; i < tSize ; i ++ )
dup_arr[i] = arr[i-size] ;
maxsum = dup_arr[0];
sumsofar = dup_arr[0] ;
ti = 0 ;
for ( i = 1 ; i < tSize ; i ++ ) {
//printf ( "\nBefore op : sumsofar = %d, maxsum = %d, i = %d, ti = %d", sumsofar, maxsum, i, ti ) ;
/* Check for resetting the lower limit */
if ( sumsofar <= 0 ) {
sumsofar = 0 ;
ti = i + 1;
}
/* Check for the array size : calculation should be with in array size*/
if ( i-ti >= size ) {
//printf ( "\nsize exceeded.");
ti = i ;
sumsofar = 0 ;
}
sumsofar += dup_arr[i] ;
/* renew the maximum sum */
if ( sumsofar > maxsum )
maxsum = sumsofar ;
}
free (dup_arr) ;
return maxsum ;
}
int main () {
int arr[] = {1,1,1,1,1,1,1} ;
printf ( "\nMax sum is : %d", maxSum (arr, (sizeof(arr)/sizeof(arr[0])) ) ) ;
return 0 ;
}
size is 16
I am trying so see what happens by commenting different parts of the question.
When it is empty class. commenting virtual destructor and 2 ints and a char. it gives 1. (Its simple)
now including the char in the class, rest of the part is same. Then it gives 1. (Again justified)
But if we include the virtual destructor then size becomes 8. If that because of padding ?? or anything else!! Size due to virtual destructor is 4. 2 ints (4*2).
But size of char suddenly changes from 1 to 4?? Is it for padding. I think so. Correct me if I am wrong.
Manan is correct. Simply codes what Manan does
#include <stdio.h>
#include <ctype.h>
int main () {
char str[] = "PST456DA85M2A!!23++46" ;
int size = sizeof (str), i = 0, pDigit = 0, cur = 0, sum = 0 ;
while ( i < size ) {
if ( isdigit(str[i]) )
cur = (cur*10) + (str[i]-'0') ;
else {
if ( cur ) {
printf ("\nNumber is : %d", cur ) ;
sum += cur ;
cur = 0;
}
}
i ++ ;
}
printf ( "\nSum is : %d", sum ) ;
getchar () ;
return 0;
}
Following the steps of @sqw with slight modifications
#include <cstdio>
#include <cstdlib>
#include <stack>
using namespace std ;
typedef struct node {
int val ;
struct node *left ;
struct node *right ;
}node ;
node* getNode (int value) {
node *element ;
element = (node *) malloc (sizeof(node)) ;
element->val = value ;
element->left = NULL ;
element->right = NULL ;
return element ;
}
void bstSort (node* root1, node* root2) {
stack<node*> s1, s2 ;
while (true) {
while (root1) {
s1.push (root1) ;
root1 = root1->left ;
}
while ( root2 ) {
s2.push (root2) ;
root2 = root2->left ;
}
if ( s1.empty() && s2.empty() )
break ;
if ( !s1.empty() && (s2.empty() || s1.top()->val < s2.top()->val)) {
root1 = s1.top () ;
printf ( "%d ", s1.top()->val ) ;
s1.pop () ;
root1 = root1->right ;
} else {
root2 = s2.top () ;
printf ( "%d ", s2.top()->val ) ;
s2.pop () ;
root2 = root2->right ;
}
}
printf ( "\n" ) ;
}
int main () {
node *root1, *root2 ;
root1 = getNode (20) ;
root1->left = getNode (15) ;
root1->right = getNode (25) ;
root1->left->left = getNode (9) ;
root1->left->right = getNode (18) ;
root1->right->left = getNode (22) ;
root1->right->right = getNode (30) ;
root1->left->right->left = getNode (17) ;
root1->right->left->right = getNode (24) ;
root2 = getNode (10) ;
root2->left = getNode (5) ;
root2->right = getNode (20) ;
root2->left->left = getNode (1) ;
root2->left->right = getNode (8) ;
root2->left->right->left = getNode (7) ;
bstSort (root2, root1);
return 0 ;
}
Take this example.
"I am an ordinary student"
Length = 24. Page width = 26.
Words = 5
extra_space = 6
space_in_bet_words = 4
each_word_spacing = 6/4 = 1
Extra_width = 6%4 = 2
So the sentence after alignment :
"I<s><s>am<s>an<s>ordinary<s><s>student"
<s> represents space.
Assuming page width >= lenth of the sentence
1. Calculate the number of words and total letters.
2. if total_words != 1 then
2.1 Extra_width = (page width - total_letter_count)
2.2 space_in_bet_words = total_wrods - 1
2.3 each_word_spacing = Extra_width / space_in_bet_words
2.4 Extra_width = Extra_width % space_in_bet_words
2.5 fill the extra width by putting extra spaces not in between consecutive word rather than first spacing, last spacing, second spacing, second last spacing etc like that.
3. else
3.a align the word in the middle. Divide the extra spaces by half. If not divisible by 2, Then add the extra space in the front (by design). So the style would be more like (<spaces(may be extra one)> <Word> <Spaces>)
Minimum number of memory access with 0(n)
Put a pointer on head and one pointer in tail.
while ( head != tail ) {
If head == 0 then head go ahead. (increment)
else if tail == 1 then tail move to previous node. (decrement)
else if ( head == 1 && tail == 0 ) {
swap the values of head and tail
move head forward (increment)
if ( head == tail )
break ;
move tail to previous node (decrement)
}
}
I think this will be most space efficient and time also.
Pick each word.
Sort the word by letters in any chosen order.
If it is not present in the trie - make an entry other wise print the actual word.
Time taken = Total word * ((sort o(length)) + (trie make_entry( O(n))))
Nice one. I think you have to check your Node structure.
Your each node contains "last" node.
And according to question -> "another pointer "child" that may point to the head of another doubly linked list of same type".
Otherwise your solution is really good. :)
Function signature says that argument should be 'float'
But converting float to string will face the storage problem.
In my computer .434 detects as .434082
So, to be specific a precision is required as argument. Otherwise we take the input as char array and returns it as char array to remove the storage problem.
Another thing is that if .00053 is the input then output should be the same.
If 1.00059 is the input then output should be the 1.00059. Because 0 in the most significant digit considered is not considered as significant.
I dint compile it. But logic is correct.
If a node has child
-> push the next element to stack checking whether the next is null or not.
-> move to the child after manipulating the prev and next pointers.
else
->move to next pointer if next is not null
->otherwise
->->check whether there is an element in the top of the stack. If present then pop and manipulate the prev and next pointers and assigned the the popped element for next iteration.
->->else break from the loop.
Hope this gonna work!
typedef struct node {
int value ;
struct node *prev ;
struct node *next ;
struct node *child ;
}node;
node* flattenTree (node* head) {
node *cur = head ;
stack <node*> s ;
while ( cur != null ) {
if ( hasChild (cur) ) {
if ( cur->next != null )
s.push (cur->next) ;
node* child = cur->child ;
cur->child = null ;
cur->next = child ;
child->prev = cur ;
cur = child ;
} else {
if ( cur->next != null )
cur = cur->next ;
else if ( !s.empty() ) {
node* popped = s.top() ;
s.pop () ;
cur->next = popped ;
popped->left = cur ;
cur = popped ;
} else break ;
}
}
return head ;
}
Shorest path and prints the path from backward
#include <cstdio>
#include <queue>
using namespace std ;
#define SIZE 6
typedef struct point {
int x ;
int y ;
int length ;
}point ;
typedef struct path {
int x;
int y;
bool visited ;
}path ;
static path visited[SIZE][SIZE] ;
int matrix[SIZE][SIZE] = {
{1,1,0,1,0,0},
{0,1,0,1,1,1},
{1,1,1,1,0,1},
{0,1,1,1,0,1},
{0,0,1,0,0,1},
{0,0,1,1,0,1}
};
bool isValidMove (int x, int y) {
if ( x >=0 && x < SIZE && y >= 0 && y < SIZE ){
if ( (matrix[x][y] == 1) && !(visited[x][y].visited ) )
return true ;
}
return false ;
}
void findPath () {
int x = visited[SIZE-1][SIZE-1].x , y = visited[SIZE-1][SIZE-1].y ;
while (true) {
printf ( "\nx = %d, y = %d", x , y ) ;
if ( x == 0 && y == 0 )
break ;
int temp_x = visited[x][y].x ;
int temp_y = visited[x][y].y ;
x = temp_x ;
y = temp_y ;
}
}
int shortestPathLengthBFS () {
queue<point> q ;
int x = 0, y = 0, pLength = 0 ;
point p ;
for ( int i = 0 ; i < SIZE ; i ++ ) {
for ( int j = 0 ; j < SIZE ;j ++ ) {
visited[i][j].visited = false ;
visited[i][j].x = -1 ;
visited[i][j].y = -1 ;
}
}
p.x = x ;
p.y = y ;
p.length = pLength ;
// printf ( "x = %d, y = %d, length = %d", x, y, pLength );
visited[p.x][p.y].visited = true ;
q.push(p);
while (!q.empty()) {
p = q.front() ;
q.pop () ;
pLength = p.length ;
x = p.x ;
y = p.y ;
// printf ( "\nx = %d, y = %d, length = %d", x, y, pLength );
if ( p.x == SIZE-1 && p.y == SIZE-1 ) {
printf ( "\n\nPath is : from (x = %d , y = %d)\n\n", x, y ) ;
findPath () ;
return p.length ;
}
if ( isValidMove(x-1,y) ) {
p.x = x - 1 ;
p.y = y ;
p.length = pLength + 1 ;
visited[p.x][p.y].visited = true ;
visited[p.x][p.y].x = x ;
visited[p.x][p.y].y = y ;
// printf ("\nup" ) ;
q.push (p) ;
}
if ( isValidMove(x,y+1) ) {
p.x = x ;
p.y = y + 1 ;
p.length = pLength + 1 ;
visited[p.x][p.y].visited = true ;
visited[p.x][p.y].x = x ;
visited[p.x][p.y].y = y ;
// printf ("\nright" ) ;
q.push (p) ;
}
if ( isValidMove (x,y-1) ) {
p.x = x;
p.y = y - 1 ;
p.length = pLength + 1 ;
visited[p.x][p.y].visited = true ;
visited[p.x][p.y].x = x ;
visited[p.x][p.y].y = y ;
// printf ("\nleft" ) ;
q.push (p) ;
}
if ( isValidMove(x+1,y) ) {
p.x = x + 1 ;
p.y = y ;
p.length = pLength + 1 ;
visited[p.x][p.y].visited = true ;
visited[p.x][p.y].x = x ;
visited[p.x][p.y].y = y ;
// printf ("\ndown" ) ;
q.push (p) ;
}
}
return -1 ;
}
int main () {
printf ("\n%d\n", shortestPathLengthBFS() );
}
As all the nodes are at equi-distance a simple bfs will do the job. There is no need of Dijkstra.
#include <cstdio>
#include <queue>
using namespace std ;
#define SIZE 6
typedef struct point {
int x ;
int y ;
int length ;
}point ;
static int visited[SIZE][SIZE] ;
int matrix[SIZE][SIZE] = {
{1,1,0,1,0,0},
{0,1,0,1,1,1},
{1,1,1,1,0,1},
{0,1,1,1,0,1},
{0,0,1,0,0,1},
{0,0,1,1,0,1}
};
bool isValidMove (int x, int y) {
if ( x >=0 && x < SIZE && y >= 0 && y < SIZE ){
if ( (matrix[x][y] == 1) && (visited[x][y] != 1) )
return true ;
}
return false ;
}
int shortestPathLengthBFS () {
queue<point> q ;
int x = 0, y = 0, pLength = 0;
point p ;
p.x = x ;
p.y = y ;
p.length = pLength ;
// printf ( "x = %d, y = %d, length = %d", x, y, pLength );
visited[p.x][p.y] = 1 ;
q.push(p);
while (!q.empty()) {
p = q.front() ;
q.pop () ;
pLength = p.length ;
x = p.x ;
y = p.y ;
// printf ( "\nx = %d, y = %d, length = %d", x, y, pLength );
if ( p.x == SIZE-1 && p.y == SIZE-1 )
return p.length ;
if ( isValidMove(x-1,y) ) {
p.x = x - 1 ;
p.y = y ;
p.length = pLength + 1 ;
visited[p.x][p.y] = 1 ;
// printf ("\nup" ) ;
q.push (p) ;
}
if ( isValidMove(x,y+1) ) {
p.x = x ;
p.y = y + 1 ;
p.length = pLength + 1 ;
visited[p.x][p.y] = 1 ;
// printf ("\nright" ) ;
q.push (p) ;
}
if ( isValidMove (x,y-1) ) {
p.x = x;
p.y = y - 1 ;
p.length = pLength + 1 ;
visited[p.x][p.y] = 1 ;
// printf ("\nleft" ) ;
q.push (p) ;
}
if ( isValidMove(x+1,y) ) {
p.x = x + 1 ;
p.y = y ;
p.length = pLength + 1 ;
visited[p.x][p.y] = 1 ;
// printf ("\ndown" ) ;
q.push (p) ;
}
}
return -1 ;
}
int main () {
printf ("\n%d\n", shortestPathLengthBFS() );
}
This is almost same as what @LoocalVinci's logic is.
int checkEachNodeOneChild (int* arr, int size) {
int i, a, b ;
for ( i = 0 ; i < size-2 ; i ++ ) {
a = arr[i] - arr[size-1] ;
b = arr[i] - arr[i+1] ;
if ( a*b < 0 )
return 0 ;
if ( a*b == 0 ) {
if ( a == 0 ) {
// This means root has all its child in right subtree
if ( b > 0 )
return 0 ;
}
}
}
return 1 ;
}
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 ...
At max 2n operation.
- Psycho August 29, 2012