## vodangkhoa

BAN USERGraduated from UT Austin. Working for Amazon.com

- 0of 0 votes

AnswerWhat is a pointer?

- vodangkhoa| Report Duplicate | Flag | PURGE

Ebay Software Engineer / Developer Terminology & Trivia - -3of 3 votes

AnswersGiven a Starting Node and Ending Node in a Graph where each Node has a pointer to its parent and all its children nodes. Find all the leaf nodes between the Starting and Ending Node.

- vodangkhoa| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 0of 0 votes

AnswersThere are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.

- vodangkhoa

ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm - 0of 0 votes

AnswersHow long it would take to sort 1 billion numbers? make any assumptions you wanted.. assume the computer would have more than 4 GB of RAM, so the array would fit in memory in its entirety, and the machine would run at 4 GHz.

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer - 0of 0 votes

AnswersGiven a list A with n elements, produce a list B with n elements such that the ith element of B is equal to the product of all elements except the ith in list A. Example: Given list A = [1, 2, 3], make a function f(x) such that f(A) = [6, 3, 2].

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm - 0of 0 votes

AnswersSuppose you have a huge file (few million entries). Each line has a name; an id and age, all three separated by a space. How do you go about sorting this and writing this in a sorted order in another file? Of course you can't read the whole thing in memory.

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm - 0of 0 votes

AnswersGiven an array having first n ints and next n chars.

- vodangkhoa

A= i1 i2 i3 ... in c1 c2 c3 ... cn

Write an in-place algorithm to rearrange the elements of the array as:

A = i1 c1 i2 c2 ... in cn| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm - 0of 0 votes

AnswersGiven two binary trees T1 and T2 which store character data, duplicates allowed. You have to devise an algorithm to decide whether the T2 is a subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes.

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm - 0of 0 votes

AnswersPrint all combinations of M members of a set of N elements in a sequence such that each set can be obtained from the previous set by deleting one member and adding one member.

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Coding Algorithm - 3of 3 votes

AnswersGiven a value and a binary search tree.

- vodangkhoa

Print all the paths(if there exists more than one) which sum up to that value. It can be any path in the tree. It doesn't have to be from the root.| Report Duplicate | Flag | PURGE

Microsoft Yahoo Software Engineer / Developer Trees and Graphs Coding Algorithm - 0of 0 votes

AnswersYou are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Testing - 2of 0 votes

AnswersGiven a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine?

- vodangkhoa

(eg given s1 = ABCD and s2 = CDAB, return true)

(given s1 = ABCD, and s2 = ACBD , return false)| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Coding Algorithm - 0of 0 votes

AnswersThere is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it's dropped from any floor below, it will not break. You're given 2 eggs. Find N, and minimize the number of drops for the worse case.

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Highbridge Capital Software Engineer / Developer Financial Software Developer Brain Teasers Algorithm - 1of 1 vote

AnswersFor small dataset (less than 200 elements), why is unsorted array has better performance than binary tree? This wasn't the case 20 years ago. (Hint: It has to do with computer architecture.)

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Computer Architecture & Low Level Data Structures - 0of 0 votes

AnswersImplement Atoi(char *str)

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Coding - -2of 0 votes

AnswersMerge two sorted array

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm - 1of 1 vote

AnswersGiven a binary tree where each node's value is a COLOR. A clump is formed when more than 3 COLORS are adjacent to each other. Return the total number of clumps in a binary tree.

- vodangkhoa| Report Duplicate | Flag | PURGE

National Instruments Software Engineer / Developer Coding - 1of 0 votes

AnswersA disk is partioned into two hemispheres colored in black and white and the disk is rotating.By appropriate positioning of sensors (A sensor can read the disk near it as black or white) we need to find the direction of the motion of the disk.

- vodangkhoa| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Computer Architecture & Low Level - 0of 0 votes

AnswersAsked me about XML. XML was on my resume but I don't know much about it. I only have used it a few times. Note to self - take anything that I don't know too well about off my resume.

- vodangkhoa| Report Duplicate | Flag | PURGE

Bloomberg LP Software Engineer / Developer General Questions and Comments - 0of 0 votes

