Interview

class was serialized and saved to disk; after that new class members were introduced; what will happen when new recompiled Java will read ond Serialazable file?

Futures in Java

http://shirleyisnotageek.blogspot.com/2016/11/frog-jump.html FROG JUMP

Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

The number of stones is ≥ 2 and is < 1,100.
Each stone's position will be a non-negative integer < 231.
The first stone's position is always 0.

At first, I thought it'a a DP problem, but it's not. The confusion comes from the question Jump game. However, since we have the restriction that the frog can jump only k - 1, k or k + 1 stones, whether the frog can jump to current stone has no relation to if frog can jump to next stone. It's possible that the current jump is 4, and next distance is 2, so you cannot jump to that stone.

A better way is to use recursion. From the first stone, we calculate what's the next stone the frog can jump to, if we find one, recursively call the function to calculate the next stone we can jump to, exit when we reach the last stone.

If you simply follow this manner, you will have TLE. So how to optimize. Since we are calculating forwardly, it's possible the same stone and largest jump it has has been calculated before, and which is definitely not working (otherwise we exit the function). We can use a visited set to track all stone and jumps we had, if we already see the combination, we directly return false because we know it's not going to work.

public boolean canCross(int[] stones) {

int len = stones.length;

if (len <= 1) { return true;}

if (len > 1 && stones[1] != 1) {return false;}

Set<string> visited = new HashSet<>();

return checkCanCross(1, 1, stones, visited);

}

