CareerCup

The Qs and output doesn't match.The Qs and output doesn't match.

Its implementation should be simple.

Take two matrices, current and next with current being the current population state and next being the next generation.
a. At any point, traverse the current matrix following the rules given by the "Conway's game of life " populate the next matrix.
b. after traversal the current matrix becomes obsolete and the next matrix becomes current. Initialise next to all zeros.
c. Continue till you reach a state where current is same as next.

I thought the nos. are separated by a space. If thy are continuously arranged, then this approach doesn't work.

In that case:
We would need to :
a. Make a guess on no. of digits in the starting no.
b. Start traversing the string with your assumption. If the current no. is x, then at any point next no. should b either x+1 or x+2(in case the next no. is missing and counter is 0). If say it is x+2 and counter is 0, increment counter. If counter is already 1 then discard this digit guess , go to step a and assume digit count one greater than previous.
c. If you are able to reach the last of string successfully for a particular digit count, print x+1 for the point where we incremented the counter. If for no digit count <= n/2 (length of string are we able to find a successful digit count, then either return the number before first or after last)

Code :

int getMissing(String input) {
	int n = input.length();	
	int missing = -1;

	for(int digitCount = 1; digitCount <= n/2; digitCount++) {
		int count = 0;
		int x = Integer.parseInt(input.substring(digitCount));
		int start = x;
		missing = start-100;
		int i = digitCount;
		
		while(i < n) {
			String next = Integer.toString(x+1);
			if(input.substring(i, next.length()+i).equals(next)) {
				x++;
				i += next.length();
			}
			else {
				String nextNext = Integer.toString(x+2);
				if(input.substring(i, nextNext.length()+i).equals(nextNext)) {
					if(count == 0) {
						count++;
						missing = x+1;
						x += 2;
						i += nextNext.length();
					}
					else 
						break;
				}
				else 
					break;
			}
		}

		if(i == n) {
			if(missing == start-100)
				return start-1;
			else
				return missing;
		}
	}

	//Assuming NOT_POSSIBLE is a value to indicate that no missing value possible
	return NOT_POSSIBLE;
}

Code :

int getMissing(BufferedReader br) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	int sum = 0;
	int count = 1;
	int min = Integer.parseInt(st.nextToken());
	int max = Integer.parseInt(st.nextToken());
	sum += min;
	count++;
	
	while(st.hasMoreTokens()) {
		int num = Integer.parseInt(st.nextToken());
		sum += num;
		if(min > num)	
			min = num;
		else if(max < num)
			max = num;
		count++;
	}

	//Using min*n+(N-1)(N)/2 == sum
	int missing = min*count + (count-1)*count/2 - sum;

	return missing;
}

Can we use stacks?

Keep an ascii char array.

Code :

boolean isAnagram(String str1, String str2) {
	char[] map = new char[256];

	int length1 = str1.length();
	int length2 = str2.length;

	for(int i = 0; i < length1; ++i) {
		char ch = str1.charAt(i);
		map[ch-0]++;
	}
	for(int i = 0; i < length2; ++i) {
		char ch = str2.length();
		map[ch-0]--;
	}

	boolean anagram = true;
	for(int i = 0; i < 256; ++i) {
		if(map[i] != 0) {
			anagram = false;
			break;
		}
	}

	return isAnagram;
}

I recently gave google interview, was not able to code in one round, all othr round went good.
Wht r my chances?

@Eugene..

The answer given in geeksforgeeks can be extended to a 2D (nXm) case.
Algo :
a. Substitute 0 by -1
b. For each columnwise, nC2 pairs exist.
The sum for each pair calculation will take O(n^2) and will vary from -n to +n (if we consider paid 1, n) at max.
c. As we traverse the matrix along a row, the sum can at max vary from -m*n to +m*n. So maintaining an array from -m*n to m*n and applying the method in geeksforgeeks the solution can be arrived at O(n^2*m).

What if we take array from -mn to mn

Well for each character in string.. the loop goes from its index to end of str... so basically the complexity is 0(n)*n = O(n^2) assuming the function isWord takes contant time.

What is the length of resultant array ?

Algo... Time complexity O(N+M)
say matrix dim N, M.
start with i = 0, j = M-1.
Say no. to b searched is x.
then if(Mat[i][j] < x)
i++;
if(Mat[i][j] > x)
j--;
else {
printf("Element found");
return;
}
Keep on doing this till i == N or j < 0.

