CareerCup

Code to check if a given short string is a substring of a main string. Can you get a linear solution (O(n)) if possible?

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.

You have a string str = "I love you".
Write a program to print the output as "you love I". Calculate the efficiency of your coding.

You are given a UNIX path with dot (current) and two dots (parent). Convert this to an absolute path

E.g. $/home/abc/.././def/./ghi/../.
becomes $/home/ghi/

write a function :
char * CreateEmptyString(int len);

function should return an pointer to an empty string of length len

You have a very very big text file.How would you read & process it to print the below output.
1. Print the top ten ranked distinct words.
2. Print the occurrence of the each alphabet in this file.

For example:
ABC (100)
XYZ (40)
PQR (10)
THE (200)
IN (200)
Then I have to display the output as
IN (200)
THE (200)
ABC (100)
XYZ (40).
And
A=1000
B=2000
C= 300
.. ...
z=300

A string of characters were given, find the highest occurrence of the character and display it.
input:AJDHURNANDANDJNAUYTRAYAUIA
output: A

Given a string, find whether it has any permutation of another string. For example, given "abcdefg" and "ba", it shuold return true, because "abcdefg" has substring "ab", which is a permutation of "ba".

Give an algorithm which removes the occurrence of A and I from string ? The algorithm must be in-place.

Given a string, find the start position of the largest block of repeated charactes.

After the solution, I was asked to write down as many test cases I could to test the function as if it was created by someone else.

You are given two Strings lets say "S" which consist Upper Case albhabets and '?' character only and p. You are required to replace '?' with some alphabet so that resulting string have maximum number of "p" in it. You can replace '?' with any alphabet.
2. Replace '?' such that it should be lexicographically sorted.
Example
S="ABAAMA????MAZON????????"
p="AMAZON"
The final string S = "ABAAMAZONAMAZONAAAMAZON"

S="?????"
p="ABCD"
Final Result="AABCD"


Soln:- Proceed from the end of the String.

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
int main()
{
    char S[]="ABAAMA????MAZON????????";
    char p[]="AMAZON";
     printf("%s  \n",S);
     int i,j,flag=0;
     i=i=strlen(S)-1;
     while(i>=0)
     {
    	int k=i;
    	for(j=strlen(p)-1;j>=0;j--)
    	{
    		if(S[k]==p[j] || S[k]=='?')
    		{
    		   k--;
                   flag=1;
                }
                else
                {
    		    flag=0;
	            break;
		 }		
    	}
        int m=i
        if(flag==1)
        {
        	for(j=strlen(p)-1;j>=0;j--)
        	{
                       if(S[m]=='?')
        		   S[m]=p[j];
                         m--;
        	}
        }
        else
        {
        	if(S[i]=='?')
        	   S[i]='A';
        }
        i--;
    }
    printf("%s",S);
}

Round 1 :
Q 2 : longest palindrome in a string ? (Need to tell in O(n) time complexity + O(1) space complexity)

Reverse words in a string
Ex:
Input : "This is a String"
Output: "String a is This"

give a string as a input(string should be one word)if the input string is multiple by 3 then print only the multiple of 3rd letter in the string, otherwise print the input. For eg: if input is Elephant, then print Elephant .
if input is Elephants then print eas.

Write a C function to remove all spaces from a string.

Follow-up question: Explain the space and time efficiency of your solution.

Write a function called reverseReplace that takes three arguments. The first will be a string of many words, the second will be a single word that we are going to search for, and the third and final will be the string we want to replace the second word with. Example output:

reverseReplace("I like cats", "cats", "dogs") -> "dogs like I"
reverseReplace("I like cats", "mice", "dogs") -> "cats like I"

You should test it against the examples above as well as a larger test suite.

given s string "1010101010" in base2 convert it into string with base4.not use extra space....

Given a stream of text eg you can read 1 char at a time, write fn that will return true if you can find a string str is in the stream before the stream runs out.Do not store the stream.

Tokenize the given string.
node* strtok(char* input ,char* delims)
Put the words seperated into the linked list and return the linked list.delims can be a single character or group of characters like "abc".
Dictate the code as you write.

Given two strings .Print all the interleavings of the two strings.
Interleaving means that the if B comes after A .It should also come after A in the interleaved string.
ex-
AB and CD
ABCD
ACBD
ACDB
CABD
CADB
CDAB

Given some string lexical order and you don't know which language these characters. How to find find the order of the characters.

regular expression matching: given a regular expression just composed with letters and *, whether a string str can be generated by the regular expression? for example, regular expression a*b*c , the string aabaabc cann't be generated by the regular expression.

Given a string, find the substring with minimum length from it which contains exactly equal no of characters given in a hashmap which contains key as character and values as count of character needed in substring.

For example:
String str ="abcrefbda";
map = {{"b"=1},{"d"=1"},{"a"=1}};

Output = "bda";

MS written test:
Given a list of words and a dictionary with many words. The dictionary may or may not include the the given list of words.
From the given list of words,you need to print only those words which are present in dictionary.
Mention time complexity.

MS written test:

STRINGZ = STRINGX + STRINGY.charAt(index) ,
How can it be done using C language.

Also, I want to add a character in each function call.
e.g.
FUNC(mainstr,"");

FUNC(char *mainstr, char *current)
{
if(index==strlen(mainstr))
print("%s",current);
else
for(int i=0; i<strlen(mainstr) ; i++)
{
FUNC(mainstr, current+mainstr.charAt(i))
}

}
//replace current+mainstr.charAt(i) with C functions and code ..

Given a list of strings, Print all possible letter strings in sorted order.
Remember that the characters in each string are sorted.

Sample I/P:
YZ
ABCD
DEF

O/P:
ADY
ADZ
AEY
AEZ
AFY
AFZ
BDY
BDZ
BEY
BEZ
BFY
BFZ
CDY
CDZ
CEY
CEZ
CFY
CFZ

Write function compress(char* strSource)
it should do the following .
repeating chars in sequence should be replaced with char & count, in case count is 1 no need to add any integer.
Example - AAAABBBCXYZEEEEPPPPPKKABC
should be A4B3CXYZE4P5K2ABC.
you are supposed to iterate the array only once, and modify the same input parameter, do not create any new string.

write a function strRemove(char *source, char *remove )
This function will delete all the chars that exist in string remove from array source, number of iteration should be only 1. Make the searching efficient.
Example
("amazon development center", "aenr")
"mzo dvlpmt ct".
Criteria - First parameter should be modified , no need to create an extra string.
(Answer - Put the second array in a hash table, like array of 256 chars, to search which are the chars needed to be removed with complexity o(1) )

You have n strings with their lengths. You are given an add(string s1,string s2) which would concatenate the string s2 with s1 and return s3. Optimize the cost of concatenation of all these strings into one big string.
Ex: 1,3,2 are the lengths of given strings.
1+3=4
4+2=6
total cost=10
Optimize this total cost?

Remove duplicates from string given " bananas " Return "bans"
Write code for both O(n) and O(n2) solutions