private boolean checkCanCross(int start, int dist, int[] stones, Set<string> visited) {

if (start >= stones.length - 1) { return true;}

if (dist <= 0 || !visited.add(start + "," + dist)) {return false;}

for (int i = start + 1; i < stones.length; i++) {

int curr = stones[i] - stones[start];

if (curr > dist + 1) { break;}

if (curr == dist - 1 || curr == dist || curr == dist + 1) {

if (checkCanCross(i, curr, stones, visited)) {

return true;

}

return false;

}

http://www.ardendertat.com/2012/01/09/programming-interview-questions/

Find if there are duplicates in string

https://tproger.ru/problems/algorithm-to-determine-if-a-string-has-all-unique-characters/

public boolean isUniqueChars2(String str) {

boolean[] char_set = new boolean[256];

for (int i = 0; i < str.length(); i++) {

int val = str.charAt(i);

if (char_set[val]) { //символ уже был найден в строке

return false;

}

char_set[val] = true;

}

return true;

}

Можно слегка оптимизировать- возвращать false, если длина строки превышает количество символов в алфавите. В конце концов, не может существовать строки с 280 уникальными символами, если символов всего 256. Однако если это Unicode-строка, то такая оптимизация не очень поможет.

Another optimization:

int datatype has 32 bits?? so we can save space and do not create char_set array example if we know in advance what all chars are in range 'a-z'; int checker below can handle such alphabet:

public boolean isUniqueChars(String str) {

int checker = 0;

for (int i = 0; i < str.length(); i++) {

int val = str.charAt(i) - 'a';

if (checker & (1 << val)) > 0) {

return false;

}

checker |= (1 << val);

}

return true;

}

All permutations of string O(n*n!)

def permutations(word):

if len(word)<=1:

return [word]

#get all permutations of length N-1

perms=permutations(word[1:])

char=word[0]

result=[]

#iterate over all permutations of length N-1

for perm in perms:

#insert the character into every possible location

for i in range(len(perm)+1):

result.append(perm[:i] + char + perm[i:])

return result

Java

public static void permutation(String str) {

permutation_helper("", str); }
private static void permutation_helper(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation_helper(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}

}

Are 2 strings are Anagram?

Method 1 - sort letter in strings alphabetically and compare sorted strings

public boolean isAnagram(String firstWord, String secondWord) {

char[] word1 = firstWord.replaceAll("[\\s]", "").toCharArray();

char[] word2 = secondWord.replaceAll("[\\s]", "").toCharArray();

Arrays.sort(word1);

Arrays.sort(word2);

return Arrays.equals(word1, word2);

}

Method 2 - count the number of every char in first string ; traverse 2nd string and decrement the counter

public boolean permutation(String s, String t) {

if (s.length() != t.length()) {

return false;

}

int[] letters = new int[256];

char[] s_array = s.toCharArray();

for (char c : s_array) {

letters[c]++;

}

for (int i = 0; i < t.length(); i++) {

int c = (int) t.charAt(i);

if (--letters[c] < 0) {

return false;

}

return true;

}

Find first not repeated character in string

http://www.programmerinterview.com/index.php/java-questions/find-first-nonrepeated-character/

public static Character findFirstNonRepeated ( String input) {
Hashtable hashChar = new Hashtable( );
int j, strLength;
Character chr;
Object oneTime = new Object( );
Object twoTimes = new Object( );
strLength = input.length( );
for (j =0; j < strLength; j++){
chr = new Character(input.charAt( j ) );
Object o = hashChar.get(chr); // why not .contains(chr) ?
if (o == null) {
hashChar.put(chr, oneTime ); }
else if (o == oneTime){
hashChar.put(chr, twoTimes); }
}

for(j = 0; j < length; j++){
chr = new Character(input.charAt(j));
if ( hashChar.get(c) == oneTime) return chr;
}

return null; } }

Max stock profit from 1 operation: 1 buy and 1 cell after buy

stock_prices = [15, 2, 5, 10, 2, 9, 1] # 8, 1

def getMaxProfit(stock_prices):

#current_profit=0

day = 0

max_profit= stock_prices[1]-stock_prices[0]

min_price=stock_prices[0]

min_price_index=0

for index, price in enumerate(stock_prices):

if index == 0:

continue

current_profit = price-min_price

max_profit = max(max_profit, current_profit)

if max_profit == current_profit:

day = min_price_index

min_price = min(min_price, price)

if min_price == price:

min_price_index = index

return max_profit, day

print getMaxProfit(stock_prices)

def get_max_profit(stock_prices_yesterday):

# убедимся, что количество цен в массиве превышает 2

if len(stock_prices_yesterday) < 2:

raise IndexError('Получение прибыли требует как минимум двух цен в массиве')

# инициализируем min_price и max_profit

min_price = stock_prices_yesterday[0]

max_profit = stock_prices_yesterday[1] - stock_prices_yesterday[0]

for index, current_price in enumerate(stock_prices_yesterday):

# пропустим 0-ой элемент массива, так как min_price инициализирован.

# Также продавать в 0-й позиции нельзя

if index == 0:

continue

# вычисляем потенциальную прибыль

potential_profit = current_price - min_price

# обновляем максимальную прибыль

max_profit = max(max_profit, potential_profit)

# обновляем минимальную цену

min_price = min(min_price, current_price)

return max_profit

http://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-search-and-getrandom-in-constant-time/

http://shirleyisnotageek.blogspot.com/2016/10/insert-delete-getrandom-o1.html

For binary tree in addition to insert(), find() and delete implements getRandomNode():

This is wrong answer:
at each node with probability 1/3 return current node; with probability 1/3 go left; with prob 1/3 go right - it is wrong because root has chance 1/3 but it should be 1/N

Each node must know the size of nodes on left or right

Design stack which in addition to push(x) and pop() has a func which returns min() in O(n)

Approach#1 - to keep the min at each node:

class NodeWithMin{

int val;

int min;

NodeWithMin(int v, int min){ val=v; this.min=min}

}

class StackWithMin extends Stack<NodeWithMin>{

void push(int v){

int newMin=Math.min(value,min());

super.push(new NodeWithMin(value, newMin));

}

int min(){

if this.isEmpty() return Integer.MAX_VALUE;

else return peek().min;

}

Approach #2 to have extra stack which keeps min; it may occupy less space when solution above

Find 2 numbers in array which sum up to given target number

Find all pairs of integers within an array which sum to a specified value

Use a hash map from integers to integers. This algorithm works by iterating through the array.

On each element x, look up sum - x in the hash table and, if it exists, print (x, sum - x).

Add x to the hash table, and go to the next element.

public int[] twoSum(int[] numbers, int target) {

HashMap<Integer, Integer> map = new HashMap<>();

int[] result = new int[2];

for (int i = 0; i < numbers.length; i++) {

if (map.containsKey(numbers[i])) {

int index = map.get(numbers[i]);

result[0] = index;

result[1] = i;

break;

} else {

map.put(target - numbers[i], i); // put complimentary number as a key

}

} // end for

return result;

}

public static void printPairsUsingSet(
int[] numbers, int n){
if(numbers.length < 2){ return; }
Set set = new HashSet(numbers.length);
for(int value : numbers){
int target = n - value; // if target number is not in set then add
if(!set.contains(target)){ set.add(value); }
else { System.out.printf("(%d, %d) %n", value, target);
} } }

Given a string containing just the characters (, ), { , } [, ] determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]" are all valid but "(]" and "([)]" are not.

Traverse string and

if current char is on of the ( [ { then push to stack

if current char is one of the )]} then get element from stack and compare it to current char counterpart : ([{

public static boolean isValid(String s) {

HashMap<Character, Character> map = new HashMap<Character, Character>();

map.put(’(’, ’)’);

map.put(’[’, ’]’);

map.put(’{’, ’}’);

Stack<Character> stack = new Stack<Character>();

for (int i = 0; i < s.length(); i++) {

char curr = s.charAt(i);

if (map.keySet().contains(curr)) {

stack.push(curr);

} else if (map.values().contains(curr)) {

if (!stack.empty() && map.get(stack.peek()) == curr) {

stack.pop();

} else {

return false;

}

}}

return stack.empty();

}

Another solution: page 124 in Elements Programming Interview

Dequeue<Character> leftChars = new LinkedList<>();

loop over string

if current_char is open bracket:

add it to beginning of dequeue leftchars

else if current char is close bracket:

if leftchars is empty:

return false

else:

if current_char counterpart == 1st element of deque:

remove first element from dequeue

else: return false

Find if the array of integers contains any duplicates.

public boolean containsDuplicate(int[] nums) {

if(nums==null || nums.length==0) return false;

HashSet<Integer> set = new HashSet<Integer>();

for(int i: nums){

if(!set.add(i)){ return true;}

}

return false;

}

Arrange numbers to biggest number which is build as string concatenation in a[0], a[1], a[2], a[3]

public static Integer[] arrange(Integer[] a){

Arrays.sort(a, new Comparator<Integer>(){

public int compare (Integer o1, Integer o2){

return( Integer.parseInt(o1+""+o2) > Integer.parseInt(o2+""+o1) ? -1:1;

}

});

return a;

}

Find duplicates in unordered array

Array of numbers from 0 to n-1, one of the numbers is removed, and replaced with a number already in the array which makes a duplicate of that number. How can we detect this duplicate in time O(n)?

int A[N]; Create a second array bool B[N] too, of type bool=false. Iterate the first array and set B[A[i]]=true if was false, else - this is a duplicate.

But it can be done in O(n) time and O(1) space.(The algorithm only works because the numbers are consecutive integers in a known range):

In a single pass compute the sum of all the numbers, and the sum of the squares of all the numbers.

Subtract the sum of all the numbers from N(N-1)/2. Call this A.

Subtract the sum of the squares from N(N-1)(2N-1)/6. Divide this by A. Call the result B.

The number which was removed is (B + A)/2 and the number it was replaced with is (B - A)/2

You can do it in O(N) time without any extra space. Here is how the algorithm works :

Iterate through array in the following manner :

1. For each element encountered, set its corresponding index value to negative. Eg : if you find a[0] = 2. Got to a[2] and negate the value.
  1. By doing this you flag it to be encountered. Since you know you cannot have negative numbers, you also know that you are the one who negated it.
2. Check if index corresponding to the value is already flagged negative, if yes you get the duplicated element. Eg : if a[0]=2 , go to a[2] and check if it is negative.

Reverse string word by word

class Solution {

public String reverseWords(String s) {

if (s == null || s.length() == 0) {return "";}

// split to words by space

String[] arr = s.split(" ");

StringBuilder sb = new StringBuilder();

for (int i = arr.length - 1; i >= 0; --i) { //loop from the end

if (!arr[i].equals("")) {

sb.append(arr[i]).append(" ");

}

return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);

}

http://stackoverflow.com/questions/9734474/find-longest-substring-without-repeating-characters

1. Create start and an end lpointers for the string and an array for storing information for each character: did it occour at least once?
2. Start at the beginning of the string, both locators point to the start of the string.
3. Move the end locator to the right till you find a repetition (or reach the end of the string). For each processed character, store it in the array. When stopped store the position if this is the largest substring. Also remember the repeated character.
4. Now do the same thing with the start locator, when processing each character, remove its flags from the array. Move the locator till you find the repeated character.
5. Go back to step 3 if you haven't reached the end of string.

If the string only contains ‘a’-‘z’, you could save space by using a table of size 26 only. Assuming c is the character, then c-‘a’ will give you a value of 0-25 which can be used to index the table directly.

What happens when you found a repeated character? For example, what happens when you reach the second appearance of ‘c’?

When you have found a repeated character (let’s say at index j), it means that the current substring (excluding the repeated character of course) is a potential maximum, so update the maximum if necessary. It also means that the repeated character must have appeared before at an index i, where i is less than j.

Since you know that all substrings that start before or at index i would be less than your current maximum, you can safely start to look for the next substring with head which starts exactly at index i+1.

Therefore, you would need two indices to record the head and the tail of the current substring. Since i and j both traverse at most n steps, the worst case would be 2n steps, which the run time complexity must be O(n).

Below is the implementation in C++. Beware of the common mistake of not updating the maximum after the main loop, which is easy to forget.

int lengthOfLongestSubstring(string s) {

int n = s.length();

int i = 0, j = 0;

int maxLen = 0;

bool exist[256] = { false };

while (j < n) {

if (exist[s[j]]) {

maxLen = max(maxLen, j-i);

while (s[i] != s[j]) {

exist[s[i]] = false;

i++;

}

i++;

j++;

} else {

exist[s[j]] = true;

j++;

}

maxLen = max(maxLen, n-i);

return maxLen;

}

Overall: O(N)

Longest substring without repeating characters

https://algorithmstuff.wordpress.com/2013/08/08/longest-substring-without-repeating-characters/

public int lengthOfLongestSubstring(String s) {

int max = 0;

int count = 0;

int a[] = new int[26];

Arrays.fill(a, -1);

for(int i = 0; i < s.length(); ++i)

{

if(a[s.charAt(i) - 'a'] >= 0) {

int from = a[s.charAt(i) - 'a'];

count = i - a[s.charAt(i) - 'a'];

a = new int[26];

Arrays.fill(a, -1);

for(int j = from + 1; j <= i; ++j)

a[s.charAt(j) - 'a'] = j;

}

else {

count++;

a[s.charAt(i) - 'a'] = i;

}

max = Math.max(max, count);

}

return max;

}

public static String longestUniqSubString(String input){

HashSet<Character> set = new HashSet<Character>();

String longestOverAll = "";

String longestTillNow = "";

for (int i = 0; i < input.length(); i++) {

char c = input.charAt(i);

if (set.contains(c)) {

longestTillNow = "";

set.clear();

}

longestTillNow += c;

set.add(c);

if (longestTillNow.length() > longestOverAll.length()) {

longestOverAll = longestTillNow;

}

return longestOverAll;

}

http://www.programmerinterview.com/index.php

http://www.amazon.com/s/ref=nb_sb_noss_1?url=search-alias%3Daps&field-keywords=coding+interviews

http://www.reddit.com/r/programming/comments/2zw9ql/the_terrible_technical_interview/

http://www.jasq.org/just-another-scala-quant/inverting-binary-trees-considered-harmful

http://gurmeet.net/puzzles/

http://gurmeet.net/computer-science/linear-time-algorithms/

https://news.ycombinator.com/item?id=9243169 INTERVIEW

https://www.talentbuddy.co/blog/coding-interview-big-data-companies/

http://www.grokit.ca/spc/computer_science_review/

http://www.cs.ucr.edu/~lyan/c++interviewquestions.pdf

http://hackercs.com/streams/Computer-Science-Challenges/

http://www.mytechinterviews.com/

http://interviewquestionsaz.blogspot.com/

http://www.restlessprogrammer.com/2013/09/hacking-coding-interview.html

http://www.daemonology.net/blog/2012-10-17-software-development-final-answers-part-1.html

http://www.daemonology.net/blog/2012-10-31-software-development-final-answers-part-2.html

http://www.daemonology.net/blog/2013-01-26-software-development-final-answers-part-3.html

http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Practice_Questions_Person_A.pdf

http://sim0nsays.livejournal.com/36466.html#cutid1

http://www.decompile.com/interview/C%2B%2B_Interview_Answers_Page_02.htm

http://codesam.blogspot.com/

https://github.com/rcasto/C---Cracking-the-Coding-Interview-Solutions

http://franciscoraulortega.com/cracking-the-code-cpp1/

http://www.leetcode.com/

http://www.careercup.com/page?pid=microsoft-interview-questions

http://www.geekinterview.com/question_details/18138

http://courses.csail.mit.edu/iap/interview/materials.php

http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

http://eyther.com/kasner/ fixed points

Return random element from list - reservoir sampling?

A probability problem. The easiest solution is to traverse the whole list, find the count (number of nodes in the list) and randomly pick one node with 1 / count probability. But if the list is too long, it will be too hard to get the length. One approach is to keep counting and choose the position at 1 / count. Traverse through the whole list and return the last number. The intuition is, for any number x, the probability is : 1 / x * (x / (x + 1))... (n - 1)/n = 1 / n.

public class Solution {

ListNode head;

Random random;

/** @param head The linked list's head.

Note that the head is guaranteed to be not null, so it contains at least one node. */

public Solution(ListNode head) {

this.head = head;

random = new Random();

}

/** Returns a random node's value. */

public int getRandom() {

ListNode curr = head;

int toReturn = 0;

for (int cnt = 1; curr != null; cnt++, curr = curr.next) {

if (random.nextInt(cnt) == 0) {

toReturn = curr.val;

}

return toReturn;

}

Find largest 1 million numbers in 1 billion numbers

http://en.wikipedia.org/wiki/Partial_sorting

http://stackoverflow.com/questions/2933758/priority-queue-with-limited-space-looking-for-a-good-algorithm

1) Sort and take 1st million O(n log n)

2) Create Min Heap with first million

For each remaining number insert into mean heap and delete the minimum value from heap

O(n log m) where m = 1 million

3) Selection runk algo: O(n)

Pick a random element in the array and use it as a ‘pivot’. Move all elements smaller than that element to one side of the array, and all elements larger to the other side.

If there are exactly i elements on the right, then you just find the smallest element on that side.

Otherwise, if the right side is bigger than i, repeat the algorithm on the right.

If the right side is smaller than i, repeat the algorithm on the left for i – right.size().

public List<integer> topKFrequent(int[] nums, int k) {

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

PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(new Comparator<map .entry="" integer="" lt="" nteger="">>() {

@Override

public int compare(Map.Entry<Integer, Integer> first, Map.Entry<Integer, Integer> second) {

return second.getValue() - first.getValue();

}

});

Map<Integer, Integer> frequency = new HashMap<>();

for (int n : nums) {

frequency.put(n, frequency.containsKey(n) ? frequency.get(n) + 1 : 1);

}

for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {

queue.add(entry);

}

int size = 0;

while (size < k) {

rst.add(queue.poll().getKey());

size++;

}

return rst;

}

Find largest sum subarray. Kadane’s Algorithm

http://www.geeksforgeeks.org/archives/576

#include <stdio.h>

int getMaxSum(int *arr, size_t len, size_t &start, size_t &end) {

start = end = 0;

size_t ti = 0;

int sum = 0;

int max_sum = arr[0];

for(size_t i = 0; i < len; ++i) {

sum += arr[i];

if(max_sum < sum) {

max_sum = sum;

start = ti;

end = i;

} else if(sum < arr[i]) {

sum = arr[i];

ti = i + 1;

}

return max_sum;

}

/* Driver program to test above functions */

int main() {

int array[5] = {3,0,2,2,-1};

size_t len=5;

size_t start, end;

int maxsum = getMaxSum ( array, len, start, end);

printf("\n sum=%d start=%d end=%d ", maxsum, start, end);

return 0;

}

Power sets http://en.wikipedia.org/wiki/Powerset is set of all subsets (total 2^n)

Power set of a set with 1 element has: 2 subsets, , they are: {} and {1}

Power set of a set with 2 element has: 4 subsets, they are: {} {1} {2} {1,2}

Power set of a set with 3 elements, has: 2**3=8 subsets, they are:

1 set with 0 elements

3 sets with 1 element

3 sets with 2 elements

1 set with 3 elements.

The power set of a set S is the set of all subsets of S including the empty set and S itself. For example, the power set of {1, 2, 3} is {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Previously, I wrote about how you can generate the power set using a recursive algorithm. This time I'll show you how to use iteration.

Recall, that when we are generating a set for the power set, each element can either be in the set or out of the set. In other words, each set can be represented in binary form, where 1 means that the element is in the set and 0 means that it is not. For example, given a set {a, b, c}, the binary string 101 would represent {a, c}.

Generating the power set just comes down to generating all numbers from 0 to 2^n (since there are 2^n possible subsets) and converting the binary representation of the number into the set!

Here is the algorithm:

public static <E> List<List<E>> powerSet(final List<E> list) {

final List<List<E>> result = new ArrayList<>();

final int numSubSets = 1 << list.size(); // 2^n

for (int i = 0; i < numSubSets; i++) {

final List<E> subSet = new ArrayList<>();

int index = 0;

for (int j = i; j > 0; j >>= 1) { // keep shifting right

if ((j & 1) == 1) { // check last bit

subSet.add(list.get(index));

}

index++;

}

result.add(subSet);

}

return result;

}

Implementation #1: Recursion

FIRST = S[0]

REST = S[1, ... , n]

Compute all subsets of REST and put them in ALL_SUBSETS.

For each subset in ALL_SUBSETS, clone it and add FIRST to the subset

Implementation #2 uses mask: http://compprog.wordpress.com/2007/10/10/generating-subsets/

If you have the a set of n elements, a valid mask would be an array of n boolean (true/false; 1/0) elements. When apply a mask to a set,

check each element (e) in the set and the corresponding one in the mask (m): if m is true(1), you add e to the result, otherwise, ignore it.

To generate all the subsets of a set of n elements, you first have to generate all the possible 2^n masks of the set and then apply them

#include <stdio.h>

/* Applies the mask to a set like {1, 2, ..., n} and prints it */

void printv(int mask[], int n) {

int i;

printf("{ ");

for (i = 0; i < n; ++i)

if (mask[i])

printf("%d ", i + 1); /*i+1 is part of the subset*/

printf(" } \n");

}

/* Generates the next mask */

int next(int mask[], int n) {

int i;

for (i = 0; (i < n) && mask[i]; ++i)

mask[i] = 0;

if (i < n) {

mask[i] = 1;

return 1;

}

return 0;

}

int main(int argc, char *argv[]) {

int n = 3; //out set size

int mask[16]; /* 16 is 2^3 */

int i;

for (i = 0; i < n; ++i)

mask[i] = 0;

/* Print the first set */

printv(mask, n);

/* Print all the others */

while (next(mask, n))

printv(mask, n);

return 0;

}

Random number generator

https://www.quora.com/How-do-you-design-a-rand7-function-using-a-rand5-function

int rand2() {
int x = rand5();
if x == 4 return rand2(); // restart
else return x % 2; // if x = 0,1,2,3
}
int rand7() {
int x = rand2() * 4 + rand2() * 2 + rand2();
if (x == 7) return rand7(); // restart
else return x;
}

Generate a random number between 1 and 7, given a generator a random number between 1 and 5

In order to generate a random number between 1 and 7, we just need to uniformly generate a larger range than we are looking for and then repeatedly sample until we get a number that is good for us. We will generate a base 5 number with two places with two calls to the RNG.

public static int rand7() {

while (true) {

int num = 5 * (rand5() - 1) + (rand5() - 1);

if (num < 21) return (num % 7 + 1);

}

Convert unfair coin to fair coin

http://www.reddit.com/r/programming/comments/lisma/how_to_turn_a_biased_coin_into_a_fair_coin/

No matter the bias, the odds of getting a Heads then Tails is always exactly the same as getting Tails then Heads.

The answer is to flip twice. If you get HH or TT, throw the result away and start over. If you get HT or TH, return the first flip as your result. This algorithm transmutes an unfair coin into a perfect, though inefficient, Fair Coin.

Split coins in 2 groups with same number of heads-up without seeing the coins

Given: there are n heads and any number of tails on the table.

Select any n coins. This set will contain m heads, where m is between 0 and n inclusive, and n - m tails. The other n - m heads will be in the remaining coins.

We now have two piles: the selection of n coins with n-m tails and the remainder with n-m heads. All we have to do is flip the selection so that the n-m tails become n-m heads, the same number as the heads in the remainder.

Flipping puzzle

https://news.ycombinator.com/item?id=9256187

http://www.solipsys.co.uk/FlippingPuzzle/AnotherFlippingPuzzle.html

http://habrahabr.ru/post/250585/

Write a method to print the last K lines of an input file

create extra space for K lines and then store each set of K lines in the array. So, initially, our array has lines 0 through 9, then 1 through 10, then 2 through 11, etc (if K = 10). Each time that we read a new line, we purge the oldest line from the array. Instead of shifting the array each time (very inefficient), we will use a circular array.

This will allow us to always find the oldest element in O(1) time.

string L[K];

int lines = 0;

while (file.good()) {

int res = getline(file, L[lines % K]); // read file line by line

++lines;

}

// if less than K lines were read, print them all

int start, count;

if (lines < K) {

start = 0;

count = lines;

} else {

start = lines % K;

count = K;

}

for (int i = 0; i < count; ++i) {

cout << L[(start + i) % K] << endl;

}

All permutations of the string O (n * n!)

http://www.geeksforgeeks.org/archives/767

# include <stdio.h>

/* Function to swap values at two pointers */

void swap (char *x, char *y) {

char temp;

temp = *x;

*x = *y;

*y = temp;

}

/* Function to print permutations of string takes three parameters:

1. String

2. Starting index of the string

3. Ending index of the string.

void permute(char *a, int i, int n) {

int j;

if (i == n)

printf("%s\n", a);

else {

for (j = i; j <= n; j++) {

swap((a+i), (a+j));

permute(a, i+1, n);

swap((a+i), (a+j)); //backtrack

}

/* Driver program to test above functions */

int main() {

char a[] = "ABC";

int str_len=2;

permute(a, 0, str_len);

return 0;

}

PUZZLES

http://profile.iiita.ac.in/pkmallick_03/adfaqpublish.html

http://careercup.com/

http://geeksforgeeks.org/

http://stackoverflow.com/questions/tagged/interview-questions?page=1&sort=votes&pagesize=35

find top 10 in upcoming stream of numbers (heap data structure)

permutate string

find duplicates in array

connect dots

bisect rectangle with cut

Interview

http://crack5e.info/

http://mycareerstack.com/

http://www.mytechinterviews.com/

http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

http://xeno-by.livejournal.com/38121.html

http://hackercs.com/streams/Computer-Science-Challenges/

http://stevenatkinson.wordpress.com/2011/04/20/software-engineer-seeks-jobs-in-the-silicon-valley-an-experience/

http://www.reddit.com/r/programming/comments/guokk/software_engineer_seeks_jobs_in_the_silicon/

http://sites.google.com/site/vijaytechi/interview

http://michaelspiro.wordpress.com/2010/06/07/the-t-cover-letter-the-only-type-worth-sending/

http://users.livejournal.com/_winnie/296263.html

http://www.careercup.com/page?pid=microsoft-interview-questions

http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other

Condition that 2 rectangles are NOT overlapping:

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&

RectA.Y1 < RectB.Y2 && RectA.Y2 > RectB.Y1)

EGG-DROPPING

http://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle

http://www.reddit.com/r/programming/comments/7evy4/programmer_interview_questions_two_bowling_balls/c06hdwh

http://www.datagenetics.com/blog/july22012/index.html

http://qntm.org/bulbs

http://news.ycombinator.com/item?id=4274631

http://artemgolubev.com/wp-content/uploads/2009/07/the-problem-of-eggs-and-a-building1.pdf

http://possiblywrong.wordpress.com/2012/01/08/light-bulb-puzzle-solution/

#include <stdio.h> #include <algorithm> #include <vector> struct State{ int answer; int where; bool calculated; State() : answer(0), where(0), calculated( false ) {} }; int eggs( std::vector< State >& t, int total ){ if ( t[total].calculated ){ return t[total].answer; } int best = total + 1; int where = 1; for ( int i = 1; i <= total; i++ ) { int current = 1 + std::max( i - 1, eggs( t, total - i ) ); if ( current < best ){ best = current; where = i; } } t[total].answer = best; t[total].where = where; t[total].calculated = true; return best; } int main(){ int total = 100; std::vector< State > t( total + 1 ); int ans = eggs( t, total ); printf( "%d\n", ans ); int floors = total; int w = 0; while ( floors > 0 ){ w += t[ floors ].where; printf("%d ", w ); floors = floors - t[ floors ].where; } printf("\n"); return 0; }

Page updated

Google Sites

Report abuse