CareerCup

Implement an iterator<WordAndCount> which takes iterator<String> and its next() method returns the count for same word in a row. I was also asked to implement hasNext method.

WordAndCount class had two properties:
1. Word
2. Count

I was asked to implement hasNext() and next() method which basically returns a WordAndCount object.

To make it clear, following is the example:

lets say Iterator<String> has following values:

{foo,foo,foo,bar,foo,bar,bar}

iterator<WordAndCount> next() method should return this:

{{foo,3},{bar,1},{foo,1},{bar,2}}

It seemed like an easy problem and because we ran out of time during coding i think interviewer didn't ask me the follow up question. Interviewer was nice and he told me he doesn't expect me to code in time limit but he only wants to see how i approach the problem.

Given a nxn grid with 1's and 0's find the length of largest black square formed with 1's.

So for below example:

00000
11110
01111
01110

The largest square length is 3.

With dynamic programming it can be done in O(n^2) time

It was a technical screen but it was taken in person for an event.

Write a program to find the given new program can be scheduled or not?
Already scheduled Programs: P1(10,5), P2(25,15)
New Programs: P3(18,7), P4(12, 10).
In P1(10, 5), where 10 is the starting time, 5 is the execution time.
As The P3(18, 7) starts at time 18 and executes for 7 mins i.e., the end time is 18+7 = 25. So this time slot is free and there is no overlap with already scheduled programs. Hence P3 can be scheduled.

As the P4 overlaps with P1, So P4 cannot be scheduled.

Lonely Pixel
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM))

Given unsorted array, find how many elements can be found using binary search
- ex : [5,4,6,2,8] -> Ans : 3 -> '6' and '8' and '5' can be found using binary search

Implement an api that let's users create multiple timers. You can only use one system timer in your implementation though. For example a user can write:

timer.startTimer(3, callback)
timer.startTimer(7, callback)
timer.startTimer(1, callback)

and the user will get three callbacks 1, 3, and 7 seconds later. In startTimer you only have one timer that you call like this:

System.startTimer(seconds, callback)

but it can only be called once it has finished with the previous timer.

Brace Expansion
Given a string, perfrom the brace expansion
For example,
Input: s = "a{d,c,b}e"
output: {ade , ace , abe}

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Generate random max index

Given an array of integers, randomly return an index of the maximum value seen by far.

e.g.
Given [11,30,2,30,30,30,6,2,62, 62]

Having iterated up to the at element index 5 (where the last 30 is), randomly give an index among [1, 3, 4, 5] which are indices of 30 - the max value by far. Each index should have a ¼ chance to get picked.

Having iterated through the entire array, randomly give an index between 8 and 9 which are indices of the max value 62.

Given a word of length n, and n six-sided dice with a character in each side, find out if this word is constructible by the set of given dice

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}

Find the indices of all anagrams of a given word in a another word.
For example: Find the indices of all the anagrams of AB in ABCDBACDAB (Answer: 0, 4, 8)

I am given an array of Transactions in a ledger. A Transaction object has three things.
1. Sender (which means who started this transaction)
2. Receiver (means who is the destination of transaction)
3. Timestamp (at what time this transaction was executed)

Now I need to write a method findIfTransactionIsValid() which will have the array of all transactions, one sender, one receiver. A transaction is valid is following cases:
1. if sender and receiver are same
2. The timestamp should be increasing (what I mean here is if A -> B happens at Time 2 and B-> C happens at Time 1, then A->C is not a valid transaction, however if B -> C happens at Time 3 then A--> C is a valid transaction)

Example:
Transaction
{
Sender;
Receiver;
Timestamp;
}

Example: [T is timestamp here]
A -> B (T=0)
B -> C (T=1)
C -> F (T=0)

findIfTransactionIsValid(A, C) -> this should return true
findIfTransactionIsValid(B,F) -> false (time is backwards)

If the question is still not clear, please see the solution I wrote. I have written a recursive solution and is working but I am seeing help to improve the solution.

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.

You are given a 2d grid where each grid item has a value of 1 or 0, you can only move horizontally or vertically and if both blocks have value of 1. You are also given a starting index, the output should have the "connected" grid items property to true.

For example:

input = [
      [{value: 0}, {value: 1}, {value: 1}],
      [{value: 0}, {value: 0}, {value: 1}],
      [{value: 1}, {value: 1}, {value: 1}]
    ];

    startRowIndex = 2;
    startColumnIndex = 0;
    
    output = [
      [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}],
      [{value: 0}, {value: 0}, {value: 1, connected: true}],
      [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
    ];

This is the first part of the question, this can be easily solved using either DFS or BFS.

The second part is you are given the output of the first function and the same start indices. Along with these two input arguments, you are also given a flipIndex. The grid item at the given flip index will have the value flipped. Now give the updated matrix with the updated "connected" path.

input = [
      [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}],
      [{value: 0}, {value: 0}, {value: 1, connected: true}],
      [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
    ];

    startRowIndex = 2;
    startColumnIndex = 0;

    flipRowIndex = 1;
    flipColumnIndex = 2;
    
    output = [
      [{value: 0}, {value: 1}, {value: 1}],
      [{value: 0}, {value: 0}, {value: 0}],
      [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
    ];

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 list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
For example:
input = [(1,4), (2,3)]
return 3
input = [(4,6), (1,2)]
return 3
input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
return 11

Write a new data structure, "Dictionary with Last"

Methods:
set(key, value) - adds an element to the dictionary
get(key) - returns the element
delete(key) - removes the element
last() - returns the last key that was added or read.

In case a key was removed, last will return the previous key in order.

Given two strings Y and Z , return True if y beats z or z beats y .
Beating Criteria : for i in [1,N] y[i]>=z[i] , if this condition is true for any of permutations of y for any of the permutations of z .

Given an arbitrary tree remove nodes which have data value 0.
As it stats arbitrary tree, I assumed n-ary tree.

Given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
and then another series [A != C, D != H, ..., F != A ]

Check whether the equations combined is valid.

For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series.

A function receives a big array (about 1G).
after manipulations done on the array it's data
will be erased. What should you're attitude be to dealing with the array? (I didn't understand totally the interviewer's meaning

read the 5'th bit from a byte

Write a function which returns
the multiplication of two inputs,
without using "return"

Convert a binary tree to a doubly linked circular linked list.(Tree is binary and not BST).Hint: using Inorder Traversal

Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.

eg: coins(10, 15, 55)
print:
10
15
20
25
30
.
.
.
1000

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

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

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.