Answers3rd Interview - Technical. You have 5 basketball teams. You want them to play each other only once. Each team plays once a week. If a team plays a home game this week, They should play a aways game the coming week. How many weeks does it take for all the teams for play each other?

- vodangkhoa| Report Duplicate | Flag | PURGE

Intuit Software Engineer / Developer Math & Computation - 0of 0 votes

AnswersYour hardest class.

- vodangkhoa| Report Duplicate | Flag | PURGE

Boeing Software Engineer / Developer Experience - 0of 0 votes

AnswersQuestions about OOP, Design Patterns, Java, and C++. Just basic OOP questions like Pure Virtual Functions, Virtual Pointer Table, Abstract classes, Interfacce, Inheritance, Polymorphism.

- vodangkhoa| Report Duplicate | Flag | PURGE

IBM Software Engineer / Developer Terminology & Trivia - 0of 0 votes

Answers100 closed lockers. You begin by opening all 100 lockers. Next, you close every second locker. Then you go to every third locker and close it if it is open or open it if it is closed (call this toggling the locker). After your 100th pass of the hallway, in which you toggle only locker number 100, how many lockers are open?

- vodangkhoa| Report Duplicate | Flag | PURGE

Infosys Microsoft Software Engineer / Developer Brain Teasers

- 7 Answers
**PIE**For some who don't know what PIE is, PIE stand for Programming Interviews Exposed. It's a very popular interview book. I highly recommend it. I have interviewed with plenty high companies and I usually get at least 1 technical question that this book talked about. The 2nd edition of this book was released recently.

- vodangkhoa April 29, 2007| Flag | PURGE

Given N elements, if you insert the numbers into the Binary Tree in sorted order, its complexity is N^2. So the worse case is still N^2.

Balanced Binary Tree.

Given a number in a binary tree, its closest number greater than itself is the Min number of the Right Subtree, closest number less than itself is the Max number of the Left Subtree.

The complexity for this is still N Log N.

I do not think you can do this in N but I'm sure there's someone here that's really clever and prove me wrong.

Vel: For sorting, you should always suggest Quicksort whenever the data that you're sorting fits in Memory. Studies have shown that Quicksort is the fastest because of locality. Quicksort worse case is N^2 but people have devise methods to avoid this and it doesn't occur frequently. Read up on Quicksort?

Mergesort requires linear memory when you Merge.

The above method is Binary Search. Its worse case is log(n).

- vodangkhoa April 02, 2007What's secondary digonal of a matrix?

- vodangkhoa March 30, 2007if both head pointers are equal, increment head1 and head2

if they are not, increment the head pointer that was previously not incremented or the pointer that is BEHIND.

Quicksort has shown to be the quickest. Here is the link to the talk.

http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf

2^10 - 1

- vodangkhoa March 21, 2007This is right off wikipedia. A context switch is the computing process of storing and restoring the state (context) of a CPU such that multiple processes can share a single CPU resource.

Here is the article. http://en.wikipedia.org/wiki/Context_switch

This question has been discussed before.

http://www.careercup.com/question/?q=1d59aabd-8c9d-4915-8e0c-16bcaf83ce92

Twin primes are pairs of primes of the form (p, p+2).

- vodangkhoa March 12, 2007Yes! Each process has an address space. When the program exit, that piece of memory now becomes Free.

- vodangkhoa March 07, 2007This question is similar to this one (http://www.careercup.com/question/?q=b5f73ade-0cdc-40c3-80fa-da5fe544f072)

- vodangkhoa March 06, 2007http://en.wikipedia.org/wiki/Introsort

- vodangkhoa March 05, 2007Also check for the return value of Malloc. If it's null, you're out of memory.

- vodangkhoa March 04, 20071) malloc passed back a VOID pointer. You need to cast this pointer to whatever you want.

- vodangkhoa March 01, 2007I don't have the code anymore but there are a few things you need to watch out for.

1) malloc passed back a NULL pointer. You need to cast this pointer to whatever you want.

2) for string, need to allocate an extra byte for the end character.

3) double pointers.

4) (delete and malloc) and (free and new) don't go together

Standard DFS or BFS would solve this. Look this up on Wikipedia.

- vodangkhoa February 27, 2007Yes! It doesn't have to be hard to be an interview question, right?