void search_element(int Mat[][], int N, int M, int x) {
int i = 0, j = M-1;
while(i > N && j >= 0) {
if(Mat[i][j] > x) 
j--;
else if(Mat[i][j] < x) 
i++;
else { 
printf("Element found, i = %d, j = %d\n", i, j);
return;
}
}

printf("Not Found\n");
}

#include<stdio.h>

#define N 10

void heapify(int arr[], int ind) {
	if(ind <= N) {
		int smaller = ind;
		int left = ind<<1;
		int right = left+1;
		if(left <= N && arr[left] < arr[smaller])
			smaller = left;
		if(right <= N && arr[right] < arr[smaller]) 
			smaller = right;
		if(smaller != ind) {
			int temp = arr[ind];
			arr[ind] = arr[smaller];
			arr[smaller] = temp;
			heapify(arr, smaller);
		}
	}
}
	

main() {
	int count = 0, i;
	int arr[N+1];

	while(count < 50) {
		int num;
		scanf("%d", &num);
		count++;

		if(count > N) {
			if(num > arr[1]) {
				arr[1] = num;
				heapify(arr, 1);
			}

			for(i = 1; i <= N; ++i) {
				printf("%3d", arr[i]);
			}
			printf("\n");
		}
		else
			arr[count] = num;
	}

	return 0;
}

Something similar to 25 horses . Minimum number of steps to find to 3

If you are already checking for sum==N, whats the need of first 2 checks?

Here...
h t t p : / / flashing-thoughts.blogspot.in/2010/06/problem-array-of-size-n-contains.html

Shouldn't the permutations for abc be {abc, acb, bac, bca, cab, cba} ?

As the search space is exhaustive we can use backtracking.
At each step the next possible option is (x-1, y+1), (x, y+1), (x+1, y+1)
modify this to return the distance till bottom as well and return the max of these three along with the current pt. to get the max path.

Use backtracking with a 3D solution matrix.
Terminating condition :
if(x == 0 || x == n-1 || y == 0 || y == n-1 || z== 0 || z== n-1)
At this pt. print the sol matrix and backtrack to find other possible paths.

@Sanjeev.. Please explain.. why.. :P
Know about the code before commenting... Its mod Dutch Flag Algo... Thanks. @Neo.

Please run the code to verify urself...
2 -1 0 1
0 -1 2 1
-1 0 2 1

Its working for every test case. :)

Please verify the solution before reducing votes. It works absolutely fine. :)

The answer is incorrect as it doesnt reparse the taile element swapped.

Let us have two arrays arr_zero and arr_one of length K.
Now arr_zero[0] = 0, arr_one[0] = 1 ( i.e. 1)
arr_zero[1] = arr_one[0] = 1, arr_one[1] = arr_zero[0]+arr_one[0] = 1 (i.e. 10, 11)
arr_zero[2] = arr_one[1], arr_one[2] = arr_zero[1] + arr_one[1] (i.e. 110, 101, 111)
and so on...
valid string count for length K = arr_zero[K-1] + arr_one[K-1]

Code :

#include <stdio.h>


int  main()
{
	int K;
	unsigned int count = 0;
	
	scanf("%d", &K);

	if(K > 0)
	{
		unsigned int i = 1;
		unsigned int zero_count = 0, one_count = 1;
	
		while(i < K)
		{
			unsigned int temp = zero_count;
			zero_count = one_count;
			one_count += temp;
			i++;
		}

		count = zero_count+one_count;

	}
	
	printf("%u", count);

	return 0;
}

For the explanation, using int dist = (k % n)-1 I come to the node just before the one which we need to delete.

Can you explain how can one avoiding traversing till kth node for every deletion?

Hi,

The right way to do it : Space complexity : O(1), Time Complexity : O(n)

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define CARD_COUNT 52

void swap(int *card_arr, int index1, int index2)
{
	if(index1 != index2)
	{
		card_arr[index1] = card_arr[index1] + card_arr[index2];
		card_arr[index2] = card_arr[index1] - card_arr[index2];
		card_arr[index1] = card_arr[index1] - card_arr[index2];
	}
}

int main(void)
{
	int i;

	int card_arr[CARD_COUNT] = {0};

	for(i = 0; i < CARD_COUNT; i++)
		card_arr[i] = i+1;
	
	for(i = 0; i < CARD_COUNT; i++)
	{
		int index = rand() % (CARD_COUNT - i) + i;
		swap( card_arr, i, index);
	}

	getch();
}

Source code : Time complexity = O(n), Space complexity = O(1)

