CareerCup

Given 2n points on a circle.find the number of ways to draw n non intersecting chords.

Code a function that receives a string composed by words separated by spaces and returns a string where words appear in the same order but than the original string, but every word is inverted.
Example, for this input string

@"the boy ran"

the output would be

@"eht yob nar"

Tell the complexity of the solution.

You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .
NOTE: The array isn't necessarily sorted.

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".

Given a source string and a destination string write a program to display sequence of strings to travel from source to destination. Rules for traversing:
1. You can only change one character at a time
2. Any resulting word has to be a valid word from dictionary
Example: Given source word CAT and destination word DOG , one of the valid sequence would be
CAT -> COT -> DOT -> DOG
Another valid sequence can be
CAT -> COT - > COG -> DOG

One character can change at one time and every resulting word has be a valid word from dictionary

Given a value and a binary search tree.
Print all the paths(if there exists more than one) which sum up to that value. It can be any path in the tree. It doesn't have to be from the root.

write a method that takes in 2 int arrays of any size and returns an array that calculates the sum of both.

for example, [1,2,3] and [2,3,4] will return [3,5,7]

Or [1,2,3] and [2,3,5,5] will return [2,4,7,8]

however, if it's like [9,9,2] and [0,1,3] you need to carry the sum so it returns as [1,0,0,5]

** SINGLE DIGIT ONLY

Given the array of digits (0 is also allowed), what is the minimal sum of two integers that are made of the digits contained in the array.
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207

You are given a huge log file which holds the entry and exit time of each person entering and exiting the office on a given day

format of file:
entry time exit time
09:12:23 11:14:35
10:34:01 13:23:40
10:34:31 11:20:10
.
.upto N entries for a given day

Design a function which returns the total number of persons in the office at any given time. e.g input to function is 11:05:20.

The interviewer said he could call the function every second with input 11:05:20, 11:05:21,11:05:22, 11:05:23..........14:30:30

I really did not understand how to optimize the function.

Given a very long list of URLs, find the first URL which is unique ( occurred exactly once ).

I gave a O(n) extra space and O(2n) time solution, but he was expecting O(n) time, one traversal.

Find if a binary tree is bst

Here is a tree. It's a binary tree but in no particular order. How do you write this tree to a file so that it can be reread in an reconstructed exactly as shown?

Given a number "n", find the least number of perfect square numbers sum needed to get "n"

Example:
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)

Question: Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T
Example
[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7

Given an array of ages (integers) sorted lowest to highest, output the number of occurrences for each age.
For instance:
[8,8,8,9,9,11,15,16,16,16]
should output something like:
8: 3
9: 2
11: 1
15: 1
16: 3

This should be done in less than O(n).

You have an array of integers(size N), such that each integer is present an odd number of time, except 3 of them(which are present even number of times). Find the three numbers.

Only XOR based solution was permitted.
Time Complexity: O(N)
Space Complexity: O(1)

Sample Input:
{1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9}
Sample Output:
1 6 8

Given a large network of computers, each keeping log files of visited urls, find the top ten of the most visited urls.
(i.e. have many large <string (url) -> int (visits)> maps, calculate implicitly <string (url) -> int (sum of visits among all distributed maps), and get the top ten in the combined map)

The result list must be exact, and the maps are too large to transmit over the network (especially sending all of them to a central server or using MapReduce directly, is not allowed)

Use SIMPLE LOGIC for Converting this string str="aaabbccc" into str="3a2b3c".
###Note:###
I gave 3 diff solutions to interviewer with loops,conditions etc.,But he wanted a real OPTIMAL SOLUTION..lets see who ll write!!!!!

Given two singly linked list, find if they are intersecting. Do this in single iteration. Also find the intersecting node in O(n) time and O(1) space. By intersection I mean intersection by reference not by value

Given preorder traversal array of a BST, recontruct the BST.

You have a random 5 function. Generate a random 7 function using this random 5 function with equal probability
hint: think at bit level

There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it's dropped from any floor below, it will not break. You're given 2 eggs. Find N, and minimize the number of drops for the worse case.

You are tasked with implementing a method that returns the lowest possible number that could be generated after removing n characters from a string of digits. The method signature should look like:

public static string GenerateLowestNumber(string number, int n)

Where the number parameter is a string that contains a number (e.g. “4205123”), and the n parameter represents the number of characters to remove from the string. The goal of this method is to return the lowest number that can be generated by removing n characters from the number provided while keeping the positions of the remaining characters relative to each other the same (i.e. the method should remove n characters from the string, but it cannot re-order the characters).
For example, if number is “4205123” and n is 4, the lowest possible number that can be generated after removing any 4 characters is “012”. If number is “216504” and n is 3, the lowest possible number that can be generated after removing 3 characters is “104”.

Determine minimum sequence of adjacent values in the input parameter array that is greater than input parameter sum.

Eg
Array 2,1,1,4,3,6. and Sum is 8
Answer is 2, because 3,6 is minimum sequence greater than 8.

Given a random string S and another string T with unique elements, find the minimum consecutive sub-string of S such that it contains all the elements in T.
example:
S='adobecodebanc'
T='abc'
answer='banc'

Given a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it.
Find the length of the shortest palindrome that you can create from S by applying the above transformation.