CareerCup

Given two binary trees, explain how you would create a diff such that if you have that diff and either of the trees you should be able to generate the other binary tree. Implement a function which takes Node tree1, Node tree2 and returns that diff.

Create an iterator class that stores a list of the built-in Iterators.
Implement the next() and hasNext() methods in a Round Robin pattern (pops next element in a circle).
Example:
Given a list [iterator1,iterator2, iterator3...]
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next() if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
until there is no more element in any of the iterators

Find whether string S is periodic.
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"

Given string S, find out the P (repetitive pattern) of S.

Given a dictionary of words & a miss-spelled input, write a function which will find 3 words from the dictionary which are closest (by difference of 1-character) to the given input.

eg - dict = {vil, sit, flick, pat, pluck, sat, vat}, input = vit, ans = {sit, vil, vat}

// For a given vector of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K
// For example, for K = 8 and vector [2, 4, 5, 7], the solution is 5 ([2], [4], [2, 4], [2, 4, 5], [2, 5])
The time complexity should be O(n2). Approach and code was asked

Write a retry function, continue to fetch data until u have exhausted max entries. If it fails, continue to retry until retry's have been exhausted.

There are N countries, each country has Ai players. You need to form teams of size K such that each player in the team is from a different country.
Given N and number of players from each country and size K. Find the maximum number of teams you can form.

Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
Follow-up: If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?

Given a directed graph and a node , find the shortest cycle in a graph with given node .

Given a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles


Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it

[Google] Design Text Editor (Doubly Linked List)
Build a text editor class with the following functions,

moveCursorLeft(),

moveCursorRight(),

insertCharacter(char) //insert the char right before cursor

backspace() //delete the char right before cursor

Follow-up
Implement undo() //undo the last edit. Can be called multiple times until all edits are cancelled.

All functions above should take O(1) time.

Example

( '|' denotes where the cursor locates. 'text' shows what's been written to the text editor. )

Start with empty text
text = "|"

insertCharacter('a')
text = "a|"

insertCharacter('b')
text = "ab|"

insertCharacter('c')
text = "abc|"

moveCursorLeft()
text = "ab|c"

moveCursorLeft()
text = "a|bc"

backspace()
text = "|bc"

moveCursorLeft()
text = "|bc" (nothing happens since cursor was on the leftmost position)

undo()
text = "a|bc"

undo()
text = "ab|c"

undo()
text = "abc|"

undo()
text = "ab|"

undo()
text = "a|"

Given a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)

For example

s = 'ababac'

Then substrings are as follow:

1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c

Now, The lengths of LCP of all substrings are as follow

1: len(LCP(s(1, 6), s)) = 6
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0

String contains only lowercase alphabates.

[Google On-site 2018 Winter]
Set Matrix Zeroes II
There are orbs on an NxM board ('O' denotes orb. 'X' denotes empty slot).

Whenever two orbs are in the same column or the same row, you get to erase one of them.

Try to erase as many orbs as possible.

Find the minimum number of orbs remained on board eventually.

e.g.

OXOXXO

XXXXXO

XXXXOX

erase (0,0) and get

XXOXXO

XXXXXO

XXXXOX

erase (2,0) and get
XXXXXO

XXXXXO

XXXXOX

erase (5,0) and get

XXXXXX

XXXXXO

XXXXOX

no more moves available. Return 2 e.g.

OXOXXO

XXXXXO

XXOXOX
erase(4,2), (2,2), (0,0), (2,0), (5,0)

Return 1
e.g.
OXOXXX

XOXXXO

XXXOOX

erase(0,0), (1,1), (3,2)

Return 3

Follow-up Build a solver for this board game that erases the as many orbs as possible.

Roulette -Gamblers Fallacy. start with $50, bet opposite color every time same color 4 in a row. loop 100 time or until $0. Suggest create roulette wheel object with history, a gambler object with maybe gamblingplan object. (you can find more detailed suggestions elsewhere)

Given a tree with n nodes. Each node has k coins, where 0 <= k <= n . There are total n coins on the tree.
The goal is to move the coins such that each node has exactly one coin. What's the minimum moves required?
Each move can only move one coin to an adjacent node.

You have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by ci. You need to put these toffee packets in 5 boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum.

You can only choose consecutive toffee packets to put in a box.

The difference between move and forward in C++

binary search

How would you tell whether a graph has a node with n degree??
tell your approach

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Given an array of integers, find out how many unique BST can be generated from the array.

Given an array of Integers, find out how many combinations in the array, satisfy the equation x+y+z=w, where x,y,z and w belong to the array and idx(x)<idx(y)<idx(z)<idx(w). Elements are unique.

Given a bench with n seats and few people sitting, tell the seat number each time when a new person goes to sit on the bench such that his distance from others is maximum?

Given a room with thief on left side of the room with finite number of sensors. He has to reach on right side missing the sensors. Each sensor is placed at any random point in the room and has its coverage in the radius r. Find out if the thief can reach to the right side without touching the range of any sensor.?

please discuss approach first & then code it..

1. Try to find whats wrong with this code

2. after fix it what is the out put

3 how to make this code more generic :D

Initial state of an array "a":

[[2, NULL, 2, NULL],
[2, NULL, 2, NULL],
[NULL, NULL, NULL, NULL],
[NULL, NULL, NULL, NULL]]

========
Main function:

FUNCTION foo()
FOR y := 0 to 3
FOR x := 0 to 3
IF a[x+1][y] != NULL
IF a[x+1][y] = a[x][y]
a[x][y] := a[x][y]*2
a[x+1][y] := NULL
END IF
IF a[x][y] = NULL
a[x][y] := a[x+1][y]
a[x+1][y] := NULL
END IF
END IF
END FOR
END FOR
END FUNCTION

Given a list L of video names and their watch rates, write a function that will return the videos with the top 10 watch rates. Video names may appear more than once.

You are given a campus map with the Google buildings, roads and Google
bikes. You have to help the employee find the nearest Google bike.

Campus map:

. - Free path/road
# - Building
B - Google bike

Employee location - (x, y) - (1, 2)

. . . . . #
. . E . . #
# # # # . #
. B . . . .
. . . . . B

write a main program to take snapshots of VMs
Input: List of VMs(vmId: String), list of SLAs -> there is one-to-one mapping from VM to SLA

class SLA {
int freq_in_mins;
}

vm1 -> sla1{30 mins}
vm2 -> sla2{60 mins}

Constraints:
1) You can use takeSnapshot(vmId: String) -> Synchronous - I/O
2) If you start a snapshot of VM(with sla1) at time t0 and if it finishes at time t1, then the next snapshot should be scheduled at t1+sla1.freq_in_mins


vm1 at 00:00 and vm2 at 00:00
00:10 and 00:15

vm1 -> 00:10 + 30 = 00:40

Given two string check if they can be made equivalent by performing some operations on one or both string.

swapEven:swap a character at an even-numbered index with a character at another even-numbered index

swapOdd:swap a character at an odd-numbered index with a character at another odd-numbered index

Given : s="cdab" , x="abcd"
s -> cdab ->swap a and c ->adcb (swapEven)-> swap b and d (swapOdd) -> s="abcd" = x="abcd"

Given: s="dcba" , x="abcd"
no amount of operation will move character from an odd index to even index, so the two string will never be equals

Given: s="abcd" ,x="abcdcd"
x length to big so will never be equals

Find top 10 most frequent words in the past hour, day and month from twitter service. Given a streaming data such as tweets from twitter service, the objective is to find the top 10 frequent words in the past hour, day and past month at any instant of time.