void find_max_sum(int *arr, int n, int *start, int *end, int *sum)
{
	int i, temp_sum, temp_start, temp_end; 

	*end = *start = temp_start = temp_end = -1;
	*sum = temp_sum = 0;

	for(i = 0; i < n; i++)
	{
		temp_sum += arr[i];

		if(temp_sum < 0)
		{
			temp_sum = 0;
			temp_start = temp_end = -1;
		}
		else if(temp_sum > 0)
		{
			if(temp_start == -1)
				temp_start = i;
			temp_end = i;
		}

		if(temp_sum > *sum)
		{
			*start = temp_start;
			*end = temp_end;
			*sum = temp_sum;
		}
	}
}

The size of pointers is machine/architecture dependent.
x86 has 4byte pointers, amd64 has 8 byte pointers

I think initially all thread other than the first be suspended, as a thread enters the method to read word it suspends the previous thread and while it exits it resumes the next thread :

Keep an array of the threads[8] = {threadId1, threadId2, ..., threadId8};

Thread.suspend(threads[1]);
Thread.suspend(threads[2]);
...
Thread.suspend(threads[7]);


Sychronize void readWord(int index)
{
if(index == 0)
Thread.suspend(threads[7]);
else
Thread.suspend(threads[index-1]);

// procedure to read word

if(index == 7)
Thread.resume(threads[0]);
else
Thread.resume(threads[index+1]);
}

Please let me know your views on this.

The requirements are not clear. Can you please elaborate the question ?

The size of pointers is machine/architecture dependent.
x86 has 4byte pointers, amd64 has 8 byte pointers

To Qs2 we are getting a compilation error : "Expression not a constant integer expression"
So Ans must be D. None.

Qs3 : Anyone ?

Hi Anonymous...
Please dont use abusive words at CC else your post will be deleted.

Hi Snehasish Barman,

I think instead of a Binary Heap, something like a N-Way Heap is better as each node can have many childs.

enum EMPLOYEE_TYPE
{
CEO,
VP,
MANAGER,
EMPLOYEE,
};

typedef struct employee
{
enum EMPLOYEE_TYPE type;
char *name;
struct employee *lead;
struct employee *employee;
struct employee *co_emp;
}employee;

typedef struct node
{
char *name;
struct node *next;
}node;

node *get_employees(employee em)
{
node *head, *current_employee;
employee *child = em->employee;
while(child != NULL)
{
node *temp = (node *)malloc(sizeof(node));
if(head == NULL)
head = temp;
else
current_node->next = temp;
current_node = current_node->next;
child = child->co_emp;
}
return head;
}

We can have an enum for the types of employee:

enum EMPLOYEE_TYPE
{
CEO,
VP,
MANAGER,
EMPLOYEE,
};

typedef struct employee
{
enum EMPLOYEE_TYPE type;
char *name;
struct employee *lead;
struct employee *employee;
struct employee *co_emp;
}employee;

typedef struct node
{
char *name;
struct node *next;
}node;

node *get_employees(employee em)
{
node *head, *current_employee;

employee *child = em->employee;

while(child != NULL)
{
node *temp = (node *)malloc(sizeof(node));
if(head == NULL)
head = temp;
else
current_node->next = temp;
current_node = current_node->next;
child = child->co_emp;
}

return head;
}

Howz this ?

#include <iostream>

using namespace std;

int main (int argc, const char * argv[])
{
    int n;
    cin >> n;
    
    int num, count = 0, prev_num, max_num, max_count = 0;
    
    for(int i = 0;i < n; i++)
    {
        cin >> num;
        
        if(i == 0)
        {
            count++;
        }
        else
        {
            if(num == prev_num)
            {
                count++;
                
            }
            else
            {
                count = 1;
            }
                
        }
        
        prev_num = num;
        if(count > max_count)
        {
            max_num = num;
            max_count = count;
        }
       
    }
    
    cout << max_num << max_count;
    
    return 0;
}

The code doesn't finds the minimum window. It just finds the window and breaks.

In order to find a pair (a, b) (s.t. a is in A, b is in B) whose sums equals x, we would :
a. Sort A, B (O(nlogn))
b. initialize i, j with
i = A[0]
j = B[n] (Assuming size of all arrays is same, n)
Then:
a. If A[i]+B[j] < x , increment i
b. If A[i]+B[j] > x, dec j
c. If A[i]+B[j] == x, print A[i], B[j]
This takes O(n).

So total time complexity is O(nlogn) and space complexity is O(1)

Now we can easily extend this approach to this qs by :

Sort A,B : O(nlogn)
For each k in C
Find if there exists a pair, (a, b) s.t. a+b = k