let val = neg_infi.

val is equal or less than N.

if (array[i] <= N && array[i] > val)

val = array[i]

I'm not an intern anymore but I post more than just my questions. other questions I have seen on the web. please do the same :).

- vodangkhoa February 06, 2007No new zeros should be considered.

- vodangkhoa February 04, 2007Do you mean strstr?

- vodangkhoa February 02, 2007Yes! DFS and Preorder are equivalent.

BFS is a totally different beast compare to preorder, inorder, and postorder.

Here is the link to tree traversal algorithms.

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

That's a really neat solution. Good job!

- vodangkhoa February 01, 2007Given 4 5 6 7 1 2 3

first element: 4.

mid element: 7.

last element: 3.

We need to determine which part to search.

Consider there are two arrays:

4 5 6 7 and 7 1 2 3

If we are looking for 6, we know it falls under the first half. We know this by looking at the first and last element of each array.

void GenParen(int n){

//there are n * 2 curly braces

//there are n { and n }

char paren[n * 2]

GenParenH(&paren, n, 0, 0, 0);

}

void GenParenH(char *paren, int n, int lp, int rp, int index){

if (lp < n) {// if we haven't generated enough {

paren[index] = '{';

GenParenH(paren, n, l+1, r, index+1);

}

if (rp < lp) { //there are more { than }

paren[index] = '}';

GenParenH(paren, n, l, r+1, index+1);

}

}

A similar question with answers.

http://www.careercup.com/question/?q=56966655-4b2c-4957-b5e0-68b06faee30a

This is a linked list. You don't have random access memory. To find the median, you need to traverse the linked list which is N.

To claim that you can sort a N sorted lists where each list has K elements in Nlog(K) is similar to claiming that you can sort two linked lists in N Log(2).

Linked list 1: 1 5 9

Linked List 2: 3 4 8

I do not think it can be done with the above linked lists.

I don't think you can do it in O(n*log(K)). There are N sorted lists where each list has K elements. Just to traverse the list, you have to go through

(N * K) elements. (N*K) > (N * Log(K)). I think the best you can do is O (N*K log(K).

Here is the discussion.

https://www2.blogger.com/comment.g?blogID=6957414&postID=109840061746437225

I tried that once to a hot recruiter. She looked at me kind of weird. Maybe it doesn't work.

- vodangkhoa January 17, 2007We can do this recursively with only a few lines of code. There are a few rules that we need to take into consideration.

1) Counting from left to right, there are always more { than }. Therefore, { is always being generated first

2) There are only N { and }.

3) We can only generate } as long there are more {.

If you write code which obeys the above rules, your solution would be correct. It's only a few intuitive lines of code.

What is the run time and memory requirement?

If there are no requirements, you can just put in an array. Sort it using your favorite N Log N algorithm and push it back on the stack.

I think the question is given a sorted array that is rotated i number of times, perform a modified binary search algorithm on it so that the complexity is still O (log N).

Let's take this case.

original array: 1 2 3 4 5 6 7

rotated array: 4 5 6 7 1 2 3

I think this is how it works.

Given 4 5 6 7 1 2 3

Say that you're looking for 5.

first element: 4.

mid element: 7.

last element: 3.

from this data, you know whether to modify your first or last pointer. There are quite a few cases to this problem. Depending on the data you have above, make the appropriate modification.

The question was answered before.

http://www.careercup.com/question/?q=3dae61bf-a912-4051-b835-b9975039fb1b

Perform a BFS starting at node_a. Each time you discover a new node, put the node's name to a hash table. Break out of BFS whenever you have seen node_b or you're done traversing the graph. Also, when you're performing BFS, remember to mark the node that you have visited so that you don't visit it again. DFS would work as well.

The above algorithm gives more information than what the question asked for. It basically tells you whether there's a path from node_a to any other node.

Here is basically how BFS work.

BFS(Node root)

queue<Node> q;

q.enqueue(root);

while q is NOT Empty

Node start = q.pop()

mark start as visited

foreach(Node node: Adj(start))

if (node has not been visited)

insert into q

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

If you're sorting a linked list using Mergesort, no extra memory is required for merge.

- vodangkhoa April 03, 2007