Marcello Ghali
BAN USERDFS:
package main
import (
"fmt"
sh "interviews/rest/shared"
)
func initGraph() *sh.Graph {
node5 := &sh.Node{
Data: 5,
}
node4 := &sh.Node{
Data: 4,
}
node3 := &sh.Node{
Data: 3,
}
node2 := &sh.Node{
Data: 2,
}
node1 := &sh.Node{
Data: 1,
}
node1.Adjacency_list = []*sh.Node{node2}
node2.Adjacency_list = []*sh.Node{node4, node3}
node3.Adjacency_list = []*sh.Node{node5}
node4.Adjacency_list = []*sh.Node{node5}
node5.Adjacency_list = []*sh.Node{node3}
g := &sh.Graph{
Nodes: []*sh.Node{node1},
}
return g
}
var visited map[*sh.Node]bool
func visit(r *sh.Node) bool {
visited[r] = true
for _, ch := range r.Adjacency_list {
if ch == r {
continue
}
if visited[ch] {
return true
} else {
if visit(ch) {
fmt.Println(ch.Data)
return true
}
}
}
return false
}
func main() {
root := initGraph()
visited = make(map[*sh.Node]bool)
fmt.Println(visit(root.Nodes[0]))
}
Using sieve of erotospenes, complexity O(nloglogn):
package main
import (
"fmt"
"math"
"math/rand"
)
func main() {
primes := findPrimes(225, 350)
r := rand.New(rand.NewSource(7))
fmt.Printf("random %d", primes[r.Intn(len(primes))])
}
func initArray(max int) []int {
toReturn := make([]int, max+1)
for i := 0; i < max; i++ {
toReturn[i] = i + 1
}
return toReturn
}
func findPrimes(min, max int) []int {
input := initArray(max)
sqrtN := int(math.Sqrt(float64(max)))
for seed := 2; seed < sqrtN; seed++ {
for i := seed; i < max; i++ {
if input[i] != -1 && input[i]%seed == 0 {
input[i] = -1
}
}
}
toReturn := make([]int, 0)
for i := min - 1; i < max; i++ {
if input[i] != -1 {
toReturn = append(toReturn, input[i])
}
}
return toReturn
}
Recursive solution, complexity O(2^(countofitems<targetsum))
package main
import (
"fmt"
"sort"
)
func main() {
input := []int{1, 1, 3, 4, 1, 1, 2, 3}
target := 4
// sorting can be done O(n)
sort.Ints(input)
used := make([]bool, len(input))
findSum(input, used, target, 0)
}
func print(used []bool, input []int) {
for i := 0; i < len(input)-1; i++ {
if used[i] {
fmt.Printf("%d ", input[i])
}
}
fmt.Println()
}
func findSum(input []int, used []bool, target, cur int) {
if cur > target {
return
}
if cur == target {
print(used, input)
return
}
for i := 0; i < len(input)-1; i++ {
if input[i] > target {
return
}
if used[i] {
continue
}
used[i] = true
findSum(input, used, target, cur+input[i])
used[i] = false
}
}
Basically, every recursion step you narrow your task to n-1 case, eventually you'll end up to solving the task, with n = 1. Here is recursive solution on Golang:
func generate(k, curSum, target int, output []int) {
if k == 0 {
output = append(output, target-curSum)
fmt.Println(output)
return
}
for i := 0; i <= target-curSum; i++ {
output = append(output, i)
generate(k-1, curSum+i, target, output)
output = output[:len(output)-1]
}
}
func main() {
n, target := 4, 6
array := make([]int, 0, n-1)
generate(n-1, 0, target, array)
}
can you post an example?
- Marcello Ghali April 18, 2017func genEvenFourDigitNumber(r *rand.Rand) int {
for true {
n := r.Intn(9000) + 1000
if n%2 == 0 {
return n
}
}
return -1
}
can you add an example?
- Marcello Ghali April 17, 2017Iterate thru the list, if prev element is same as current, find next non-equal and swap those. Repeat until the end. Worst case O(n^2)
- Marcello Ghali April 08, 2017Create a hash table, go through each element and:
1) if starts with 'E' insert if such element isn't there, otherwise return invalid error
2) if starts with 'L' remove element with a key 'L {number}', otherwise return invalid error
Finally, if there are any keys left, that means building isn't empty, return invalid list error
Greedy algorithm, iterating over n buckets and choosing at each iteration 3 marbles by iterating over marbles set and tracking colors already used in the bucket and decrementing marbles count.
- Marcello Ghali April 07, 2017Dynamic programming question.
Let P(i, j) be the min number of sum of sq root numbers, where i ∈ [0, round(sqrt(N))], j ∈ [0, N]. P(i,j) = min(P[i-1, j], P[i, j-1] + 1)
private static void Main(string[] args)
{
int[] input = { 5, 6, 7, 4, 0, 1, 2 };
int direction = -4;
if (direction < 0)
{
input = reverse(input);
}
for (int i = 0; i < Math.Abs(direction); i++)
{
rotate(input);
}
if (direction < 0)
{
reverse(input);
}
}
private static int[] reverse(int[] input)
{
int i = -1;
int j = input.Length;
int tmp = 0;
while (i++<j--)
{
tmp = input[i];
input[i] = input[j];
input[j] = tmp;
}
return input;
}
private static void rotate(int[] input)
{
if (input == null || input.Length == 0 || input.Length == 1)
{
return;
}
int i = input.Length - 1;
int tmp = input[i];
while (i > 0)
{
input[i] = input[i - 1];
i--;
}
input[i] = tmp;
}
With a string of length n, you have 2 in power of (n-1) different possible coma delimited strings. You can represent state of coma positions as an array of 0s and 1s, where 1 means that comma is needed at i+1 position. In this example: 123, would have the following:
0,0 => 123
0,1 => 12,3
1,0 => 1,23
1,1 => 1,2,3
the way you do it is you need introduce a variable of type
int k;
and increment it by 1 at each cycle, until
k<input.length-1
. To check whether the coma is needed you need to check condition:
(k>>1)&1==1
I would approach using the following steps:
1. Given the whole line doesn't fit memory, you can compact the line, by taking it in chunks and generating an MD5 hash on them
2. Apply merge sort on hashed lines
3. Go through the lines and check if
line[i]==line[i-1]
If a node of linked list contain only positive integers, then you can sort it in O(n), using Counting sort. And then print it in Ascending and Descending order. Solution complexity is O(n).
- Marcello Ghali June 10, 2015Do you consider condition, that no step is taken?
General question: why there is a such condition, that at n action, step might or might not be taken?
I would define the following method signature:
short* findMaxDiscountPeriods(const short * periods, const short * discounts)
, where
/// pointer to a periods array. Ex. day 1-5, 0001 1111 = 31
const short * periods
/// pointer to a corresponding discounts array
const short * discounts
method returns array with a sum of discounts. After only max values are printed.
#include <iostream>
using namespace std;
const int PeriodCounter = 3;
short* findMaxDiscountPeriods(const short * periods, const short * discounts)
{
static short results[sizeof(short) * 8] = {};
for (int i = 0; i < PeriodCounter; i++){
short k = 0;
short period = periods[i];
while (k < sizeof(short) * 8){
if (period & 1){
results[k] = results[k] + discounts[i];
}
period = period >> 1;
k++;
}
}
return results;
}
void printMaxDiscounts(const short* results)
{
short max = -1;
// find max
for (int i = 0; i < sizeof(short) * 8; i++){
if (results[i] > max){
max = results[i];
}
}
for (int i = 0; i < sizeof(short) * 8; i++){
if (results[i] == max){
cout << i << " : " << max<<"\n";
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
short periods[PeriodCounter] = { 31, 254, 24 };
short discounts[PeriodCounter] = { 10, 5, 20 };
short* maxRange = findMaxDiscountPeriods(periods, discounts);
printMaxDiscounts(maxRange);
return 0;
}
Complexity: O(numberOfPeriods*(max period))
- Marcello Ghali April 27, 2015I agree with your answer.
int numberOfPixelsGivenColor(QuadTree* t, bool col)
can be implemented as a trivial tree traversal.
- Marcello Ghali April 24, 2015consider words: key, keychain. 2 entries in a Dictionary are needed, however since they share common prefix - "key" they can be compacted using, say, prefix tree.
- Marcello Ghali April 21, 2015Trie can be used for this problem.
N - word n
L[n] - number of characters in N word
1. Iterate thru files, with N words and get next word. Complexity: L[n]
2. Build a trie along the way for next found word. Leafs contains number of word occurrence. Complexity L[n]
3. Keep a counter (or an array of 5 top mose) for the most frequent word
Overall complexity: L[n]*L[n]
Given:
? - any char
* - any string
wildmatch (agcbc, a*ba) is supposed to return 0, isn't it?
@Imran Khan, can you explain your solution or point us to a good resource?
- Marcello Ghali April 01, 2015how did you come up with this solution?
- Marcello Ghali March 31, 2015what if the min number would be at the very end? How do you fall back to prev. max difference with Highest number index>Lowest number index?
- Marcello Ghali March 31, 2015I'd like to look at O(n) solution, however here is the O(nlogn) solution:
1. Create a copy and sort the array asc.
2. Use 2 pointers: start, end.
3. Move 2 pointers to get the max difference, until max pair number have higher index, than min pair number.
copy of string (n) + sort (nlogn) + move pointers (n/2) = O(nlogn)
Got it, thanks!
- Marcello Ghali March 19, 2015Am I the only who didn't understand this task? Are those bar vertically or horizontally aligned on the graph? What does "maximum amount of storage" mean?
- Marcello Ghali March 19, 2015I like your solution, it doesn't require explicit extra-memory, however pascal method does the whole re-processing for every new row, having an array of previous values would dramatically improve performance. However this is the requirement.
- Marcello Ghali March 19, 2015is it an adjacency matrix, that is given?
- Marcello Ghali March 03, 20151. if extra memory is allowed, an array of lengths of 1st string can be used introduced. 3rd string would be computed as str1+str2. when the string needs to be resurrected back, you print first K chars from the 3rd string (K is taken from the lengths array), N-K chars would be your 2nd string.
2. if extra memory is not allowed you can put the length of str1 at the beginning of str3. say you have: str1="abc" str2="def", str3="3abcdef".
3. if non of above is not acceptable then I would ask what encoding is assumed?
1. if extra memory is allowed, an array of lengths of 1st string can be used introduced. 3rd string would be computed as str1+str2. when the string needs to be resurrected back, you print first K chars from the 3rd string (K is taken from the lengths array), N-K chars would be your 2nd string.
2. if extra memory is not allowed you can put the length of str1 at the beginning of str3. say you have: str1="abc" str2="def", str3="3abcdef".
3. if non of above is not acceptable then I would ask what encoding is assumed?
how about strings have unequal length?
- Marcello Ghali February 20, 2015Couple of questions:
1. By saying infinite value, did you mean streams are infinite?
2. Any memory restrictions?
pseudo code:
sting input="hotelfeat";
nextcombinations(position)
{
if (position=input.length) return;
string word;
int iterator = position;
while(iterator<input.length)
{
word=word+input[iterator];
if (isValidWord(try))
{
print(word);
}
iterator+=1;
}
nextcombinations(position+1);
}
what is the human readable format? Different countries have different readable format. would you please bring in example?
- Marcello Ghali February 19, 2015you need to specify how you sort file sizes asc. or desc. order. Using below order, algorithms doesn't work: {90, 70, 50, 20, 15}
- Marcello Ghali February 18, 2015pseudo code:
void parse(position)
{
while(position<input.length())
{
switch(input[position])
{
case '(':
parse(position+1);
parse(getNextAlternativeChar(position+1));
return;
case ')':
position(getNextCharPositionAfterCurrentBrace(position));
brake;
case ',':
position(getNextCharPositionAfterCurrentBrace(position));
brake;
default:
position+=1;
brake;
}
}
}
void main()
{
parse(0);
}
Would you please share more details?
- Marcello Ghali January 17, 2015The easiest way is to create a prefix tree. For instance, given a T="aababcabcd" you'll have one root with 2 nodes: "empty string" and "a", in turn "a" will have "b" as a child and "b" will have "c" as a child and "c" will have "d" as a child. Once you build a tree you can match it with your T, which gives you O(n) solution. See more more info about Suffix trees, Tries, Prefix trees
- Marcello Ghali June 26, 2013Hi, would you please clarify is this tree balanced? With currently having requirements it's ambiguous how to rebuild a tree, consider the following string: "ppppllppll". There are 2 trees, that meet given requirements.
- Marcello Ghali June 24, 2013Would you please clarify the task: is the task to find the largest sum of consequent numbers?
- Marcello Ghali June 24, 2013Nice solution! For those, who needs more info and prove on this approach, please see p.194 of Cracking The Coding Interview.
- Marcello Ghali June 24, 2013
Since BinaryTree doesn't maintain any ordering properties for child nodes, worst case is in-order successor is the leaf node, which means we have to traverse the whole tree and find the next closest biggest element with O(n) complexity.
- Marcello Ghali May 01, 2017However we can try to optimize it and look for the node that have n.val+1 along the traversal, since n.val + 1 will be guaranteed the next successor, since there is no smaller int between n.val and v.val + 1.