Now the complexity of the algo is O(nlogn)+O(n^2) = O(n^2).

Rearranging as in modifying the existing node in a link list format .. like
node1 -> right = node2
node2 -> right = node3 ?
You mean like this?

The best resource:
geeksforgeeks.org/archives/1155

The matrix being mXn you would need to take care of that while deciding limits. It should be min(ceil(m/2), ceil(n/2))

K Distance Nodes:

void mod_inorder_traversal(node *root, int n, int dist)
{
    static int dist_start = -1;
    
    if(root == NULL)
        return;
    else
    {
        if(dist_start != -1)
        {
            if((dist - dist_start) == k)
            {
                cout << root->data << endl;
                return;
            }
        }
        
        if(root->data == n)
            dist_start = dist;
        
        dist += 1;
        mod_inorder_traversal(root->left, n, dist);
        
        if(dist > dist_start)
        {
            mod_inorder_traversal(root->right, n, dist);
        }
        
        else
        {
            if(dist_start == -1)
                mod_inorder_traversal(root->right, n, dist);
        
            if(dist_start != -1)
            {
                if(((dist - 1) - dist_start) == k)
                {
                    cout << root->data << endl;
                    return;
                }
            }
        }
    }
}

Any correct answers for this ?

Can someone please provide explanation to Peiyush Jain's "A Simple In-Place Algorithm for In-Shuffle." paper which provides the answer to the problem but I fail to understand it. :(

If bitset set to 2^32 size doesn't works (As is the case with my compiler), we can use short array and get the arr_index, bit_index:

//
//  main.cpp
//  InfiniteStream_SumPair
//
//  Created by Srikant Aggarwal on 11/01/12.
//  Copyright 2012 NSIT. All rights reserved.
//

#include <iostream>
#include <math.h>

using namespace std;

int get_num()
{
    int n;
    cin >> n;
    return n;
}

int main (int argc, const char * argv[])
{
    int sum;
    cin >> sum;
    
    //assuming the duplicate number range is b/w 0 to 2^32
    const int length = 2^28;
    static short bit_array[length];
    
    while(true)
    {
        int n = get_num();
                
        int arr_index = n/8;
        int bit_index = n%8;
        
        int temp = 1 << bit_index;
                
        if(bit_array[arr_index] & temp)
        {
            cout << sum - n << " " << n << endl;
            return 0;
        }
        else
        {
            n = sum - n;
            arr_index = n/8;
            bit_index = n%8;
            
            temp = 1 << bit_index;
            
            bit_array[arr_index] =  bit_array[arr_index] | temp;
        }
    }
    
    return 0;
}

For n = 2
Output :
cd bd bc cd ad ac bd ad ab bc ac ab :(

My code :

//
//  main.cpp
//  ListListFromMatrix
//
//  Created by Srikant Aggarwal on 10/01/12.
//  Copyright 2012 NSIT. All rights reserved.
//

#include <iostream>

using namespace std;

typedef struct node
{
    int data;
    struct node *right;
    struct node *down;
}node;

int main (int argc, const char * argv[])
{
    int n, m;
    int i = 0;
    
    cin >> n >> m;
    
    int **arr = new int *[n];
    while(i < n)
    {
        arr[i] = new int[m];
        i++;
    }
    
    int j = 0;
    i = 0;
    
    while(i < n)
    {
        while(j < m)
        {
            cin >> arr[i][j];
            j++;
        }
        j = 0;
        i++;
    }
    
    node *parent = NULL, *child = NULL;
    node *start = NULL;
    
    i = 0;
    while(i < n)
    {
        j = 0;
        node *head = NULL;
        while(j < m)
        {
            node *temp = new node;
            temp->data = arr[i][j];
            temp->right = temp->down = NULL;
            
            if(head == NULL)
            {
                head = temp;
                if(start == NULL)
                    start = head;
            }
            else
                child->right = temp;
                
            if(parent != NULL)
            {
                parent->down = temp;
                parent = parent->right;
            }
            
            child = temp;
            j++;
        }
        
        parent = head;
        j = 0;
        i++;
    }
    
    node *curr_ver_node = start;
    while(curr_ver_node != NULL)
    {
        node *curr_hor_node = curr_ver_node;
        while(curr_hor_node != NULL)
        {
            cout << curr_hor_node->data << " ";
            curr_hor_node = curr_hor_node->right;
        }
        cout << endl;
        curr_ver_node = curr_ver_node->down;
    }
    
    return 0;
}