CareerCup

???

Can somebody explain the recursion?? Why it's working?

@I am not here to get votes on my answer. It's a public forum , where people contribute and get their doubts cleared. A healthy discussion is always a good thing. But This is not the way. Tail recursion is the first thing I suggested please see my post. But i didn't claimed O(1) space complexity.

Mathematics is wrong. But correct code!

+1

It's not mirror image.

When we merge two lists , we compare the smallest not inserted element of the the two list two decide which will be the new element of the new list. This is done till one gets empty. In this case empty for circular list would mean when iterator becomes equal to head again.

Push every thing in stack. And pop and swap one by one. Another is recursive approach which uses internal stack. I doubt this can be solved without using extra memory. Recursion also uses stack.

A recursive function

void rotate(int a[], int n, int *left,int right)
{
  if(right==n)
    return ;
  rotate(a,n,left,right+1);
 swap(a[*left],a[right]);
 (*left)++;
 return;

}

Call this as
int left =0,right =0;

rotate(a,n,&left,right);

Corrected!
See this
codepad.org/tKbYOpCE

I don't think they are asking answer for comparison sort. Option doesn't make sense in that case. Even worst of comparison sorts in worst of cases will give less number of comparison than the given option

Well I don't have the book.
Think in this way
My buckets will be link lists in an array say,
buck[10]
when I need to push a digit say i, in its corresponding bucket
the bucket will be buck[i]. What comparison I did?? ith bucket is mapped to ith location.

You don't need to compare with each bucket. 1 will go in bucket 1 , 2 will go in bucket 2 .....

Number of buckets will be 10.

counting +radix sort
answer is 40
First MSB will be sorted using counting or bucket sort (both are stable sorts) total number of buckets will be 10 (decimal base 10) so 10 comparisons. similarly for other digit positions.
Total comparison 4*10 =40

Inplace (Working code!)

ideone.com/u1oS4

#include<stdio.h>
 
#define n 3
void printm(int (*a)[n])
{
int i,j;
for(i=0; i<n; i++)
{
for(j=0;j<n;j++)
printf("%d\t",a[i][j]);
printf("\n"); 
}
}
void rotate(int (*a)[n])
{
 int i,j,temp,l;
 for(i=0; i<n/2;i++)
  {
    l=n-2*i; 
    for(j=0;j<l-1; j++)
     {
       temp = a[i+j][i];
       a[i+j][i] = a[n-1-i][i+j];
       a[n-1-i][i+j] = a[n-1-i-j][n-1-i];   
       a[n-1-i-j][n-1-i] = a[i][n-1-i-j];
       a[i][n-1-i-j] = temp; 
     }
  }
 
}
 
int main()
{
int a[][3]={{1,2,3},{4,5,6},{7,8,9}};
printm(a);
 
printf("\n\n\nAfter Rotation\n");
rotate(a);
printm(a);
return 0;

}

Breaking in sub problems can give better run time. To decide how to break, we need DP

Have one more pass to store the number as they were in original array. This would be something like this.

if(ceil(a[i])==floor(a[i]))
    a[i]= int(a[i]);

This won't work if there are numbers like 2.0 , 3.0 in the original array.
You can do one more thing. Sort the number by any method . For all comparison do something like this

