Detect Uninitialized Read

Detect Uninitialized Read

Hard Programming Interview Data Structures 21 views
Explanation Complexity

Problem Statement

You will receive n statements in a tiny language: 'set x v' or 'add x y' meaning x = x + y. If add uses a variable that was never set before (for x or y), count it as a bad read. Output badReadCount.

Input Format

First line n. Next n lines statements.

Output Format

One integer badReadCount.

Example

4
add a b
set a 1
add a b
set b 2
2

Constraints

1

Input / Output Format

Input Format
First line n. Next n lines statements.
Output Format
One integer badReadCount.
Constraints
1

Examples

Input:
4 add a b set a 1 add a b set b 2
Output:
2

Example Solution (Public)

Programming Interview 
import sys
lines=sys.stdin.read().splitlines()
if not lines or not lines[0].strip():
  sys.exit(0)
n=int(lines[0].strip())
known=set()
bad=0
for i in range(1,1+n):
  parts=(lines[i] if i<len(lines) else '').split()
  if not parts: continue
  if parts[0]=='set':
    known.add(parts[1])
  else:
    x=parts[1]; y=parts[2]
    if x not in known:
      bad+=1
    if y not in known:
      bad+=1
    known.add(x)
sys.stdout.write(str(bad))

Official Solution Code

import sys
lines=sys.stdin.read().splitlines()
if not lines or not lines[0].strip():
  sys.exit(0)
n=int(lines[0].strip())
known=set()
bad=0
for i in range(1,1+n):
  parts=(lines[i] if i<len(lines) else '').split()
  if not parts: continue
  if parts[0]=='set':
    known.add(parts[1])
  else:
    x=parts[1]; y=parts[2]
    if x not in known:
      bad+=1
    if y not in known:
      bad+=1
    known.add(x)
sys.stdout.write(str(bad))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.