CareerCup

Write a function to evaluate a string that has only integers, and operators '+' & '*'. The evaluation should be done in a single pass. For example passing "3*2+5*6" should result in this function returning 36.

Write a function fix a loop in the linked list based on the assumption that the linked list is sorted.

Write a function to perform string replace without using any inbuilt functions.

Find the maxProduct of three numbers from a given integer array.
1. Handle all the cases
2. Interviewer was looking for a complete code

public int maxPro()
{ // -5, -4, -3, -2 , 0
    Int array[] = new Int[]{4,5,6,0,-5,-7,-2,-10};
    Arrays.sort(array);
    // -10,-7,-5,-2,0,4,5,6
    int count =0;
    for(int i =0; i<array.length();i++){
        if(array[i]<0)
            count = count+1;
    }
    int maxProduct =1;
    if ( array.length()<3){
        return -1;
    }
    else if( array.length()>=3 ){
        int a=1; b=2;
              if(count>=2){
                  a = array[0]*array[1]*array[array.length-1];
                  b = array[array.length-1]*array[array.length-2]*array[array.length-3];
                  maxProduct = Math.max(a,b);
                  
              }
              else if (count == 0 || count == 1 || count == array.length()){
                  maxProduct = array[array.length-1]*array[array.length-2]*array[array.length-3];
              }
                      
    }        
    return maxProduct;
}

Given a string, find the longest possible even palindrome (length of palindrome is even) from it.
Eg:
Input: abcicbbcdefggfed
Output: defggfed (length is 8)

Available palindromes are
1) bcicb - has odd length
2) cbbc - even length
3) defggfed - longest palindrome with even length

This question was asked in a telephonic interview for my friend. I will be posting his solution in a day.

following coins: half dollar, quarters,dime, nickel and penny. Print all the possible combinations of coins that will equal to one dollar.(Ex : (2) half-dollar , (4) quarter dollar etc )..

Flatten a List<List<Integer>> in Java and implement the hasNext() and next() methods.
e.g. [[6,8],4] should return true when at 6, 8 and false at 4.

Implement a simple regex parser which, given a string and a pattern, returns a boolean indicating whether the input matches the pattern. By simple, we mean that the regex can only contain one special character: * (star). The star means what you'd expect, that there will be zero or more of any character in that place in the pattern. However, multiple consecutive stars are allowed. Some examples of valid input (and expected output):

f(a*b, acb) => true
f(abc*, abbc) => false
f(**bc, bc) => true

Write a service or services to support tic-tac-toe between two players, on an infinite board. Normal rules apply (i.e. three in a row to win), but the players are not limited to a 3X3 board and can choose to place an X or an O in any arbitrary, positive (i, j) position. Solution should be as space and time efficient as possible. Your service is only responsible for maintaining and updating the state of the board between two players, given their sequence of moves.

Q: Do you know what is a Binary tree? How would you go about coding for addition of a new element to Binary tree?
A: I asked if they want a Binary Tree or a BST? When he said BST I just said we can have a recursive function in which we pass the root of the tree and see if the value to be added is smaller or bigger than the root, and depending on result, we go to left or right of the tree, assuming the left (or right) is not null. If null, just use new to create a memory location, put the value, and use the left reference of the root to link to this new memory. Simple basic stuff.

I Got this Crazy Question on PHONE INTERVIEW AT GOOGLE:

Design and implement a class to generate random numbers in an arbitrary probability distribution given by an array of integer weights, i.e. for int[] w return a number, n, from 0 to w.length - 1 with probability w[n] / sum(w). Using an existing random number generator with a uniform distribution is permitted.

Example distribution:
w = 1, 2, 3, 2, 1

Example probabilities:
w / sum = 1/9, 2/9, 1/3, 2/9, 1/9

Example results:
n = 0, 1, 2, 3, 4

Documentation:

Class java.util.Random

public int nextInt(int n)

Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.

Parameters:
n - the bound on the random number to be returned. Must be positive.
Returns:
the next pseudorandom, uniformly distributed int value between 0 (inclusive) and n (exclusive) from this random number generator's sequence
Throws:
IllegalArgumentException - if n is not positive

Reverse words in a sentence.
Ex:
Input: "reverse the word"
Output: "word the reverse"

How can you implement queue?
I told him about list, array, stack implementation of queue.

If an N X N matrix is given, print it in spiral order.
Example: Below is 5 X 5 matrix

i l o v e
d i n t e
n i e e p
a v w r i
m a x e c

