CareerCup

Given two (binary) trees, return the first pair of non-matching leaves

Tree 1: A, B, C, D, E, null, null
Tree 2: A, D, B

Output: (E,B)

Given: sorted array of integers
Return: sorted array of squares of those integers
Ex: [1,3,5] -> [1,9,25]

Integers can be negative.

Design a HTTP response service that will allow sync and async download. What classes would you create and the methods used with paramerters and return types.

Convert a number to English representation.
Ex: Input : 100
Output : One Hundred.

How do I find the longest possible route in a matrix?
There are some hurdles in the path.
Details in image : https://s31.postimg.org/7nwp4gmzv/hurdle1.jpg

Given Nodes such as

M->       N->       T->       D->       E
|          |         |        |	
C         X         Y          L
|         |
A         Z

-> right pointer
| down pointer
Output should be
M->C->A->N->X->Z->T->Y->D-L>E

Write this to flatten
flatten(Node head) {

}

Node {
Node right;
Node down;
char a;
}

You have an array of unique integer numbers and only one operation: MoveToFront(x) that moves given number to the beginning of the array.
Write a program to sort the array using the minimum possible number of MoveToFront() calls.

Given an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X

[1, 3, 5, 18] X = 8 Output: True
X = 9 Output: True
X = 10 Output: False
X = 40 Output :False

A museum was represented by a square matrix that was filled with O, G, and W where O represented open space G represented guards, and W represented walls. Write a function that accepts the square matrix and returns another square matrix where all of the O's in the matrix are replaced with the number of how many spaces they are away from a guard, without being able to go through any walls.

You are given a string "abc" which is encoded like "123" where alphabets are mapped like a => 1 to z => 26. Now find out how many string can be formed by reverse engineering encode string "123".

For ex. given string "123" we can form 3 string "abc"(1,2,3), "lc" (i.e 12,3), "aw"(1,23).

for string "1234" we have following possible combinations, I might be missing some of them but you get the idea

{12, 3, 4}
{1, 23, 4}
{1, 2, 3, 4}

// Reverse the words. Given a String that contains words separated by single space, reverse the words in the String. You can assume that no leading or trailing spaces are there.
// For example: "Man bites dog" => "dog bites Man”

String reverseWords(String value) {
    // Insert implementation
}

Select Kth largest value in the array. Given an unsorted array of size n, and a value k. Select the kth largest value from the array.

For example:

Array is [5, 3, 9, 1], n is 4
k = 0 => 9
k = 1 => 5
k = 3 => 1

public int kthLargest(int array[], int k) {
// ..... 
}

Given two sorted linked lists of integers write an algorithm to merge the two linked lists such that the resulting linked list is in sorted order. You are expected to define the data structure for linked list as well. Analyze the time and space complexity of the merge algorithm.

There are N coins with coordinates (x, y) where x >0 and y >0
You start at (0, 0) and you can only do steps of form (dx, dy) where dx >0 and dy > 0
Print the maximum number of coins that you can collect.

Clarification: you can do as many moves as you wish, the point is to collect maximum number of coins. If you are located at position (a, b) you may jump to position (a+dx, b+dy) for all dx > 0 and dy > 0

@krbchd: Your algorithm may output incorrect values. Suppose there are points (5, 7), (5, 8), (5, 9) for y coordinates LIS will output 7, 8, 9, however since these points are on the same x axis, you can choose only one of them.

GIven a string "str" and pair of "N" swapping indices, generate a lexicographically largest string. Swapping indices can be reused any number times.

Eg 1)

String = "abdc"

Indices:

(1,4)

(3,4)

Answer:

cdba, cbad, dbac,dbca

​you should print only "dbca" which is lexicographically largest.

Given the root of a binary tree containing integers, print the columns of the tree in order with the nodes in each column printed top-to-bottom.

Input:
      6
     / \
    3   4
   / \   \
  5   1   0
 / \     /
9   2   8
     \
      7

Output:
9 5 3 2 6 1 7 4 8 0

Input:
       1
     /   \
    2     3
   / \   / \
  4   5 6   7

