Monthly Archives: October 2012

Amazon interview preparation

Tree formation:

class Node
{
public:
  Node(value) { nValue = value; pLeft = pRight = NULL; }

  Node* pLeft;
  Node* pRight;
  int nValue;  // or any other data
}

class Tree
{
public:
  Node* pRoot;
  Tree() { pRoot = NULL; }

  Node* search(int value); //...
  void createLeaf(int value); //...
  // ...
}

Geeks for geeks (Update: Feb 15, 2013)

http://www.geeksforgeeks.org/find-the-minimum-distance-between-two-numbers/

http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

http://www.geeksforgeeks.org/check-if-each-internal-node-of-a-bst-has-exactly-one-child/

http://www.geeksforgeeks.org/majority-element/

http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

http://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/

LeetCode must read problems:

http://www.leetcode.com/2010/04/how-to-determine-if-point-is-inside.html

http://www.leetcode.com/2010/04/rotating-array-in-place.html

http://www.leetcode.com/2010/09/fun-with-bit-operations.html

http://www.leetcode.com/2010/09/number-of-1-bits.html

http://www.leetcode.com/2010/09/printing-binary-tree-in-level-order.html [Done]

http://www.leetcode.com/2010/09/determine-if-binary-tree-is-binary.html [Done]

http://www.leetcode.com/2010/09/printing-binary-tree-in-zig-zag-level_18.html [Done]

http://www.leetcode.com/2010/10/print-edge-nodes-boundary-of-binary.html [Done]

http://www.leetcode.com/2010/11/stack-that-supports-push-pop-and-getmin.html

http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in_22.html [Done]

http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

http://www.leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html [Done]

http://www.leetcode.com/2011/05/determine-if-two-rectangles-overlap.html

http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html [Done]

http://www.leetcode.com/2011/08/reverse-bits.html
GeeksForGeeks data structure link:

http://www.geeksforgeeks.org/forum/tags/data-structures
Cool questions:

http://www.geeksforgeeks.org/forum/topic/given-inorder-and-postorder-traversals-construct-a-binary-tree [Done]

http://www.geeksforgeeks.org/archives/category/linked-list

Diameter of tree: http://www.geeksforgeeks.org/archives/5687 [Done]

Three way partitioning: ( low and high are the numbers you want to partition by. p and q are regular quick sort counters. Check anything lower than low and swap it with the number placed at p and increment p, parallely, check anything more than high and swap it with the number placed at q and decrement q

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] < low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }
}

2 way partitioning:

Low = 0 , High = n-1
A[low] = 0.. Lo++, 1.. A[lo]><A[high] & low++ & high--

3 way partitioning:

Low = 0, Mid = 0, High = n-1
A[mid] = 0.. a[low]><A[mid] & low++ & mid++, 1.. mid++, 2.. a[mid]><a[high] & mid++ & high--
Advertisements

1 Comment

October 20, 2012 · 10:28 am

Android phone porting and Lenovo touchpad problems in Ubuntu 12.04

Sony ericsson WT19i (Android) phone port:

1. Go to settings -> experia –> connectivity

2. If connected to PC, remove USB

3. Click on “USB Connection Mode” nd select MSC (for Linux)

Lenovo (Y500) Touchpad not working:

1. Press cntrl+Alt+T

2.type “sudo gedit /etc/default/grub” (without quotes) and press enter.

3.When prompted for password Enter the admin password.

4 Add the line “i8042.reset” (with quotes) after the text “quiet splash”

After adding the the line in /etc/default/grub it should look like the following line

GRUB_CMDLINE_LINUX_DEFAULT=”quiet splash i8042.reset”

5. Save the changes and close in order to return to the Terminal window.

6. type “sudo update-grub” (Without Quotes) and press enter

7. Restart Ubuntu.

Leave a comment

Filed under My e-devices

Dynamic Programming – Kadane’s Algorithm

Question: Write a program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Answer:

We need to focus on the fact that whenever sum of digits of array goes less than zero it is better to keep the sum as 0. Anywhere we’ll encounter a positive integer we’ll again start the sum.

Example:

array : -2 -3 4 -1 -2 1 5 -3

sum  :  0 0 4 3 1 2 7 4

So 7 is the result.

Code:

Image

Leave a comment

Filed under Algorithms

Dynamic Programming – Famous coin sum question

Question: Out of given ‘N’ coins, give the minimum number of coins required to sum upto ‘S’

Answer: 

(Assumption: list of coins is sorted)

Loop from 1 to S and check solution for each denomination keeping solution for 0 as 0. DYNAMIC PROGRAMMING !!

For example, if you have N coins as {1, 3, 5} and you have to sum upto 10 then loop from 1 to 10 and for each number check if the number is more than maximum value of denomination present. If yes, than your answer will be (number – maximum denomination)’s answer + 1.

Number — COINS REQUIRED

0 — 0

1 — 1

2 — 2  (i.e. [2-1]’s answer + 1 i.e. [1]’s answer + 1 i.e. 1 + 1 == 2)

3 — 3  (i.e. [3-3]’s answer + 1 i.e. [0]’s answer + 1 i.e. 0 + 1 == 1)

4 — 2

5 — 1

and so on…

10 — 2  (you know why !)

Code:

Image

Leave a comment

Filed under Algorithms

Object Oriented Programming in Javascript

Learned at Code Academy

1. Classes in Javascript:

Person is a class and bob and susan are instances of that class.

2. Inheritance:

 Here, Penguin class inherits Animal class and hence can access the function sayName().

3. Abstraction:

Public variables are those declared above (name, numLegs etc.)

Private variable is declared as shown below:

Here variable bankBalance is hidden and we need function getBalance() to show it.

Private methods can also be declared in same fashion by removing this keyword from then. You can use a private function by returning it from a public one.

* * * * *

Leave a comment

Filed under javascript