Category Archives: Interviews

Backend interview questions

Sources:

Important questions and links:

TSQL Questions:

  • Finding Grand parent in a parent-child table (http://sqlfiddle.com/#!6/24c7b/6)
  • There are three projects and each have its table. Table have information of employee ids and hours of work they have done in that project. Print list of all employees and total hours they have worked across all projects. (Full Outer Join with Coalesce)
  • Implementation of SCD – 2 (Pull data from sources, make a dimension which has 4 of its columns trended)
  • Output for a query that contains a self-joined table on condition A.ID = B.ID – 1 and select has subtraction of fact
  • Many to many relationship (keep mapping table)
  • Left Join and WHERE clause (which works as EXCEPT

SQL Hacks: http://sqlzoo.net/wiki/Running_Total

SQL Hacks book: (Download it from 4shared.com)

Important hacks:

  • 3
  • 10 (Without the subquery, the optimizer finds it much easier to use your indexes)
  • 11
  • 23
  • 24 (Multiply across result set) (Exp, SUM, Log)
  • 25
  • 27 (Join on equality condition and OR)
  • 31
  • 51
  • 52
  • 56
  • 75
  • 78
  • 80
  • 81
  • 82
  • 84
  • 85
  • 88
Advertisements

Leave a comment

Filed under Interviews

Maha important puzzles

1. Hour glass: http://dailybrainteaser.blogspot.in/2013/07/hour-glass-riddle.html

2. Water jug problem: (figured out an algorithm) http://dailybrainteaser.blogspot.in/search?updated-max=2013-07-19T00:10:00%2B05:30&max-results=7&start=14&by-date=false

3. Chameleon: http://gurmeet.net/puzzles/chameleons/

4. Fox in hole: http://gurmeet.net/puzzles/fox-in-a-hole/

5. Cube cutting: http://gurmeet.net/puzzles/cube-cutting/

6. Ant collisions: http://gurmeet.net/puzzles/ant-collisions/

7. Colored heavy and light balls: http://gurmeet.net/puzzles/six-colored-balls-two-weighings/

8. Cards flipped and blind man: http://gurmeet.net/puzzles/blind-man-and-cards/

9. Magicians and hats (W and B): http://gurmeet.net/puzzles/whats-the-color-of-my-probabilistic-hat/

10. Black and white balls in 3 containers: http://gurmeet.net/puzzles/three-boxes-with-two-balls-each/

11. 3 light and 3 heavy marbles (lookalike): http://gurmeet.net/puzzles/three-heavy-and-three-light-balls/

12. Puzzle caps: http://gurmeet.net/puzzles/cap-colors/

13. Salaries: http://www.techinterview.org/post/491505435/salaries

Gurmeet puzzle left:

2, 8, 9, 10, 11, 13, 16, 18, 19, 21, 23, 27, 29, 34 onwards

Leave a comment

Filed under Interviews

C++ important links

  1. http://www.learncpp.com/cpp-tutorial/121-pointers-and-references-to-the-base-class-of-derived-objects/ (array animal example)
  2. http://www.learncpp.com/cpp-tutorial/122-virtual-functions/ (array animal example)

Left:

When do we pass arguments by reference or pointer?

Initializer list: when to use?

More about default constructor

Virtual destructors prevent memory leak !

Multiple inheritance in C++ (Initialization list process: 2nd problem)

RTTI

Advanced C conversion operators

* * * * *

Leave a comment

Filed under Interviews

GS attempts

Attempt 1:

Written round: C++, SQL, Analytical reasoning

Round – 1:

  • Write a function to return angle between minute hand and hour hand at any particular time (as input)
  • Give nth number in Fibonacci series
  • Stack implementation

Round – 2:

  • Pirate and gold coin puzzle
  • Circular parking lot puzzle

Round – 3:

  • Given 20,000 numbers (in range 1-25,000), store them in a space of 4000 bytes
  • What is ‘Pure Virtual Constructor’?
  • When is copy constructor called? What about assignment operator?
  • c = a+++++b, how does compiler distinguish what is this?

*****

Leave a comment

Filed under Interviews

Amazon attempts

1st Amazon attempt (Cape Town):

  • Kadane’s Algorithm
  • Implementation of HashTables
  • Difference between new and malloc

2nd Amazon attempt:

Online test questions:

  • LCA
  • Delete duplicate nodes in Linked List

1st telephonic:

  • Generate excel column names (A, B,… , Z, AA, BB,… , ZZ, AAA,…)
  • Find square root of a number without using sqrt()

2nd telephonic:

  •  Print if there exists a path with sum equal to K
    • Print the path
    • Return only True or False

1st onsite:

  • isBST
  • Circular linked list
    • Number of nodes in the loop
    • First node that is circularly linked
  • Rope puzzle

2nd onsite:

  • In a BST find two numbers with sum K
  • Array return index of number from where left and right sum are same

Amazon third attempt:

Onsite written test:

  • Find if a given LinkedList is palindrome or not
  • Given an ‘ascending sorted’ and rotated array find the index of the given number
  • Next largest number in a BST when a node is given

1st onsite:

  • Distance between given two nodes in a binary tree (Upon hearing about LCA, wanted a solution for finding it in O(n) time and O(1) space)
  • Kadane’s Algorithm
  • In an array, delete a number if there exists greater number than it, on its right side

2nd onsite:

  • Delete duplicate elements in a string
    • Do this in O(1) space and O(n^2) time complexities
    • Do this when resulting string can be in any given order (O(n) time and O(1) space)

3rd onsite:

  • Data structure that supports insertion, deletion and searching in O(log n) time
  • Vertical sum in a binary tree
  • In a gven 2 D array with sorted rows, sort the whole matrix

* * * * *

Leave a comment

Filed under Interviews

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--

1 Comment

October 20, 2012 · 10:28 am