CareerCup

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.

Given n boxes of different weights and m machines of different weight carrying capacity. Find the minimum time required to move all boxes.

Machines Capacities : C[0] , C[1] , C[2],........C[m-1].

Box Weights : W[0] , W[1] , W[2] .... W[n].

Each machine takes 1 minute to carry one time. What can be the optimal approach recursive approach will be to try assigning current box to given machine and not assign and recur for rest of thee boxes.

Note: A single machine can carry boxes multiple times , Each round trip takes exactly 1 unit time.

How to evaluate a mathematical expression by compiler design. The program will ask the user to input a value (say n). Then user will input n lines of input each of which contains an identifier and its corresponding value. Then program will ask the user again to input a value (say m). Then user will input m lines of expressions. Calculate the final value for each of the given expression using first n lines of input. If you can't evaluate any expression from given numbers of identifiers then output 'Compilation Error'. Allowed mathematical operators are +(add), -(subtract), x(multiply), /(divide).

Example: a = 1
b = 2
c = 2


a x b + a x c + b x c output 8
a x c - b / c + c x c out put 5


g = 2
p = 3
t = 1
w = 2

g + p x t - w x p output -1
t - g + t - w output -2
e + t x t - m output compilation error

binary search

It was a online coding round on software provided by samsung itself.
Given a graph print either of the set of the vertices that are colored with the same color. And if the graph is not bipartite print “-1”. Test cases also included the cases when a graph is not connected.
Note: No STL or other library functions were allowed

A company wants to fly in a total of 100 candidates for the interview. The company has two office location, one in NY and other in SF and max capacity at each location is 50 candidates. You are given the cost it incurs to fly in each candidate to NY and SF.

[500, 300],[540, 600],[550, 600],[300, 50]..so on

Write an algorithm for the minimum total cost?

Given the arraylist<meals> input, find the number of dishes with unique ingredients.

class meals{
        String cuisine;
        ArrayList<String> dish = new ArrayList<String>();
        meals(String s, String[] arr){
                cuisine = s;
                for(String i:arr){
                    dish.add(i);
                }
        }
    }

Example:
Input: [
{
"cuisine" : "American",
"dish" : ["lettuce", "cheese", "olives", "tomato"]
},
{
"cuisine" : "Mexican",
"dish" : ["lettuce", "cheese", "pepper", "tomato"]
},
{
"cuisine" : "French",
"dish" : ["lettuce", "cheese", "pepper", "tomato"]
},
{
"cuisine" : "Continental",
"dish" : ["lettuce", "cheese", "olives", "tomato"]
},
]

Output: 2

Because there are two unique ingredient-dishes; {Mexican, French} and {American, Continental}.

I have tried different methods, but could not get to the solution. Thank you!