if((float)a >float(b)
..

Make all other operations (swapping) with original values

Nklog(N) not Nklog(NK) in this case
as lists will be atleast of k size

For binary tree This is true. But BST has some properties of it's own and its not just any binary tree. For BST we can build with either post or pre order alone. But not with inorder alone

This is in place Array transpose.
Working code!

http://codepad.org/GzIUMLjy

#include <stdio.h>
 
int get_index(int idx, int N) {
    return (idx % 3) * N + (idx / 3);
}
 
void swap(int *a,int *b)
{
        int t=*a;
        *a=*b;
        *b=t;
}
 
void transform_array2(int *s, int len) {
    int N = len / 3,i;
    for(i = 0; i < len; i++) {
        int new_idx = get_index(i, N);
        while(new_idx < i) {
            new_idx = get_index(new_idx, N);
        }
        printf("i: %d; new_idx: %d\n", i, new_idx);
        swap(&s[i], &s[new_idx]);
    }
    for(i = 0; i < len; i++) {
        printf("%d ", s[i]);
    }
    printf("\n");
}
 
int main()
{
        int arr[]={1,2,3,4,5,6,7,8,9,10,11,12};
        transform_array2(arr,12);
        return 0;

}

Good!

Few points:

This is sufficient!
static int r[]={0,0,1,1,1};
static int c[]={-1,1,-1,0,1},k;
in total five adjacent points. This is because,
outer loop for countImage ensures for any point with x coordinate i , ( (0..i-1), j) have been already visited.j can have any value here

Secondly why are vectors r anc c static??

Third:

You are modifying the original input . You can use an auxiliary array for marking visited. And use stacks for DFS you can avoid recursion.

This can be done non recursively

for(i=0 i<n; i++)
for(j=0; j<n ; j++)
if(a[i][j])
{
count ++; //one image found
point tmp = point(i,j);
while(!queue_empty(&s))
{

//enqueue all previously not visited neighbors of tmp (which are 1) in the queue
tmp = dequeu(s);

}
// This image finished now search other
}

Correct!
Just build the tree!

Got it!
Never mind!

Make a binary tree with a node having an extra field for counting number of elements
in it's right sub tree.
Now insertion will be like this:
Say root is (Xr,Yr) and element to be inserted is x,y
if x>Xr and y>yr , (x,y) will go to right sub tree and count for root node will be incremented
In all other cases coming node will be inserted in left subtree

Traverse the tree too get the sum of count

logic??

@niraj: Recursion internally uses stack to function so this is again not avoiding memory constraint!

I missed a return after the success check (in case where sucess has already been achieved )

search for extreme set of points on the three axes that is with minimum and maximum x coordinate andd similarly for other two axes. (can be multiple points on a plane)

These points will be in 6 different planes each having multiple points ( at faces of cuboid)

Now same problem reduces to finding minimum points in a 2d plane which will enclose all the points in that plane . Now again do similar step that is forming pair of extreme along x and y co-ordinate . These points will be included . For left over points they may or may not be included . They will be included if they don't lie in the existing figure .
This can be checked as follows.

Consider A,B,C,D points (three are already included so check for 4th one if this is already in the figure or not)
D is within ABC if
Area (ABC)= Area(ABD)+AREA(BCD) +AREA(ACD)
If true no need to include . Otherwise include
This can be extended for any number of points

gcc test.c &; ls >txt &; uname -a;

This will compile test.c in background and ''ls" will run while with it's
output being redirected to txt so again everything in background on screen
you will get output of third command (program)

This should do I guess!

recurse(&success_flag, args....)
{
if(!(*success_flag))
recurse(sucess_flag, args...);
if(success)
*success_flag = 1;
}

@Selme... What is not true?? Better try the code and see for your self!

O(n)

1. Make all zeros -1
2. change array such that a[i] = a[i] + a[i-1] (cumulative sum)
3.Now look for two location i,j such that a[i]=a[j] and choose
such that j-i is maximum possible. Same numbers at two location means cumulative sum of numbers between them is zero. For largest such sub array this range should be maximum . This step can be done by hashing with key as number and storing first and last occurrence of that number

But there can be one more possibility, i.e cumulative sum itself zero up to some point (a[k] =0). Choose maximum k , i.e farthest location where 0 is stored

Return MAX( (j-i) , k)

If for SISC than no written just interview
for SEL there will be written for under 3 years of experience .It will focus on
basic knowledge of c

There are some very good examples in geeksforgeeks.org archives .
Search under dynamic programming tag

I have considered that case!
When the numbers of negative numbers are odd you will discard the number with minimum absolute value and use max instead

@incognitosj

I think we need to do some more modification to above approach!

1. We need to maintain number of negative nodes inserted.
2. We need to keep track of greatest positive number from those inserted or deleted from the heap at any point of time.
say max.

In the final heap if number of -ve numbers is odd use the max from above along with other two positive nuumber
else you have the solution.

Note: Original numbers will be inserted in the heap with proper sign just comparison while inserting will be based on absolute values

In the above example:
Number of odd numbers in final heap is odd so we will discard the negative number and calculate product using other two and max (42)

Please comment if any error!

This is the right approach!

Just when lengths are equal you need to check for both first and last nodes!

Consider a tree structure for the directory.

Read the input and while input string is not over do following for
each element after 'cd '


switch(ch)
current directory will be root.
when command is
case 1. cd a

two possibilities
a) There is a child directory a, you need to go to this node
b) No child directory called a stop and print error

case 2 cd .

Do nothing. '.' means current directory

case 3 cd ..

Go to parent

@log... Thanks for pin pointing. Sorting on the basis of rank can give one solution. But ranking itself will be O(n2)

You will get linker error!


Compiler only looked for names for binding not the type so int *a was binded to int a[] (basically that means both a have same address). If you try to print '&a' in file 1 and '&a' in file 2 you will get same address. so both the pointers are at same location.
So basically binding is some what like this
&a = &a; instead of a = a

Although the pointer addresses are same the content at the addresses ('a ' not *a )) is not. In first case it was the addresses of first element of array (const int*) , in second case it is NULL. Why it is happening is something , that can be attributed solely to compiler architecture . Here what is happening is , a const int* cannot be converted into int* so the compiler decides to Make it NIL.

This will work;
file 1: char* a =&('a')
fil2 2; extern int *a;
print *a; //off course with %c to avoid memory infringement
because char* can be type casted to int*

In your example even access to *a is in valid as it is essentially Null.

My final conclusion is may be on different compiler the results will be diffrent as it is clearly upto compiler how to handle.

This is O(n)

I just need to make list of element greater and less than root for both and then compare corresponding lists for equality!

I got this!
Thanks for pointing

Sorry I mean j can be b/w 0 and max-min
so j+min is between 0 and max

Please look at the solution again! Either I don't understand you or you missed something. Can you explain how I have assumed that?? I didn't intended
so please pinpoint it.

I didn't understand what you mean! My only assumption was that they are of same sign. Can you
be more clear??

Please look again j can be between min and max-min
so j+min is between min to max, where min and max are minimum and maximum in the array

@eugene: I agree, but I specified them. And I guess interviewer was looking for this approach as well as
otherwise it seems is not possible to come up with a solution for this!

Sorry I missed one condition!
After forming the heap once, If incoming element is larger than root replace!

In your example! Below is the heap formation and you need to compare only absolute values . -100 is converted to 100

------------
       12
100       42
-----------
       42
100     89
------------
       89
100       103
    
----------

O(n) time O(1) Space

1. Find max and min
2. Traverse the array and for each a[i] change sign of a[[a[i]- min]]

Each time a element is found sign of location corresponding to that
(mapped to a[i]-min) changes sign. So same sign after this traversal means
even number of occurrences, different sign means odd no. of occurrences

3.Finally traverse the array from i =0 to i = max-min
and look for -ve element at location 'j'.
4. Return j+min

This algorithm will work only if all elements are of same sign initially

No need to the element to be in any range!

See my comment below for the approach!