When two nodes share the same position (e.g. 5 and 6), they may be printed in either order:

Output:
4 2 1 5 6 3 7
or:
4 2 1 6 5 3 7

Given an array and a number, add it in such a way where array is [0,0,1] and number is 4 output will be [0,0,5]

Example 2 :
array is [1] and number is 9 output will be [1,0]

Given a set of numbers {x1, x2, x3, x4, ..., xN} (N>=3) a set of its pairwise sums is {x1+x2, x1+x3, x1+x4, x2+x3,x2+x4,x3+x4, ...,}. (That is s_k = x_i + x_j where i != j)
Restore a set of numbers given a set of its pairwise sums.
Note: you don't know given some k, to which i and j it refers, (i.e. input is given in undefined order)


EDIT: couldn't comment, so here is clarification

Example:

S = {1, 5, 10, 100} (n elements)
P = {6, 11, 101, 15, 105, 110} (n * (n - 1) / 2 elements)

Given P you have to restore S.
Note here means that if you knew which element in P corresponded to which pair of indices in S, you could just solve a simple linear equation

x1+x2=a{k1} x2+x3 = a{k2}, ...., x{n-1} + x{n} = a{k{n-1}, x{n} + x1 = a{k{n}}

Given a string where in each word letters were randomly shuffled and after that words were written without spaces (lets call it X). Also you have a dictionary. The task is to return all possible strings S that can be transformed into the string X and all words in S are from dictionary.

Given two arrays/Lists (choose whatever you want to) with sorted and non intersecting intervals. Merge them to get a new sorted non intersecting array/list.

Eg:
Given:
Arr1 = [3-11, 17-25, 58-73];
Arr2 = [6-18, 40-47];

Wanted:
Arr3 = [3-25, 40-47, 58-73];

Task schedule: given a sequence of task like A B C(means 3 different tasks), and a coldtime, which means you need to wait for that much time to start next [same] task. Now----

Input: string, n
Output: the best task-finishing sequence.

eg. input: AAABBB, 2
Output: AB_AB_AB
( "_" represents do nothing and wait)

Given a decimal number, write a function that returns its negabinary (i.e. negative 2-base) representation as a string.

#!/usr/bin/env python3
assert solution(-15) ==	'110001'
assert solution(2) == '110'
assert solution(13) == '11101'

Given a forest of balanced binary trees and two nodes, n1 and n2, find the closest common parent of n1 and n2. Nodes have parameters "parent", "left" and "right", and you cannot access the values of the nodes. If n1 and n2 are not on the same tree, return NULL.

Try to do this in O(log(n)) time and O(1) space.

Given an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.

Given integer k and a subset S of set {0, 1, 2, ..., 2^k - 1}
Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a)
& here is bit-wise and.
Do it faster than O((2^k)^2), assume k <= 16

Example:
0b111
0b101
0b010
Answer: 2

0b110
0b011
0b101
Answer: 0

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 set of ranges:
(e.g. S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}.
And given a target range R (e.g. R = (3, 13) - meaning the range going from 3 to 13). Write an algorithm to find the smallest set of ranges that covers your target range. All of the ranges in the set must overlap in order to be considered as spanning the entire target range. (In this example, the answer would be {(3, 9), (9, 12), (11, 14)}.

Given an array of positive integers (excluding zero) and a target number. Detect whether there is a set of consecutive elements in the array that add up to the target.

Example: a = {1, 3, 5, 7, 9}
target = 8

output = true ({3, 5})

or target = 15
output = true : {3, 5, 8}

but if target = 6, output would be false. since 1 and 5 are not next to each other.

Given an array of integers. Modify the array by moving all the zeros to the end (right side). The order of the other elements doesn't matter.

Given a dictionary containing a list of words, a starting word, and an ending word, return the minimum number of steps to transform the starting word into the ending word.

A step involves changing one letter at a time to a valid word that is present in the dictionary.

Return null if it is impossible to transform the starting word into the ending word using the dictionary.

Example:

Starting word: cat
Ending word: dog

cat -> cot -> cog -> dog ('cot' and 'cog' are in the dictionary)

return 3