CareerCup

def find_duplicate(arr):
    for i in range(len(arr)):
        while arr[i] != i:
            if arr[arr[i]] == arr[i]:
                return arr[i]
            else:
                buf = arr[i]
                arr[i] = arr[arr[i]]
                arr[buf] = buf

    return None

def reverse(s):
    l = list(s)
    l2 = [c for c in l if c != ' ']
    j = 0

    for i in range(len(l) - 1, -1, -1):
        if l[i] == ' ':
            continue
        else:
            l[i] = l2[j]
            j += 1

    return ''.join(l)

This is solution

y = ((x - 1) & a) | (~(x - 1) & b)

Sort an array.

Then for each element a[i] and remained array a[i + 1:] solve two sum problem with sum equal to -a[i]

For english you have 26 files, each is responsible for particular character. If word contains this character then it is presented there. "good" is presented in file g,o and d. Each record also contains a field how much particular character have occured in this word.
For good g - 1, o - 2, d - 1. Each file contains word in sorted order. So when you receive and request you find intersection of c1 and c2 in O(n), and so on. Also you check quantity of particular character in the words.

You inrecment both i and j. But what if you can increment only the i and next maximum will be bigger then B1[j]?

Please clarify question. How to find rectangle that contains a point?

Please could you give some examples.

You meant double checking without volatil or with?

Please, could you explain vulnerability of volatile&double-checking initilization usage?

Maybe you should use double checking and synchronized section instead of synchronizing whole method.

First sort them.

Them calculate cumulative sum.
If some element a[i] is greater than sum + 1 then there is a gap between them. So number sum + 1 cannot be formed - this is the answer.

First sort them.

Them calculate cumulative sum.
If some element a[i] is greater than sum + 1 then there is a gap between them. So number sum + 1 cannot be formed - this is the answer.

def find(a):
	sum = 0
	
	for i in range(len(a)):
		sum += a[i]
		 
		if sum < a[i] - 1:
			return sum + 1
	return sum + 1

def check(pattern, text, d):
    if len(pattern) == 0 and len(text) == 0:
        return True

    if len(text) == 0 or len(pattern) == 0:
        return False

    if pattern[0] in d:
        tmp = d[pattern[0]]

        if len(tmp) > len(text) or text[:len(tmp)] != tmp:
            return False
        else:
            return check(pattern[1:], text[len(tmp):], d)
    else:
        for i in range(1, len(text)):
            d[pattern[0]] = text[:i]
            if check(pattern[1:], text[i:], d):
                return True
            del d[pattern[0]]

    return False

Please, could you explain in details how to apply branch and bound approach.

All you need it is to found the biggest such palindrone that s = prefix + palindrom.
You can do it in O(N^2), but it is better to use Manacher algorithm for finding all subpalindromes in O(N) and add reversed prefix to the and.

s = prefix + palindrome + reverse(prefix)

Also how to restore numbers, that were used to make a solution.

Please, coult you explain your solution?

Always shrink occupied seats to median

def count_moves(s):
    lst = []

    for i in range(len(s)):
        if s[i] == 'X':
            lst.append(i)

    med = len(lst) / 2

    left_count = 0
    right_count = 0

    for i in range(med - 1, -1, -1):
        left_count += lst[med] - lst[i] - (med - i)

    for i in range(med + 1, len(lst)):
        right_count += lst[i] - lst[med] - (i - med)

    return left_count + right_count

def encode(strings):
    result = ''
    count = str(len(strings))
    result += count + '|'

    for s in strings:
        result += str(len(s)) + '|' + s

    return result



def decode(s):
    index = s.find('|')
    count = int(s[:index])
    result = []

    s = s[index + 1:]

    for i in range(count):
        index = s.find('|')
        count = int(s[:index])
        s = s[index + 1:]
        result.append(s[:count])
        s = s[count:]

    return result

def encode(strings):
    result = ''
    count = str(len(strings))
    result += count + '|'

    for s in strings:
        result += str(len(s)) + '|' + s

    return result



def decode(s):
    index = s.find('|')
    count = int(s[:index])
    result = []

    s = s[index + 1:]

    for i in range(count):
        index = s.find('|')
        count = int(s[:index])
        s = s[index + 1:]
        result.append(s[:count])
        s = s[count:]

    return result

N!/(k1! * k2! * ... * kn!) isnt it? permutation with repeatitions.

Algo
1)find first element ')(' from the right side of the string
2)substitute it by '()'
3) count the balance from left to current position
4)add so many close parenthesis as you need to keep the balance
5)Fill the rest with ()

You can use only the one key to,delete or insert an element or any combination of them? If second,i thinnk you should use some spatial data structure like KD-tree.

I think the answe is product (n - i) where i from 1 to k plus one, where one is 0 of swaps.

Give an example,please.

Just a zig-zag traverse?

We can use simple Bubble sort.

