CareerCup

Give you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.
o(n)time complexity and o(1) space complexity is perfect.

Given an int array which might contain duplicates, find the largest subset of it which form a sequence.
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7

Sorting is an obvious solution. Can this be done in O(n) time

test cases for atm

If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.

For example:
Input: "1123". You need to general all valid alphabet codes from this string.

Output List
aabc //a = 1, a = 1, b = 2, c = 3
kbc // since k is 11, b = 2, c= 3
alc // a = 1, l = 12, c = 3
aaw // a= 1, a =1, w= 23
kw // k = 11, w = 23

Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )

You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo

Given two strings a and b, find whether any anagram of string a is a sub-string of string b. For eg:
if a = xyz and b = afdgzyxksldfm then the program should return true.

Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.
* The sub-arrays should not overlap.

eg- [2 -1 -2 1 -4 2 8] ans - (-1 -2 1 -4) (2 8), diff = 16

I gave him o(n^2) algorithm but he was not satisfied.

give me the code for :
Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such.
Eg: O/p should be "I ma a namuh gnieb"

I somewhat wrote the code, but i was asked what if there are extra spaces etc.
(i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence)
let me know the best and optimised way of writing this code.
Also i suggest people to aviod using inbuilt functions as much as possible



My Answer is as below in perl

#i want the reverse of the letters of all words in a string
#eg Input is "I am a human being" then o/p shud be "I ma a namuh gnieb"
$str="I am a human being";
@arr=split(' ',$str);
print @arr;
for($i=@arr-1;$i>=0;$i--)
{
$_=@arr[$i];
####intead of above for loop if we use foreach(@arr) then it will reverse the whole string
@word=split('',$_);
{
foreach $n (@word)
{
unshift(@final,$n);
}
}
}
print "\n @final \n";

one unsorted array is given.Find out the index i and j ,j> i for which a[j] - a[i] is maximum.perform in linear time complexity

You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

For example,
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.

You are given a string S and a set of n substrings. You are supposed to remove every instance of those n substrings from S so that S is of the minimum length and output this minimum length.
Eg:
S- ccdaabcdbb
n=2 - substrings-- ab, cd
Output: 2
Explanation:
ccdaabcdbb -> ccdacdbb -> cabb -> cb (length=2)
Can someone help me with the algo?

A k-palindrome is a string which transforms into a palindrome on removing at most k characters.

Given a string S, and an interger K, print "YES" if S is a k-palindrome; otherwise print "NO".
Constraints:
S has at most 20,000 characters.
0<=k<=30

Sample Test Case#1:
Input - abxa 1
Output - YES
Sample Test Case#2:
Input - abdxa 1
Output - No

Push all the zero's of a given array to the end of the array. In place only. Ex 1,2,0,4,0,0,8 becomes 1,2,4,8,0,0,0

1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.
for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.
the question is to find the max qaz.
it can be solved simply using 2 loops which takes time of O(n^2).
that's ok but how can we solve this problem in O(nlogn).
I have an approach and know the algorithm I got during the interview but it take a 40 of me to find it and write the code, but it was hard to think about it during the interview in that way.
I want to know if somebody can think and write the code in less than 20 minutes !!!

given an int array with no duplicate numbers, write a function to return number of ways to calculate a target number.

example: given {2,4,6,8} Target = 12
2 + 4 + 6 = 12,
4 + 8 = 12,
6 + 8 - 2 = 12,
2 - 4 + 6 + 8 = 12,

return 4

We have an array of objects A and an array of indexes B. Reorder objects in array A with given indexes in array B. Do not change array A's length.

example:

var A = [C, D, E, F, G];
var B = [3, 0, 4, 1, 2];

sort(A, B);
// A is now [D, F, G, C, E];

Implement the plusplus operator when we are getting the input as integer array = { 9,9,9,9 }.output will be {1,0,0,0,0}

Simulate a seven-sided die using only five-sided

Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)

Given a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest.
i.e:
bcabc
You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest.

ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case:
cbacdcbc. answer is acdb not adcb

I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.

Print a character 1000 times without using loop and recursion.

Given a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.
Example:
Input : a?b?c?
Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.

Q: Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?

The obvious and naive way that I thought of was to convert the entire array into a 1D and do a mergesort on it, but there must be a better way than that. I'm wondering what the better and more efficient way is.