Print in spiral order. Output is iloveepicexamandinterview

Setup:
Assume primitive Facebook. FB has Members.
class Member {
String name;
String email;
List<Member> friends;
}

Question:
Code printSocialGraph(Member m). Direct friends of m are Level 1 friends. Friends of friends are level 2 friends.....and so on
Print level 1 friends first. Then print level 2 friends....and so on

void printfriendsByLevel(Member m){

//Your code here

}

write a program to Generating Random Integer numbers without repetition ??

Each time a visitor requests a page from our website, our webserver writes a log entry recoding the visitor's identity and the kind of page requested. Entries are written in chronological order to a plain-text file, with one entry per line. The format of each entry is:

user-id page-type-id

User IDs are arbitrary strings that uniquely represent a given user; if a user visits multiple pages, each log entry will have the same user ID. Page type IDs are arbitrary strings that uniquely represent a given kind of page on our site, such as the homepage, a product detail pages, or the shopping cart. Tons of users visit our website, but there are only a few dozen types of pages.

We can use our weblogs to answer questions about user behavior. One interesting question is: what is the most common three page sequence through the site? E.g., if the most common pattern is to buy items advertised on the home page of the site, we might see the most common three page sequence as "Homepage -> ProductDetailPage -> ShoppingCart". However, if customers spend a lot of time browsing the "Customers who bought this item also bought" feature, we might see the most common three page sequence as "ProductDetailPage -> ProductDetailPage -> ProductDetailPage".

Attached is a sample log file for your reference. Within the first 10 lines of the sample, customer "234" travels through the sequences "Listmania -> ProductDetail -> Checkout" and "ProductDetail -> Checkout -> HomePage" once each.

For the sake of this test feel free to assume that everything will fit in memory. Do keep in mind that given the size of our data sets, performance has to be considered, also, we will be looking at more than just correct output..

Input is a number of words. Construct a listing of valid 6-letter words. You have access to bool IsValid(const string& word); Implement Insert() and Get() for this listing.

Escape strings. Convert special ASCII characters to form of ‘\ooo’, where ‘ooo’ is oct digit of the corresponding special character.
The ascii characters that smaller than space are regarded as special characters.

Write a program to find the first occurance of one string into another : it is okay to write a O(n2) algorithm

Write a program to print the powerset.
E.g. given this set {1,2,3}, it will print {},{1},{2},{3},{1,2},{1,3}, {2,3}, {1,2,3}

Write a program to clone a graph

Find the k'th largest element in a binary search tree. Write code for

struct Node {
    int val;
    struct Node *left;
    struct Node *right;
} Node;

Node * kth_largest(Node *root, unsigned int k);

How will you design Game of life - http://en.wikipedia.org/wiki/Conway's_Game_of_Life

We have a coding system from alphabets to numbers where a=1, b=2, ...z=26. You are given a string of digits as an input. Write a function that will compute the number of valid interpretations of the input.

Here are some examples:
f('11') = 2 Actual interpretations: ('aa', 'k')
f('111') = 3 Actual interpretations: ('aaa', 'ak', 'ka')

You are given two array lists. One Array List contains information of latitudes and longitudes of all the amazon stores and another array list contains all the possible values of latitudes and longitudes. Find an optimal way to find out all the latitudes and longitudes which are nearest to one pair of amazon store.
ArrayList<latitude, longitude> AmazonStore;
ArrayList<latitude, longitude> World;

Write a function that gets a number n and prints out a random list
of numbers 1..n to the screen. For example:

randlist(5) : 1 5 3 2 4
randlist(6) : 4 6 1 5 3 2

This should be truly random (uniformly spread) and with a O(n) complexity.
Every number should appear only once. Random(n) is given as a tool you can use to generate a
single random number between 1-n

Write the following function
void drawLine(byte[] img, int len, int wid, int r, int x1, int x2)
such that you draw a line from x1 to x2 at row r.
len is the length and wid is the width of the image/canvas.
Setting a pixel on to draw the line is to set the corresponding bit on the img array
Each byte corresponds to 8 pixels, that is each pixel is a bit in the array

Print all the permutaion of a given string.

1) explain time\space complexity?

2) how can you improve time\space complexity?

Print all valid phone numbers of length n subject to following constraints:

1.If a number contains a 4, it should start with 4
2.No two consecutive digits can be same
3.Three digits (e.g. 7,2,9) will be entirely disallowed, take as input