CareerCup

Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.

Examples:
abc -> ac
ac->''
react->rt

Sort an array which only has 0's and 1's. Do not use count sort.

Given a string, find the longest possible even palindrome (length of palindrome is even) from it.
Eg:
Input: abcicbbcdefggfed
Output: defggfed (length is 8)

Available palindromes are
1) bcicb - has odd length
2) cbbc - even length
3) defggfed - longest palindrome with even length

This question was asked in a telephonic interview for my friend. I will be posting his solution in a day.

write a program to serialize and deserialize a Binary tree

For 2 given array a[] and B[], find the highest index of A such that logical array A[0...i] and A[N-1...N-1-i] are same.

Given an array of integers such that each element is either +1 or -1 to its preceding element. Find 1st occurrence of a given number in that array without using linear search.

Given a rotated sorted array, find the MIN of the array.

He pointed out a mistake in my
int middle = (begin+end)/2 which could overflow if the array size was INT_MAX.
Answer was:
middle = (end-begin)/2 + begin

Find the Max sum subsequence in array

You have an array Char[] chArray = {'a','a','b','c','a','b','d','c','c','d','a','a'}

Write a program to remove the duplicate and the output should be as per the below:
{'a','b','c','d','','','','','','',''} . You should not use any collection api

For given N* N matrix,

1 2 3
8 9 4
7 6 5
Write a program to
print 1,2,3,4,5,6,7,8,9

//Q. Given an array of integers,write a function that retrieves unique instances of any duplicates, returning them in a //new array -
// [2,1,2,4,3,1,5,1]
//= [2,1]
// [1,1,1,1,1,1,1,1,1]
// =[1]

// Write test cases for this function

find a pattern in byte array and change that pattern in place (do not use temp array or variable)
for example, find pattern 0,0,3 in an byte array and replace it with 0,0
should be o(n)
my solutions :

Byte*remPattern003(byte arr[] , int &size) //size is input and output variable ///outputs size of  output array
{
	int k = 0;
	for(int i=0;i<size;)
	{
		if(arr[i] == 0 && arr[i+1] == 0 && arr[i+2] == 3)
		{
			arr[k++]=arr[i];
			arr[k++]=arr[i+1];
			arr[k]=arr[i+3];
			i+=3;

		}
		else
			arr[k++]=arr[i++];

	}
	size= k;
	return arr;
}

Write a program to find the element in an array that is repeated more than half number of times. Return -1 if no such element is found.

Design a Tic Tac Toe Game. Classes Segregation and Code Flow.

Length is given as input.Print all possible permutations of numbers between 0-9.
Eg: if input length=4
all possible combinations can be 0123, 1234, 5678,9864,...etc all combinations of length from in all numbers between 0-9

Which one is faster and why?
1. Array
2. Link List.
If we just want to iterate in for loop and print it.

An array contains two sub- sorted arrays. Give an inplace algorithm to sort two sub arrays.

for ex: I/P: 1 4 5 7 8 9 2 3 6 10 11
O/P: 1 2 3 4 5 6 7 8 9 10 11

Arrange 1 to N in random order with no duplication.

Suppose we have r lists with integers from 1 to n. The sum of the lengths of the lists is n. The lists can be different lengths and the same integer may appear in more than one list. Sort all the lists in O(n) time.

given a string in form of an array find an expanded string
e.g. A2B3C4 => AABBBCCCC
also, size of given array is exactly same as expanded string. so return the same array with expanded string.

Write a function to sum up two polynomials. Design the data structure for polynomial.

Given an array sort all the elements in even positions in ascending order and odd positions in descending order

Given an array elements, Find the maximum number which can be formed by the array elements
Eg input – a[ ] = {9,6,8,1]
Output - 9861

Given an infinite sequence of integers which are repeated many times. WAP to print "beep" if an integer appears ODDth time else print "no beep".
example: input: a[] = { 1,4,2,4,3,2,4}
output: beep, beep, beep, no beep, beep, no beep, beep
Space complexity - O(1)

You are given an unsorted integer array of size N. This array contains integer from range 0 - N (not necessarily distinct and same integer can appear multiple time in an array).
You need to find pair of all the elements in array which sum up to N.

First i gave a solution using an extra array of size N to keep count of each integer in original array and was able to give solution in O(n) Time complexity and O(n) space complexity.

Then interviewer asked me to decrease space complexity, for which i gave solution as sorting the given array (in nlogn time) and then find the pairs in O(n) time, and hence total time complexity was O(nlogn) and space complexity as O(1).

But interviewer kept pressing for a better time complexity (than O(nlogn)) with O(1) space complexity.

How is it possible, i could not think of any way.

Given a 2D array of chars and a raw list of valid words.
1) Find all the valid words from the array. From each element in the array, you can traverse up, down, right or left.
Eg,

g o d  b  o  d  y
  t a m o  p   r  n 
  u i  r  u  s  m  p

valid words from the above 2D array -> god, goat, godbody, amour,....

2) Also, find a suitable DS to store the raw words list.

I used a recursive approach to solve the problem in exponential time. Can't think of any better approach.

Given a two dimensional matrix of booleans, there is a function that returns the number of "true regions".

A region is a group of True values aligned vertically or horizontally.

T T    <= 1 region
T F

T F    <= 2 regions
F T

Question 1: How would you test a function that solve this problem, but is written by another developer. How many tests cases do you see?

Question 2: Now write the code to solve this problem. What are the time and space complexities?

Given two arrays of ints that are sets, create a function to merge them to create a new set.

A set must pass on these three conditions:
- All values are positive
- Sorted
- Non-duplicates

Tell me if a array of integers is a set.

A set must pass on these three conditions:
- All values are positive
- Sorted
- Non-duplicates

After the first solution, I was asked about time and space complexity and to create 5 test cases for my function.

We are given a matrix of MxN elements with each element either being 0 or 1.Find the shortest path between a given source cell to a destination cell.
An element value of 0 means we cannot create a path out of that cell