public void sort(Node head) {
	cur = Head;
	cur_next = cur.next;
	count = 0;

	while(cur != null) {
		cur= cur.next;
		count++;
	}

	for(int i = 0;i < count ;i++){
		cur = head;
		cur_next = cur.next;
		
		for(int j = 0;j < i;j++) {
			if(cur.value < cur_next.value){
				swap_values(cur,cur_value);
			}
		}
	}
}

You meant that final list should be sorted?

I think is even number has appeared at least once in [x,y) then mumber will be even.

Explain the idea, please

Divide it in n parts of equal length , then if some points are equals unioun them . Finally on need to have n points with different values, Than do binary search in each of interval.

DFS will be ok in acyclic graphs.

Simple, user in-order and pre-order traversal to serialize and then deserialize tree.

what does it mean transition point?

LCA problem?

def subsets(target,left,stack,seq,sum):
    for i in range(left,len(seq)):
        if sum + seq[i] <= target:
            stack.append(seq[i])
            sum += seq[i]

            if sum  == target:
                print stack


            subsets(target,i + 1,stack,seq,sum)
            sum -= stack.pop()

public boolean findCycle(List<Tuple> tuples) {
	Map<Character,Character> map = new HashMap();

	for(Tuple t : tuples) {
		if(map.get(t.getChild() != null) {
			return false;
		} else {
			map.put(t,getParent());
		}

		return true;
}

def find_pivot(array):
    left = 0;
    right = len(array) - 1
    cur = (right + left) / 2

    while left < cur < right:
        cur = (right + left) / 2

        if array[cur] <  array[right]:
            left = cur
        elif array[left] < array[cur]:
            right = cur


    return cur

You deen to write serialization. I've written something simular in Java. All you need - it is resolve cyclic reference in order to reject infinite cycle copying. In java You can use identityHashCode and identityHashMap to store each node only once. And that build up list from them. You put the node to the identyty hash Map. Then you looks to pointer. If nodes they are referenced to are in the map - then store their hashcode else put theese node to map and store their hash code.
from
Node next -> some other node
to
Node next -> 0xAB23FD133

use multidimensional indexed trees like KD-tree etc.
Or maintain bit index and make queries with bit operations.

Mutex allow only one thread, semaphore has a counter of threads it can allow to critical section of code.

public void visit(Node* root, int& number,int n) {
if(root == null) return;

visit(root->left,number,n);

if(number == n) {
cout<<root->value;
return;
}
number += 1;
visit(root->right,number,n);
}

int number = 0;
visit(root,number,3);

public class PhomeNumbers {

    public static List<List<Character>> initData() {
        List<List<Character>> list = new ArrayList<List<Character>>();

        list.add(new ArrayList<Character>());//0
        list.add(new ArrayList<Character>());//1
        list.add(new ArrayList<Character>());//2
        list.add(new ArrayList<Character>());//3
        list.add(new ArrayList<Character>());//4
        list.add(new ArrayList<Character>());//5
        list.add(new ArrayList<Character>());//6
        list.add(new ArrayList<Character>());//7
        list.add(new ArrayList<Character>());//8

        int j = 0;

        for(int i = 0;i < 9;i++) {
            for(int k =0;k < 3 && j < 26;k++,j++) {
                list.get(i).add((char)('a' + j));
            }
        }

        return list;
    }

    public static void sequence(int[] numbers,int pos,List<List<Character>> phone,char[] str) {
        if(pos == numbers.length) {
            for(Character ch : str) {
                System.out.print(ch);
            }
            System.out.println();

            return;
        }

        for(int i = 0;i < phone.get(pos).size();i++) {
            str[pos] = phone.get(pos).get(i);
            sequence(numbers,pos + 1,phone,str);
        }
    }

    public static void main(String[] args) {
        List<List<Character>> list = initData();
        int[] numbers = new int[]{1,2};
        char[] str = new char[numbers.length];

        sequence(numbers,0,list,str);
    }
}

public class Combinations {

    public static List<String> combinations(int n, int k) {
        List<String> list = new ArrayList<String>();
        boolean flag = false;

       List<Integer> cur = new ArrayList<Integer>(k);

        for (int i = 0; i < k; i++) {
            cur.add(i + 1);
        }
        list.add(cur.toString());

        for (int i = k - 1; i >= 0; i--) {
            while (cur.get(i) < (n - (k - i) + 1)) {
                cur.set(i, cur.get(i) + 1);

                for (int j = i + 1; j < k; j++) {
                    cur.set(j, cur.get(j - 1) + 1);
                }

                list.add(cur.toString());
            }
        }

        return list;
    }

    public static void main(String[] args) {
        List<String> list = combinations(5,3);

        for(String s : list) {
            System.out.println(s);
        }
    }
}

I hav idea how to decide whether we can do it or not. We need to factorize number in prime factors. If among of themat least one prime that is greater than 10 - we cannot do it .

Use radix sort. And then find first a[i] != a[i + 1]. Complexity is O(n * k) where K = 32. Actually if all numbers are positive it can be done in constant memory.

Sort chunks of data unsing radis sort in O(k*n) complexity. Then merge them.

Would you give an example.